简介一致性Hash(Consistent Hashing)

[介绍]

一致性Hash(Consistent Hashing）被应用在很多地方，如LVS, 缓存(memcache, redis)等等.

 

[Ref 1]，与 [Ref 2]已经给出了非常清楚明白的解释，我也是参考他们的。其他相关的文章更是多得汗牛充栋。

我写这个小短文(以我自己的语言重新组织)的目的是为了加深印象，以及稍加补充我觉得更加好理解的解释。

维护于： Youdao Note http://note.youdao.com/share/?id=5b0d78a41e0d35eccac3be2267b34ffd&type=note

 

[现实问题]

问题：对key使用普通hash方法产生hashcode，以决定该key分配到那些缓存节点上。当减少(或者增加)节点数量时，将会倒置几乎所有的key都将重新分配到其他的节点上。因为hash的mod值从N，变成了N-1(or N+1). 譬如原来映射到节点 X， 则之后映射到X-1 (or X+1). 进而原有的缓存内容全部失效。 这将引起系统功能的剧烈变化。

 

 

[为什么一致性Hash]

一致性hash中，针对 key 和 缓存节点 都生成hash code(0 ~ 2^32-1)。将这些hash code映射到一个环上。这样，按照以顺时针方向，key距离那个节点比较近，就分配到哪个节点上。

这样，增加、减少节点则只对换上相邻的key产生影响。其他的key仍然还在原有节点上。

 

此图来自 [Ref 1]

 

 

[深入]

1. 平衡性

只是映射节点和key的话，可能有些节点load很大，其他确很小。引起所谓的，不平衡问题。为了缓解(注意：缓解，而非彻底解决)这个问题,引入虚拟节点的概念。每个物理节点，对应若干虚拟节点。使用虚拟节点的hashcode映射到环上，注意：同一物理节点的虚拟节点在换上不相邻。因为有了更多的“节点”在环上、而且物理节点都打散了，则key的分布必然会更平均一些。

[Ref 1]中也描述了

 

2. 判断该算法好坏的四个特性

- 平衡性 Balance    "哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。" [Ref 2]

- 单调性 Monotonicity。 What:已缓存到NodeA中的内容，由于增加新节点NodeX，可能不得不映射到新的节点上。只能映射到原有NodeA或者新的NodeX中。而不能映射到其他Node上。How: 一致性Hash的圆环很简单的保证了这点。

- 分散性 Spread。 相同内容被cache到不同节点上、导致低存储效率的程度。BY:什么时候会曹成重复cache呢？谁给个实际的例子？ [Ref 2]说“在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分”， 为啥不能看到所有缓冲？

- 负载 Load - BY:无法理解[Ref 2]中说解释的Load。

[Ref 2]中给出了比较好的解释。但是需要认真读才行。读之前，请理解一致性hash。读的时候，请结合一致性hash。

 

3. 一致性哈希算法有多种具体的实现，包括Chord算法，KAD算法等实现

 

Reference 

1. [置顶] 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)

http://blog.csdn.net/cywosp/article/details/23397179/

 

2. 一致性hash算法简介

http://blog.huanghao.me/?p=14