Cloudflare 优化一致性哈希：负载均衡内存省超 100 TB

Cloudflare 近日发文，披露其内部负载均衡服务的内存占用已减少逾 100 TB。做法是改造 pingora-ketama 中一致性哈希的 Rust 实现：压缩哈希环条目，同时借助对哈希分布与碰撞率的统计分析，把每台后端服务器上的哈希数量削减约 90%，负载均衡的准确性并未因此打折。

在 Pingora 的后端路由里，可缓存请求要靠一致性哈希分到多台服务器上。系统要支持加权服务器，还要应付不同的功能组合，于是得维护大量哈希环，内存开销随之水涨船高。团队追查后确认，问题出在 pingora-ketama 这套一致性哈希数据结构上，随后着手研究并优化它的设计。

他们把概率论搬进一致性哈希，算出满足分布要求所需的最少哈希点数。这样一来，分布效果能维持预期，哈希结构的规模却可以大幅收缩。

误差每降一个数量级，每服务器哈希数量（几乎）就要多一个数量级。继续加哈希，换来的收益越来越小。

哈希数量增加，对负载分布的改善呈边际递减：最后新增的 90000 个哈希，只把误差改善了 0.7%。团队据此把单台服务器的哈希数量减少了 90%。生日悖论描述的是随机取值集合中碰撞概率远超直觉的现象，它同时解释了另一件事——32 位哈希点越多，碰撞概率越高，额外的分布误差也就跟着来了。

存储剩余哈希值的 Rust 数据结构同样被动了刀：原有实现用的是 8 字节的Point结构体，可哈希值和服务器索引其实只要 6 字节就放得下，内存又省了一截。Guthrie、Iurchenko、Abd Al Hadi 和 Babrou 补充道：

还有一层麻烦：哈希环一改，部分可缓存请求的路由目标就会变。新哈希环效果再好，一次性切换整个网络，几乎所有缓存内容都会失效。内存优化反倒可能让回源流量暴涨，后果不堪设想。

新实现采取逐步推广的方式，与现有哈希环并行运行，以此压住缓存抖动，避免回源流量出现尖峰。

在 Hacker News 和 Reddit 的热门讨论帖里，不少开发者争论：一致性哈希明明有开销，为什么依然有用？它和请求哈希又差在哪？用户 Teanut 写道：

看到在大规模场景下微小的改变能产生什么效果，这很有意思。很好地运用了数学来论证这些改变。

这并非 Cloudflare 头一回做大范围内存优化。今年 8 月，该公司就介绍过 DNS 团队如何通过一系列数据结构优化，压低 DNS 缓存的内存占用。