在Cloudflare的全球网络中,内存资源从来不应该是被浪费的。我们目前运营着数万台服务器,它们加起来拥有超过PB级别的RAM,以及数百万颗CPU核心。在这样庞大的规模面前,即便是细微的改进,也会被放大成惊人的数字。例如,我们想尽办法减少每一次服务器选择所需的内存,最终成功为整个系统削减了超过100TB的内存占用。这背后既包含了对一致性哈希算法的深入探索,也包含了用Rust语言进行底层内存布局优化的精妙技巧。今天,我们就来回顾这段从一笔工单开始的技术旅程。
故事的开端来自一个普通的内部工单:Pingora Backend Router中的一个模块,名为pingora-ketama,它的内存使用量高得异常。PBR是我们处理缓存请求路由的核心服务,它使用一致性哈希算法来为每个请求分配一台最合适的后端服务器。一致性哈希是一种非常优雅的架构:服务器的IP地址和请求的缓存键会被哈希到同一个数字空间中,然后每个请求在数字空间中查找它左边最近的那台服务器。每当服务器增减时,这种算法能确保只有少量请求需要迁移,因此它的稳定性得到了广泛采用。然而,这种看似简洁的算法背后,隐藏着一些不为人知的数学特性。 在经典的一致性哈希中,假设我们有N台服务器。
理想情况下,每台服务器应该处理1/N的请求。但由于哈希值的随机性,实际负载分配在统计上会存在不小的偏差。我们通常用变异系数来量化这个偏差。对于单点模型,变异系数大约等于N减1除以N加1的平方根。当N等于100时,这个值竟然高达99%。这也就是说,在实际运行中,有的服务器可能承受近乎两倍于平均值的请求,而另一些服务器则可能处于相对空闲的状态。
这显然无法满足生产环境的负载均衡要求。 为了让负载更加均匀,自然的思路是增加采样点。也就是说,每台服务器在数字空间中拥有多个哈希点,而不是仅仅一个。根据大数定律,这些点所围成的区域长度总和会随着点数的增加而逐渐接近期望值。如果为每台服务器配置160个哈希点,那么变异系数就会从99%下降到大约8%。这也是NGINX和Pingora默认采用160作为基准哈希数的原因。
当我们还希望根据服务器的磁盘容量设置权重时,可以使用ketama算法。它通过让权重更大的服务器拥有更多的哈希点,来实现负载的加权分配。以我们常用的配置为例,某台服务器如果有625的权重,那么它的哈希点总数就达到了100,000个。完成这项分配所需的元数据,需要被保存在内存中。 起初,这似乎不是一个大问题。但随着业务需求不断演进,我们遇到了新的挑战。
实际的路由常常受到多种特性组合的影响。合规要求、缓存功能开关,甚至是网络分区策略,都可能导致只有一部分服务器能够处理特定的请求。要让一致性哈希精确地适配这些约束,唯一的方法是针对每一种特性组合建立独立的哈希环。假设有5个独立的特性,就需要维护32条不同的哈希环。当这些环同时被加载到内存中时,存储开销就会成倍增长。我们的PBR进程,在某些情况下竟然需要额外的6GB内存来完成这些环的存储。
这显然是一种浪费。更关键的是,无论是数学推导还是仿真实验都表明,当每个服务器的哈希点数超过一定阈值后,继续增加点数对均匀性的提升微乎其微,但内存消耗和计算开销却会线性增加。此外,我们使用的是32位哈希值,哈希碰撞的隐患在点数变多后也会逐渐显现。 在认识到单纯堆砌更多哈希点并非一条可持续的路径后,我们开始考虑两种优化策略。第一种是数据结构的压缩,第二种是哈希点数量的削减。我们先看数据结构。
最初的点表示为包含4字节哈希值和4字节索引的结构体,共占8字节内存。由于PBR的规模在短期内不可能超过65535台服务器,索引字段完全可以只用2字节表示。但在Rust中,仅仅缩小字段大小是不够的。Rust在内存中布局结构体时,为了确保对齐,会在字段之间插入填充字节。这导致我们定义的结构体仍然占据8字节空间。要解决这个问题,必须放弃安全的抽象,使用带有原始字节数组的结构体,并手动从字节序列中读取哈希和索引。
经过这样的改造,每个点从8字节降至6字节,压缩了25%的空间。 第二种策略是从数学上削减冗余。当我们把变异系数公式随手绘制成曲线图时,一个有趣的规律浮现出来:随着每台服务器的哈希点数k不断增加,减少误差的边际效果会越来越弱。从1个点到10个点,误差大幅下降;从10个点到100个点,改进依然可观;但当k从10000增加到100000时,曲线的斜率已经趋近于零。这意味着,最后加入的那些点,只是让误差减少了微乎其微的一部分,而带来的额外内存却实实在在。加之一致性哈希在实际部署中对服务器增减的容忍度本来就很高,因此我们做出了一个大胆的决定:将默认的160乘以权重的哈希点数量减少90%。
换句话说,仅使用原来10%的哈希点,便可以达到几乎相同的负载均衡效果。这个决定一旦实施,极大缓解了内存瓶颈。 理想与现实之间还有一道巨大的鸿沟,那便是迁移安全。任何对哈希环的调整,都会改变缓存键的映射关系,导致现有缓存内容失效。如果切换得太突然,大规模的缓存未命中请求会把我们的源站压垮。为此,我们选择了一种渐进式、可回滚的迁移方式。
在相当长的一段时间内,新版本的PBR同时加载了旧的和新的两套哈希环。当一个请求到达时,系统会用一个稳定的、基于请求哈希值的规则来决定它应该查找哪套环。我们称之为按请求迁移,它保证了同一个请求在迁移期间的行为始终保持一致。此外,我们还选择了在单个数据中心内开始迁移,逐步增加流量比例,并同时监控后端选择追踪、缓存命中率和源站负载等指标。一切正常后,再向更多数据中心推进。这种分层的策略,让可能发生的故障被控制在最小的爆炸半径内。
除了内存占用之外,减少哈希点还带来了另一个附带收益:启动时间。由于构建新的哈希环时无需再对海量的点进行排序,整个初始化过程都会变快。在滚动更新场景中,更快的启动时间意味着服务可以更快地进入就绪状态,从而减少了因实例重建而导致的能力下降时间窗口。这将间接提升我们服务的整体可靠性。也许有人会问,既然哈希点减少了,会不会对哈希碰撞更加敏感?实际上,我们通过仿真对比了32位哈希在10000个点和100000个点下的误差表现。结论是,在数据中心的服务器数量达到2048台时,减少到10000个点后,误差仍然保持在极低水平。
显然,10000个点已经足以覆盖真实场景的需求。 最终,在确保所有指标都平稳运行之后,我们彻底关闭了旧的哈希环路径。这一刻,从全球各地内存监控图表上可以看到一条陡峭的下降曲线,我们成功释放了100TB的RAM。这100TB的内存节省,不仅让我们有更多余地来处理未来的流量,也为其他团队提供了借鉴。这些扎实的优化,最终得以回馈给开源社区。我们已将v2环的代码以cargo feature的形式,公开在pingora-ketama crate中。
并且,为了确保稳定性,我们让v1环和v2环可以同时运行,由工程师根据请求粒度决定何时从v1切换到v2。 在实现v2环的过程中,我们也特别注重了排序性能。为了在哈希点中快速找到应该路由到哪台服务器,需要对哈希点进行排序。之前的实现采用了非常高效的排序策略,而新的v2环在此基础上进一步优化了内存的局部性。得益于更紧凑的数据结构,更多的哈希点能够被直接缓存在CPU的L2或L3缓存中,这也带来了微弱的性能提升。这些细节,普通用户很难直接察觉,却在每天数以万亿计的请求中一点点累积起来,成为支撑整个平台顺畅运转的底层基石。
当你下一次使用负载均衡、缓存服务或是编写Rust程序时,希望你能回想起这个故事。在不改变任何外部行为的前提下,我们通过数学优化和严谨的系统编程,为整个平台争取到了整整100TB的宝贵内存。这不仅是工程上的胜利,也是数学与计算机科学结合的最好例证。也许下一次,当你面对自己的内存瓶颈时,你也会想到:先别急着加机器,仔细看看算法和数据结构,也许数学早已给出了更好的答案。 。
