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

Cloudflare 的规模到底有多大？在这里工作多年，我依然觉得不太真实。我们在全球有数千台服务器，PB 级内存、数百万 CPU 核心，而且全部跑在极限上。资源看着多，终究有限，而当每个节点都要跑所有服务时，就没有浪费的空间。在这个量级上，任何小改进都会被放大，所以哪怕一次只优化 1% 也值得庆祝。有些调整带来的收益远不止于此：本文要讲的，就是对一个算法做的小改动，如何大幅降低我们某个基于 Pingora 的服务的内存占用。这让我们在全球范围内回收了超过 100TB 内存，而上个月 DNS 团队才刚刚省下 100TB。

不浪费

在团队之间维持公平的资源分配并不容易，组织越大越难。Cloudflare 靠 Performance 团队的不懈努力来维持这种平衡。故事始于 Ivan 提的一个工单：Pingora Backend Router 中 pingora-ketama 内存占用过高。问题在于，我们的内部负载均衡服务 Pingora Backend Router（没错，PBR）用的内存远超预期，具体出在与 pingora-ketama 相关的数据结构上——那是我们处理一致性哈希的开源库。要讲清楚我们怎么解决这个内存占用过高的问题，得先说明一致性哈希是什么、PBR 为什么要用它，以及它是怎么变得这么吃内存的。顺带还会聊点 Rust，甚至一点数学。

一致性哈希

一致性哈希是一种广泛使用的任务分配方法，把任务分散到多台服务器上，增删服务器时不需要大规模改动。我们在内部用它按 URL 把可缓存的请求路由到服务器，这样每个数据中心只需存一份文件副本，同时能稳定地找到每个文件的位置。我们之前多次介绍过这套系统，不过还是花点时间走一遍这个算法的用途和原理。一致性哈希的关键在于：哈希函数能接受任意输入，输出却只有一个无符号整数（32、64 或 128 位，取决于用哪个哈希函数）。这让我们能以_一致_的方式把任务和服务器关联起来。大多数讲一致性哈希的资料会让你把输出空间想象成一个连续的环，从最大值绕回零。这种画法可视化效果不错，但也会让整数区间这个简单概念显得比实际复杂。本文中，我们把哈希函数的 32 位输出表示为一条数轴。

BLOG-3083 2.png

假设我们有一组服务器 A、B、C，以及一组任务 t–z。根据各自代表值的哈希，我们可以把它们映射到数轴上——服务器用 IP 地址，任务用缓存键。

BLOG-3083 3.png

把任务分配给服务器，就变成了找每个任务左侧的第一个服务器。我们可以把每个服务器对应的哈希区间涂上颜色，直观地表示出来。注意服务器 C 覆盖的区间绕回到了开头，所以才有哈希分布在一个环上的说法。

BLOG-3083 4.png

就这么简单。从最基本的层面来说，一致性哈希就是这么回事——但用不了多久就能看出还有改进空间。注意例子中服务器 A 覆盖的区间明显比 B 和 C 都大。这是个问题，因为一个服务器处理的请求比例正比于它在数轴上区间的大小。理想情况下，我们希望保证每个服务器的区间大小相等，但哈希本质上就是随机数，所以只能从_统计学_的角度来讨论区间大小。😨

数学与后果

首先：别慌。我保证我不会骗你，而且我们讨论的内容不会超出一节入门概率课的范围。谈到统计分布，有两个重要概念能帮我们有效地量化不确定性：期望值和标准差。用（过度）简化的说法，期望值给出基于某个分布的测量值会聚集的中心点，标准差则说明大多数测量值离这个中心点有多近。

对于一致性哈希，我们可以针对 N 台服务器中某一台所对应区间的占比，计算出以下指标。（这个公式的来历稍后再讲。）

 Exp = (1)/(N) 

 SD = (1)/(N)√((N-1)/(N+1))

代入具体数字，假设有 100 台服务器。上面的公式给出：

Exp=1/100 = 1% 

 SD= (1)/(100)√((100-1)/(100+1)) ≈ 0.99%

也就是说，每台服务器负责的区间会以总范围的 0.99% 为中心，多数区间的长度会落在期望值上下 1% 的范围内。这_听上去_不错，但别忘了这是_总长度_的 0.99%。我们得用标准差除以期望值，才能看出误差相对于目标大小究竟占多大比例。这个值叫做变异系数。

CV = (SD)/(Exp) = √((N-1)/(N+1))

当 N=100, CV ≈ 99% 时——意味着有些服务器很可能要干比应干的多 99% 的活（处理两倍的请求），而另一些几乎什么都不用做！现在我们有了预测一致性哈希下服务器负载均衡程度的方法，就可以着手改进了。

多加几个哈希会怎样？

