[转][转]memcache的一致性hash算法使用

标签： memcache 一致性 hash | 发表时间：2012-12-03 01:08 | 作者：heiyeshuwu
出处：http://blog.csdn.net/heiyeshuwu

 

来源： http://blog.csdn.net/kongqz/article/details/6695417

 

一、概述

  1、我们的memcache客户端（这里我看的spymemcache的源码），使用了一致性hash算法ketama进行数据存储节点的选择。与常规的hash算法思路不同，只是对我们要存储数据的key进行hash计算，分配到不同节点存储。一致性hash算法是对我们要存储数据的服务器进行hash计算，进而确认每个key的存储位置。

 2、常规hash算法的应用以及其弊端

    最常规的方式莫过于hash取模的方式。比如集群中可用机器适量为N，那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。的确，这种结构是简单的，也是实用的。但是在一些高速发展的web系统中，这样的解决方案仍有些缺陷。随着系统访问压力的增长，缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式，在增加机器节点的这一时刻，大量的缓存命不中，缓存数据需要重新建立，甚至是进行整体的缓存数据迁移，瞬间会给DB带来极高的系统负载，设置导致DB服务器宕机。

  3、设计分布式cache系统时，一致性hash算法可以帮我们解决哪些问题？

   分布式缓存设计核心点：在设计分布式cache系统的时候，我们需要让key的分布均衡，并且在增加cache server后，cache的迁移做到最少。

   这里提到的一致性hash算法ketama的做法是：选择具体的机器节点不在只依赖需要缓存数据的key的hash本身了，而是机器节点本身也进行了hash运算。


 

二、一致性哈希算法情景描述（转载）

1、 hash机器节点


首先求出机器节点的hash值（怎么算机器节点的hash？ip可以作为hash的参数吧。。当然还有其他的方法了），然后将其分布到0～2^32的一个圆环上（顺时针分布）。如下图所示：

图一 

集群中有机器：A , B, C, D, E五台机器，通过一定的hash算法我们将其分布到如上图所示的环上。


2、访问方式

如果有一个写入缓存的请求，其中Key值为K，计算器hash值Hash(K)， Hash(K) 对应于图 – 1环中的某一个点，如果该点对应没有映射到具体的某一个机器节点，那么顺时针查找，直到第一次找到有映射机器的节点，该节点就是确定的目标节点，如果超过了2^32仍然找不到节点，则命中第一个机器节点。比如 Hash(K) 的值介于A~B之间，那么命中的机器节点应该是B节点（如上图 ）。


3、增加节点的处理

如上图 – 1，在原有集群的基础上欲增加一台机器F，增加过程如下：

计算机器节点的Hash值，将机器映射到环中的一个节点，如下图：

图二 

增加机器节点F之后，访问策略不改变，依然按照（2）中的方式访问，此时缓存命不中的情况依然不可避免，不能命中的数据是hash(K)在增加节点以前落在C～F之间的数据。尽管依然存在节点增加带来的命中问题，但是比较传统的 hash取模的方式，一致性hash已经将不命中的数据降到了最低。

 

Consistent Hashing最大限度地抑制了hash键的重新分布。另外要取得比较好的负载均衡的效果，往往在服务器数量比较少的时候需要增加虚拟节点来保证服务器能均匀的分布在圆环上。因为使用一般的hash方法，服务器的映射地点的分布非常不均匀。使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配100～200个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上，就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。
下面有一个图描述了需要为每台物理服务器增加的虚拟节点。


图三 

x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale)，y轴是实际物理服务器数，可以看出，当物理服务器的数量很小时，需要更大的虚拟节点，反之则需要更少的节点，从图上可以看出，在物理服务器有10台时，差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。

三、以spymemcache源码来演示虚拟节点应用

1、上边描述的一致性Hash算法有个潜在的问题是:
     （1）、将节点hash后会不均匀地分布在环上，这样大量key在寻找节点时，会存在key命中各个节点的概率差别较大，无法实现有效的负载均衡。
     （2）、如有三个节点Node1,Node2,Node3，分布在环上时三个节点挨的很近，落在环上的key寻找节点时，大量key顺时针总是分配给Node2，而其它两个节点被找到的概率都会很小。

