之前的文章中，我们曾介绍过世界最大的免费CDN供应商CloudFlare使用Rust从零开发自建Web代理服务器Pingora代替其广泛使用的Nginx服务器的详细的案例和技术细节。CloudFlare也承诺会逐渐对其进行开源以及更多技术细节的分享。上周CloudFlare开始建立了Pingora的Github共享库，开源了Pingora的一个底层库pingora-limits。

今天我们就来学习一下这个底层库（或者叫板条箱crate）有关的技术细节。

概述

pingora-limits是Pingora服务器中的一个重要的组件，提供了计算代理服务器运行中的事件统计和估计事件发生率的功能。该功能用于保护基础设施和服务免受某些类型的恶意或行为不当请求的影响。

例如，当源服务器变慢或无响应时，请求将累积到前端代理服务器上，这会给前端代理服务器和后端的客户服务器都造成压力。有了这个库，就可以准确识别有问题的请求来源，然后可以不影响其他流量的情况下对其进行处理。

这个问题可以用一种非常简单的方式抽象出来。输入是不同类型事件的流。在任一时刻，系统都应该能够判断某类事件的出现次数（或比率）。

在一个简单的例子中，可以将颜色当做事件的类型，这样一个可能事件流示例：

红、蓝、红、橙、绿、棕、红、蓝……

在上面示例中，应该统计到“红色”事件出现了3次。

相应的算法设计起来很简单，一个明显的答案是使用哈希表，以颜色为键，值是它们对应次数。当出现新事件时，算法都会查找哈希表的健并对其增加计数。哈希算法的时间复杂度为O(1)，空间复杂度为 O(n)，其中n是事件类型的数量。

技术细节

哈希表解决方案在常见场景中很好，但有一些地方需要改进。

当行为异常的服务器在某一时刻只有少数时，面对百万台的在线代理服务器，需要大量空间（内存）来保存所有键的计数器似乎有点浪费。

另外更新哈希表（尤其是添加新键时）需要锁。这种行为可能会强制所有并发事件处理通过我们的系统序列化。换句话说，当锁竞争很频繁时，锁会使系统性能大大减小。

考虑到需要大规模部署此类算法，改进上述算法解决以上问题非常有必要：

该算法在数万台机器上运行。

它每秒处理超过两千万个请求。

提高效率可带来巨大的成本节约。

pingora-limits中采用更优化的算法count-min sketch（CM sketch）估计。CM sketch 估算O(1)中的事件计数，但仅使用O(log(n))的空间。

由于该算法的简单性，可以在没有锁的情况下实现。因此，与前面讨论的哈希表方法相比，pingora-limits运行得更快、更有效。

CM sketch

CM sketch和Bloom filter算法类似。CM sketch数学细节不在讨论（有意者，可以自己搜索学习），此处只直白说明其工作原理。

CM sketch 数据结构有两个参数：

H：哈希数（行）

N：每个哈希（行）的计数器（列）数。

行和列形成一个矩阵。他们占用的空间是H*N。每行都有自己独立的哈希函数（hash_i()）。

例如，假使H=3，N=4，则是个三行四列的矩阵：

当发生“红色”事件时，每一行都会独立对其进行计数。每行将使用其自己的哈希函数( hash_i(“red”) )来选择一列，增加的列计数器而不用担心碰撞。

下表说明了一个“红色”事件后矩阵的可能状态：

然后，假设事件“蓝色”发生，假设它在第2行与“red”发生冲突：两者都哈希到第三个槽：

假设又经历了一系列事件 “蓝色、红色、红色、红色、蓝色、红色”，到目前为止，总共观察到5个“红色”和3个“蓝色”。按照该算法，估计器矩阵终变为：

现在，根据矩阵数值，看看CM sketch如何计算每个事件的发生的呢？为了检索各键（红蓝色）的数量，CM sketch估计器用了一个最小计算原则，即返回各行中各个健值的最小数即可。

所以红色的计数是min(5, 8, 5) = 5，

