一致性hash在memcache中的路由应用

butter7372

memcache主要由：路由模块、通信模块、接口等等够成。
 
一、普通hash映射的应用
 
人称通常称这种算法为“余数hash”、或者“取模hash”。只考虑hash的应用，不考虑具体hash算法的实现。具体hash算法实现，参考http://baike.baidu.com/view/273836.htm
 
应用场景：
 
比如你有 3 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 3 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 3 个 cache ；
服务器编号＝hash(object)%3
 
一切都运行正常，再考虑如下的情况；
 
1、由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1)；
 
假如：当向原有的cache服务器中再添加cache时，此时映射结果会有如下变化

key的hash尾数	3台时的映射对象cache	4台时的映射对象cache	5台时的映射对象cache	...
00000	0	0	0
00001	1	1	1
00002	2	2	2
00003	0	3	3
00004	1	0	4
00005	2	1	0
...	...	...	...

       
 
根据上表依次类推会发现：
当3变成4时有25%的命中，不命中率为75%；
当4变成5时有20%的命中，不命中率为80%；
当5变成6时有16.7的命中，不命中率为83.3%;
当N变成N+1时有N/N与N+1的最小公倍数，不命中率为1-N/N与N+1的最小公倍数
 
当减少基数时仍然会发生上述情况，当基数变大时，不命中率如此之高。在实际应该中，对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务……
 
二、一致性hash的应用
   
1.将整个哈希值空间组织成一个虚拟圆环，假设某哈希函数H的值空间为0-(2^32-1)，即32位无符号整数;
2.将各节点用H函数哈希，可以将服务器的IP或主机名作为关键字哈希，这样每个节点就能确定其在哈希环上的位置;
3.将id用H函数映射到哈希空间的一个值，沿该值向后，将遇到的第一个节点做为处理节点。
 
 
 

 
 
 
当向原有的cache服务器中再添加cache时，此时映射结果会有如下变化
 
 


  

	3->4	4->5	5->6	…
不命中率	1/6	1/8	1/10	1/N*2

 
随着cache服务器的个数增加，在添加会减少服务器个数时，影响范围越来越小，基本上可以解决洪水般的访问都会直接冲向后台服务了。但是，当4变5时，node4和node5的实际利用率和压力大小仅为其它服务的一半。负载不能达到均衡了……
 
三、虚拟节点应用
考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：
 
平衡性
 
　　平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
 
hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，比如在上面的例子中，仅部署 cache A 和 cache C 的情况下，在 4 个对象中， cache A 仅存储了 object1 ，而 cache C 则存储了 object2 、 object3 和 object4 ；分布是很不均衡的。
 
为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：
 
“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。
 
仍以仅部署 cache A 和 cache C 的情况为例，在图 4 中我们已经看到， cache 分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假设一种比较理想的情况，参见图 6 。
 
 
 
图  引入“虚拟节点”后的映射关系
 
 
 


  
 
 
此时，对象到“虚拟节点”的映射关系为：
 
objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；
 
因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。
 
引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。
 
 


  
 
通常一个节点可分为150个虚拟节点。通过使用虚拟节点后，增加或减少cache 服务器对于节点的不命中率大大降低，平衡性也有大的改善。
 
参考：
 
http://blog.csdn.net/sparkliang/article/details/5279393
http://blog.csdn.net/mayongzhan/article/details/4298834