2、这种问题的解决方案可以有:
     改善Hash算法，均匀分配各节点到环上；［引文］使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配100～200个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上，就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。

在查看Spy Memcached client时，发现它采用一种称为Ketama的Hash算法，以虚拟节点的思想，解决Memcached的分布式问题。 

3、源码说明

该client采用TreeMap存储所有节点，模拟一个环形的逻辑关系。在这个环中，节点之前是存在顺序关系的，所以TreeMap的key必须实现Comparator接口。
那节点是怎样放入这个环中的呢？

  

[html]  view plain copy
  1.    protected void setKetamaNodes(List<MemcachedNode> nodes) {  
  2. TreeMap<Long, MemcachedNode> newNodeMap = new TreeMap<Long, MemcachedNode>();  
  3. int numReps= config.getNodeRepetitions();  
  4. for(MemcachedNode node : nodes) {  
  5.     // Ketama does some special work with md5 where it reuses chunks.  
  6.     if(hashAlg == HashAlgorithm.KETAMA_HASH) {  
  7.         for(int i=0; i<numReps / 4; i++) {  
  8.             byte[] digest=HashAlgorithm.computeMd5(config.getKeyForNode(node, i));  
  9.             for(int h=0;h<4;h++) {  
  10.                 Long k = ((long)(digest[3+h*4]&0xFF) << 24)  
  11.                     | ((long)(digest[2+h*4]&0xFF) << 16)  
  12.                     | ((long)(digest[1+h*4]&0xFF) << 8)  
  13.                     | (digest[h*4]&0xFF);  
  14.                 newNodeMap.put(k, node);  
  15.                 getLogger().debug("Adding node %s in position %d", node, k);  
  16.             }  
  17.   
  18.         }  
  19.     } else {  
  20.         for(int i=0; i<numReps; i++) {  
  21.             newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);  
  22.         }  
  23.     }  
  24. }  
  25. assert newNodeMap.size() == numReps * nodes.size();  
  26. ketamaNodes = newNodeMap;  



上面的流程大概可以这样归纳:四个虚拟结点为一组，以getKeyForNode方法得到这组虚拟节点的name，Md5编码后，每个虚拟结点对应Md5码16个字节中的4个，组成一个long型数值，做为这个虚拟结点在环中的惟一key。第10行k为什么是Long型的呢？就是因为Long型实现了Comparator接口。

处理完正式结点在环上的分布后，可以开始key在环上寻找节点的游戏了。
对于每个key还是得完成上面的步骤:计算出Md5，根据Md5的字节数组，通过Kemata Hash算法得到key在这个环中的位置。

 

[html]  view plain copy
  1. MemcachedNode getNodeForKey(long hash) {  
  2.     final MemcachedNode rv;  
  3.     if(!ketamaNodes.containsKey(hash)) {  
  4.         // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5  
  5.         // in a lot of places, so I'm doing this myself.  
  6.         SortedMap<Long, MemcachedNode> tailMap=getKetamaNodes().tailMap(hash);  
  7.         if(tailMap.isEmpty()) {  
  8.             hash=getKetamaNodes().firstKey();  
  9.         } else {  
  10.             hash=tailMap.firstKey();  
  11.         }  
  12.     }  
  13.     rv=getKetamaNodes().get(hash);  
  14.     return rv;  
  15. }  


 上边代码的实现就是在环上顺时针查找，没找到就去的第一个，然后就知道对应的物理节点了。

四、应用场景分析

1、memcache的add方法：通过一致性hash算法确认当前客户端对应的cacheserver的hash值以及要存储数据key的hash进行对应，确认cacheserver，获取connection进行数据存储

2、memcache的get方法：通过一致性hash算法确认当前客户端对应的cacheserver的hash值以及要提取数据的hash值，进而确认存储的cacheserver，获取connection进行数据提取

五、总结

1、一致性hash算法只是帮我们减少cache集群中的机器数量增减的时候，cache的数据能进行最少重建。只要cache集群的server数量有变化，必然产生数据命中的问题

2、对于数据的分布均衡问题，通过虚拟节点的思想来达到均衡分配。当然，我们cache server节点越少就越需要虚拟节点这个方式来均衡负载。

3、我们的cache客户端根本不会维护一个map来记录每个key存储在哪里，都是通过key的hash和cacheserver（也许ip可以作为参数）的hash计算当前的key应该存储在哪个节点上。

