通过数学（和 Rust）节省另外 100TB RAM

Cloudflare 的运营规模如此之大，即使在这里工作多年，它也显得不真实。我们在世界各地拥有数千台服务器，拥有 PB 级 RAM 和数百万个 CPU 核心，并且所有这些都已达到极限。尽管这些资源感觉很庞大，但它们仍然是有限的，当您需要每个服务在每个节点上运行时，就不会留下浪费空间的空间。在这种规模下，微小的改进会被大大放大，因此即使一次 1% 的改进也值得庆祝。一些调整加起来意义重大：在这篇文章中，我们将了解对单个算法的微小更改如何显着减少我们基于 Pingora 的服务之一的内存占用。这使我们能够在全球范围内回收超过 100TB 的 RAM，而 DNS 团队上个月已经削减了 100TB 的内存。不要浪费 维持团队之间公平的资源共享并不容易，尤其是在大型组织中。 Cloudflare 确保保持平衡的方法之一是通过出色的性能团队的不懈努力。这个故事始于 Ivan 提交的一张票证，他发现： Pingora 后端路由器中的 pingora-ketama 内存使用过多。结果发现，我们的内部负载平衡服务 Pingora 后端路由器（是的，PBR）使用的内存比预期多得多 - 特别是与 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\% \\ \te