伴随着系统规模的扩增，出现了很多分布式应用。比如在分布式系统中为了保证 Redis 的高可用需要搭建 Redis 对数据进行分槽处理，再比如 MySql 数据库存储的数据达到一定规模的时候需要对数据库分库操作。除了这些典型的分布式应用之外，比如我们要开发一款分布式作业调度系统，实际的执行作业的节点拥有不同的配置（CPU、内存以及 GPU 等），同时也分布在不同的地域，我们如何保证的作业尽可能调度到正确的节点，同时在新增节点或者某节点宕机的情况下保证尽可能减少对作业调度的影响呢？

说白了，上面所述的问题就是如何把数据对象按照一定的规则映射到不同的机器上，我们能想到的最直观的方式就是哈希函数，借助于哈希函数，我们能够准确地知道数据对象需要映射到哪个节点。但是普通的哈希函数可以解决我们在分布式系统中遇到的数据对象映射的问题吗？

简单哈希

我们还是以上面所说的分布式作业调度系统为例，联想到 Java 中哈希表 hashmap 的实现原理，通过哈希函数对作业数据对象的键来计算哈希值，最简单的哈希函数就是通过作业数据对象对作业执行节点总数执行取模运算，得到的哈希值可以看作是“哈希桶”，也就是作业应该调度到的节点。

这看起来很简单地就解决了数据对象的映射问题，但是如果随着系统吞吐量的增加，我们需要重新增加一些新的计算节点到集群中，此时我们再次计算数据对象的哈希值的时候，取模运算的底数已经发生了变化，这会导致数据对象映射的结果也发生变化，也就是说作业调度的节点发生了变化，这对于一些对配置有特殊需要的作业来说，影响是巨大的。所以，我们需要想办法让这种情况不发生，这种情况发生的根本是哈希算法本身的特性导致的，直接使用取模的话这是无法避免的。

最简单的哈希算法通过求模运算来计算关键字的哈希值，然后将关键字映射到有限的地址空间中，以便于快速检索关键字。由于简单哈希算法只是采用了求模运算，使得它存在很多缺陷:

  1. 增删节点更新效率低：如果整个系统中的存储节点数量发生变化，哈希算法的哈希函数也需要变化。例如，增加或删除一个节点是，哈希函数将变化为 hash(key)%(N±1)，这种变化使得所有关键字映射的地址空间都发生变化，也就是说，整个系统所有对象的映射地址都需要重新计算，这样系统就无法对外界请求做出正常的响应，将导致系统处于瘫痪状态；
  2. 平衡性差：采用简单哈希算法的系统没有考虑不同节点间性能的差异，导致系统平衡性差。如果新添加的节点由于硬件性能的提升具有更强的计算能力，该算法不能有效地利用节点性能差异提高系统的负载；
  3. 单调性不足：新的节点加入到系统中时，哈希函数的结果应能够保证之前的已分配映射地址的数据对象可以被映射到原地址空间。简单哈希算法不能满足单调性，一旦节点的数量发生变化，那么所有的数据对象映射的地址都会发生变化；

一致性哈希

一致性哈希算法对简单哈希算法的缺陷进行了修正，保证系统在删除或者增加一个节点时，尽量不改变已有的数据对象到地址空间的映射关系，也就是尽量满足哈希算法的单调性。

  1. 环形哈希空间

一致性哈希算法将所有数据对象的键值映射到一个32位长的地址空间值中，即 0~2^32-1 的数值空间，该地址空间首尾相连形成一个环状，即一个首(0)尾(2^32-1)相接的闭合圆环，如下面所示:

consistent-hash-1.png

  1. 把数值对象映射到哈希空间

把所有的数值对象映射到环形哈希空间。考虑这样的4个数值对象：object1~object4，通过哈希函数计算出的哈希值作为环形地址空间中的地址，这样4个数值对象在环上的分布如图所示：

hash(object1) = key1;
......
hash(object4) = key4;

consistent-hash-2.png

  1. 把机器节点映射到哈希空间：对于机器节点也使用相同的哈希函数映射到环形地址空间。一致性哈希对于数值对象和机器节点使用相同的哈希函数映射到同一个环形哈希空间中。然后沿着环形地址空间按照顺时针方向将所有的数据对象存储到最近的节点上：

