Maglev 一致性哈希：原理与 C++ 实现

秋落风声

345人浏览 · 2026-06-07 01:23:10

秋落风声 · 2026-06-07 01:23:10 发布

注

本文不是 Maglev 四层负载均衡器本身，而是其内部使用的一种一致性哈希算法，通常称为 Maglev Hash。

本文默认哈希函数为 MurmurHash64。

本文沿「背景 →算法核心 → 哈希表开放寻址 → 数论原理 → 算法实现 → 复杂度分析与 ketama 对比 → 参考附录」的主线展开。

背景

Maglev

Google 在 2016 年发表了 Maglev: A Fast and Reliable Software Network Load Balancer。论文内部提出了一种一致性哈希算法的新实现方案，后被微服务网关 Envoy 与 Google 的 gRPC 采用为工业级方案。

回顾负载均衡

负载均衡算法有「族」的概念，其中之一叫做映射粘性族。它回答的是：同一个 key 怎么永远落入同一台机器。它宁愿牺牲一部分均衡性，来换取其它族没有的性质——粘性。

为什么需要粘性

后端机器存储了某个客户端的热点缓存，客户端当然希望一直打到这台后端命中本地缓存，否则就是缓存 miss + 回源。又比如，会话状态保存在后端内存里，用户下一次落到同一台机器，登录状态才不会丢；如果落到其它机器，又要重新登录。

这种需求下，再追求均衡反而是破坏性的：把各个用户均匀分散，缓存命中率低、会话容易断。映射粘性族直接不追均衡，转而追求 key -> upstream_peer 的稳定映射。

朴素的映射：IP 哈希

IP哈希:请求的某个 key(比如客户端 IP),哈希一下,对后端数取模,hash(key) % N,落哪台就哪台。同一个 IP,只要后端数 N 不变,每次算出来都是同一台。粘性达成了,O(1),无状态。

致命问题
负载极度不均衡，高峰期用户量全打向同一机器，单机瞬间瘫痪。
取模对 N 极度敏感，N一变化(增加机器或者机器宕机), 缓存大量失效集体回源打崩数据库。

从公式上，hash(key) % N,N 一变,几乎所有 key 的归属同时变。3 台变 4 台,hash % 3 和 hash % 4 的结果对绝大多数 key 都不同——理论上只有约 1/N 的 key 还落在原位,其余全部重新洗牌。

缓存场景下这是灾难:加一台机器扩容，结果导致几乎全量缓存失效，根因就是哈希取模跟后端机器绑定太死。
一致性哈希就是来解开这个绑定。

注

IP 哈希现在已经退居幕后而不是彻底废弃。
在L4负载均衡中。系统拿不到上层的Cookie和Session，只能看到IP。当系统遭受大流量 DDoS 攻击时，安全网关在最外层用 IP Hash 将特定 IP 段的流量固定分流，进行行为审计和限流，避免污染其它干净的服务器。
IP 哈希属于映射粘性族，一致性哈希具有固定映射和负载均衡的能力。

朴素一致性哈希

一致性哈希需要将key与N解绑，思路就是建一个环。把哈希值空间(比如 0 ~ 2^31 - 1) 首尾相接成一个圆。

把每个后端哈希映射到环上一点(比如hash(节点标识)); 把每个key也哈希到环上一点。一个key属于哪个机器？顺时针遇到的第一个节点就是它的归属后端。

举一个例子，有三台后端 A B C

hash_ring:  0 ----A---- 0.33 ----B---- 0.66 ----C---- 1 
request1:    hash(key) = 0.4  -->  落在 B 的区间  -->  路由到 B
request2:    hash(key) = 0.6  -->  落在 B 的区间  -->  路由到 B

加一台机器，比如 D 插入到AB这个区间

hash_ring:  0 ----A---- 0.33 ----B---- 0.5 ----D---- 0.66 ----C---- 1 
request1:    hash(key) = 0.4  -->  保持在 B 区间  -->  路由到 B
request2:    hash(key) = 0.6  -->  变更到 C 区间  -->  路由到 C

只要中间新增的一段区间的所有节点划到新机器上。根本上全量更新到局部调整，这样缓存大量失效就变成来局部缓存失效，这是可接受的扰动。

朴素一致性哈希的问题: 分布不均匀。这正是ketama 一致性哈希要解决的问题。

ketama 一致性哈希

