Java 实现一致性哈希实测：40 万键下的 90.9% 增员迁移、4194 万点位理论失准与 9.5 倍环内存差

分布式

解决什么问题：把「一致性哈希」这个词后面藏着的三个工程决策——要不要环、每节点铺多少个虚拟点位、点位在内存里怎么放——变成六个可以自己复跑的数字：成员变更迁移率、CV 理论对拍、碰撞失准点、每点位字节、查找分位与构建耗时，外加两个实验台返工的完整因果链。

适合谁读：维护或正要维护分片路由、缓存集群、负载均衡表的 Java 后端；被问到「虚拟节点为什么是 160」只会背定义的人；以及任何准备对「显然正确」的默认参数动手之前，想知道怎么先算一笔账的人。

能收获什么：一份 40 万键、三组集群规模、最高 4194 万点位的实测数据；一条「取模分片加删都要搬九成」的硬证据；一个 CV 随点位数失准的实测拐点；一笔 TreeMap 80.1 字节对打包数组 8.4 字节的内存账；两个「数字对不上先怀疑实验台」的返工实录。

把时间锚一下：2026 年 9 月 18 日，Cloudflare 发布复盘，工程师从一张「pingora-ketama 内存占用异常」的工单出发，最终从全球负载均衡服务里回收了超过 100TB 内存；复盘里的关键事实包括：每服务器默认 160 个哈希点（承自 NGINX ketama）、负载波动率随点位数按平方根衰减、团队据此把每台服务器的哈希数量砍掉约 90%、并把每个点位从 8 字节手工打包压到 6 字节——以上为 Cloudflare 官方博客内容，我经 InfoQ 10 月底趋势榜收录与网易科技 10 月 24 日中文转述核实，原文细节以官方博客为准。10 月最后两天，这篇复盘和 DNS 缓存省下另一个 100TB 的文章还同时挂在 InfoQ 热门榜上——一致性哈希在超大规模下的真实成本，仍是这个月工程师们争论的话题。

争论里最常出现的一句是「一致性哈希到底贵在哪、值不值」。与其转述，我决定在本机把它拆开量一遍：40 万个键、3/10/30 三组集群规模、每节点 1 到 81920 个点位、三种内存形态，全部交给一个自包含的纯 JDK 程序跑出来。下面所有数字都是这台 Windows 11 机器上真实运行的输出，三次复跑的统计列逐位一致；先钉环境口径。

一、先把环境口径钉死：所有数字都从这台机器上来

先说清楚这篇的实验口径，免得你拿自己环境对不上来质疑结论。所有数据来自我本机一次纯 JDK 实验（单文件，无任何第三方依赖），程序自己打印环境与结果，三次复跑的统计列逐位一致。命令与判定标准在第九节给全。

哪些数字换环境会变：第九节判定标准里，P1 的迁移率、P2/P3 的波动率与碰撞数、P4 的每点字节数由确定性算法加固定键空间决定，应当逐位复现；P4 的毫秒与纳秒列是本机性能采样，换任何机器都会变，只看量级。下面进入正题。

二、问题定义：扩容那天，你的缓存键有多少要搬家

分片路由做的事只有一件：把一个键映射到一个物理节点。工程里最常见的两种写法，一是取模分片，owner = hash(key) % N；二是一致性哈希环，把节点和键都散列到 32 位整数环上，键归属顺时针遇到的第一个节点点位。

衡量它们的指标是迁移率：成员变更（扩容一个节点、摘除一个节点）前后，owner 发生变化的键的占比。它为什么值这么多钱：缓存场景里，迁移率 90% 意味着一次扩容等于全量回源，源站流量瞬间放大一个数量级；会话粘滞场景里，等于全量用户被踢下线重登。

取模分片有个反直觉的数学事实。加一个节点（N 变 N+1）时，一个键能留下的条件是 h % (N+1) == h % N，也就是 h 模 N(N+1) 的余数恰好小于 N，概率只有 1/(N+1)——N=10 时九成的键都要搬家。摘除中间节点更糟：多数实现里节点按数组下标编号，摘掉一个，后面所有节点的编号整体前移，等价于一次全量重映射。这两条推导，第三节用 40 万个真实的键验证。

三、40 万键实测：取模分片加删都要搬九成，环把它压回 1/N