目前存在 node A, node B, node C 共3台机器节点，通过哈希函数的计算，它们在环形地址空间上的映射结果将如图所示，可以看出这些机器节点在环形哈希空间中，基于对应的哈希值排序。

hash(node A) = key A;
......
hash(node C) = key C;

consistent-hash-3.png

Note: 对于机器节点哈希值的计算，哈希函数的输入可以选择机器的 IP 地址或者机器名的字符串签名。

从图中可以看出，所有的数值对象与机器节点处于同一环形哈希空间中，从数值对象映射到的位置开始顺时针查找对应的存储节点，并将数值对象保存到找到的第一个机器节点上。这样 object1 存储到了 node A 中，object3 存储到了 node B中，object2 和 object4 都存储到了 node C 中。处于这样的集群环境中，环形地址空间不会变更，通过计算每个数值对象的哈希地址空间值，就可以定位到对应的机器节点，也就是实际存储数值对象的机器。

  1. 机器节点的添加与删除：一致性哈希可以有效地避免集群中新增加节点或者删除节点时，整个系统所有的数值对象在哈希空间中的地址都会发生变化的情况。对于节点的变动只需迁移环形地址空间中的一小部分数据，避免了大量数据的迁移，减小了服务器的的压力，具有较好的容错性和可扩展性。

1）删除机器：

consistent-hash-4.png

2）增加机器：

consistent-hash-5.png

虚拟节点

一致性哈希算法修正了简单哈希算法的缺陷，保证哈希算法的单调性和分散性以及负载均衡要求，但还需要解决平衡性的问题。所谓平衡性，就是指尽量将数值对象的哈希结果分布到所有的地址空间中，这样可以使得所有的地址空间都得到充分利用并保证系统压力负载的均衡。

一致性哈希算法具有随机性，严格来说不能保证平衡性，例如当机器数量较少时，数值对象就不能被均匀的映射到所有机器上，在上面的例子中，如果只是部署 node A 和 node C，那么 node A 就只存储 object1，而 node C 则同时存储 object2、object3 和 object4，这样的映射不满足平衡性要求。

虚拟节点的引入可以很好的解决一致性哈希算法的平衡性问题:

虚拟节点(virtual node)是实际机器节点在环形哈希空间中的副本，一个实际的机器节点对应了多个“虚拟节点”，“虚拟节点”在环形哈希空间中以哈希值排列。

如果没有虚拟节点，只部署 node A 和 node C 两台机器，如图所示，数值对象在机器节点上分布很不平衡。为此引入虚拟节点，并且设置一个实际的物理节点对应2个虚拟节点，这样就会存在4个“虚拟节点”，虚拟节点 node A1, node A2 对应实际物理节点 node A，虚拟节点 node C1, node C2 对应实际物理节点 node C，这样数值对象在各个节点上的分布情况如图所示:

consistent-hash-6.png

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

objec1->node A2;
objec2->node A1;
objec3->node C1;
objec4->node C2;

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

引入“虚拟节点”后，之前数值对象到机器节点的映射关系就从{ 数值对象 -> 机器节点 }变成了现在的{ 数值对象 -> 虚拟节点 -> 实际物理节点 }。这样查询数值对象所在节点时的映射关系如图所示:

virtual-node.png

“虚拟节点”的哈希值的计算，一般是将对应实际物理节点的IP地址加数字后缀作为哈希函数的输入。例如假设 node A 的 IP 地址为202.168.14.241。 在集群引入“虚拟节点”之前，计算实际物理机器节点 node A 的哈希值：Hash(“202.168.14.241”) 在集群引入“虚拟节点”之后，要计算的是“虚拟节点” node A1 和 node A2 的哈希值:

Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2

总结

一般来说，分布式系统需要哈希以均匀地分配负载，然而简单哈希不足以解决当分布式集群发生变化的时候将影响最小化的问题，因此需要一致性哈希，保证哈希环变更，集群只需要最小量的工作适应。此外，节点需要存在于环上的多个位置，确保从统计学上来说负载更可能更均匀地分配。最后还需要引入“虚拟节点”来解决平衡性的问题，保证哈希结果分布到所有的地址空间中，这样可以使得所有的地址空间都得到充分利用并保证系统压力负载的均衡。