哈希的均匀性有两个前提，良好的哈希和函数和大量的输入。
朴素哈希环的毛病在于值域很大但输入很少，存在AB离得近，C离得远，于是C的前面一段区间全归C管。节点少的时候这种倾斜特别明显，重映射有保证但退化到了IP哈希的场景，均衡性和缓存又崩了。

方案是人为制造输入，用虚拟节点技术。即一台后端可以放k个虚拟节点，分别用hash(节点标识 + i)算出K个分散的位置。物理机器就是这哈希环上的k个虚拟节点。物理后端节点A就被分散在环里。

带权实现，通常用权重 * 每权重虚拟节点个数算出真实的虚拟节点个数。

好的哈希函数同样重要，通常用MurmurHash3分布均匀且雪崩性好。

保障均衡性的方案

映射粘性族的ketama一致性哈希已经不错了，均衡性也有了。那为什么有其它一致性哈希算法呢？
映射粘性族看的是静态负载不是动态负载。 ketama 不关心真实的运行时负载，它在静态时把key均衡的分给后端。
ketama的缺点在于概率，讨论一下最坏情况。虚拟节点K多少合适？K小了随机分布不均匀，退化到朴素一致性哈希甚至IP哈希的场景。

具像化到算法实现上， ketama的哈希环本质就是虚拟节点哈希值排序的数组，虚拟节点多了废内存，查找速度 $O (l o g (N * k))$ 加虚拟节点也拖累查找。

扰动的不可控，基于概率的保证，哈希落点不可控，重映射代价分布是随机和倾斜的。

ketama:均匀性，内存/查找开销，增删扰动可控性 – 这些都被K的这个旋钮捆死了。
如果说ketama是概率派，那么Maglev就是构造派，后者是结构性的设计不依赖概率。
注:
上面说明的ketama缺点并不表示一定劣于Maglev, 没有免费的午餐。两者的对比后文再说明。

Maglev 算法思想

先简单说明 Maglev 的核心思路，其采用一个固定大小的查找表(lookup table), 表的大小是质数M(论文中为65537)。
每个后端通过两个哈希函数计算一个偏好序列，然后所有后端按轮次依次填表。

for backend i, compute:
  offset[i] = h1(id) mod M
  skip[i] = h2(id) mod (M - 1) + 1

每个后端都有offset表示它在查找表的初始位置， skip表示它每次跳跃的步长(必须大于0且小于M)
然后是偏好序列的计算

backend i permutation:
  permutation[i][j] = (offset[i] + j * skip[i]) mod M

核心:填充算法

// 伪代码实现, 以 A B C 三个 backend 举例
func maglev_populate(backends, M):
  table <- [0] * M // 初始化填充表
  filled <- 0 // 当前查找表填充的个数
  while filled < M :
    // 轮询 backends [A, B, C, A, B, C, ...] 依次填表
    for backend in backeds:
      //先找到第一个表没被占的偏好数位置
      do {
        // pos 为当前后端的偏好数
        pos = (backend.offset + backend.next * backend.skip) % M
        backend.next++;
      } while table[pos] != nil;
      table[pos] = backend.peer
      filled++
      if filled == M:
        break // 整个表填完了。
  return table

看看均匀性, 假设M = 7，A B C

服务器 A： (Offset = 3, Skip = 2)
服务器 B： (Offset = 0, Skip = 3)
服务器 C： (Offset = 5, Skip = 1)
A 的偏好顺序： [3, 5, 0, 2, 4, 6, 1]
B 的偏好顺序： [0, 3, 6, 2, 5, 1, 4]
C 的偏好顺序： [5, 6, 0, 1, 2, 3, 4]
顺序 A占3， B占0，C占5，无冲突。那么第一轮结束了，第二轮回到A， A发现5被C占了，去它的下一个0，0被B占了，再去下一个2，拿到了; 同理B发现3被A占了，去占下一个6, 拿到了; C从6开始，6刚被B占了，去0发现也被B占了，去占1拿到了，第二轮结束。
第三轮从A开始， A从4开始拿到4了，此时查找表已经填完了，结束。
最终结果[0:B,1:C,2:A,3:A,4:A,5:C,6:B]。
这个例子不太好但是能理解填充表的过程，当M过大时不会出现上述AAA连续填的情况，实现完美的均匀。
每个后端机器的分布数量都至少都大于等于 M/N 的向下取整数。AB,C都大于等于 7 / 3 向下取整数2，其中A由于轮班在前面且M必定是质数，所以A是M/N的向上取整数(这里是3)。
总之，从算法角度，当M过大时每台后端机器是可以认为拥有M/N的均匀分布。

