对于分布式存储，在不同机器上存储不同对象的数据，我们通过使用哈希算法来建立从数据到服务器之间的映射关系。

为什么需要一致性哈希

使用简单哈希算法的例子就是m = hash(o) mod n，其中 o 为对象，n 为机器数量，得到的 m 为机器编号，hash()为选用的哈希函数。

考虑以下场景：

3 个机器节点，有 10 个数据哈希值为 1，2，3…10。使用的哈希算法为m = hash(o) mod 3，其中机器 0 上保存的数据有 3,6,9，机器 1 上保存的数据有 1,4,7,10，机器 2 上的数据保存的是 2,5,8。

当增加一台机器后，n=4，此时通过哈希算法索引数据所在节点编号时会发生变化，如数据 4 会保存的机器是编号 0 而不再是 1，所以数据也需要根据集群节点的变化而迁移。当集群中数据量较大时，使用这种简单哈希函数所导致的迁移带来的开销将是集群节点难以承担的，在分布式存储系统中，这意味着如果想要增加一台机器时，就要停下服务，等待所有文件重新分布一次才能对外重新提供服务，而一台机器掉线时，尽管只掉了一部分数据，但所有数据访问路由都会出现问题，导致整个服务无法平滑的扩缩容，成为了有状态的服务，这种问题又被称为 rehashing 问题。

除此之外，当节点数量发生变化时，所有的节点都需要获取到对应哈希函数的配置，如上述是强哈希简单取模，那么需要获取结点数量 n。

一致性哈希简述

一致性哈希算法就是为了解决 rehashing 问题而生的，它能够保证当机器增加或减少时，节点之间的数据迁移只限于两个节点之间，而不会造成全局的网络问题。

在一致性哈希中，会维护一个哈希环，根据常用的哈希算法将对应的 key 哈希到一个具有 2^32 次方个桶的空间，将数字头尾相连（0 到 2^32-1），即想象成一个闭合的环形。与常用的哈希算法不同，常用的哈希算法是对节点的数量进行取模运算，而一致性哈希算法则是对 2^32 进行取模运算。

img

哈希环的空间是按顺时针方向组织的，需要对指定 key 对应的值进行读写时，会首先将 key 作为参数通过哈希函数确定 key 在环上的位置，然后从这个位置沿着哈希环顺时针“行走”，遇到的第一个节点就是 key 对应的结点。我们假设有 key1，key2，key3，经过哈希算法计算后，在环上的位置如图所示：

img

在上述例子中，我们假设在 3 个节点的集群中再添加一个节点 node4，可以看到，key1 与 key2 的映射不会受到影响，只有 key3 的映射会由原先的 node3 映射到 node4。

img

假设此时 node1 故障了，key1 也会被重新转移，映射到 node2 上。可以从下图看到，key2 与 key3 的映射并不受到影响，会受到影响的数据仅仅只是会寻址到此节点与前一节点之间的数据。

img

比起普通的哈希算法，使用一致性哈希算法后，在扩容或缩容时，只需要重定位环空间中一小部分的数据，一致性哈希算法具有较好的容错性和可扩展性。但是在哈希寻址中经常有客户端集中访问少数几个节点的情况，这是由于 key 在节点之间分布不均导致的，从而出现某些机器高负载，某些机器低负载的情况。

img

虚拟节点

在节点数量较少的情况下，上述问题尤为显著，我们可以通过虚拟节点来增加节点数，使得节点的分布更为均匀。

对每一个机器节点计算多个哈希值，在每个计算结果的位置上都放置一个虚拟节点，并将虚拟节点映射到实际节点中，如可以在主机名后增加编号，分别计算 node2-1，node2-2，node2-3…node2-x 的哈希值，为 node2 节点形成了 x 个虚拟节点，如此为所有真实节点都计算 x 个虚拟节点，再分布到哈希环上，这样节点的分布就会显得比较均匀。当然，节点越多分布的会越均匀，此外，使用虚拟节点还可以降低节点之间的负载差异。

对于 x，我们称之为权重，具体取值取决于不同的情况（也可能每个节点的权重都不同），来调整 key 最终在每个节点的概率，如果机器节点 node1 能承受的负载更大，那么它可以被分配两倍的权重，因此平均而言，最终会有两倍的 key 映射到 node1 上。

img

