一致性哈希的数学：从大 O 到精确误差公式
来源: ch.terabyteoff.com — 2026-09-19
概述
这是 Cloudflare 那篇「用数学省下 100TB 内存」的配套数学文章，作者 Kevin Guthrie 把一致性哈希的负载分布误差从渐近上界推到精确公式。他抱怨搜索结果的两种极端：要么是晦涩的技术论文，要么是讲得通但推导不全的课程讲义，都只给出 O(√(1/k)) 这样的界，却看不出实际误差与这个界有多接近。结论是解这个问题只需要高中数学加一点创造力：N 台服务器、每台 k 个哈希时，误差为 √((N-1)/(kN+1))，在服务器数量超过 50 时与 √(1/k) 的偏差约 1%。文章还配了 WebAssembly 交互演示，并回答「各服务器哈希数不相同时会怎样」。
核心要点
- 推导的捷径是把哈希从 32 或 64 位整数换成 0 到 1 之间的实数，此时某台服务器承担的工作比例就等于分配给它的区间长度。
- 最终给出的误差公式是 Err_k = √((N-1)/(kN+1))，在 N 很大时非常接近粗略的 √(1/k)。
- 实践意义在于：服务器数量到 50 台以上时，实际误差与 √(1/k) 近似值的差距只有约 1%。
- 作者强调这个推导的价值不只是数值：「不看到它是怎么来的，就无法看出它还有哪些别的含义」，例如每台服务器哈希数不同时该怎么算。
- 文章同时是技术论文、演示和博客，用 WebAssembly 做交互式演示，让读者直接拖动参数观察区间大小如何偏离期望值。
金句
解这个问题所需要的，只是一点高中数学加一点点创造力。
👍 0
👎 0
← 返回 Lobsters 首页