M为什么一定是质数？
这种填充法为什么保证不会漏表，比如有一个位置索引没有在任何后端节点的偏好序列上。
前文的offset,skip的设计原理？偏好序列的作用是？

偏好序列原理：哈希表开放寻址法

上述的查找表本质就是哈希表，查询过程哈希一下就可以 $O (1)$ 取后端节点了。

这源于哈希表的两种常见实现方式之一的开放寻址法，另一种常见是链地址法。
开放寻址有多种实现技术，比如线形探测，二次探测，这次涉及的是另外一种双重散列。

双重散列
给予定义:
$h(k,i) = (h_1(k) + ih_2(k)) mod\ m$
对比上文: permutation[i][j] = (offset[i] + j * skip[i]) mod M
$offset = T[h_1(k)]$ 决定探测的起点
$skip = T[h_2(k)]$ 决定探测的步长
这本质就是双重散列公式，偏好序列本质就是双重散列的探测序列。
Maglev填表是同一件事的"集体版本", 每个后端预先计算下一个填表序列，没有冲突(其它后端没填这个位置)填表，否则继续探测。

为什么 $o f f se t$ , $s k i p$ 不采用线性探测那样的固定步长1？
开放寻址的经典坑，聚集。一个连续槽被占，顺序遍历查找表，一路往下滑，插入和查找都恶化了。双重散列把步长 $s t e p$ 交给 $h_2$ 哈希函数决定，不同后端步长各异，探测序列错开几乎不聚集。

事实上，h1和h2可以采用同一哈希函数+不同种子，比如h1种子数为0，h2种子数为黄金分割数。 $h 1 (i d, 0)$ , $h 2 (i d, 0 x 9 e 3779 b 9 U)$ , 哈希函数通常是 $M u r m u r ha s h 3$

上文的公式skip[i] = h2(id) mod (M - 1) + 1, 保证步长大于0且小于M，它是不漏查找表能遍历全表的前提。
为什么M为质数，一定不会漏表呢？见下文数学原理。

数学原理：欧几里得

M是7，A，B，C的偏好序列在单周期M都完整覆盖了[0, 6]。这是意外吗？还是数学的必然？
"不漏表"本质要求就是走M步，每步互不相同。满足这个已经满足[0, m-1]全覆盖

用反证法
假设走X步和走Y步同余
$\times Skip) \equiv (Offset + y \times Skip) \pmod M$
消去 $O f f se t$ 并移项，得到：
$\times Skip \equiv 0 \pmod M$
如果成立， $\times Skip$ 必须是 $M$ 的整数倍。
M有两种讨论
讨论一: 假设M是质数，那么它的约数只有1和它本身。
M能整除 $\times Skip$ 。

根据欧几里得引理（Euclid’s Lemma）：如果一个质数能整除两个整数的乘积，那么这个质数至少能整除其中一个因数。

以下两个条件中必须有一个成立：

$M$ 能整除 $(x - y)$ ，记作 $\mid (x - y)$
$M$ 能整除 $S k i p$ ，记作 $\mid Skip$

然而，已知：

$(x - y)$ 的范围是 [1, M-1]，比 $M$ 小。
$S k i p$ 的范围是 [1, M-1]，也比 $M$ 小。

一个质数绝对不可能整除任何比它自身小的正整数！

因此，条件 1 和条件 2 统统不成立，从而产生了矛盾。这说明最初的假设（即同余碰撞）完全错误，不会发生。

结论一（质数情况）：
当 $M$ 是质数时，服务器走 $M$ 步的每一步余数都绝对互不相同。既然每步都不同，走完 $M$ 步就必然完美覆盖 [0, M-1] 的所有位置。数学的必然。

讨论二：假设 M 是合数

如果 $M$ 是合数，意味着它除了 1 和自身外，还可以分解为其他因数的乘积。我们设 $d_1 \times d_2$ （其中 $d_1, d_2 > 1, d_1和d_2可能相同$ ）。

因为 Maglev 的 $S k i p$ 是由哈希函数随机生成的，如果某台服务器算出来的步长刚好是 $Skip = d_1$ （或者 $d_1$ 的倍数）。