当一个真实节点故障时（或被移除集群），必须从环中删除其所有虚拟节点，而以前与被删除节点相邻的节点则将继承被删除节点的 key 的映射。而其余已经被映射到其它节点的 key 不会受到丝毫影响。

当我们向集群中添加节点时，发生的事情也是相似的，大概会有 1/3 的 key（属于其它节点）会被重定向到新加入的节点中，而其余的 key 映射则不变。

这就是一致性哈希解决 rehashing 问题的方法，一般来说，当 a 为 key 的数量，b 为 node 的数量时（确切来说，是初始和最终节点数的最大值），只有 a/b 的 key 需要被重新映射。

算法权衡

一致性哈希的概念在 Karger 1997 年发布的论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中引入，之后在许多其他分布式系统中使用，并不断优化和改良。

在论文中，作者在讨论 Consistent Hashing 的定义时，针对算法好坏给出了 4 个评判指标：

  • 平衡性（Balance）：不同 key 的哈希结果分布均匀，尽可能均衡地分布到各个节点上。标准哈希函数的设计很重视平衡性，在分布式存储的设计中，它能使得所有的节点空间都得到利用。
  • 单调性（Monotonicity）：当有新节点上线后，系统中原有 key 要么还映射到原来的旧节点上，要么映射到新的节点上，而不会出现从一个旧节点重新映射到另一个旧节点的情况。即当可用存储桶的集合发生更改时，只有在必要时才移动项目以保持均匀的分布。
  • 分散性（Spread）：在不同客户端视角中，由于它们可能无法看到后端的所有服务，对于相同的 key，它们可能会认为会被分散到不同的服务节点上，从而降低后端存储的效率，我们称之为不同的观点。分散性要求总的观点数量必须有一个上限，优秀的一致性算法应当让分散性尽可能的小。
  • 服务器负载均衡（Load）：类似于 Spread，Load 从服务端的角度来看，指各个服务节点的负载尽量均衡。简单来说，它规定单个节点所能承受 key 映射的上限，好的一致性算法应该让这个上限尽可能的小。

在后续论文《Web Caching with Consistent Hashing》中，Karger 等人提出了一致性哈希的实现，即上文所述的环切法，这个算法的特点在于维护哈希环需要占用内存，具体大小根据节点总数（虚拟节点）而定。

ketama 算法

最常见的一致性哈希算法实现是 ketama 算法，它满足单调性，实现简单，因此也被广泛使用。在 github 上有多语言实现版本。

img

算法的核心思路是：从配置文件中读取机器节点列表，包括节点地址以及 mem，其中 mem 参数用于衡量一个节点的权重。对于每个节点按权重计算需要生成几个虚拟节点，ketama 算法的基准是每个节点会计算 160 个虚拟节点，每个节点会生成成 10.0.1.1:11121-1、10.0.1.1:11121-2 到 10.0.1.1:11121-40 共 40 个字符串，以此算出 40 个 16 字节的哈希值（使用的哈希算法是 MD5），每个哈希值生成 4 个 4 字节的哈希值，共计 160 个哈希值，对应 160 个虚拟节点。将所有哈希值及其对应地址存放到一个 continuum 存组中，并按哈希值排序，方便后续通过二分查找直接计算映射节点。

这里贴出代码的关键实现：

img

img

算法的总体复杂度是 log(vn)，n 为节点数，v 为每个节点的虚拟节点数，默认为 160。

算法的缺点是占用内存较大（n*v），且在虚拟节点数较少的情况下，平衡性较差。

HRW 算法

集合哈希（Rendezvous hashing），也被称为最高随机权重哈希（HRW），是 1996 年的论文《A Name-Base Mapping Scheme for Rendezvous》中发布的算法，它让多个客户端对 key 映射到后端 n 个服务达成共识，典型的应用就是代理：客户需要将对象分配给哪些站点达成一致。

算法思路是：对于每个 Object O，为每个 Server j 去计算一个得分，然后将 O 分配给最高得分的 Server。首先所有的 client 要有一个一致的 hash 算法 h()，对于每个 O，都会调用 w(i, j) = h(Oi, Sj)，由于算法是一致的，所有 client 都可以各自计算权重并挑选最高权重的 Server，从而使得任意 client 都可以基于 HRW 计算 Object 最终的分配位置。

此外，HRW 还可以轻易适应不同 Server 的不同负载能力，假如 Server k 的负载能力是其他 Server 的两倍，只要将 Server k push 到 Server list 中两次即可，显然，Server k 就会被分配到两倍的 Object。