实验设计：40 万个键分别用取模分片和 160 点位的一致性环分配，基线集群 N ∈ {3, 10, 30}，然后各做一次「追加 node-N」和「摘除中间那个节点」，统计 owner 变化的键数。环的查找正确性先用线性扫描逐键对拍（10000/10000 一致）才开跑。

两个值得停一停的地方。第一，取模分片加和摘都要搬九成左右——「摘一个只搬 1/N」的直觉对取模分片不成立，因为摘除导致下标重排，这在 10 节点时是 90.01% 的实测迁移。第二，环的两个方向都落在 1/N 附近：N=10 加节点迁 9.34%（理论 1/11 = 9.09%），摘节点迁 9.53%（被摘节点的实际份额，理论 1/10，偏差来自节点份额本身的 ±8% 波动）。N=3 时环摘节点迁 36.28% 而不是 33.3%，同样是份额波动，不是误差。

所以第一条可带走的判断在这里就成立了：扩容成本是架构选出来的，不是调出来的。键到节点之间隔不隔一个环，决定了那天晚上是搬 9% 还是搬 90%。

四、160 这个默认值不是玄学：CV 理论曲线与实测逐点对拍

环的均衡度用变异系数 CV（各节点份额的标准差除以均值）度量。份额怎么算：把排序后的环看成一组首尾相接的区间，每个节点分到的区间总长除以 2^32 就是它的份额——键均匀时这就是它的流量占比。Cloudflare 在 2026-09-18 的复盘里给出过每节点 k 个点位的 CV 精确表达式 CV_k = sqrt((N-1)/(N·k+1))，我按这个公式在本机逐点对拍：

三个解读。一，k=1 时实测 CV 99.67%，和理论 99.01% 对上——单点位环等于把流量随机扔给节点，这行数字验证了实验台本身。二，160 把 CV 压到 7%~8%，最富节点拿 1.25 倍均值：10 个节点时意味着有的机器比别的忙四分之一。这个数是从 NGINX 的 ketama 默认值一路继承下来的（转述自 Cloudflare 复盘），实测说明它确实把不均衡压进了可用区间。三，实测围绕理论的偏差在 ±10% 以内——CV 是期望值，单次实现有抽样噪声，这张表没有做多次平均，偏差方向不固定属正常。

核心代码不长，这是环的构建与查找（打包、排序、二分）：

// 点位打包：高 32 位 = 无符号哈希异或 0x80000000（符号偏置），
// 低 32 位 = 节点 id。偏置让 Arrays.sort 的带符号 long 序等价于无符号哈希序
static long pack(int hash, int id) {
return (((hash ^ Integer.MIN_VALUE) & 0xFFFFFFFFL) << 32) | (id & 0xFFFFFFFFL);
}
static long pHashU(long p) { return ((p >>> 32) ^ 0x80000000L); }
static int pId(long p) { return (int) p; }

static long[] buildRing(List<String> nodes, int k) throws Exception {
int n = nodes.size();
long[] ring = new long[n * k];
// 并行生成：节点 i 的第 j 个点位 = md5(name + "-" + j) 前 4 字节
// ……（并行填充略，见第九节完整源码）……
Arrays.sort(ring);
return ring;
}

/** 第一个无符号哈希 >= 键哈希的点位；越过环尾回绕到 0 */
static int lookup(long[] ring, int hash) {
long key = hash & 0xFFFFFFFFL;
int lo = 0, hi = ring.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (pHashU(ring[mid]) >= key) hi = mid; else lo = mid + 1;
}
if (lo == ring.length) lo = 0;
return pId(ring[lo]);
}

五、继续加点开始失准：4194 万点位处，实测高出理论 27%

把规模推到 N=512、k 最高 81920（总点位 4194 万）后，曲线形状变了。32 位哈希空间只有 42.9 亿个格子，点位越铺越密，两个节点撞在同一个哈希值上的概率按平方涨——生日悖论。碰撞的后果是两个点位重叠、区间语义错位，均衡度开始偏离理论。

两个证据藏在拆解维度里。其一，碰撞数对拍：n 个 32 位随机点的碰撞期望约为 n²/2^33，n=4194 万时代入是 20.4 万，实测 204,393——公式没骗人，碰撞确实是平方级的。其二，边际收益坍塌：从 k=40960 翻倍到 81920，内存翻倍，理论 CV 应降 29.3%（0.494%→0.349%），实测只降 8.5%（0.486%→0.444%）——最后一个翻倍只兑现了理论收益的 29%，实测对理论的偏离从前一格的 -1.6% 恶化到 +27.3%。