此时，当服务器跑了 $d_2$ 步时（因为 $d_2 < M$ ，这在 $M$ 步之内必然会发生），相乘的结果：
$\times Skip = d_2 \times d_1 = M$

这个乘积变成了 $M$ 的 1 倍（ $M$ 的整数倍）！
同余方程 $\times Skip \equiv 0 \pmod M$ 成立。服务器还没跑满 $M$ 步，就已经踩到了之前踩过的格子，这意味着死循环，没到的格子永远不会到了也就漏掉了。

结论二（合数情况）：
当 $M$ 是合数时，算法在跑满 $M$ 步前就提早发生同余碰撞并陷入局部死循环，无法全覆盖，这就是“漏表”灾难。

唯一因子分解定理或欧几里德引理证明自行查阅。

C++ 算法实现

接下来的代码是我实际项目中的实现Maglev，忽略其它细节比如RCU,指纹验证。
这是从整个负载均衡算法完整代码中截取出的Maglev，不能直接跑通，理解真实实现后自行改写即可。

Maglev算法分为建表和查询。初次建表或者重建表(增加机器或者机器宕机)，另一种是查表(哈希函数打桶)
查找表: 一个数组, 由填充算法建立。另一字段是指纹验证技术的字符串(自行了解)

  struct LookupTable {
    std::vector<std::shared_ptr<UpstreamPeer>> entries;
    std::string fingerprint;
  };

后端游标的， peer表示真实的后端节点描述， offset是起点，skip表示步长，next表示下一个所在偏好序列的下标。

  struct BackendCursor {
    std::shared_ptr<UpstreamPeer> peer;
    std::size_t offset;
    std::size_t skip;
    std::size_t next{0};
  };

建表的代码, 先看完整。

  std::shared_ptr<const LookupTable> BuildTable(
    const std::vector<std::shared_ptr<UpstreamPeer>>& peers,
    uint64_t now_ms) const {
    auto table = std::make_shared<LookupTable>();

    std::vector<BackendCursor> backends;
    table->fingerprint.reserve(peers.size() * 32);
    for (const auto& peer : peers) {
      if (!peer->AvailableAt(now_ms)) continue;

      table->fingerprint += peer->config().name;
      table->fingerprint += ':';
      table->fingerprint += std::to_string(peer->config().weight);
      table->fingerprint += ';';

      const int weight = std::max(peer->weight(), 1);
      for (int replica = 0; replica < weight; ++replica) {
        std::string id = peer->config().name;
        id += '#';
        id += std::to_string(replica);

        const uint64_t h1 = runtime::ds::MurmurHash64(id, 0);
        const uint64_t h2 = runtime::ds::MurmurHash64(id, 0x9e3779b9U);

        backends.push_back(BackendCursor{
          peer,
          static_cast<std::size_t>(h1 % table_size_),
          static_cast<std::size_t>((h2 % (table_size_ - 1)) + 1),
          0,
        });
      }
    }

    if (backends.empty()) {
      return table;
    }

    table->entries.assign(table_size_, nullptr);
    std::size_t filled = 0;
    while (filled < table_size_) {
      for (auto& backend : backends) {
        std::size_t pos = 0;
        do {
          pos = (backend.offset + backend.next * backend.skip) % table_size_;
          ++backend.next;
        } while (table->entries[pos] != nullptr);

        table->entries[pos] = backend.peer;
        if (++filled == table_size_) break;
      }
    }

    return table;
  }

填表过程的具像化，
最外层循环的终止条件是查找表填满。
内部分别是轮询后端机器，然后找到空位填表。

table->entries.assign(table_size_, nullptr);
    std::size_t filled = 0;
    while (filled < table_size_) {
      for (auto& backend : backends) {
        std::size_t pos = 0;
        do {
          pos = (backend.offset + backend.next * backend.skip) % table_size_;
          ++backend.next;
        } while (table->entries[pos] != nullptr);

        table->entries[pos] = backend.peer;
        if (++filled == table_size_) break;
      }
    }

查询过程
下游客户端请求到了，比如用客户端ip做键值算出哈希值，然后对查找表长度取模。
找出固定的后端节点。

  static std::shared_ptr<UpstreamPeer> Lookup(const LookupTable& table, uint64_t hash) {
    if (table.entries.empty()) {
      return nullptr;
    }
    return table.entries[hash % table.entries.size()];
  }

所以相当于手写一个多后端双重散列哈希表？
对，这也是笔者首次写开放寻址的哈希表。

