随机化与近似结构

一致性哈希

简单取模错在哪

把 key 分配到 N 台机器上，最直接的写法：

const node = nodes[hash(key) % nodes.length];

正确、均匀、一行。但加一台机器时全盘崩塌 —— % 5 变成 % 6，几乎每个 key 的归属都变了。

实测 20 万个 key，从 5 台加到 6 台：

简单取模 hash % N     迁移 83.31%     （理论 1 - 1/6 = 83.33%）

⚠️ 而理论上只需要迁移 16.7% —— 新机器应当承担 1/6 的 key，把这部分搬过去就够了，其余 83.3% 本可以原地不动。 📌 也就是说，取模法做了 5 倍于必要的搬迁。对缓存来说这意味着一次扩容后缓存几乎全失效，请求全部打到数据库。

环：把节点和 key 放到同一个空间里

⭐ 一致性哈希的想法：别用「第几台」定位，用「哪一段区间」定位。

把哈希值想成一个首尾相接的环（0 到 2³²-1）。节点按 hash(节点名) 落在环上， key 按 hash(key) 落在环上，每个 key 归属于顺时针方向遇到的第一个节点。

        A
    ↗       ↘
  E     环     B      key 落在这里 ─┐
    ↖       ↙                      ↓ 顺时针
        D ← C                    归 B 所有

加一个节点 F，只有「原本落在 F 与它逆时针方向前一个节点之间」的 key 变了归属， 其余节点之间的分界线一条都没动。

function createRing(nodes, vnodes) {
  const points = [];
  for (const n of nodes)
    for (let i = 0; i < vnodes; i++) points.push([hash(`${n}#${i}`), n]);
  points.sort((a, b) => a[0] - b[0]);

  return (key) => {
    const h = hash(key);
    // 环形：超过最后一个点就绕回第一个
    if (h > points[points.length - 1][0]) return points[0][1];
    let lo = 0, hi = points.length - 1;
    while (lo < hi) {                       // ⭐ 二分找第一个 ≥ h 的点
      const m = (lo + hi) >> 1;
      if (points[m][0] < h) lo = m + 1; else hi = m;
    }
    return points[lo][1];
  };
}

📌 查找是在有序数组上二分，O(log(N·vnodes))。

🚨 hash 是什么，决定了下面每一张表。 这一篇里它是 FNV-1a 32 位 再过一遍 murmur3 的收尾混合：

function hash(s) {
  let x = 2166136261;
  for (let j = 0; j < s.length; j++) {
    x ^= s.charCodeAt(j);
    x = Math.imul(x, 16777619);
  }
  x ^= x >>> 16;  x = Math.imul(x, 2246822507);   // ⭐ 这三行不是装饰
  x ^= x >>> 13;  x = Math.imul(x, 3266489909);   //   去掉它们虚拟节点会失效
  return (x ^ (x >>> 16)) >>> 0;                  //   见下面「雪崩性」一节
}

⚠️ 本篇所有数字的测量口径：20 万个 key（k0 到 k199999），5 个节点，新增节点记作 F、删除节点记作 C。凡是标了「中位数」的表，都是换 200 组不同的节点名各测一次得到的分布——单独一组节点名只是一次抽样，见下文。

⭐ 真正的保证：非必要迁移为 0

5 → 6 个节点，把迁移的 key 按「去了哪」拆开。200 组节点名各测一次：

vnode     总迁移 中位数 (p10~p90)     两个老节点之间的迁移（200 组最大值）
   1        12.5%  ( 2.2 ~ 34.9)              0.0000%
  10        16.6%  (11.2 ~ 23.4)              0.0000%
  50        16.6%  (14.3 ~ 19.4)              0.0000%
 150        16.6%  (15.0 ~ 18.4)              0.0000%
 500        16.7%  (15.8 ~ 17.4)              0.0000%
1000        16.7%  (16.2 ~ 17.3)              0.0000%

⭐ 最后一列全是 0.0000% —— 这才是一致性哈希的核心性质： 它从不在两个既有节点之间搬数据。 每一个被迁移的 key，去向都是新节点。

📌 这一列和别的列不是一类东西。中间那一列会随抽样上下浮动，最后这一列是结构性的：跨 2400 组配置（两种哈希 × 200 组节点名 × 6 档 vnode）一个反例都没有。要记的是这一列。

