后端Cloudflare数学性能

Cloudflare 只改了一个结构体和一个参数，回收了 100TB 内存

Pingora 的一致性哈希把内存吃到 6GB：功能组合让哈希环变成几十张，而每台服务器 10 万个哈希点在数学上早已收益递减。Cloudflare 用 u16 索引与 90% 的哈希裁剪省下 100TB RAM，并靠双环并行迁移避免缓存雪崩。

Cloudflare Blog4 分钟阅读

中文
中文日本語
复制
内存占用曲线在切换哈希环当天出现陡降的示意图

Cloudflare 的一篇技术博客讲了一件很“划算”的事：他们只改了一个算法里的存储结构和参数，就在全球范围回收了 100TB 内存——而且是紧接着 DNS 团队上个月省下的另外 100TB 之后。

起因是一张工单：Pingora Backend Router（PBR）——也就是 Cloudflare 内部的一致性哈希负载均衡服务——内存占用远超预期，个别情况下达到 6GB，占用大头是 pingora-ketama 里的结构。

先讲清一致性哈希为什么会失衡

哈希函数的输出是一个 32 位无符号整数，所以可以把服务器和任务都映射到同一条数轴上，然后把每个任务交给「它左边最近的服务器」处理。这也解释了为什么常把它画成一个环——哈希空间从最大值绕回零。

问题在于：因为哈希本质上是随机数，各服务器覆盖的区间长度是统计量。对 N 台服务器中的一台：

Exp = 1/N
SD  = (1/N) · √((N−1)/(N+1))

对 100 台服务器来说，覆盖比例的期望是 1%，标准差约 0.99%。但标准差是相对总长度的，要除以期望值才知道误差占目标大小的比例——也就是变异系数：

CV = √((N−1)/(N+1)) ≈ 99%

意思是：有些服务器可能承担了两倍的请求量，而另一些几乎闲着。

加哈希：有用，但有天花板

解法只有一个方向——加哈希：让每台服务器对应多个哈希点，各自的区间相加后趋于均衡（大数定律）。NGINX 把每台服务器的哈希数硬编码为 160，Pingora 沿用了同样的默认值；CV 从约 99% 降到约 8%。

如果不想平均分配，就用 ketama 算法给服务器加权：要让 S1 承担 w 倍于 S2 的请求，就让 H1 = w × H2。Cloudflare 用磁盘空间做权重（其他团队会用 CPU 或 GPU 数）。

但真正的麻烦来自功能组合：合规要求、缓存特性等意味着只有一部分服务器能处理某个请求，于是不能只在一张环上做取舍，而要为每一种特性组合建一张环——组合数是 2^特性数，很快就变成几十张环。这就是内存暴涨的根源。

20% 来自一个 u16

原来的结构体是：

struct Point {
    hash: u32,
    index: u32,
}

八字节：四个给哈希（省不掉），四个给指向服务器数组的索引。Zaidoon 的洞察是这个 32 位索引浪费了——PBR 同时协调的服务器几乎不可能超过 2^16 ≈ 65k 台，用 u16 就够。

但直接把索引改成 u16 不会省内存：Rust 的对齐规则要求结构体大小是最对齐字段（这里是 4 字节的哈希）的整数倍，所以最小还是 8 字节。作者没有用有争议的 #[repr(packed)]，而是把数据存成裸字节数组再配 getter：

struct Point([u8; 6]);

impl Point {
    fn hash(&self) -> u32 {
        u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
    }
    fn index(&self) -> u16 {
        u16::from_ne_bytes(self.0[4..6].try_into().unwrap())
    }
}

两种写法编译结果完全一样，而内存直接降了 25%。

剩下的大头来自数学

作者（顺便提到自己是被数学老师养大的）推导出了每台服务器有 k 个哈希时的精确标准差，而不是常见的近似式：

SD_k = √((k+1) / (N(kN+1)) − 1/N²)
CV_k = √((N−1) / (N·k+1))

把它画出来就暴露了「不停加哈希」的代价：误差每下降一档，需要的哈希数几乎要多一个数量级。按权重 625 计算，k = 160 × 625 = 100,000——而最后加进去的 90,000 个哈希，只换来 0.7% 的误差改善。

更糟的是碰撞：哈希是 32 位整数，哈希数量增加时碰撞概率按生日悖论上升，碰撞意味着某些贡献被随机丢弃，引入不可预测的误差。模拟显示，在 2048 台服务器的数据中心里，当每台服务器的哈希数处于 1 万到 10 万之间时，误差反而上升。

于是结论变得很清楚：他们可以把每台服务器生成的哈希数减少 90%，而不带来可感知的误差。

迁移才是最危险的部分

换环意味着可缓存请求的路由目标改变。一次性全网切换等于让几乎所有缓存失效，把一次内存优化变成对回源流量的末日级打击。

所以他们没有做「一次全局切换」：PBR 在一段时间内同时持有新旧两张环，每个请求由既有的迁移框架决定用哪张——这让决策按请求哈希保持稳定，也留出了干净的回滚路径（不用重新部署就能把新请求送回旧环）。

铺开时分了两层：先在少量验证机房，再到逐步扩大的数据中心分组，最后才推向全球。关键在于独立控制两个维度——多少流量用新环，以及这些流量允许迁移到哪里。普通的全局百分比灰度会把缓存抖动摊到所有地方，而按数据中心分批能把爆炸半径限制住。

迁移期间他们盯着后端选择轨迹、环版本计数、PBR 连接错误、进程内存、启动时间、缓存行为和回源流量。等 100% 迁移完成后，把临时的旧环路径删掉——内存曲线出现一个陡降，差值就是那 100TB。

你可以直接用

改动已经进入开源的 pingora-ketama crate，目前是一个没怎么宣传的 cargo feature：v2 环有紧凑的存储格式、更快的排序方式，以及可调整的基础哈希数。出于稳定性和可控性的考虑，v1 环与过去完全一致，并且库支持两者同时运行、逐请求决定用哪个。

作者最后那句总结挺好：

你可能没法用 Rust 解决所有问题，但数学是普适的。

来源: Cloudflare Blog← 返回首页