复杂度分析

Maglev 不是全面碾压 ketama。
负载均衡 <-> 增删扰动
Maglev:

查找 $O (1)$ , 不必在环上二分
均匀性更好，不依赖概率和虚拟节点数量。根因在设计理念。
代价在增删扰动: 增加/删除后端需要整表重建，重映射的key比例高于ketama一致性哈希的 $1/ n$ 。
换言之, Maglev用非最小扰动换近乎完美的均匀性。

维度	ketama(环 + 虚拟节点)	Maglev(查找表)
查找复杂度	O(log(n·K)),哈希环上二分查找	O(1),直接 `table[hash(key) % M]`
构建复杂度	O(n·K·log(n·K)),生成并排序虚拟节点	O(M·logM)(实践中约 O(M),M ≫ n)
均匀性	概率均匀,靠虚拟节点数 K 逼近,有可见偏差	构造均匀,各后端槽数至多差一个,不依赖 K
增删扰动	≈ 1/n 的 key 重映射(理论最小),但落点不均、可能集中	远大于 1/n,整表重建;靠大 M 压低绝对量
空间	O(n·K),K 默认 160 (通常范围在100～200之间)	O(M),M 通常取质数 65537
调参旋钮	K(虚拟节点数):牵动均匀性、内存、查找	M(表大小):主要影响扰动与精度

工业采用上,Envoy 提供 maglev 负载均衡策略,Katran(Facebook)使用 Maglev 哈希。

一致性哈希算法的方案选择

映射粘性族(缓存亲和)
+-- 是 --> 后端频繁增删 / 最怕缓存失效？
            +-- 是 --> 一致性哈希（虚拟节点）   # 扰动最小
            +-- 否 --> Maglev               # 均匀+O(1)，代价是扰动大
+-- 否 --> 根据需求选择(静态族/动态族)...

代码完整实现

这里只贴了代码，仅供参考

// Maglev hashing: precomputed lookup table for stable O(1) hash selection.
//
// Unlike ketama, the hot path is a single table lookup:
//   MurmurHash64(key) % table_size -> peer
//
// The table is rebuilt only when the available peer fingerprint changes.
// This implementation supports weights by expanding each peer into "weight"
// logical Maglev backends.
class MaglevHashLB : public LoadBalancer {
public:
  static constexpr std::size_t kDefaultTableSize = 65537;
  static constexpr std::size_t kMinTableSize = 257;
  static constexpr std::size_t kMaxTableSize = 1048583;

  enum class HashOn : uint8_t {
    kClientIp,
    kUri,
    kUserId,
    kSessionId,
  };

  explicit MaglevHashLB(std::size_t table_size = kDefaultTableSize,
    std::string_view hash_on = "client_ip")
  : table_size_(NextPrime(std::clamp(table_size, kMinTableSize, kMaxTableSize))),
    hash_on_(ParseHashOn(hash_on)) {}

  std::shared_ptr<UpstreamPeer> Select(Upstream& upstream, const RequestContext ctx = {} ) override {
    const auto& peers = upstream.peers();
    const uint64_t now_ms = detail::SteadyClockMs();
    auto fp = ComputeFingerprint(peers, now_ms);
    if (fp.empty()) return nullptr;

    auto table = table_.load(std::memory_order_acquire);
    if (table && table->fingerprint == fp) {
      return Lookup(*table, runtime::ds::MurmurHash64(HashKey(ctx)));
    }

    std::lock_guard lk{rebuild_mutex_};
    table = table_.load(std::memory_order_acquire);
    if (!table || table->fingerprint != fp) {
      table = BuildTable(peers, now_ms);
      table_.store(table, std::memory_order_release);
    }
    return Lookup(*table, runtime::ds::MurmurHash64(HashKey(ctx)));
  }

private:
  struct LookupTable {
    std::vector<std::shared_ptr<UpstreamPeer>> entries;
    std::string fingerprint;
  };

  struct BackendCursor {
    std::shared_ptr<UpstreamPeer> peer;
    std::size_t offset;
    std::size_t skip;
    std::size_t next{0};
  };

  static std::string ComputeFingerprint(const std::vector<std::shared_ptr<UpstreamPeer>>& peers,
                                        uint64_t now_ms) {
    std::string fp;
    fp.reserve(peers.size() * 32);
    for (const auto& peer : peers) {
      if (!peer->AvailableAt(now_ms)) continue;
      fp += peer->config().name;
      fp += ':';
      fp += std::to_string(peer->config().weight);
      fp += ';';
    }
    return fp;
  }