与常规 consistent hashing 相比，HRW 不需要提前计算和存储 token（这里指节点在哈希环上的哈希值），避免了正确处理每个 Server token 带来的开销和复杂性，HRW 还能保证全局均匀分摊 Object，在计算哈希值后，还能选择多个 Server。

跳转一致性哈希

跳转一致性哈希（Jump consistent hash）是 Google 于 2014 年发表的论文《A Fast, Minimal Memory, Consistent Hash Algorithm》中提出的一种一致性哈希算法，特点是占用内存小且速度快，实现代码精简，适合用在分 shard 的分布式存储系统中。

算法思路如下：

以下代码是一个一致性哈希函数，将 key 一致性映射到给定的几个节点中的一个上，输入 key 和节点数量 num_buckets，输出映射到的节点的标号。

1
2
3
4
5
6
7
8
9
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = -1, j = 0;
  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}

假设我们要求的一致性哈希函数的 ch(k, n)，n 为节点数量，k 为要映射的 key，K 是 key 的总数。那么有以下情况：

  1. 当 n 为 1 时，所有 k 要映射到同一个节点上，函数返回 0，即 ch(k, 1) = 0。
  2. 当 n 为 2 时，为了映射均匀，每个节点需要映射到 K/2 个 key，因此有 K/2 的 key 需要重新映射。
  3. 以此类推，当 n 为 n+1 时，需要 K/(n+1) 个 key 进行重新映射。

那么哪些 key 需要被重新映射呢？跳转一致性哈希的做法就是使用随机数来决定一个 key 每次是否需要重新映射到新的节点上，此处的随机为伪随机，随机序列随种子变化。为了保证节点数量从 j 变到 j+1 时会有 1/(j+1) 占比的数据重新映射到新结点 (j+1) 中，可以通过这个方法来判断：如果random.next() < 1 / (j + 1)则重新映射，否则不变。实现思路与跳表有点相似，得到如下代码：

1
2
3
4
5
6
7
8
int ch(int k, int n) {
  random.seed(k);
  int b = 0;  // This will track ch(k, j+1).
  for (int j = 1; j < n; j++) {
    if (random.next() < 1.0/(j+1)) b = j;
  }
  return b;
}

img

这个函数的复杂度显然是 O(N)，接下来我们将其优化到 O(logN)。

在上面的代码中，random.next() < 1 / (j + 1)发送的概率相对小一点，因此命中率不高，只有少数的 key 选择重新映射，这里我们可以帮助其加速。

b 是用于记录 key 最后一次重新映射的节点标号，假如我们现在处于 key 刚刚最后被重新映射的时刻，此时一定有 b+1 个节点，接下来要新增一个节点为 b+2 时，可以知道 k 不需要重新映射的概率是 (b+1)/(b+2)。假设我们要找的下一个 b 是 j，即当节点数量新增到 j+1 个时，恰好位于 key 刚刚最后被重新映射的时候。这个期间 k 保持连续不重新映射的概率应该是 (b+1)/j。

img

改下 ch 函数，当符合连续不重新映射的概率时，直接跳过。

1
2
3
4
5
6
7
8
9
int ch(int k, int n) {
  random.seed(k);
  int b = 0, j = 0;
  while (j < n) {
    if (random.next() < (b+1.0)/j) b = j;
    j += continuous_stays;
  }
  return b;
}

设 r=random.next()，转换为 j 最多移动 (b+1)/r 的条件，向下取整为 floor(b+1)/r，改写函数如下：

1
2
3
4
5
6
7
8
9
10
int ch(int k, int n) {
  random.seed(k);
  int b = -1, j = 0;
  while (j < n) {
    b = j;
    r = random.next();
    j = floor((b+1) / r);
  }
  return b;
}

由于 r 分布均匀，当节点数变化为 i 时发生重新映射的概率是 1/i，所以预期的映射次数是 1/2+…+1/i+…1/n，函数收敛，复杂度为 O(logN)。

与一致性哈希相比，跳转一致性哈希在执行速度、内存消耗、映射均匀性上的表现都更优秀，几乎没有额外的内存消耗。它的性能虽然优秀，但是缺点也显著，它不支持设置节点的权重，尽管可以通过尝试添加虚拟节点来做权重；其次，跳转一致性哈希只能在末尾增删节点，如果在非尾部增删节点会导致后面的节点全部重新标号，会影响数据一致性；此外，跳转一致性哈希还不允许自定义节点编号，标号都是从 0 开始递增的。

