常见一致性哈希算法简析（一致性哈希算法有哪些）

常见一致性哈希算法简析（一致性哈希算法有哪些）

编码文章call10242025-07-18 13:42:045A⁺A^-

0.简介

在分布式系统中，负载均衡和数据分布是确保系统高效运行的关键。传统的Hash算法虽然能在一定程度上实现数据的均匀分布，但在节点增减时，需要重新分配所有数据，这会导致巨大的开销和潜在的性能问题。为了解决这个问题，一致性Hash算法应运而生。本文将详细介绍常见的几种一致性Hash算法的原理。

1.概念介绍

一致性哈希算法本质是构造一种函数f(k,n)->m，把字符串映射到n个槽上，m表示其位置，其输入为随机的字符串k和槽的个数n，输出则是槽的编号m（m在0-n之间）。

该函数需要满足以下的性质：首先对于一个哈希的函数来说需要做到均匀的映射，对于随机输入的k，函数返回0-n中任意一个数字的概率相等；其次一致性哈希算法需要做到当槽数量增减时，映射和之前不一样的字符串要尽可能少。

一致性哈希常见的算法有哈希环法、跳跃一致性哈希和Maglev一致性哈希，下面将对其进行详细分析。

2.哈希环法

哈希环法时将哈希值空间映射到一个环形结构上，通常这个环的范围是0到2^32-1（或其他合适的范围），在这个环形空间上服务器节点和数据项都通过哈希函数计算得到一个哈希值，这个哈希值决定了它们在环上的位置。具体算法描述如下：

1）设hash(key)是映射到区间0到2^32-1的一个hash函数，形成一个首位相连顺时针增长的has环。

2）将所有槽位（或者节点n1,n2...nn)依次作为hash的输入进行hash，将结果在环上进行记录。

3）关于对key的映射，求出z=hash(key)，标记在环上，其规则如下：如果z正好在槽位上，就返回这个槽位的编号，否则顺时针找到最近的槽位并返回编号。

如下图所示，当新增n5槽位时，只需要变更hash（k）的归属，对于hash(k1)和其他部分都不需要变化，即只变化n1 < hash(k) < n5的区间，避免了全量的重新映射。在实际应用过程中，还会对槽位添加权重，也就是增加指向真实节点的虚拟节点（也称为影子节点），虚拟节点之间权重一致，选中影子节点就代表使用背后的真实节点，权重大影子节点也就多，选中概率也就高；同时，每个真实节点对应的影子节点越多，映射分布越均匀。

3.跳跃一致性哈希

跳跃一致性哈希（Jump Consistent Hash）是在一致性哈希基础上的改进和优化，由Google的John Lamping和Eric Veach在2014年提出，其核心思想是对于某个对象来说，通过一种高效的计算方式，将其分配给某一个节点。与传统的一致性哈希相比，它不需要构建环状拓扑结构，也不需要每个节点都有多个虚拟节点，而是直接根据对象和节点的数量进行映射。算法中没有使用random，而是自己做了一个64位的线性同余随机数生成器，代码如下：

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

代码具体步骤说明如下：

对象通过某种哈希函数生成一个整数key，用来决定分配到哪个节点。
初始化一个虚拟桶号b，设置为-1，表示目前没有任何桶被选中。
初始化一个计数器j为0，从节点0开始迭代。
不断地循环，逐步将哈希值和当前节点j结合计算，并检查是否更新b，直到遍历完所有节点为止。
返回最终确定的b值，它就是被选中的节点。

接下来我们来对这个跳跃一致性算法进行一个推导（来看这个函数是如何得到的），假设需要的一致性hash函数f(k,n)，n是槽位数量，k是要映射的键key，num是映射的总数量：

1）当n=1时，所有的k都要映射到一个槽位上，函数返回0，即为f(k,n)=0。

2）当n=2时，为了均匀的映射，每个槽都要映射num/2个k，也就是原本n=1时全部放到0位置上的num/2个k需要重新映射。

3）以此类推，当槽位由n变为n+1时，需要对num/(n+1)个k进行重新映射。

我们知道了重新映射的数量才能保证映射均匀，接下来面临的问题是：那些key需要被重新映射。其方式是通过随机数（伪随机数，只要种子不变，随机序列就不变）来决定一个key要不要被重新映射到新槽位，对于每个key，用它作为随机数种子，就能获得一个key的随机序列，为保证槽位数量由j变为j+1时有num/(j+1)的数据会被重新映射到新槽位，可以使用如下条件决定，如果random.next < 1/(j+1)则重新映射，如此我们就能获得一个初步的f函数。

int f(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;
}

下图是n从一到五的一个变化过程，k1和k2每一次都要根据随机序列相应的值和目标分布1/n做比较来决定是否留在原位。

其中k（key)一旦确定，给定一个n时，其结果也就确定，如果随机序列足够均匀，结果就足够均匀，同时，f函数没有造成全量重新映射，而是将1/（n+1）的数据比例进行重新映射，达到一致性哈希的标准。

当然，其仍然可以优化，random.next < 1/(j+1)的概率相对较小，命中概率并不高，在上面f函数中，b用来记录k最后依次跳入的槽位号，加入k跳入最有一个槽位时，此时一定有b+1个槽位，当增加到b+2个槽位时，k不换槽的概率时(b+1)/(b+2)，假设要找的下一个b是j，当槽位数目达到j+1时k跳入了最新槽位，那么，在此期间，k保持连续不换槽的概率：

也就是说，k连续不跳槽知道增加到j+1的概率为(b+1)/j，如此我们可以将符合不换槽概率时的进行跳过，也就是：

int f(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;
}

4.Maglev一致性哈希算法

Maglev一致性哈希算法是由Google开发的一个一致性哈希算法。用于在分布式系统中实现负载均衡和数据分布。它通过建立一个槽位的查找表（lookup table），对输入键（key）进行哈希计算并取余，从而映射到表中的一个槽位。其算法原理是：

查找表的建立：

首先，创建一个大小为M（M为质数）的待填充空表作为查找表。为每个槽位生成一个大小为M的序列，称为“偏好序列”。这个序列是通过两个独立的哈希函数h1和h2计算得到的，具体计算方式为：offset=h1(b)%M，skip=h2(b)%(M-1)+1，然后对每个j计算出permutation[j]=(offset+j×skip)%M，即为槽位b生成了一个偏好序列。