Cloudflare 的复盘走得更远：他们在 2048 节点、密度更高的配置里测到了 CV 随加点绝对回升的反向劣化，于是把每服务器点位砍掉约 90%（转述）。本机 512 节点装不下那个密度，只复现到「失准」这一步就到了内存边界——这是本文与该复盘的差距，先说明白，第八节还会收一遍。

六、环的内存账：同样 4194 万个点，TreeMap 要 3.36GB，打包数组 336MB

均衡度只是环的一半故事，另一半是环本身放在内存里的形态。教科书实现用 TreeMap<Long, Integer> 存点位，工程实现（含 Cloudflare 的做法）把它压成连续数组。我按 GC 前后差值法实测了 100 万点位三种结构的每点成本：

TreeMap 的 80.1 字节是这么堆出来的：每个 Entry 自带对象头、key/value 两个引用、左右子树加父节点三个指针、颜色标记，外加 key 装箱出来的一个 Long 对象。数组结构的 8.4 字节里没有这些东西。查找延迟有个反直觉细节：p50 上 TreeMap 反而更快（27ns 对 50ns，树顶几层常驻缓存），但 p99 差 2.3 倍（251 对 107ns），构建差 15.7 倍——高频路径上，数组结构的优势全在尾部延迟和重建速度上。

按实测单价外推到第五节那张 4194 万点位的环：TreeMap 形态 3.36GB，打包数组 336MB。同一个环，两种写法，10 倍内存。Cloudflare 从全球数千台机器的同类结构里回收 100TB 内存、把每个点位从 8 字节手工压到 6 字节省 25%（转述），乘数逻辑和这张表是同一件事：点位形态是结构选择，结构选择是内存定价。

七、两次返工实录：数字对不上时，先怀疑实验台

这组数据不是一次跑对的。两次返工都值得写下来，因为它们的症状都不是「报错」，而是「出数字」——出了数字你才会去信它。

返工一：CV 飞到 3200%，自检 9758/10000。完整因果链：Arrays.sort 按带符号 long 排序 → 打包点的高 32 位是无符号哈希，凡是 ≥2^31 的点位最高位是 1，被当成负数排到了数组开头 → 环在 2^31 处断成两截，每截内部有序、两截之间乱序 → shares() 沿「排序数组」算区间长，跨界处算出负长度，个别节点吞下半个环 → CV 飞到 3200%；二分查找在断点附近返回错误后继，1 万次对拍失配 242 次。修复：打包前对哈希做 hash ^ 0x80000000 符号偏置（无符号序映射为带符号序），取哈希时异或回来。修复后自检 10000/10000，CV 回到理论附近。

返工二：N=30 摘节点测出 50.2% 迁移，理论只有 3.3%。因果链：buildRing 按列表下标给节点编号 → 摘除中间节点后，其余节点的下标整体减一 → 迁移比对用的是「下标是否变化」→ 尾部 15 个节点（占 46.7% 的键）被误判成迁移 → 50.2% ≈ 46.7% + 真实的 3.3%。修复：按节点名字符串比对物理身份，而不是下标。修复后 3.79%，回到 1/30 加噪声的位置。

两条共同的教训：50.2% 这个数字自己就在招供——它恰好等于「尾部节点份额加 1/N」，看见这种「可疑地接近某个可解释组合」的数字，先去实验台找结构性错误，而不是给真实现象编故事。以及：任何「排序后数组」的结论，先问一句按什么序排的。

八、适用边界与风险提示

先把成立范围说清楚，免得结论被带出实验室。

1. 本文全部结论在单机进程内成立，键到节点的映射是纯内存计算；不涉及跨机房网络拓扑、副本放置、以及有界负载（bounded-load）的动态再平衡——后者是 Cloudflare 新方案的另一半，本文未实验。

2. 哈希函数只测了 MD5 截断 32 位（ketama 同款）。murmur3、xxHash 等更快哈希的分布质量与碰撞率未对拍；MD5 在这里只承担「散列均匀」职责，不涉及密码学安全语义。

