分布式系统下的哈希一致性算法

本文涉及：普通哈希算法存在的问题，分布式系统的哈希一致性算法，哈希一致性算法中的数据倾斜问题

我们知道，在分布式系统中当数据量无法使用单机进行存储时，最简单粗暴的方法就是水平扩展：加机器，搞集群。

然而所有的集群模式都会面临一个数据存放的问题：即一个集群有多台机器，我们怎么知道这次的数据应该放在哪个机器上呢？这次的数据放到了一台机器上我下一次读取的时候能保证还来这台机器上找么？

假如当前我们有一个Redis集群，共5个节点对外提供服务

◆

Hash取模

◆

最开始的解决方案就是首先给5台机器分别编号：1、2、3、4、5

当对一个数据进行操作时首先计算key的hash然后对机器数量5进行取余，得出的余数就是需要放置的机器的编号。

key应该放置的机器编号=hash(key) % 5

这个方案完美解决了文章开始提到的两个问题，但是大家都知道，程序员的智力是没有上限，当然主要是因为问题逼的：

如果其中一台机器宕机了、或者新增了服务器，则整个集群所有的数据都需要重新计算位置，这个过程简直不要太痛苦。

◆

一致性Hash

◆

既然出现了问题，聪明的程序员很快就想到了解决方案：一致性哈希算法

如上图所示，程序员们把所有的机器模拟成了一个虚拟的哈希环，然后设计了一个空间的大小，这个空间被平均分配到了所有机器的中间。当需要对一个key操作时，同样进行进行取模运算，只不过这里的模不再是机器数量而是空间大小，然后根据得出的结果，去离结果顺时针最近的一个节点上操作key。

例如：当一个集群有5个节点、空间大小被设置为500的时候，当要设置一个key的hash值为601时。首先会对key的hash进行取余，601%500 结果为101，然后根据结果101顺时针查找最近的节点找到了192.168.1.3。

同理，设置另一个key，先算hash，假如是888，则首先取余得出结果388然后得出节点192.168.1.5。

使用Hash一致性的时候如果遇到了节点宕机或者新增服务器的情况下可就简单的多了：

节点宕机，只需要把宕机节点的数据迁移到顺时针的下一个服务器上

新增节点仅仅需要迁移逆时针的第一台服务器的部分数据

◆

数据倾斜

◆

一致性哈希算法完美的解决了普通的哈希算法的问题，但是呢，没有十全十美的算法，一致性哈希算法同样存在一些问题。由上方的示例我们可以看出来，当集群内扩缩容次数多了以后，数据很容易出现不均匀的情况，有的机器负责了大半的空间，而有的机器仅仅负责一点点空间。这个问题有一个名词，数据倾斜：

为了解决数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即将每一个服务节点都计算为多个虚拟节点，避免单个节点持有连续的大空间：