  std::shared_ptr<const LookupTable> BuildTable(
    const std::vector<std::shared_ptr<UpstreamPeer>>& peers,
    uint64_t now_ms) const {
    auto table = std::make_shared<LookupTable>();

    std::vector<BackendCursor> backends;
    table->fingerprint.reserve(peers.size() * 32);
    for (const auto& peer : peers) {
      if (!peer->AvailableAt(now_ms)) continue;

      table->fingerprint += peer->config().name;
      table->fingerprint += ':';
      table->fingerprint += std::to_string(peer->config().weight);
      table->fingerprint += ';';

      const int weight = std::max(peer->weight(), 1);
      for (int replica = 0; replica < weight; ++replica) {
        std::string id = peer->config().name;
        id += '#';
        id += std::to_string(replica);

        const uint64_t h1 = runtime::ds::MurmurHash64(id, 0);
        const uint64_t h2 = runtime::ds::MurmurHash64(id, 0x9e3779b9U);

        backends.push_back(BackendCursor{
          peer,
          static_cast<std::size_t>(h1 % table_size_),
          static_cast<std::size_t>((h2 % (table_size_ - 1)) + 1),
          0,
        });
      }
    }

    if (backends.empty()) {
      return table;
    }

    table->entries.assign(table_size_, nullptr);
    std::size_t filled = 0;
    while (filled < table_size_) {
      for (auto& backend : backends) {
        std::size_t pos = 0;
        do {
          pos = (backend.offset + backend.next * backend.skip) % table_size_;
          ++backend.next;
        } while (table->entries[pos] != nullptr);

        table->entries[pos] = backend.peer;
        if (++filled == table_size_) break;
      }
    }

    return table;
  }

  static HashOn ParseHashOn(std::string_view s) {
    if (s == "uri") return HashOn::kUri;
    if (s == "user_id") return HashOn::kUserId;
    if (s == "session_id") return HashOn::kSessionId;
    return HashOn::kClientIp;
  }

  const std::string& HashKey(const RequestContext& ctx) const {
    static const std::string empty;
    switch (hash_on_) {
      case HashOn::kUri:
        if (!ctx.uri.empty()) return ctx.uri;
        break;
      case HashOn::kUserId:
        if (!ctx.user_id.empty()) return ctx.user_id;
        break;
      case HashOn::kSessionId:
        if (!ctx.session_id.empty()) return ctx.session_id;
        break;
      case HashOn::kClientIp:
        break;
    }
    return ctx.client_ip.empty() ? empty : ctx.client_ip;
  }

  static std::shared_ptr<UpstreamPeer> Lookup(const LookupTable& table, uint64_t hash) {
    if (table.entries.empty()) {
      return nullptr;
    }
    return table.entries[hash % table.entries.size()];
  }

  static bool IsPrime(std::size_t num) {
    if (num < 2) return false;
    if (num == 2 || num == 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (std::size_t d = 5; d <= num / d; d += 6) {
      if (num % d == 0 || num % (d + 2) == 0) return false;
    }
    return true;
  }

  static std::size_t NextPrime(std::size_t num) {
    if (num <= 2) return 2;
    if (num % 2 == 0) num++;
    while (!IsPrime(num)) num += 2;
    return num;
  }

  std::size_t table_size_;
  HashOn hash_on_;
  std::atomic<std::shared_ptr<const LookupTable>> table_;
  std::mutex rebuild_mutex_;
};

参考文献

Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI 2016
Karger et al., Consistent Hashing and Random Trees, STOC 1997
Mirrokni, Thorup & Zadimoghaddam, Consistent Hashing with Bounded Loads, SODA 2018
gRPC Load Balancing — grpc.io/blog/grpc-load-balancing/ (Accessed: 2026-06)
Envoy Load Balancing — envoyproxy.io 文档,Upstream / Load Balancing (Accessed: 2026-06)

教科书(算法导论第三版)

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS), 3rd/4th ed.
- 第 11 章 Hash Tables,§11.4 Open Addressing(开放寻址、双重散列)——本文"偏好序列 = 双重散列探测序列"
- 第 31 章 Number-Theoretic Algorithms,§31.1–31.2(模运算、GCD 与欧几里得算法)——本文"gcd(skip, M)=1 保证遍历全表"