一致性哈希的简单是一把双刃剑。它容易理解和实现，因为一切都变成了同一条数轴上易于对应的哈希值，但任何改进也必须能对应到这条数轴上。这意味着，一致性哈希的任何问题，解法都只能是_更多的哈希_。它不太像金锤子（拿着它看什么都像钉子），倒更像一根金_钉子_，能把所有工具都变成锤子。

要解决负载不均的问题，我们可以给每台服务器加多个哈希，而不是只用一个。背后的数学稍后再说，但直觉上应该说得通：单个区间的标准差虽然大，把一堆区间加起来，总大小就会趋于平均。拿上面图里的三服务器例子，给每台服务器再随机加两个哈希，就能看到每台服务器的负载变得更均衡了。

BLOG-3083 5.png

这个例子确实有些刻意。系统的随机性意味着，每台服务器多加 2 个哈希值能带来多少改善并无保证，但把更多这样的哈希段组合在一起会让分布更均匀，这一点在直觉上说得通。求和中的每一段都有机会平衡另一段。可能有一段太短，也可能有一段太长。大数定律说的基本就是这个……显而易见的问题是，它只在大数下成立。在 NGINX 中，每台服务器的哈希数基线硬编码为 160，Pingora 使用的默认值与之相同。数学推导这里先略过，但回到前面 100 台服务器的例子：如果每台服务器用 160 个点而不是 1 个，变异系数（可以把它理解为误差范围）会从约 99% 降到约 8%，改善相当明显。

多加一些哈希值会怎样？

上面我们看到，按固定数量增加每台服务器的哈希数，可以让工作负载在服务器之间分布得更均匀。但如果我们_并不_想让负载均匀分布呢？在 Cloudflare 的场景里，有些服务器的存储空间比其他的大，那么让分配给某台服务器的请求数与其磁盘空间成正比会更好。实现这一点的方法之一是 ketama 算法。这个名字有点意思，因为算法是以最早实现它的那个库命名的，而那个库的名字……你可以自己去搜 😶‍🌫️。

整个算法归结起来就是：对于任意两台服务器 S_1 和 S_2，如果我们希望 S_1 处理的请求数是 S_2 的 w× 倍，那么与 S_1 关联的哈希数需要满足 H_1 = w× H_2。这样我们就能为每台服务器设置一个“权重”，用它来缩放与该服务器关联的哈希数。可惜这并不能替代上一节里加的那个固定缩放系数。那个缩放必须保留，用来设定误差范围的下限——这一点会在权重最低的那些服务器上体现出来。

对我们来说，既然希望工作负载能随存储规模伸缩，那就可以拿磁盘空间当权重——这正是 Pingora 团队多年来一直在做的事。公司里其他计算密集型的工作负载，权重则可能按 CPU 或 GPU 数量来定。

要是再加更多哈希呢？？？

最后一个要解决的问题是：到目前为止，我们都假设任何服务器都能处理任何请求，但现实中并非如此。合规要求、启用的缓存特性等因素，意味着只有一部分服务器能处理某个特定请求。麻烦的是，这次没法像之前那样靠往同一个环上加更多哈希来解决。我们必须新增完全_独立_的环，而且不止如此——每一种特性_组合_都可能需要自己专属的环！

按组合做复制，是典型的指数爆炸配方。在我们的场景里，几种不同的特性就会带来 2^handful = dozens 个彼此独立的一致性哈希环。所以你可能已经猜到了，Ivan 发现的“内存占用过高”（某些情况下高达 6GB），正是因为要容纳我们所需的全部功能，哈希数量极其庞大，而且必须常驻内存。那该怎么办？

存储优化

一大改进来自 Zaidoon，他对 PBR 中存储哈希的 struct 有了新的想法。那个 struct 长这样：

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

在内存中它占八个字节，其中四个给哈希（这部分省不掉），另外四个给一个索引，指向存在另一个数组里的服务器。Zaidoon 的洞察是：用 32 位整数存这个索引太浪费了，因为 PBR 不太可能同时协调超过 2^16 ≈ 65k 台服务器，16 位整数就够用。于是可以把上面的 struct 换成这个：

struct PointV2 {
 hash: u32,
 index: u16,
}

可惜 Rust 没那么好说话。像上面那样改索引大小，并不会减少内存占用。因为 Rust 有对齐规则，要求结构体在内存中的大小必须是其最大（也就是“对齐要求最高”）字段的整数倍。这里哈希最大，占四个字节，所以存到内存里时，一个 Point 的大小必须是 N × 4，最小也就是八个字节。

好在有成熟的绕行方案。你（其实是我）可能会想用 #[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())
 }
}

这个简单（ albeit 啰嗦）的改动，把一致性哈希占用的内存一举减少了 25%！想再进一步，就得回到数学里去了，各位抓稳扶手，这是最后一段冲刺。