⭐ 另外注意总迁移量：vnode 一大起来就稳定停在 16.6~16.7%，正是理论下界 1/6。它搬的每一个 key 都是非搬不可的。

删节点同理。删掉 C（vnode=1 那组恰好是 C 独占了 47%）：

vnode=  1   迁移 47.0%   而 C 原本就持有 47.0%
vnode=150   迁移 18.8%   而 C 原本就持有 18.8%

📌 迁移量恰好等于被删节点原本持有的份额 —— 一个多余的 key 都没动（实测「原本不属于 C 的 key 被动了几个」= 0）。

🚨 但环上直接放节点会严重不均

只放 5 个点到一个 2³² 的环上，间距是随机的，分布好不到哪去。实测：

vnode=1   A=50423  B=30518  C=94049  D=10318  E=14692
          最大/最小 = 9.1 倍     标准差/均值 = 76.2%

⚠️ C 拿到 47% 的流量，D 只拿 5.2%。这不是哈希函数不好，是点太少 —— 5 个随机点本来就分不均一个环。

📌 这一条能算出来：n 个节点各放 v 个点时，单个节点的负载份额服从 Beta(v, nv-v)，于是标准差/均值 = √((n-1)/(nv+1))。 n=5、v=1 代入得 81.6%，实测这一组 76.2%、200 组的中位数 75.5% （p10~~p90 是 47.0~~110.1%）—— 对得上，也说明单看一组毫无意义。

解法是虚拟节点：每个物理节点在环上放 v 个副本（A#0、A#1…），点多了间距自然趋于均匀。

vnode     最大/最小 中位数(p10~p90)     标准差/均值 中位数(p10~p90)    理论值
    1      15.8×   ( 4.6 ~ 85.1)           75.5%  (47.0 ~ 110.1)      81.6%
   10       2.1×   ( 1.5 ~  3.1)           25.9%  (13.3 ~  39.2)      28.0%
   50       1.4×   ( 1.2 ~  1.7)           11.1%  ( 5.8 ~  17.0)      12.6%
  150       1.2×   ( 1.1 ~  1.3)            6.6%  ( 3.6 ~  10.2)       7.3%
  500       1.1×   ( 1.1 ~  1.2)            3.8%  ( 2.2 ~   5.6)       4.0%
 1000       1.1×   ( 1.0 ~  1.1)            2.7%  ( 1.6 ~   4.0)       2.8%

⭐ 每一档都贴着理论值 √((n-1)/(nv+1))，收益一路按 1/√v 递减，没有平台期。从 150 加到 1000，均衡度还能从 6.6% 再降到 2.7%。

⚠️ 所以常见实现取 100~200，理由不是「再加就没用了」，而是性价比： 6.6% 的不均衡在真实集群里已经够用，而 v 再翻十倍要多排序、多驻留十倍的环上点位（1000 台机器 × 1000 副本 = 一百万个点）。是成本换的，不是收益没了。

🚨 虚拟节点能不能起效，取决于哈希的雪崩性

上面那张表如果把 hash 换成朴素的 FNV-1a（去掉那三行收尾混合），同样的代码、同样的 key，结果完全变样：

vnode    朴素 FNV-1a    加收尾混合    理论值      朴素版的「有效点数」
    1       77.7%          75.5%      81.6%        1 / 1
   10       73.0%          25.9%      28.0%        1 / 10      ← 十个副本等于一个
   50       42.3%          11.1%      12.6%        5 / 50
  150       28.3%           6.6%       7.3%       16 / 150
  500       17.7%           3.8%       4.0%       51 / 500
 1000       10.5%           2.7%       2.8%      108 / 1000

⚠️ 朴素版每一档都差理论值一大截，而且越往后差得越多（v=1000 时差 3.8 倍）。如果只测这一版，会得出「虚拟节点收益在 50~150 之后趋于平缓」的结论 —— 那不是虚拟节点的性质，是哈希函数的缺陷。

原因看一眼相邻虚拟节点的哈希值就清楚了：

朴素 FNV-1a：  A#0 =1416880759   A#1 =1400103140   Δ = -16777619
               A#2 =1450435997   Δ = +50332857     A#3  Δ = -16777619
               A#4  Δ = -83888095                  A#5  Δ = -16777619
               → 相邻差恒为 16777619 的整数倍（-1×、+3×、-5× 轮转）

