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

 

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