如果少用一些哈希呢？

你可能已经注意到，我们给出的标准差公式只适用于每台服务器只有一个哈希的情况。推导每台服务器有 k 个哈希时的公式并不容易，大多数资料只给近似值或渐近极限，但我们不给。我算不上统计学家，但我是被一位微积分老师带大的（妈，你好！），我想知道那个_真正_的值。完整推导放在一篇补充文章里，这里只给出结果。

Exp_k = (1)/(N),

 SD_k=√(((k+1))/(N(kN+1))-(1)/(N^2))

要看增加哈希数量如何提升精度，得再看一眼变异系数。

CV_k=(SD_k)/(Exp_k)=√((N-1)/((N*k+1)))

把 CV_k 画出来，就能看到“多加哈希就行”这种思路的潜在问题（除了吃内存之外）。

BLOG-3083 6.png

可以看到，误差每下降一档，每台服务器的哈希数量几乎就要增加一个数量级，所以哈希加得越多，收益越小。回想一下，我们用的是以 160 为基数、按服务器存储容量缩放的哈希数。为方便计算，假设某台服务器的权重系数 m_w 是 625，于是 k = 160×625 = 100,000。从上图可以看出，最后加的那 90,000 个哈希只换来区区 0.7% 的误差下降。而更糟的还在后面。

我那个漂亮数学的预测，只有在把哈希想成一个连续环时才成立，但实践中哈希用的是 32 位数字，存在碰撞的可能，而且随着哈希数量增加，碰撞概率上升得出奇地快（参见生日悖论）。碰撞之所以要紧，是因为在理想情况下，每个哈希都会影响对应服务器所处理请求的量和分布，而一旦碰撞，某些贡献就会被随机丢弃，引入不可预测的误差。把使用 32 位哈希的模拟结果与预测误差率对比，可以看到对于拥有 2048 台服务器的数据中心，误差率在每台服务器 10,000 到 100,000 个哈希之间开始上升。

BLOG-3083 7.png

说到底，虽然这个认识让人有点不爽，但对我们回收一部分 RAM 的计划来说却是好消息。既然有了数学支撑，我们确定可以把每台服务器生成的哈希数量减少 90% 而不会带来明显的误差，于是就这么做了。

迁移，但别把源站打爆

还有一个问题：改变哈希环会改变部分可缓存请求的去向。即便新环更好，一次性切换整个网络也几乎会让所有缓存内容失效，把一次内存优化变成源站流量的灾难性增长。

所以我们没有做一次全局切换。有一段时间，PBR 在内存中同时保留了两版可缓存负载均衡器：旧的 ketama 环和新的小环。每个请求都通过常规的迁移框架来决定由哪个环选择后端。这样一来，上线决策对每个请求哈希是稳定的，也给了我们一条干净的回滚路径。一旦发现异常，我们可以让新请求重新走旧环，而不必重新部署 PBR。

接下来，我们分层推进迁移：先在小范围验证点试点，再逐步扩展到更多数据中心，最后才推向全球其他地区。

关键在于，我们独立控制了两个维度：有多少流量使用新的环，以及这些流量被允许迁移到哪里。如果只是按全球百分比一刀切地推进，缓存抖动会同时扩散到所有地方；而按数据中心范围推进，则能把影响范围控制得很小，也更容易判断一项改动是否真的安全。

迁移期间，我们持续观察后端选择 trace、环版本计数器、PBR 连接错误、进程内存、启动时间、缓存行为以及回源流量。迁移达到 100% 后，我们移除了临时的旧环路径，大功告成！

BLOG-3083 8.png

上图对比了变更当周 PBR 使用的内存与几周前的数据，以及两者相减的结果。那个陡降对应的是带有大型（现已不再使用）哈希环的 PBR 版本被永久下线的日子。看差值，我们得到了一个令人满意的结果：这些改动让使用的内存减少了 100TB！

BLOG-3083 9.png

自己试试

本文讨论的所有改动现在都可以在 pingora-ketama crate 中使用，形式是一个（目前）尚未公开宣传的 cargo feature。v2 环采用了紧凑的存储格式、更快的排序方法，并且能够调整每个节点的基础哈希数量。我们在做这些改动时必须以稳定性和可控性为重，因此 v1 环与 pingora ketama 一直以来的实现完全一致，而该库也支持同时运行两者，并按请求逐个决定使用哪一个以及何时使用。

除了亲手改我们的一致性哈希实现，我更希望你能从中得到一点启发：回头翻一翻自己的系统，看看哪些“简单”或“显而易见”的决定，其实藏着可观的收益——前提是你愿意认真算一算数字。你未必能用 Rust 解决所有问题，但数学是通用的。

不浪费