一致性哈希算法

前记：由于在学习redis 集群时使用到了twemproxy方案，twemproxy是以一致性哈希算法为原理进行代理多个孤立的redis 节点集成集群。所以很有必要学习下一致性哈希算法。

 

一、什么是一致性哈希

•  一致性哈希算法在1997年由麻省理工学院提出，设计目标是为了解决因特网中的热点(Hot spot)问题。
• 初衷和CARP（Common Access Redundancy Protocol共用地址冗余协议）十分类似。
• 一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT(Distributed Hash Table，分布式哈希表)可以在P2P环境中真正得到应用。

 

二、普通哈希算法的缺点

假如有N个redis节点（单机，孤立的），我们在这些N个redis节点前面做一个代理，转发客户端的读和写，使用hash算法分配到后面的redis节点中。

一般情况，我们是这样使用 hash(object_x) %N = object_x_key，当N个节点没有任何问题时，一切运行良好。。。突然，有一天！

• 有一台redis抽风出现故障，不可用了，此时hash(object_x)%(N-1)=object_x_key_1 。再也找不回熟悉的味道。。。哦，错了，熟悉的节点。
• 内存不够了，运维哥哥说加一台机器，此时hash(object_x)%(N+1)=object_x_key_2。也找不到熟悉的节点了。
• 运维哥哥发现有几台机器内存使用率很高，还有几台内存使用率很低，完全浪费。怎么回事，不是说好了做彼此的天使，有困难一起扛吗？

 

 

三、一致性哈希算法怎么解决普通哈希算法遗留的问题

 

看看一致性哈希算法的如何映射数据的。

（1）、环形Hash空间

按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中，即0~(2^32)-1的数字空间中（数据量不够，2^64也行）。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。

如下图所示：

 

（2）、把缓存数据映射到哈希环上

假如有四个缓存数据需要映射，通过hash函数计算出的hash值key 在环上的分布。

hash(object1)=key1
hash(object2)=key2
hash(object3)=key3
hash(object4)=key4

 

 如下图所示：

 

（3）、把缓存节点服务器映射到哈希环上

假设我们有三台缓存服务器节点，命名为：Cache A,Cache B,Cache C 通过hash函数计算出的hash值key 在环上的分布。

hash(CacheA) = keyA;
hash(CacheB) = keyB;
hash(CacheC) = keyC;

 如下图所示：

 

说到这里，顺便提一下 节点cache 的 hash 计算，一般的方法可以使用 cache 机器的 IP 地址或者唯一机器名作为 hash输入。

 

（4）、把缓存数据映射到缓存节点服务器上

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中，如果沿着顺时针方向从缓存对象的 key 值出发，直到遇见一个 节点cache ，那么就将该对象存储在这个 节点cache 上，因为缓存对象和 节点cache 的 hash 值是固定的，因此这个 缓存cache 必然是唯一和确定的。

 

那么根据上面的方法，对象 object1 将被存储到 节点cache A 上； object2 和object3 对应到 节点cache C ； object4 对应到 节点cache B ；

 

图和（3）、【把缓存节点服务器映射到哈希环上】共用，上图所示。

 

 

说了那么多，还没说怎么解决问题，下面来看

（1）、移除一个缓存节点

假设节点CacheB挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 节点cache B 逆时针遍历直到下一个 cache （ cache A ）之间的对象，也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ，将其重新映射到 cache C 上即可 。

 

如下图所示：

 

 

（2）、新增一个缓存节点

假设添加一台新的节点 cache D 的情况，假设在这个环形 hash 空间中， 节点cache D 被映射在对象 object2 和object3 之间。

这时受影响的将仅是那些沿 节点cache D 逆时针遍历直到下一个节点cache （ 节点cache B ）之间的对象（它们是本来映射到 cache C 上对象的一部分），将这些对象重新映射到 cache D 上即可。

 

因此这里仅需要变动对象 object2 ，将其重新映射到 cache D 上 。

 

如下图所示：

 

 

（3）、平衡分配数据

 在【（1）、移除一个缓存节点】中，移除了节点CacheB，结果object4也转移到CacheC，这时节点CacheA只有object1，而节点CacheC有，object2,object3,object4，分布不平衡。

为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念。

它可以如下定义：

“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。

 

 

仍以仅部署 节点cache A 和节点 cache C 的情况为例，在【（1）、移除一个缓存节点】 中我们已经看到，节点 cache 分布并不均匀。

现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点：

节点 cache A1,节点 cache A2 代表了节点cache A ； 

节点cache C1, 节点cache C2 代表了 节点 cache C ；假设一种比较理想的情况。

 

如下图：

 

 

 

 

此时，对象到“虚拟节点”的映射关系为：

objec1->节点cache A2 ； objec2->节点cache A1 ； objec3->节点cache C1 ； objec4->节点cache C2 ；

因此对象 object1 和 object2 都被映射到了节点 cache A 上，而 object3 和 object4 映射到了 节点cache C 上；平衡性有了很大提高。

 

引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系 。

如下图所示：

 

 

 

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。

例如假设 节点cache A 的 IP 地址为192.168.11.1 。
引入“虚拟节点”前，计算节点 cache A 的 hash 值：
Hash(“192.168.11.1”);
引入“虚拟节点”后，计算“虚拟节”点 中节点cache A1 和节点 cache A2 的 hash 值：
Hash(“192.168.11.1#1”);  // 节点cache A1
Hash(“192.168.11.1#2”);  // 节点cache A2

 

 

 

四、一致性哈希算法优点总结

（1）、单调性（Monotonicity）

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 

 （2）、平衡性（Balance）

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

 （3）、分散性（Spread）

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

 （4）、负载（Load）

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

 

五、一致性哈希算法局限性

（1）、某个单个节点出现故障时，该节点下的数据全部不可用

在【三、（1）、移除一个缓存节点】时，节点CacheB的key是转移到了CacheC，但是事实上数据已经丢失了。

这个也不是该算法所能解决的范畴，只能通过主从模式对该节点进行做从节点，一旦主节出现故障时，从节点能自动接替主节点，从而该节点下的数据不至于丢失。

 

（2）、增加节点时，该节点下的数据没有重新分配到其他节点

 在【三、（2）、新增一个缓存节点】时，新增节点CacheD时，处于节点CacheB和CacheD之间的数据，本来属于CacheC的，确没有转移到CacheD上，只有key转移到了CacheD上，那么这些数据也丢失了。

这个算法也解决不了，只能通过一些特殊的办法，转移数据。最好能做到新增一个节点时，数据自动分配，那就完美了。

 

六、小结

一致性哈希算法解决了一些问题，但是又引出了一些新的问题，这些问题至少从算法的角度不能轻易解决。不知道能不能通过数据冗余的办法or算法解决掉吗？

 

评论

1 楼 无名草 2016-09-27  

讲得真不错