Cloudflare : 利用数学（和 Rust）节省 100TB 内存
https://cdn3.ldstatic.com/original/4X/0/7/2/0723fdc2049f4e3ccaa52f39c71c20c7e9ad44c3.svgCloudflare Blog – 18 Sep 26 (https://blog.cloudflare.com/saving-100-tb-of-ram-with-math/)
https://cdn3.ldstatic.com/optimized/4X/e/b/1/eb1a3a6a79b3df9f8690337477b77f86619668a4_2_690x361.png
Saving another 100TB of RAM with math (and Rust) (https://blog.cloudflare.com/saving-100-tb-of-ram-with-math/)
Cloudflare's global network is immense but not limitless. As we look for small ways to trim our resource usage, we sometimes get lucky and we can cut significantly more. Here’s how we reduced one of our Pingora-based service's RAM usage with...
[!quote]+
Cloudflare的规模如此庞大，即使在这里工作多年，也让人觉得不真实。我们在全球拥有数千台拥有PB内存和数百万CPU核心的服务器，所有这些都被推到极限。尽管这些资源看起来庞大，但它们依然有限，当你需要每个节点上运行所有服务时，就不会留空间给浪费空间。
在这个规模下，微小的改进会被放大，因此即使是每次1% (https://blog.cloudflare.com/pingora-saving-compute-1-percent-at-a-time/)的改进也值得庆祝。一些调整加起来效果更多：在本文中，我们将探讨对单一算法的微小调整如何显著减少我们基于Pingora的服务的内存占用。这让我们在全球范围内回收了超过100TB内存，此外还保留了DNS团队上个月牺牲的100TB内存 (https://blog.cloudflare.com/dns-cache-memory-optimization-1111/)。
不要浪费
在大型组织中，保持团队间资源的公平共享并不容易。Cloudflare确保平衡的方式之一是出色的Performance团队不懈努力。
这个故事从Ivan (https://blog.cloudflare.com/author/ivan/)提交的工单开始，他发现：Pingora后端路由器中pingora-ketama (https://docs.rs/pingora-ketama/latest/pingora_ketama/)内存使用过高。结果发现，我们的内部负载均衡服务 Pingora Backend Router（没错，就是 PBR）使用了远超预期的内存——尤其是在与 pingora-ketama 相关的结构中，这是我们用于处理一致哈希的开源库。
为了讨论我们如何应对内存过度使用的问题，我们需要先谈谈什么是一致性哈希，为什么我们在PBR中使用它，以及它是如何变得如此耗费内存。在这过程中，我们会学到一些Rust，甚至学点数学。
一致性哈希
一致性哈希是一种广泛使用的方法，用于在多个服务器之间分配任务，且在服务器添加或移除时无需大幅更改。内部我们用它通过URL将可缓存请求路由到服务器。这使得每个数据中心只存储一份文件副本，并提供了稳定的方式查找每个文件的位置。我们之前 (https://blog.cloudflare.com/making-magic-transit-health-checks-faster-and-more-responsive/)提到 (https://blog.cloudflare.com/rearchitecting-workers-kv-for-redundancy/)过这个 (https://blog.cloudflare.com/high-availability-load-balancers-with-maglev/)系统 (https://blog.cloudflare.com/counting-things-a-lot-of-different-things/)，但现在让我们花时间来讲解这个算法是如何被使用、为什么使用的，以及它是如何工作的。
一致哈希的关键概念是，虽然哈希函数可以接受任何类型的输入，但其输出仅限于一个无符号整数（根据哈希函数的不同，为32位、64位或128位整数）。这使我们能够以一致的方式将任务和服务器相互关联。大多数关于一致性哈希的讨论，你会把输出空间看作一个连续的圆形环，从最大值环绕到零。这种描绘带来了一些不错的可视化效果，但也可能让整数区间的简单概念显得比实际复杂。在讨论中，我们将哈希函数的32位输出表示为一条数轴。
https://cdn3.ldstatic.com/optimized/4X/a/4/0/a40c8fce52e931de3339fb1f3dd0de14856e50e2_2_690x80.png
现在，假设我们有一组服务器 A、B、C 和一组任务 t-z。我们可以根据它们代表值的哈希值映射到数轴上，比如服务器的IP地址和任务的缓存键。
https://cdn3.ldstatic.com/optimized/4X/6/0/7/6078efa1fe763c28d4fc4df892b8e2d267fdb0cc_2_690x134.png
现在，将任务分配到服务器只需找到每个任务左侧的第一个服务器即可。我们可以通过给每个服务器关联的哈希区域涂色来直观表示。注意服务器C覆盖的范围会绕到起始，因此哈希存在于环中。
https://cdn3.ldstatic.com/optimized/4X/c/7/4/c74636e70071db6a645c4f9bbdef492904229fb6_2_690x134.png
就这样。从基础上看，一致性哈希就是这么简单——但很快就会发现还有改进空间。请注意，在我们的例子中，服务器A覆盖的范围明显大于B或C。这是个问题，因为服务器处理请求的比例与其在数轴上的范围大小成正比。理想情况下，我们希望保证每个服务器的大小相等，但由于哈希本质上是随机数，我们必须用统计数据来讨论区域大小。
https://cdn.ldstatic.com/images/emoji/twemoji/fearful.png?v=15
数学与后果
第一：不要慌。我保证我不会骗你 (https://x.com/ThePrimeagen/status/1861040630832742795)，我们会安全地保持在第一天概率课程的范围内。当我们谈论统计分布时，有两个重要因素帮助我们以有益的方式量化不确定性：期望值 (https://en.wikipedia.org/wiki/Expected_value)和标准差 (https://en.wikipedia.org/wiki/Standard_deviation)。用（过于）简化的术语来说，期望值给出一个基于分布的测量值会被中心化的点，标准差则说明大多数测量值可能接近该中心点的距离。
对于一致的哈希，我们可以计算这些因子，适用于N台服务器之一所关联的范围分数大小。（关于该公式的来源细节稍后说明）。
\begin{align*} \text{Exp} &= \frac{1}{N} \\ \text{SD} &= \frac{1}{N}\sqrt{\frac{N-1}{N+1}} \end{align*}
具体来说，假设我们有100台服务器。上述公式给出：
\text{Exp}=1/100 = 1\% \\ \text{SD}= \frac{1}{100}\sqrt{\frac{100-1}{100+1}} \approx 0.99\%
这告诉我们，我们可以预期每台服务器处理的范围大约会占总长度的0.99%，大多数长度也在预期值的1%以内。这听起来不错，但我们意识到那只是总长度的0.99%。我们需要将标准差乘以期望值，以了解误差占目标大小的比例。这个值称为变异系数 (https://en.wikipedia.org/wiki/Coefficient_of_variation)。
\text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}}
在 N=100, \text{CV} \approx 99\% 这意味着有些服务器可能比应有的更努力工作（处理两倍的请求），而其他服务器几乎什么都不做！既然我们已经有了通过一致哈希预测服务器负载均匀程度的方法，就可以开始着手改进。
如果我们加哈希值呢？
一致性哈希的简单性是一把双刃剑。它很容易理解和实现，因为所有内容都转化为同一数轴上的易于关联的哈希值，但系统的任何改进也必须与该数字轴相关。这意味着任何一致的哈希问题的解只能是更多的哈希。它不像金锤 (https://en.wikipedia.org/wiki/Law_of_the_instrument)（所有问题看起来都像钉子的工具），更像金钉，因为它能把所有工具变成锤子。
为了解决工作负载不平衡的问题，我们可以添加多个哈希值来代表每个服务器，而不仅仅是一个。我们稍后会讲解背后的数学原理，但直观上应该有道理：虽然每个区间的标准差很大，但将多个范围加起来，它们的总大小应该会趋于平衡。如果我们取上述三服务器示例，随机为每台服务器添加两个哈希值，我们会发现这有助于平衡每台服务器的工作量。
https://cdn3.ldstatic.com/optimized/4X/b/8/2/b824399f9a062390b43d603930dace78b1d70549_2_690x248.png
这确实是一个刻意的例子。系统的随机性意味着你无法保证每台服务器增加两个哈希会带来多少提升，但直观上，将更多哈希片段组合在一起能获得更均匀的分布。和中的每个部分都有机会平衡另一个部分。也许一个太短;也许一个太长了。这本质上就是大数定律 (https://en.wikipedia.org/wiki/Law_of_large_numbers)告诉我们应该发生的事情…显而易见的问题是，这方法只适用于大量人。在NGINX中，每个服务器的基础哈希数被硬编码为160，Pingora (https://github.com/nginx/nginx/blob/0427f5335f7abfbb733a72d6bf3561508f5d8a88/src/http/modules/ngx_http_upstream_hash_module.c#L408)使用与默认值相同的数值 (https://github.com/cloudflare/pingora/blob/200cee483d895dac0bb2698fa6b3bd6347270197/pingora-ketama/src/lib.rs#L136)。我暂且不讲数学，但如果我们回到100台服务器的例子，如果每个服务器用160点而不是只用一个，变异系数（我们可以把它看作误差范围）会从大约99%降到大约8%，这是一个显著的提升。
如果我们增加更多的哈希值呢？
我们上面看到，通过保持每个服务器的哈希数增加，我们可以改善工作负载在每台服务器上的均匀分配，但如果我们不想让工作均匀分配呢？以Cloudflare为例，有些服务器的存储空间比其他服务器大，所以分配给服务器的请求数量与其磁盘空间成正比会更好。实现这一点的一种方法是使用ketama算法。这个命名有点奇怪，因为算法是以它首次实现的库 (https://github.com/RJ/ketama)命名的，而该库的名字是…你可以谷歌一下 (https://www.aboutwayfair.com/tech-innovation/consistent-hashing-with-memcached-or-redis-and-a-patch-to-libketama#:~:text=What's%20up%20with%20the%20name,Heh.)
https://cdn.ldstatic.com/images/emoji/twemoji/face_without_mouth.png?v=15
https://cdn.ldstatic.com/images/emoji/twemoji/fog.png?v=15
。
整个算法归结为：对于任意两个服务器，S_1&S_2 ，如果我们希望 以下请求被S_1存在w\times比起服务的S_2，与 相关的哈希数S_1必须是H_1 = w\times H_2 .这让我们可以为每台服务器设置一个“权重”，从而增加该服务器关联的哈希数量。遗憾的是，这并不能替代我们在上文部分添加的恒定比例因子。这种缩放需要设定最小误差范围，这个误差范围会显示在权重最低的服务器上。
对我们来说，既然希望工作负载基于存储空间进行扩展，我们可以用磁盘空间作为权重，这正是Pingora团队多年来一直在做的。在公司其他工作负载较为高的部门，权重可能基于CPU或GPU数量。
如果我们再加更多哈希呢???
我们需要解决的最后一个问题是，到目前为止，我们假设任何服务器都能处理任何请求，但实际上并非如此。诸如合规要求或启用缓存功能意味着只有部分服务器能处理特定请求。遗憾的是，与以往不同的是，我们无法通过向同一环添加更多哈希来解决这个问题。我们必须添加全新的戒指，而且不仅如此——每种功能组合都可能需要自己独特的戒指！
基于组合的复制是指数爆炸的经典配方。就我们而言，有几个不同的功能导致2^\text{handful} = \text{dozens}由独立且一致的哈希环组成。所以你现在可能已经猜到了，伊万发现的“过度内存使用”（在某些情况下是6GB）是由于大量哈希值以容纳我们所需的所有功能，这些都必须存储在内存中。那我们能做什么？
存储改进
一个重大改进来自Zaidoon (https://blog.cloudflare.com/author/zaidoon/)，他对我们在PBR中存储哈希的结构 (https://github.com/cloudflare/pingora/blob/702f69015e53f7244d6ad2e743de571d859a70a4/pingora-ketama/src/lib.rs#L101-L107)提出了见解。这个结构看起来像这样：
struct Point {
hash: u32,
index: u32,
}
在内存中，这表示为八字节，其中四字节对应哈希（这是不可避免的），四字节指向存储在另一个数组中的服务器索引。Zaidoon的见解是，32位整数用于该索引是浪费的，因为PBR很可能永远不需要协调超过的次数2^16 \approx 65\text{k}服务器同时运行，所以16位整数是可以工作的。所以我们可以用这个来替换上面的结构：
struct PointV2 {
hash: u32,
index: u16,
}
不幸的是，Rust并没有让这件事变得那么简单。像上面那样改变索引大小并不能减少内存占用。这是因为 Rust 的对齐规则要求内存中结构的大小必须是其最大（或“最对齐”）字段的整数倍。在这种情况下，哈希是最大的，有四个字节，因此存储在内存中时，点必须具有大小，最小大小为八字节。
幸运的是，有许多知名的解决方法。你（指我）可能会想用# (https://doc.rust-lang.org/nomicon/other-reprs.html#reprpacked-reprpackedn)，但这有争议，原因充分 (https://github.com/rust-lang/rust/issues/27060)。一个更安全但不易读取的解决方案是将哈希和索引存储为原始字节数组，并用获取器访问它们。这两种方法编译到的是同一个结果 (https://godbolt.org/z/1E5TeW1za)。
struct Point();
impl Point {
fn hash(&self) -> u32 {
u32::from_ne_bytes(self.0.try_into().unwrap())
}
fn index(&self) -> u16 {
u16::from_ne_bytes(self.0.try_into().unwrap())
}
}
这个简单（虽然冗长）的改动，使得用于一致哈希的内存消耗减少了惊人的25%！为了做得更好，我们需要重新回到数学上，所以每个人都要抓住一些东西;现在是最后冲刺阶段。
如果我们尝试更少的哈希值呢？
你可能注意到，我们给出了每个服务器只有一个哈希值时标准差的公式。推导当 有 的情况 k 每台服务器的哈希值并不容易，大多数资料只给出近似值或渐近极限，但我们没有。我可能不是统计学家，但我从小有一位微积分老师（嗨，妈妈！），我想知道它的实际数值。完整的推导在补充文章 (https://ch.terabyteoff.com/)中，但这里是总结。
\text{Exp}_k = \frac{1}{N}, \text{SD}_k=\sqrt{\frac{(k+1)}{N(kN+1)}-\frac{1}{N^2}}
为了了解增加哈希计数如何提升准确性，我们需要再次关注变异系数。
\text{CV}_k=\frac{\text{SD}_k}{\text{Exp}_k}=\sqrt{\frac{N-1}{(N*k+1)}}
剧情规划显示了“直接增加哈希值”心态的潜在问题（除了过度使用内存之外）。
https://cdn3.ldstatic.com/optimized/4X/5/6/c/56ca0109b3227e190247525a72d471c4972f140d_2_690x459.jpeg
你可以看到每降低一个错误范围，服务器的哈希数几乎增加了一个数量级，所以增加哈希带来的改进越来越少。回想一下，我们使用的是基于服务器存储大小的160个哈希值。为了简化计算，我们说权重因子{m_w}对于服务器，是625，所以我们得到{k = 160\times625 = 100{,}000}
.从上图可以看出，我们最近添加的9万个哈希值只为我们带来了0.7%的错误减少。不幸的是，事情从那以后变得更糟。
我那漂亮的数学预测只有在考虑哈希在连续环中时才成立，但实际上我们用32位数来表示可能发生碰撞的哈希，碰撞的概率随着哈希数增加而迅速上升（参见生日悖论 (https://en.wikipedia.org/wiki/Birthday_problem)）。碰撞很重要，因为理想情况下，每个哈希都会增加相关服务器处理的请求量和分布，但碰撞意味着部分贡献被随机丢弃，从而引入不可预测的误差。如果我们将一些模拟结果与32位哈希与预测错误率进行比较，可以看到对于拥有2048台服务器的数据中心，错误率会增加：每台服务器的哈希值在10,000到100,000之间。
https://cdn3.ldstatic.com/optimized/4X/c/7/3/c73380677bff4358097ed069cbc1148e9cd1531f_2_690x459.jpeg
最终，虽然这个事实让人有些难过，但这对我们恢复内存的计划来说是个好消息！现在我们有了数学支持，确定可以在不产生明显错误的情况下，将每个服务器产生的哈希数减少90%，这就是我们的目标。
迁徙时不融化的起源
还有一个问题：更改哈希环会改变某些可缓存请求的去向。即使新环更好，一次性切换整个网络实际上会使几乎所有缓存内容失效。这会让内存优化变成源流量的灾难性增长。
所以我们没有把这次做成单一的全球翻转。一段时间内，PBR内存中同时携带了两种可缓存负载均衡器：旧的ketama环和较小的新环。每个请求都使用我们常规的迁移框架来决定哪个环应该选择后端。这意味着每个请求哈希的推送决策都很稳定，同时也给了我们一条干净的回滚路径。如果有任何异常，我们可以通过旧环发送新请求，而无需重新部署PBR。
然后我们分层铺开了迁移过程。我们从小型验证点开始，逐步扩展到越来越多的数据中心，然后才继续向世界其他地区推进。
关键在于我们独立控制了两个维度：有多少流量使用了新的环路，以及这些流量被允许移动到哪里。如果是单纯的全球百分比部署，缓存流失会一次性扩散到各个地方。数据中心范围的推广保持了爆炸范围较小，使得判断变更是否安全变得更加容易。
迁移过程中，我们观察了后端选择跟踪、环形版本计数器、PBR连接错误、进程内存、启动时间、缓存行为和起始流量。迁移达到100%后，我们移除了临时的旧环路径，瞧！
https://cdn3.ldstatic.com/optimized/4X/d/e/e/deecd8430efc39e4a298b7f3454955b08ae76fd4_2_690x206.jpeg
上图显示了PBR在变更当周内内存使用的比较，与几周前的数据，以及从两者中减去的结果。急剧下降的那一天，是那个拥有大型（现已废弃）哈希环的PBR版本被永久淘汰的那一天。看了差异，我们满意地发现，我们的更改让使用的内存减少了100TB！
https://cdn3.ldstatic.com/optimized/4X/b/0/f/b0f4ab52590432d9919a429f4bddfba9814f6693_2_690x206.png
你自己试试
我们在这篇文章中讨论的所有改动现在都以（目前）未公开的货物功能形式，在pingora-ketama箱 (https://github.com/cloudflare/pingora/blob/main/pingora-ketama/Cargo.toml#L34)子中提供。环采用紧凑的存储格式，更快的排序方法，并能够按节点调整基数哈希数。我们在做这些改动时必须注重稳定性和控制，所以环形结构与 Pingora Ketama 一直使用的完全相同，图书馆也使得两者可以同时运行，并根据每个请求决定使用哪种和何时使用。v2v1
除了尝试我们字面上的一致哈希变更外，我希望你能从中获得一些灵感，深入挖掘自己的系统，看看哪些“简单”或“显而易见”的决策隐藏着潜在的胜利，如果你愿意深入数字的话。你可能无法用Rust解决所有问题，但数学是通用的。
你的第一个视频可能很糙，但没关系， 先拉屎再屎上雕花 。 公司买断的不仅是你的时间，更是 你的人生可能性 。 看到就转：别让任何人消耗你内心的晴朗，生活应该被热爱的人和事填满。强调要守护好自己内心的美好，专注于热爱的事物 小白一个，顶一下！ 最近这类资源感觉很多啊 建议星颖出个资源保险箱，我的收藏夹快炸了
页:
[1]