Saving another 100TB of RAM with math (and Rust)

用数学（和 Rust）再节省 100TB 内存 | Cloudflare 博客

post

优化

性能

Pingora

Rust

深度解析

工程

开源

2026年9月18日

用数学（和 Rust）再节省 100TB 内存

Kevin Guthrie ,  Mariia Iurchenko ,  Zaidoon Abd Al Hadi ,  and Ivan Babrou

13 分钟阅读

复制链接

Cloudflare 的运营规模如此庞大，即使在这里工作多年，这种规模仍然显得不真实。我们拥有遍布全球的数千台服务器，配备 PB 级内存和数百万个 CPU 核心，所有资源都处于满负荷运行状态。尽管这些资源看起来非常庞大，但它们仍然是有限的，当需要每个服务都在每个节点上运行时，根本容不得任何浪费。

在这个规模下，微小的改进会被显著放大，因此即使是 1% 的逐步改进也值得庆祝。某些调整的累积效果更是显著：在本文中，我们将探讨对单一算法进行的小幅修改如何显著减少了基于 Pingora 的某项服务的内存占用。这使我们能够在全球范围内回收超过 100TB 内存，这在 DNS 团队上个月释放的 100TB 内存基础上更进一步。

避免浪费

在大型组织中维持团队间的资源公平分配并不容易。Cloudflare 通过性能团队的不懈努力来确保这种平衡。Â

这个故事始于 Ivan 提交的一张工单，他发现：Pingora 后端路由器中 pingora-ketama 的内存使用过高。调查发现，我们的内部负载均衡服务 Pingora 后端路由器（是的，PBR）使用的内存远超预期，尤其是在与 pingora-ketama 相关的结构中，而 pingora-ketama 是我们用于处理一致性哈希的开源库。

为了说明我们是如何解决这种看似过度的内存使用问题的，我们需要先解释一致性哈希到底是什么，为什么我们在 PBR 中使用它，以及它为何会占用如此多的内存。在这个过程中，我们还将学习一些 Rust 编程知识，甚至一点点数学。

一致性哈希

一致性哈希是一种广泛使用的分布式方法，它可以在添加或移除服务器时无需进行大规模调整即可将任务分配到多个服务器上。我们在内部使用它来通过 URL 将可缓存的请求路由到服务器，这使我们能够在每个数据中心只存储文件的一个副本，并提供一种稳定的方式来定位每个文件的位置。我们之前曾提到过这个系统，但让我们花点时间了解这个算法的使用方式和工作原理。

一致性哈希的核心概念在于，虽然哈希函数可以接受任何类型的输入，但其输出仅限于一个无符号整数（根据使用的哈希函数，可能是 32 位、64 位或 128 位整数）。这使我们能够以一致的方式将任务和服务器相互关联。大多数关于一致性哈希的讨论都会让你想象输出空间是一个连续的环形结构，从最大值环绕到零。这种描述虽然能产生一些直观的可视化效果，但也可能让简单的整数范围概念显得更加复杂。在我们的讨论中，我们将把哈希函数的 32 位输出表示为一条数轴。

现在，假设我们有一组服务器 A、B 和 C，以及一组任务 t-z。我们可以根据它们代表值的哈希值将它们映射到数轴上，例如服务器的 IP 地址和任务的缓存键。

将任务分配给服务器现在只需找到每个任务左侧的第一个服务器。我们可以通过为每个服务器着色来直观表示这一过程，着色区域对应哈希值的范围。请注意，服务器 C 覆盖的范围会绕回数轴的起点，这正是哈希值存在于环形结构中的概念。

这就是一致性哈希的基本原理。从基础层面来看，它非常简单——但很快就能发现还有改进空间。请注意，在我们的示例中，服务器 A 覆盖的范围明显大于 B 或 C。这是一个问题，因为服务器处理的请求数量会与它在数轴上范围的大小成正比。理想情况下，我们希望每个服务器的范围大小相等，但由于哈希值本质上是随机数，我们必须用统计学的方式来描述这些区域的大小。😅

数学与影响