蓝色是min(3, 8, 3) = 3。

该算法选择碰撞最少的单元格。因此，单个单元格中事件之间有碰撞是可以接受的，因为只要给定类型的事件存在无碰撞单元格，该事件的计数就是准确的。

当两个（或更多）键在所有槽上发生碰撞时，估计器可能会高估。假设只有两个键，它们总碰撞的概率是 1/N^H（本例中为 1/64）。另一方面，它从不低估，所以，CM sketch不会遗漏任何事件。

代码实现

由于该算法只需要散列、数组索引和计数器递增，因此可以用几行代码中实现，并且是无锁的。

以下是它在 Rust 中如何实现的代码片段。

基线测试

将上面的设计与两种基于哈希表的方法进行比较。

Rust原生的Mutex<HashMap<u32, usize>>。这种方法参考了上面提到的简单哈希表方法。该方法要求对每个操作都进行锁定。

优化的DashMap<u32, AtomicUsize>。DashMap利用多个哈希表来分片键以减少不同键之间的争用。另外，在这里还使用原子计数器，这样计算现有键就不需要写锁了。

对基线测试使用了两个测试用例，一个是单线程的，另一个是多线程的。在两种情况下，都有一百万个健。并对着百万健生成了1的亿个事件。这事件针对每个健均匀分布。

测试使用M1 MacBook Pro本上Debian VM 上执行的，结果：

速度

每个事件（上面的incr()函数）计时，越低越好：

在没有锁争用的单线程情况下，pingora-limits方法比原始方法快5倍，比优化方法快4倍。 对于多线程下，存在大量争用。pingora-limits方法类似于优化版本。两者都比原生算法的快7倍。pingora-limits 和优化哈希表的性能相似的原因是因为在这两种方法中，都只是更新原子计数器。

内存消耗

越低越好。为简单起见，这些数字仅从单线程测试用例中收集。

Pingora-limits峰值需要优化算法内存的1/1300，只是原始算法内存的1/2000。

从上面的数据来看，pingora-limits 在CPU和内存上都是高效的。

Pingora-limits 提供的估计器是有偏估计器，因为它可能高估事件的出现。在准确计数的场合，是不允许有误报的。但pingora-limits 使用的场合不是这样的，pingora-limits是用于对代理流量的第一级过滤器，只有特定时间超过一定阈值的才会触发统计，记录到哈希表以进行准确计数。在这种情况下，大多数低频事件类型被过滤器过滤掉，因此哈希表也消耗很少的内存也损失任何准确性。

架构

在pingora中，有很多地方使用了这个库。最常用的部分是实现连接限制功能：当服务器尝试与单个源服务器建立太多连接时，为了保护服务器和基础设施不超载，该功能将开始拒绝新请求并返回503错误。

在这个功能中，每个传入请求都被增加一个计数器，由具有相同客户ID、服务器IP和服务器主机名的所有其他请求共享。 当请求完成时，计数器相应地减少。 如果计数器的值超过某个阈值，则请求被拒绝并返回503错误响应。在CloudFlare生产环境中，选择库的参数，以便两个不相关的客户之间的理论碰撞机会约为1/2^ 52。拒绝阈值明显高于健康客户的流量所能达到的水平。因此，即使多个客户的计数发生碰撞，高估值也基本达不到所设的正常阈值。因此不太可能发生连接限制的误报。

结论

Pingora-limits crate现已在GitHup开源，在源码仓库中提供了核心的功能和性能基准测试用例。

pingora-limits，这是一个兼顾了有效性、性能以及资源占用各方面综合考虑下的统计事件库，基准测试表明，pingora-limits实现速度快且内存消耗非常有效。在此，我们可以学习这种解决问题的思路（思想），以及可以直接拿走这个算法，用在我们类似的应用上，当然最方便是直接拿走这个板条箱在我们自己Rust项目中使用。

另外，希望CloudFare可以加大开源进程，然我们可以早日用上这个Rust开发的Web代理服务器（代替Nginx）。