3. P4 的每点字节用 GC 差值法（3 次 System.gc 栅栏取差）估算，受 JVM 对象布局与版本影响，换 JDK 版本会漂移；查找延迟用 100 批 × 1 万次的批均法——Windows 上 nanoTime 粒度约 100ns，单次计时的 p50 会全部塌成 0，这个坑我踩过才改的。

4. 没做的实验：异构权重节点的份额曲线、点位命名策略对碰撞的影响、多次抽样平均后的 CV 置信区间、以及 Cloudflare 尺度（2048 节点）下 CV 绝对回升的复现——本机内存只够到 4194 万点位。以上都属于方向提示，不是结论。

5. 实验为纯计算负载，未修改任何系统配置、证书或网络设置；复现只需一个 JDK 与一条命令。

6. AI 辅助说明：实验代码在本机编译运行，文中所有数字取自程序实际输出文件（三次复跑统计列一致）；文字由 AI 辅助整理，两次返工过程如实收录在第七节。

九、复现命令与判定标准

完整源码是一个自包含的 ConsistentHashLab.java（380 行，含 P0 环境打印、P1 迁移矩阵、P2 CV 曲线、P3 碰撞密度、P4 内存与查找五个阶段，输出为 LABEL|key=value 行）。核心流程三步：

# 1. 编译（JDK 17 测过；无需任何依赖）
javac -encoding UTF-8 ConsistentHashLab.java

# 2. 连跑三次（-Xmx4g：P3 的 4194 万点位需要约 700MB 堆峰值）
for i in 1 2 3; do java -Xms2g -Xmx4g ConsistentHashLab > run$i.txt 2>&1; done

# 3. 复跑一致性：忽略耗时列后三次输出应完全一致
# （把 gen_sort_ms、毫秒/纳秒列剔除后 diff，应为空）

判定标准，按顺序核对：

① 正确性：输出含 P1|ring_self_check=10000/10000，环查找与线性扫描逐键一致；否则先查排序序与打包偏置（第七节返工一）。

② 确定性：P1 的 12 行迁移数、P2/P3 的 cv 与 collisions 列、P4 的字节数三跑逐位一致；不一致说明键空间或点位哈希变了。

③ 锚点值：P1 N=10 加节点取模 90.92%、环 9.34%；P2 k=1 实测 CV 99.67%、k=160 实测 7.21%；P3 k=81920 碰撞 204,393、实测 CV 0.4443%（这两项由 MD5 确定性决定，应精确复现）；P4 每点字节 TreeMap 约 80、long[] 约 8.4。任何一项对不上，先怀疑实验台再怀疑结论。

十、结论：三句话和一个自检动作

第一，迁移率的分水岭在键与节点之间隔不隔一个环：取模分片加删都是九成迁移（90.92%/90.01%），160 点位的环把它压回 1/N（9.34%/9.53%）——这是架构差异，不是参数差异。

第二，虚拟节点数是拿内存买均衡，且这笔买卖有失准点：160 点把 CV 压到约 8%、最富节点 1.25 倍均值；继续翻倍收益按平方根衰减，4194 万点位处实测已高出理论 27%，最后一个翻倍只兑现 29% 的理论收益——加参数之前先算碰撞期望 n²/2^33。

第三，环的内存形态是结构选择问题：同 4194 万点位，TreeMap 3.36GB 对打包数组 336MB，10 倍差距，Cloudflare 的 100TB 就是这个乘数乘上机器数乘出来的。

给你一个具体的自检动作：今天就打开你项目里的分片实现（sharding、路由表、缓存定位都算），确认三件事——成员变更时迁移率是多少、每个节点铺了多少个虚拟点位、这些点位在内存里是对象还是数组。三个答案里如果有你不知道的，就是风险。

两个问题留给你：你现在的分片方案，上一次扩容实际搬了多少键，和本文哪个数字更接近？如果让你把环从 TreeMap 换成打包数组，你预计最大的阻力来自代码还是来自监控？

这篇值得收藏的原因：它把「一致性哈希」从名词拆成了六个可以自己复跑的数字——迁移率矩阵、CV 对拍、碰撞对拍、每点字节、查找分位、返工因果链，下次你做扩容评审或面试被问到「为什么是 160」时，直接把第九节的命令跑一遍就有底气。