4、当我们的cache节点崩溃了。我们必定丢失部分cache数据，并且要根据活着的cache server和key进行新的一致性匹配计算。有可能对部分没有丢失的数据也要做重建...

5、至于正常到达数据存储节点，如何找到key对应的数据，那就是cache server本身的内部算法实现了，此处不做描述。


这里只是针对数据的存储方式以及提取方式进行了流程展示。

 

作者：heiyeshuwu 发表于2012-12-3 1:08:47 原文链接
阅读：141 评论：0 查看评论

相关 [memcache 一致性 hash] 推荐：

[转][转]memcache的一致性hash算法使用

- - heiyeluren的Blog
来源： http://blog.csdn.net/kongqz/article/details/6695417.   1、我们的memcache客户端（这里我看的spymemcache的源码），使用了一致性hash算法ketama进行数据存储节点的选择. 与常规的hash算法思路不同，只是对我们要存储数据的key进行hash计算，分配到不同节点存储.

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类：  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法（ consistent hashing ）.

一致性HASH算法

- - 企业架构 - ITeye博客
一致性 hash 算法（ consistent hashing ）. consistent hashing 算法早在 1997 年就在论文 . Consistent hashing and random trees 中被提出，目前在cache 系统中应用越来越广泛；. 比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；.

一致性Hash算法背景(转)

- - 开源软件 - ITeye博客
一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似. 一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用. 　　但现在一致性hash算法在分布式系统中也得到了广泛应用，研究过memcached缓存数据库的人都知道，memcached服务器端本身不提供分布式cache的一致性，而是由客户端来提供，具体在计算一致性hash时采用如下步骤：.

一致性hash算法测试

- - Java - 编程语言 - ITeye博客
package com.xll; //服务器对象 public class Server {. private void init() { // 初始化一致性hash环. for (int i = 0; i != servers.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点.

memcached的总结和分布式一致性hash

- - 开源软件 - ITeye博客
当前很多大型的web系统为了减轻数据库服务器负载，会采用memchached作为缓存系统以提高响应速度. memcached是一个开源的高性能分布式内存对象缓存系统. 其实思想还是比较简单的，实现包括server端（memcached开源项目一般只单指server端）和client端两部分:. server端本质是一个in-memory key-value store，通过在内存中维护一个大的hashmap用来存储小块的任意数据，对外通过统一的简单接口（memcached protocol）来提供操作.

一致性hash算法在memcached中的使用

- - CSDN博客推荐文章
  1、我们的memcache客户端（这里我看的spymemcache的源码），使用了一致性hash算法ketama进行数据存储节点的选择. 与常规的hash算法思路不同，只是对我们要存储数据的key进行hash计算，分配到不同节点存储. 一致性hash算法是对我们要存储数据的服务器进行hash计算，进而确认每个key的存储位置.

【转】一致性hash算法与server列表维护

- - 编程语言 - ITeye博客
考虑到不用重复造轮子，特此转载好文，出处http://shift-alt-ctrl.iteye.com/blog/1963244.     普通的hash算法有个很大的问题:当hash的"模数"发生变化时,整个hash数据结构就需要重新hash,重新hash之后的数据分布一定会和hash之前的不同;在很多场景下,"模数"的变化时必然的,但是这种"数据分布"的巨大变化却会带来一些麻烦.所以,就有了"一致性hash",当然学术界对"一致性hash"的阐述,还远远不止这些..

Hash Collision DoS 问题

- mazhechao - 酷壳 - CoolShell.cn
最近，除了国内明文密码的安全事件，还有一个事是比较大的，那就是 Hash Collision DoS （Hash碰撞的拒绝式服务攻击），有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比. 这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样，但是key一样数据，然后让你的Hash表成为一张单向链表，而导致你的整个网站或是程序的运行性能以级数下降（可以很轻松的让你的CPU升到100%）.

局部敏感Hash

- - xiaobaoqiu Blog
之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东. LSH可以理解为一种衡量文本相似度的算法，特点是散列前的相似点经过哈希之后，也能够在一定程度上相似，并且具有一定的概率保证. 其有坚实的理论依据(98年左右理论就提出来了，99年有第一版实现)并且在高维数据空间中表现优异.