🚨 末尾字符只被异或、然后乘一次质数，A#0…A#999 就落成了一串步长约 2²⁴ 的等差格点，而不是撒在环上。1000 个虚拟点实际只占到 108 个不同格点 （最后一列），v=10 时更极端：十个副本全叠在同一个格子上，与 v=1 完全等价 —— 这正是朴素版 v=1 到 v=10 几乎没有改善（77.7% → 73.0%）的原因。

⭐ 判据：v 加十倍，均衡度没按 √10 ≈ 3.2 倍改善，先怀疑哈希而不是怀疑虚拟节点。 最省事的自测是数一下「v 个虚拟点落在几个不同的位置上」，不够 v 个就说明哈希在结块。

📌 布隆过滤器那一篇撞上的是同一个坑的另一面：那里的 k 个哈希靠 种子 ^ i 区分，结果 k 个位置的奇偶被锁死，误判率系统性高出一到两成。同一个弱点，一个表现为负载不均，一个表现为误判偏高。

⚠️ 一个容易读反的现象

回头看迁移表：vnode=1 的中位数只有 12.5%，vnode=150 却要迁移 16.6% —— 虚拟节点越多，迁移越多？ 看起来像是虚拟节点有害。

不是。把 vnode=1 那一组加入 F 前后的负载列出来就清楚了：

加 F 前   A=50423  B=30518  C=94049  D=10318  E=14692
加 F 后   A=50423  B=26993  C=94049  D=10318  E=14692  F=3525

⭐ F 只从 B 手里抢走了 1.8%，别的节点纹丝不动 —— 因为环上只有一个 F 点，它只能从顺时针方向的那一个邻居手里抢。而它应得的份额是 1/6 ≈ 16.7%。

📌 所以：vnode=1 迁移量小，是「新节点没分到应得的份额」的症状，不是优点。 vnode=150 迁移 16.6%、恰好落在理论下界 16.7% 上，那才是正常工作的样子。

🚨 这类「指标变好其实是坏事」的情况，只看单一数字必然读反 —— 得把它和「新节点最终承担了多少」放在一起看。这两个数在一致性哈希里是同一个数：迁移过去的 key 就是新节点最终持有的全部。

面试怎么答

「缓存集群扩容怎么办」这类题，一个完整回答是四层：

问题：取模法扩容要迁移 1-1/N，实测 5→6 台是 83.3%，缓存几乎全失效
环：节点与 key 映射到同一个哈希空间，顺时针归属；加删节点只影响相邻区间
保证：老节点之间迁移恒为 0 —— 迁移量恰好等于「新节点应得的」或「删除节点原有的」
虚拟节点：5 个点时最大/最小是 15.8 倍（中位数），加到 150 个副本压到 1.2 倍；不均衡度按 √((n-1)/(nv+1)) 下降，取 100~200 是成本与收益的折中

⚠️ 第 4 点是分水岭。只答「用一致性哈希」而不提虚拟节点的话，面试官通常会追问「那负载不均怎么办」—— 因为不加虚拟节点的一致性哈希在真实集群里基本不能用。

📌 还想再加一层的话，说第 5 点：虚拟节点的前提是哈希对 节点名#序号 这种短相似串有雪崩性。用朴素 FNV-1a 之类的弱哈希，副本会叠在同一个格点上，加多少个都没用 —— 这是个真实踩过的坑，比背公式更能证明动过手。

⚠️ 关于配套题

同样地，力扣上没有一致性哈希的题。下面那一道是思路上的近亲（都是「加一个间接层，把昂贵的整体重排换成局部调整」），不是同类题。 📌 这一篇真正的练习是自己实现一遍再量一次：把上面那些表的数字跑出来，比做十道题记得牢。⭐ 量的时候记住两件事 —— 换几组节点名再报数（一组只是一次抽样）， 把结果和 √((n-1)/(nv+1)) 对一下（对不上就是哈希的问题）。

下一步

前三篇换的都是空间或结构上的确定性。最后一篇的限流器换的是时间上的：用 O(1) 的状态近似出一条速率曲线，而不是精确记录每一次请求。

练习

勾选记录做过哪些，0 / 1 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

1381. 设计一个支持增量操作的栈中等⚠️ 看似要遍历，其实把增量记在边界上就行 —— 和虚拟节点一样是「用间接层换均摊」

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。