除了上述几种算法外，一致性哈希衍生算法有很多种针对不同方面进行优化的实现算法，如有界载荷一致性哈希（Consistent Hashing with Bounded Loads）、悬浮一致性哈希（Maglev Hash）等，读者感兴趣自行了解即可。

应用场景

  • 分布式存储分片
  • P2P 系统
  • 服务路由，负载均衡：当服务为一个有状态服务时，需要根据特定 Key 路由到相同服务机器进行处理。

一致性哈希实战

WebSocket 集群实践

WebSocket 常用于记录用户在线状态、计时，服务端主动传输数据等方面。

为什么要用到一致性哈希

WebSocket 集群的实践中有两个重点需要解决的问题：

  1. 连接用到的 WebSocketSession 存储在服务节点，如何找到某个用户的 Session 所在服务节点？
  2. 如何确保客户端均衡连接到各个服务节点，防止单个服务节点负载过高？

这两个问题都可以通过一致性哈希来解决。

第一个问题主要围绕路由，上文也解释过了，一致性哈希解决了 rehashing 代价高昂的问题，第二个问题则围绕服务节点负载均衡的问题。这里笔者通过添加 Gateway 作为代理层实现路由，当有服务节点故障下线时，该节点与客户端的连接会自动断开（这里假设服务节点与服务中心的连接是畅通的，且客户端有心跳机制去探索服务节点是否存活），重新连接时（客户端 WebSocket 的重连机制），会在 Gateway 通过一致性哈希，通过客户连接标识的哈希值路由到应该重新映射到的服务节点上，而其余节点的连接不会受到影响。

当添加节点时，Gateway 会监听到有新节点上线，根据计算映射到新节点与上一个节点之间的 key 的集合，这些 key 将被重新映射到新节点，因此 Gateway 会通知该旧节点将这些 key 对应的连接断开，然后这些 key 会自动重新连接，通过 Gateway 路由重新映射到新节点上。

如下图，如果新节点 node3 映射到了 node1 与 node2 中间，以顺时针为例，这里的 key2 与 key3 都应该重新映射到 node3 上，因此 Gateway 会通知 node1，将 key2 与 key3 的连接主动断开，当他们自动尝试重连时，会重新连接到 node3 上。关于通知 node1，由于 Gateway 维护了哈希环，可以通过 key 找到映射的节点 node，因此通过路由，通知服务节点是可实现的。

img

尽管 WebSocket Server 是有状态的，但有着客户端的自动重连机制，可以尽可能将切换连接的损耗降低，尽管还有 WebSocket 连接建立和断开的开销。

存在的其他问题

  1. 网络连接与服务状态：前文中我们假设服务节点与服务中心的连接是畅通的，在服务节点无法与服务中心沟通时，我们保证客户端也无法与服务节点沟通。但是实际生产环境中可能存在各种各样的问题，比如服务节点无法与服务中心沟通时，已连接的客户端却能与服务节点沟通，这样 Gateway 在路由时就会丢失很多信息。
  2. 哈希环的存储：前文假设哈希环存放在 Gateway 上，当 Gateway 集群中，一个 Gateway 节点宕机后应该如何正确同步数据。这里需要保证哈希环应该是集群共享读写，服务中心必须灵敏感知服务节点状态，及时更新哈希环，才能避免消息丢失，这里如果将哈希环维护在 Gateway 本地，由于 IO 延迟等因素，需要保证哈希环及时更新的话，实现起来较为复杂。
  3. 负载不均衡：服务节点之间由于访问 key 的热度不同，可能存在的问题是相同 key 数量映射到相同服务节点上时，有些服务节点的压力会更大一些，因此建立连接的路由不能仅仅通过哈希环，还应该记录服务节点的负载情况，根据负载情况来选择路由。另一种办法是缓存该 key 与路由到的节点的映射，避免了多次调用哈希函数的开销，但也需要动态变化。

从一致性哈希看分布式缓存设计

总结

本文简要介绍了一致性哈希，从使用简单的哈希函数取模引出 rehashing 带来的高昂代价问题，说明了一致性哈希存在的意义。在后文中，还介绍了一致性哈希用于解决负载不均衡的问题，同时，本文还介绍了几种常见的一致性哈希算法。在末尾，本文还通过 WebSocket 集群的例子来实践一致性哈希。

参考