首先：别担心。我向你保证，我不会欺骗你，我们将在第一天概率课程的安全范围内进行讨论。当我们谈论统计分布时，有两个重要因素可以帮助我们以有用的方式量化不确定性：期望值和标准差。用（过度）简化的术语来说，期望值为我们提供了基于分布的测量值的中心点，而标准差则说明了大多数测量值距离这个中心点有多近。

对于一致性哈希，我们可以计算与 N 个服务器之一相关联的范围比例的期望值和标准差。（稍后会详细介绍这个公式的来源）。

$$m \begin{align*} \text{Exp} &= \frac{1}{N} \\ \text{SD} &= \frac{1}{N}\sqrt{\frac{N-1}{N+1}} \end{align*} Â m$$

以具体数值为例，假设我们有 100 台服务器。上述公式给出：

$$m     \text{Exp}=1/100 = 1\% \\     \text{SD}= \frac{1}{100}\sqrt{\frac{100-1}{100+1}} \approx 0.99\% m$$

这告诉我们，我们预计每个服务器处理的范围将围绕总长度的 0.99% 为中心，大多数长度会落在预期值的 1% 范围内。这听起来不错，直到我们意识到这是总长度的 0.99%。我们需要将标准差除以期望值，才能了解误差作为目标大小比例的大小。这个值被称为变异系数。

$$m \text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}} m$$

当 $m N=100, \text{CV} \approx 99\% m$ 时，这意味着一些服务器可能会比预期多工作 99%（处理两倍的请求数），而其他服务器可能几乎什么也不做！现在我们有了预测一致性哈希下服务器负载均衡情况的方法，可以开始着手改进方案了。

如果我们增加哈希值？

一致性哈希的简洁性是一把双刃剑。它易于理解与实现，因为所有内容都会被转换为同一数轴上的简单可关联的哈希值，但系统任何改进也都必须与该数轴相关联。这意味着解决一致性哈希问题的方案只能是添加更多哈希值。它不像万能锤（一种让所有问题都看起来像钉子的工具），更像是一个黄金钉子，将所有工具都变成锤子。

为了解决负载不平衡的问题，我们可以为每个服务器添加多个哈希值来表示，而不仅仅是一个。我们稍后会讨论背后的数学原理，但可以直观理解：虽然每个单独区间存在较大的标准差，但将多个区间合并后，总大小应该会趋于平衡。如果我们以之前图表中的三台服务器为例，为每台服务器随机添加两个额外哈希值，会发现这确实有助于平衡每台服务器的负载。

这显然是一个刻意构造的例子。系统的随机性意味着，每台服务器添加两个额外哈希值能带来多少改进没有保证，但可以直观理解：将更多这样的哈希片段组合在一起，会产生更均匀的分布。总和中的每个片段都有机会与其他片段相互平衡。也许某个片段太短，也许某个片段太长。这本质上就是大数定律告诉我们的结果……但显而易见的问题在于，它只适用于大量数据。在 NGINX 中，每台服务器的哈希数基线被硬编码为 160，Pingora 也使用相同的值作为默认值。暂且不讨论数学推导，如果我们回到之前的 100 台服务器示例，如果每台服务器使用 160 个哈希点而非一个，变异系数（可以理解为误差范围）会从约 99% 降至约 8%，这是一个显著的改进。

如果我们添加更多哈希值会怎样？

我们之前看到，通过按固定数量增加每台服务器的哈希值，可以改善负载在服务器间的均衡性。但如果不想实现完全均衡的负载分配呢？在 Cloudflare 的案例中，有些服务器的存储空间比其他服务器更多，因此将请求分配数量与服务器磁盘空间成比例会更合理。实现这一目标的一种方法是使用 ketama 算法。这个名称有点有趣，因为该算法是以首次实现它的库命名的，而该库的名称……你可以在网上搜索一下 😄。

整个算法可以简化为：对于任意两台服务器 $m S_1m$ 和 $mS_2m$，如果我们希望 $mS_1m$ 服务的请求数量是 $mS_2m$ 的 $mw\timesm$ 倍，那么 $mS_1m$ 关联的哈希数量需要满足 $mH_1 = w\times H_2m$。这使我们能够为每台服务器设置一个“权重”，从而调整与该服务器关联的哈希数量。不幸的是，这不能替代我们在上文部分添加的固定比例因子。这种比例调整必须存在，以设定一个最小误差范围，这个误差范围会出现在权重最低的服务器上。

