分布式原理：一致性哈希算法简介

一致性哈希算法

普通的哈希算法使用取余操作：hash(o) mod n，其中 n 代表机器的数量。如果在集群中新增加一个节点时，计算公式会变为：hash(o) mod (n+1)；在集群中删除一个机器时，计算公式变为：hash(o) mod (n-1)。所以当集群中机器数量有所变化时，几乎所有的 Object 的哈希值都会改变。一致性哈希可以保证当从集群中删除一台机器时，仅仅保存在该机器上的 Object 的值会变化；当集群中增加一台机器时，也仅仅是非常小的一部分 Object 的哈希值会发生改变。

一致性哈希算法的实现原理其实很简单，它也是使用取模的方式，只是刚才描述的取模法是对机器的数量进行取模，而一致性哈希算法是对2^32取模，hash(o) mod 2^32 什么意思呢？我们慢慢聊。

其将整个哈希值空间组织成一个虚拟的圆环，比如某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），那么整个哈希空间环看起来就像下图所示：

将机器映射到环中

一致性哈希算法是数据分布的方式，而数据最终是需要存到机器中的，所以我们首先需要将机器映射到环中。假设我们有四台机器 Node1、Node2、Node3 以及 Node4，我们使用机器名或者 ip 计算这些机器的哈希值，然后分别映射到环中去，看起来就像下面一样：

将数据映射到环中

我们使用相同的哈希函数计算需要存储数据的哈希值，假设现在我们有四份数据 data1、data2、data3 以及 data4，我们需要将这些数据映射到环中去，这样看起来像下面图一样：

在这个哈希环中，数据存储的机器是按照顺时针方向遇到的第一个节点就是这个数据存储的节点，所以图中：

• 数据 data2 存储在节点 Node1 上；
• 数据 data3 存储在节点 Node4 上；
• 数据 data1 存储在节点 Node2 上；
• 数据 data4 存储在节点 Node3 上。

添加节点在分布式环境中，添加或减少节点是很常见的操作。现在我们往上面的哈希环添加一个节点 Node5，同样使用相同的哈希函数计算这个节点在哈希环的位置，假设计算的结果如下：

添加节点 Node5 之后，原本存储在 Node4 上的数据 data3 就转移到 Node5 了，其他数据分配不变。相比于普通的哈希添加节点会导致大量映射失效，一致性哈希可以很好的处理这种情况。如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

删除节点

如果哈希环中有节点出现故障，需要从哈希空间中移除，那么影响的数据也是有限的。假设节点 Node1 出现故障需要移除，新的哈希空间的数据映射如下：

Node1 节点移走之后，数据 data2 就转移到 Node4 节点上了。所以如果从环中删除节点，受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

虚拟节点

上述最基本的一致性哈希算法有很明显缺点，随机分布方式使得难均匀的分布哈希值域；尤其在动态增加节点后，即使原先的分布均匀也很难保证继续均匀 即hash环的偏斜。由此带来另一个较为严重的缺点，当一个节异常时，该节点的压力全部转移到相邻的一个节点，当加入一个新节点时，只能为一个相邻节点分摊压力。

为此一个改进方法是引入虚拟节点（virtual node），虚拟节点是实际节点在哈希空间的复制品（ replica ），一实际个节点（机器）对应了若干个虚拟节点，这个对应个数也成为复制个数，虚拟节点在哈希空间中以哈希值排列。

为了表述方便，假设我们有2个节点，4份数据，在引入虚拟节点之前节点和数据分布如下：

可以看见节点 Node2 管理的数据有 data1、data3 和 data4；而节点 Node1 仅仅只管理数据 data2。这就造成了数据分布不均匀的情况。如果我们通过引入虚拟节点，并且假定复制个数为3，则哈希之后的情况如下：

其中 Node1_1、Node1_2 和 Node1_3 是 Node1 虚拟出来的节点；同理Node2_1、Node2_2 和 Node2_3 是 Node2 虚拟出来的节点。通过添加虚拟节点之后，各个节点管理的数据已经比较均匀了。