一致性哈希：加一台机器为什么不用重排所有键

分片的第一反应是 hash(key) % N。它均匀、简单，只有一个问题：N 变了几乎全部键都要搬家。从 4 台扩到 5 台，命中同一个下标的键只剩五分之一。

把哈希空间接成环

一致性哈希的做法：把 [0, 2^32) 首尾相接成环，机器与键都按哈希值落到环上，每个键归给它顺时针方向遇到的第一台机器。

加一台新机器时，只有落在「新机器」到「它逆时针方向前一台机器」之间的键需要迁移 —— 期望约 1/N。其余键的归属不变。

虚拟节点解决倾斜

只有几台机器时，它们在环上的位置是随机哈希出来的，分布会很不均（一台可能占了半个环）。标准解法是虚拟节点：每台物理机器在环上放 100–200 个点，键先归到虚拟节点，再映射回物理机器。

function buildRing(nodes, replicas = 120) {
  const points = [];
  for (const node of nodes) {
    for (let i = 0; i < replicas; i += 1) {
      points.push({ hash: hash32(node + '#' + i), node });
    }
  }
  points.sort((a, b) => a.hash - b.hash);
  return points;
}

function owner(points, key) {
  const h = hash32(key);
  let lo = 0;
  let hi = points.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (points[mid].hash < h) lo = mid + 1;
    else hi = mid;
  }
  return points[lo === points.length ? 0 : lo].node;
}

虚拟节点数越多越均匀，代价是环数组更大、构造更慢。120 是个常见的折中：分布的标准差已经够小，查找仍然是几次二分。

什么时候不该用它

• 数据是静态的：一次性分好就不再变，用 hash % N 或者干脆按大小排好再切，一致性哈希带来的迁移收益等于零，却多了虚拟节点与环的复杂度。
• 需要严格均匀：虚拟节点只是近似。要更简单的等价方案可以用 rendezvous hashing（对每个候选算 hash(key + node) 取最大），不需要维护环，也不需要虚拟节点，代价是每次要算 N 个哈希 —— N 小的时候更划算。

一致性哈希买的是「节点变动时的迁移量」，如果节点不会变，这笔钱就白花了。