一致性哈希

为什么取模在规模上会失效

使用 hash(key) % N 时，改变 N 会重新映射几乎所有键。缓存集群从四个节点扩到五个节点，大部分缓存会立即失效，可能压垮源站；分片数据库则必须迁移几乎所有行。一致性哈希把节点和键放在一个环上，键属于顺时针方向的下一个节点。新增节点只会接管其前驱到自身之间的弧段，其余键保持不动。

import { createHash } from 'node:crypto';

function position(value: string): number {
  const digest = createHash('sha256').update(value).digest();
  return digest.readUInt32BE(0);
}

function owner(key: string, nodes: string[]): string {
  const keyPos = position(key);
  const ring = nodes
    .map((node) => ({ node, pos: position(node) }))
    .sort((a, b) => a.pos - b.pos);
  return ring.find((entry) => entry.pos >= keyPos)?.node ?? ring[0].node;
}

这个最小实现没有虚拟节点，也没有副本。它只用于说明查找过程，不是生产实现。真实系统应使用经过验证的库，尤其是在成员并发变化时。

虚拟节点与均衡

一个物理节点在环上只有一个位置时，可能拥有过大或过小的弧段。虚拟节点为每个物理节点分配多个位置，从而平滑分布。代价是更多内存和略多的查找工作。要测量真实的键分布：均匀哈希并不保证均匀流量，因为有些键远比其他键更热。

成员变化仍然有成本

节点加入时要接管一段弧并加载或获取这些键。在这个窗口内，请求可能未命中缓存或仍被路由到旧节点。应规划预热期、为可用性复制键，并在小集群中避免同时迁移多个节点。节点移除时，其键必须由其他节点提供；如果没有副本，这些键就会丢失。

何时使用

当节点集合会变化，而重新映射所有键代价高昂或会造成中断时，使用一致性哈希。优点是迁移具有局部性；缺点是成员管理和再平衡更复杂。与集中式目录服务相比，它省去了查找服务，但失去了对放置位置的精细控制。