对于我们来说，由于希望根据存储空间调整负载，我们可以使用磁盘空间作为权重，这正是 Pingora 团队多年来一直采用的做法。在公司其他需要更多计算资源的场景中，权重可能基于 CPU 或 GPU 数量。

如果我们添加更多的哈希值会怎样???

我们还需要解决的最后一个问题是，到目前为止我们假设任何服务器都可以处理任何请求，但实际上并非如此。合规性要求或启用的缓存功能等特性意味着只有部分服务器可以处理特定请求。不幸的是，与之前不同，我们无法通过向同一个环添加更多哈希值来解决这个问题。我们必须添加全新的环，而且不仅仅是这样——每种特性的组合都可能需要自己的专属环！

基于组合的重复是导致指数级爆炸的经典配方。在我们的情况下，少量的不同特性导致了 $m2^\text{handful} = \text{dozens}m$ 个独立的一致性哈希环。因此，你可能已经猜到了，Ivan 发现的“内存使用过多”（某些情况下高达 6GB）问题，是由于需要存储大量哈希值以满足所有功能需求，而这些哈希值必须保留在内存中。那么我们该怎么办呢？

存储优化

一个重大改进来自 Zaidoon，他对我们存储哈希值的 PBR 结构体有了一个洞察。该结构体如下所示：

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

在内存中，这个结构体占用 8 字节，其中 4 字节用于哈希值（这是不可避免的），另外 4 字节用于一个指向存储在另一个数组中的服务器的索引。Zaidoon 的洞察是，这个索引使用 32 位整数是浪费的，因为 PBR 很可能永远不需要同时协调超过 $m2^{16} \approx 65\text{k} m$ 台服务器，因此使用 16 位整数就足够了。因此我们可以将上面的结构体替换为以下结构体：

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

不幸的是，Rust 并不会让这件事变得容易。如上所述改变索引的大小并不能减少内存占用。这是因为 Rust 有对齐规则，要求结构体在内存中的大小必须是其最大（或“最对齐”）字段大小的整数倍。在这种情况下，哈希值是最大的字段，占 4 字节，因此当存储在内存中时，Point 的大小必须是 $mN \times 4m$，所以最小大小是 8 字节。

幸运的是，有一些众所周知的解决方法。你（也就是我）可能会想使用 #[repr(packed)]，但出于良好的原因，这种方法存在争议。一个更安全但可读性较差的解决方案是将哈希值和索引存储为原始字节数组，并通过访问器方法获取它们。这两种方法在编译后生成的代码是相同的。

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%！为了做得更好，我们需要回到数学领域，所以大家抓紧了；我们已经接近终点了。

如果我们尝试使用更少的哈希值会怎样？

你可能已经注意到，我们只给出了每台服务器只有一个哈希值时的标准差公式。推导出每台服务器有 $m k m$ 个哈希值时的公式并不容易，大多数资料只会提供近似值或渐进行为，但这次我们给出了精确结果。我可能不是统计学家，但我的微积分老师（嗨，妈妈！）让我对实际值产生了强烈兴趣。完整的推导过程在补充文章中有详细说明，但这里是我们得到的结论。

$$m     \text{Exp}_k = \frac{1}{N},     \text{SD}_k=\sqrt{\frac{(k+1)}{N(kN+1)}-\frac{1}{N^2}} m$$

要观察哈希值数量增加如何提升准确性，我们需要再次审视变异系数。

$$m \text{CV}_k=\frac{\text{SD}_k}{\text{Exp}_k}=\sqrt{\frac{N-1}{(N*k+1)}} m$$

绘制 $m\text{CV}_km$ 的图表揭示了“只要增加更多哈希值”这种思维的潜在问题（除了过度消耗内存之外）。

