又节省了100TB RAM

# 用数学（和Rust）再省100TB内存 来源：https://blog.cloudflare.com/saving-100-tb-of-ram-with-math/ Cloudflare运营的规模如此庞大，即便在这里工作多年，仍感觉有些不真实。我们在全球拥有数千台服务器，配备数PB内存和数百万CPU核心，所有资源都被推至极限。尽管这些资源看似浩瀚，它们仍然是有限的。当需要每个服务在每个节点上运行时，就没有空间浪费了。 在这种规模下，微小的改进会被放大，因此即使是1%的渐进式改进（https://blog.cloudflare.com/pingora-saving-compute-1-percent-at-a-time/）也值得庆祝。而某些调整的累积效果更为显著：在本文中，我们将探讨如何通过微调单个算法，显著减少我们某个基于Pingora的服务的内存占用。这让我们在全球范围内回收了超过100TB的RAM，这还不包括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后端路由器（是的，PBR）占用的内存远超预期——具体体现在与pingora-ketama相关的数据结构中，这是我们的开源一致性哈希处理库。 为了讨论如何解决这个看似过度的内存使用问题，我们需要先解释什么是一致性哈希、为什么在PBR中使用它，以及它为何如此耗内存。在此过程中，我们将学习一些Rust知识，甚至一点数学。 ## 一致性哈希 一致性哈希是一种广泛使用的方法，用于在多个服务器之间分配任务，且在服务器增删时无需大规模调整。我们内部使用它通过URL将可缓存的请求路由到服务器。这使我们能为每个数据中心仅保存文件的一个副本，并提供稳定的文件位置查找方式。我们之前提到过（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/）（https://blog.cloudflare.com/making-magic-transit-health-checks-faster-and-more-responsive/），但让我们花时间梳理这个算法的应用方式、原理和工作机制。 一致性哈希的核心概念是：虽然哈希函数可以接受任何输入，但其输出限于单个无符号整数（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。这是个问题，因为服务器处理的请求比例与其在数轴上的范围大小成正比。理想情况下我们希望保证每个服务器的范围大小相等，但由于哈希本质上是随机数，我们必须从*统计学*角度讨论区域大小。😨 ## 数学与后果 首先：别慌。我保证（https://x.com/ThePrimeagen/status/1861040630832742795）不会骗你，并且会严格控制在概率论入门课程的范围内。讨论统计分布时，有两个关键因素帮助我们量化不确定性：期望值（https://en.wikipedia.org/wiki/Expected_value）和标准差（https://en.wikipedia.org/wiki/Standard_deviment）。简言之，期望值给出基于分布的测量中心点，标准差则反映大多数测量值与该中心点的接近程度。 对于一致性哈希，我们可以计算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%。我们需要将标准差按期望值缩放，以查看误差相对于目标大小的比例。这个值称为变异系数（https://en.wikipedia.org/wiki/Coefficient_of_variation）。 $$m \text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}} m$$ 当$m N=100, \text{CV} \approx 99\% m$——意味着某些服务器可能比应承担的工作量多99%（处理两倍请求），而其他服务器几乎空闲！现在我们有了预测一致性哈希负载均衡效果的方法，就可以开始改进了。 ## 如果我们增加哈希值呢？ 一致性哈希的简洁性是把双刃剑。它易于理解和实现，因为所有内容都转化为同一数轴上易于关联的哈希值，但任何系统改进也需要与该数轴关联。这意味着任何一致性哈希问题的解决方案只能是*更多哈希*。这不像金锤（https://en.wikipedia.org/wiki/Law_of_the_instrument）（所有问题都像钉子的工具），而更像是金钉子——它把所有工具都变成了锤子。 为解决工作负载不平衡问题，我们可以为每个服务器添加多个哈希而非单个。我们稍后会讲解其数学原理，但直观上应该能理解：虽然单个区间标准差很大，但将多个区间合并应使总大小趋于均衡。若在示例图中为每个服务器随机添加两个哈希点，会发现这有助于均衡每个服务器的工作负载。 BLOG-3083 5.png 这是个刻意设计的例子。系统的随机性意味着无法保证为每个服务器添加2个额外哈希能带来多大改进，但直观上合并更多哈希区段应产生更均衡的分布。求和中的每个区段都有机会平衡另一个：可能一个太短，一个太长。这本质上是大数定律（https://en.wikipedia.org/wiki/Law_of_large_numbers）预测的结果...明显的问题是它只适用于大数。在NGINX中，每个服务器的基础哈希数硬编码为160（https://github.com/nginx/nginx/blob/0427f5335f7abfbb733a72d6bf3561508f5d8a88/src/http/modules/ngx_http_upstream_hash_module.c#L408），Pingora默认值与之相同（https://github.com/cloudflare/pingora/blob/200cee483d895dac0bb2698fa6b3bd6347270197/pingora-ketama/src/lib.rs#L136）。暂不展开数学推导，但回到100服务器的例子，若每个服务器使用160个点而非1个，变异系数（可理解为误差范围）将从约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.）😶🌫️。 整个算法可归纳为：对于任意两台服务器$m S\_1m$和$mS\_2m$，若希望$mS\_1m$处理的请求是$mS\_2m$的$mw\times m$倍，则$mS\_1m$关联的哈希数需满足$mH\_1 = w\times H\_2m$。这允许我们为每台服务器设置"权重"来缩放其哈希数。但可惜这无法替代上文添加的常数缩放因子。该缩放必须存在以设置最小误差范围，这将在权重最低的服务器上体现。 对我们而言，由于希望工作负载按存储缩放，我们可以使用磁盘空间作为权重，这正是Pingora团队多年来的做法。公司其他计算密集型工作负载的部门，权重可能基于CPU或GPU数量。 ## 如果增加更多哈希值??? 我们需要解决的最后一个问题：目前假设任何服务器都能处理任何请求，但实际并非如此。合规要求或启用的缓存功能等意味着只有部分服务器能处理特定请求。不幸的是，与之前不同，我们无法通过在同一个环上添加更多哈希来解决此问题。我们必须添加全新的*环*，不仅如此——每个功能*组合*可能都需要其专属环！ 基于组合的重复是指数爆炸的经典配方。在我们的案例中，少量功能导致$m2^\text{handful} = \text{dozens}m$个独立的一致性哈希环。所以你可能已经猜到，Ivan发现的"内存过度使用"（某些情况达6GB）是因为需要存储海量哈希以支持所有功能。那么我们能做什么？ ## 存储改进 一项重大改进来自Zaidoon（https://blog.cloudflare.com/author/zaidoon/），他对PBR中存储哈希的struct（https://github.com/cloudflare/pingora/blob/702f69015e53f7244d6d2e743de571d859a70a4/pingora-ketama/src/lib.rs#L101-L107）产生了洞察。该结构如下： ``` 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\)\]`](https://doc.rust-lang.org/nomicon/other-reprs.html#reprpacked-reprpackedn)，但这是有争议的（https://github.com/rust-lang/rust/issues/27060），理由充分。更安全但可读性稍差的解决方案是将哈希和索引存储为原始字节数组，并通过getter访问。两种方法编译结果相同（https://godbolt.org/z/1E5TeW1za）。 ``` 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$个哈希的情况并不简单，大多数资料只提供近似值或渐近极限，但我们例外。我可能不是统计学家，但我在微积分老师（嗨，妈妈！）的熏陶下长大，我想知道*真实*值。完整推导在补充文章（https://ch.terabyteoff.com/）中，以下是最终结果。 $$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$曲线揭示了"只管增加哈希"思维模式的潜在问题（除占用RAM外）。 BLOG-3083 6.png 你可以看到误差范围每降低一个台阶都需要（几乎）一个数量级的哈希数增加，因此增加哈希带来的改进越来越少。回顾我们使用的是基于服务器存储缩放的160个基础哈希。为简化计算，我们假设服务器的权重因子$m\{m\_w\}m$为625，因此得到$m\{k = 160\times625 = 100\{,\}000\}m$。从上图可见，最后增加的90,000个哈希仅换来微不足道的0.7%改进。