一致性 Hash 算法是一种常用于分布式系统负载均衡的算法，可以将外部发送来的请求均匀的分配到服务器集合中的某个节点，由此解决大量并发访问服务器的问题。今天我们就来了解一下该算法的原理，并且试着用代码来实现。

普通 Hash 算法

服务器集群接收到一次请求时，可以根据请求的信息（比如客户端的 IP 地址，或者请求路径与请求参数等信息），利用 Hash 算法得到一个哈希值。对于相同的 IP 地址，或请求路径和请求参数，同一个 Hash 算法算出来的哈希值是一样的。

除此之外，我们还需要一个算法，把哈希值映射成服务端的 IP 地址，可以让相同的请求落到同一台服务器上。因为客户端发起的请求是无穷无尽的（请求地址不同，请求参数不同等），所以对于算出来的哈希值也是也是无穷的。所以我们不可能把所有的哈希值都映射到服务器 IP 上，所以我们将其改造成哈希环。
image.png
最常见的做法就是：将一个哈希环分成一个个 Slot，具体的个数可以由用户自己指定，然后将客户端请求得到的哈希值与 Slot 的个数进行取模，最终落到某一个 Slot 上。如上图所示：

  • 客户端的哈希值取模运算后，落在 IP1 和 IP2 之间，由 IP2 的服务器进行处理；
  • 客户端的哈希值取模运算后，落在 IP2 和 IP3 之间，由 IP3 的服务器进行处理；
  • 客户端的哈希值取模运算后，落在 IP3 和 IP4 之间，由 IP4 的服务器进行处理；
  • 客户端的哈希值取模运算后，落在 IP4 和 IP1 之间，由 IP1 的服务器进行处理；

上面是分配比较均衡的情况，但是如果出现了有新节点加入集群或者旧节点宕机退出集群的情况。假设我们有一种完善的数据迁移机制，当有某个节点加入或退出时，会将其他节点的 Slot 或该节点的 Slot 分配出去。
image.png
假设 IP4 的服务器宕机退出集群后，其 Slot 都分配给了 IP1 的服务器，IP3 到 IP1 的范围较大，会有更多的请求落到 IP1 的服务器上，而其他节点请求较少，出现请求负载不公平的现象。

一致性 Hash 算法

一致性哈希提出了在动态变化的服务器环境中，该算法应该保证：

  • 平衡性：哈希的结果能够尽可能分布到所有的服务端中去，这样可以使得所有的服务器都得到利用。
  • 扩展性：如果已经有一些客户端过哈希落到了相应的 Slot 中，如果有新的服务器加入到集群中，那么哈希的结果应能够保证原有已分配的请求可以被映射到新的服务器中去。如果有节点宕机，那么只需要将少数请求转移到别的服务器上。

首先解决哈希环上 Slot 分配不均匀的问题，为此我们可以加入虚拟节点。所谓的虚拟节点就是对每一个服务节点计算多个哈希，每个计算结果位置都映射到同一个服务节点，称为虚拟节点。具体做法可以先确定每个物理节点关联的虚拟节点数量，然后在 IP 或者主机名后面增加编号。
image.png
接下来分析一下一致性哈希算法的扩展性。当添加新节点时，必须将含有各种请求的哈希环的某些部分分配给该节点。反过来，删除节点时，已分配给该节点的请求需要由另外某个节点来处理。

如果 IP2 的服务器宕机，那么落在 “IP3-1 至 IP2、IP3 至 IP2-1、IP3-2 至 IP2-2” 区间的请求需要重新被分配到其他最近的服务器上，如请求 2 由 IP1 服务器处理。
image.png
上述的过程如何用代码实现呢？对于服务端的个数和其 IP 地址我们可以轻易获取，那么我们只需要控制虚拟节点的个数、映射关系的存储和 Hash 算法的选择。虚拟节点越多，Hash 算法越散列，流量分配越均衡。

  1. public class ConsistentHash {
  2.     private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
  3.     private static final int VIRTUAL_NODES = 160;
  4.     static {
  5.         // 对每个真实节点添加虚拟节点，虚拟节点会根据哈希算法进行散列
  6.         for (String ip : ServerIps.LIST) {
  7.             for (int i = 0; i < VIRTUAL_NODES; i++) {
  8.                 int hash = getHash(ip+"VN"+i);
  9.                 virtualNodes.put(hash, ip);
  10.             }
  11.         }
  12.     }
  13.     private static String getServer(String client) {
  14.         int hash = getHash(client);
  15.         // 得到大于该Hash值的排好序的Map
  16.         SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
  17.         // 大于该hash值的第一个元素的位置
  18.         Integer nodeIndex = subMap.firstKey();
  19.         // 如果不存在大于该hash值的元素，则返回根节点
  20.         if (nodeIndex == null) {
  21.             nodeIndex = virtualNodes.firstKey();
  22.         }
  23.         // 返回对应的虚拟节点名称
  24.         return subMap.get(nodeIndex);
  25.     }
  26.     private static int getHash(String str) {
  27.         final int p = 16777619;
  28.         int hash = (int) 2166136261L;
  29.         for (int i = 0; i < str.length(); i++)
  30.             hash = (hash ^ str.charAt(i)) * p;
  31.         hash += hash << 13;
  32.         hash ^= hash >> 7;
  33.         hash += hash << 3;
  34.         hash ^= hash >> 17;
  35.         hash += hash << 5;
  36.         // 如果算出来的值为负数则取其绝对值
  37.         if (hash < 0)
  38.             hash = Math.abs(hash);
  39.         return hash;
  40.     }
  41.     public static void main(String[] args) {
  42.         // 连续调用10次,随机10个client
  43.         for (int i = 0; i < 10; i++) {
  44.             System.out.println(getServer("client" + i));
  45.         }
  46.     }
  47. }

一致性哈希确保一旦出现服务器环境变更，集群中只需要最小的工作量来调整。此外，节点需要存在于环上的多个位置，确保从统计学上来说负载更可能更均匀地分配。为每个环变更迭代整个哈希环效率很低下。随着分布式系统的规模不断扩大，势必需要一种更高效的方法来查明什么发生了变更，从而尽可能减小环变更对性能带来的影响。这就需要新的索引和数据类型来解决这个问题。