你可以看到，每次误差范围下降一个台阶都需要（几乎）将每台服务器的哈希值数量提升一个数量级，因此增加更多哈希值带来的改进越来越小。回想一下，我们使用的是以 160 个哈希值为基数，根据服务器存储大小进行缩放。为了简化计算，我们假设服务器的权重因子 $m{m_w}m$ 为 625，因此得到 $m{k = 160\times625 = 100{,}000}m$。从上图可以看出，最后添加的 90,000 个哈希值只带来了微不足道的 0.7% 误差降低。不幸的是，情况从这里变得更糟。

我的漂亮数学推导结果只有在将哈希值视为连续环时才成立，但在实际应用中，我们使用 32 位数字表示哈希值，这些数字存在碰撞的可能性，且随着哈希值数量增加，碰撞概率会出人意料地迅速上升（参见生日悖论）。碰撞会带来影响，因为在理想情况下，每个哈希值都会对相关服务器处理的请求数量和分布产生贡献，但碰撞意味着某些贡献会被随机丢弃，引入不可预测的误差。如果我们把使用 32 位哈希值的模拟结果与预测误差率进行比较，可以发现对于拥有 2048 台服务器的数据中心，误差率在每台服务器使用 10,000 到 100,000 个哈希值时会增加。

最终，尽管这一发现听起来有些令人沮丧，但它对我们计划回收部分内存来说是个好消息！现在我们有数学依据支持，我们确定可以将每台服务器生成的哈希值数量减少 90%，而不会产生显著的误差，这就是我们最终采取的行动。

在不破坏源站的情况下迁移

还有一个问题需要解决：改变哈希环会导致部分可缓存请求的路由发生变化。即使新哈希环更优，一次性切换整个网络会有效使几乎所有缓存内容失效。这会将内存优化变成源站流量的灾难性激增。

因此我们没有采取全局一次性切换的方式。一段时间内，PBR 同时在内存中维护了两种可缓存负载均衡器的版本：旧的 ketama 环和新的更小的环。每个请求使用我们正常的迁移框架决定应该使用哪个环来选择后端。这意味着迁移决策对每个请求哈希是稳定的，也为我们提供了清晰的回滚路径。如果发现任何异常，我们可以在不重新部署 PBR 的情况下，将新请求重新路由到旧环。

我们随后分阶段推进了迁移工作。我们首先从少量验证地点开始，逐步扩展到更大规模的数据中心群体，最后才覆盖到全球其余地区。

关键之处在于我们独立控制了两个维度：新环路所承载的流量比例，以及允许这些流量移动的范围。如果采用普通的全球百分比推进方式，会导致缓存更新操作瞬间扩散到所有区域。而数据中心级别的推进方式将影响范围控制得更小，也更容易判断变更是否真正安全。

在迁移过程中，我们监控了后端选择追踪、环版本计数器、PBR连接错误、进程内存、启动时间、缓存行为和源站流量。当迁移达到100%后，我们移除了临时的旧环路径，效果立竿见影！

上图显示了变更当周PBR内存使用情况与几周前数据的对比，以及两者相减后的结果。急剧下降的那一天，正是使用大型（现已弃用）哈希环的PBR版本被永久停用的日期。通过对比数据，我们得到了令人满意的结论：变更使使用的内存减少了100TB！

自行尝试

我们在此文章中讨论的所有变更现已以（目前）未公开宣传的cargo特性形式包含在pingora-ketama crate中。v2环采用了压缩存储格式、更快的排序方法，并支持调整每个节点的基础哈希数量。由于这些变更的重点必须放在稳定性和控制上，因此v1环与pingora ketama一直使用的版本完全一致，库也支持同时运行两种环，并可根据每个请求决定使用哪一种。

除了尝试我们字面意义上的一致性哈希变更外，我希望你们能从本文中获得启发，深入研究自己的系统，发现那些看似"简单"或"显而易见"的决策背后可能隐藏的优化机会——只要愿意深入分析数据。你可能无法用Rust解决所有问题，但数学是普适的。

目录栏

讨论栏

相关标签及社交媒体链接

相关标签

关注社交媒体

• Cloudflare

• Kevin Guthrie

• Mariia Iurchenko

电子邮件订阅