一文了解一致性哈希

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

为什么需要一致性哈希

使用简单哈希算法的例子就是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进行取模运算。

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

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

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

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

虚拟节点

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

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

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

当一个真实节点故障时（或被移除集群），必须从环中删除其所有虚拟节点，而以前与被删除节点相邻的节点则将继承被删除节点的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上有多语言实现版本。

算法的核心思路是：从配置文件中读取机器节点列表，包括节点地址以及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存组中，并按哈希值排序，方便后续通过二分查找直接计算映射节点。

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

算法的总体复杂度是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，输出映射到的节点的标号。

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的总数。那么有以下情况：

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

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

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;
}

这个函数的复杂度显然是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。

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

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，改写函数如下：

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集群的实践中有两个重点需要解决的问题：

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

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

第一个问题主要围绕路由，上文也解释过了，一致性哈希解决了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，因此通过路由，通知服务节点是可实现的。

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

存在的其他问题

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

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

总结

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