每秒两千万请求，Cloudflare 用什么数据结构来计数？
原文链接：https://blog.cloudflare.com/how-pingora-keeps-count/ 想象一条永不停歇的事件流： 系统需要在任意时刻回答：某类事件出现了多少次？ 这个问题看起来很基础，但当规模放大到 Cloudflare 的量级——数万台机器、每秒超过两千万请求——"基础"的解法往往撑不住。 大多数人第一反应会是哈希表：键是事件类型，值是计数器。每来一个事件，找到对应的键，计数器加一。时间复杂度 O(1)，逻辑清晰，没什么问题。 但在 Cloudflare 的实际场景里，这个方案有两个隐患： 第一，内存浪费。 Pingora 需要监控数百万个不同的源服务器，但任何时刻出现异常的只有极少数。哈希表必须为所有键维护计数器，绝大多数空间用来记录那些根本不需要关注的正常流量。 第二，锁竞争。 多线程并发更新哈希表，尤其是插入新键时，需要加锁。在高并发场景下，锁竞争会把所有并行处理强行串行化，成为性能瓶颈。 在数万台机器上部署这样一个算法，哪怕每个请求只多花几十纳秒，累积起来的代价也相当可观。Cloudflare 决定换一条路。 Pingora 采用的是一种叫做 Count-Min Sketch（CM Sketch） 的概率数据结构，它在空间和速度上都远优于哈希表，代价是计数结果是估算值，可能略有高估，但绝不会低估。 CM Sketch 用一个矩阵来存储计数，矩阵有 H 行、N 列。每一行对应一个独立的哈希函数。 以 H=3、N=4 为例，初始状态： 当事件 "red" 到来时，三行各自用自己的哈希函数计算出一个列索引，然后对应格子的计数器加一。不同行选中的列可能不同，这是设计意图，不是缺陷。 一次 "red" 之后，矩阵可能变成： 接着 "blue" 到来，假设它在第2行和 "red" 发生了碰撞，都映射到第3列： 再经过 "blue, red, red, red, blue, red" 这一轮，目前为止共有 5 次 "red"、3 次 "blue"，矩阵最终变为： 查询某个事件的计数时，算法取它在各行对应格子中的最小值。 碰撞导致某些格子被多个事件共享，数值偏高，但只要有一行没有发生碰撞，最小值就能反映真实计数。两个事件在所有行都碰撞的概率是 关键性质：只会高估，不会低估——因为算法从未丢弃任何计数。 CM Sketch 的操作本质上只有：哈希、数组寻址、原子加法。这意味着它可以完全无锁实现。 Pingora 的核心实现大致如下： 每一行用 Cloudflare 用 100 万个不同的键、1 亿个事件做了基准测试，对比三种方案： 单线程下没有锁竞争，CM Sketch 仍然比 naive 快 5 倍，比 optimized 快 4 倍——快的原因是操作更简单，路径更短。多线程高竞争下，CM Sketch 和 optimized 速度相当，都比 naive 快 7 倍，因为两者的热路径都是原子操作，瓶颈相同。 内存差距极为悬殊：pingora-limits 峰值内存仅为 naive 的 1/2000，optimized 的 1/1300。哈希表必须为每一个键维护一条记录，而 CM Sketch 的空间由参数 H×N 完全决定，和键的数量无关。 pingora-limits 在生产环境中最典型的使用场景是连接数限制。 当 Cloudflare 的服务器向某个源服务器发起的连接数过多时，为了防止源服务器和自身基础设施过载，系统会开始拒绝新请求并返回 503 错误。 具体做法：每个进入的请求，都会根据客户 ID + 服务器 IP + 主机名组合成一个计数键，调用 在参数选择上，Cloudflare 将两个不相关客户之间的理论碰撞概率控制在约 1/2^52 的量级。加上拒绝阈值本身远高于正常流量水位，即便碰撞导致计数轻微高估，也不足以触发误判。 对于那些要求精确计数、完全不能接受误判的场景，CM Sketch 也有用武之地——用作第一阶段过滤器。 低频事件被 CM Sketch 拦截，不进入后续处理；只有超过阈值的事件才进入精确的哈希表计数。这样，哈希表只需要处理真正需要关注的少数热点事件，内存占用极小，同时精度不受任何损失。 CM Sketch 的思路本质上是一种工程上的权衡：用少量可控的不确定性（可能高估，不会低估），换取空间和速度上的极大优势。 这种权衡在 Cloudflare 的场景下是划算的：被保护的目标（源服务器）数量极多，但任意时刻需要重点关注的只是少数；哈希表为所有目标维护计数的做法，既浪费内存，又在高并发下引入锁竞争。CM Sketch 绕开了这两个问题，同时在生产参数下将误判概率压到了可以忽略不计的程度。 pingora-limits 目前已在 GitHub 开源，感兴趣的读者可以直接查阅代码和基准测试： https://github.com/cloudflare/pingora/tree/main/pingora-limits本文基于 Cloudflare 官方博客，介绍其代理框架 Pingora 中的计数库 pingora-limits，以及背后采用的概率数据结构 Count-Min Sketch。
从一个简单的问题说起
red, blue, red, orange, green, brown, red, blue, ...最直觉的方案：哈希表
Count-Min Sketch：概率换资源
结构长什么样
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |计数过程
| 0 | 1 | 0 | 0 | ← 第1行，red 映射到第2列
| 0 | 0 | 1 | 0 | ← 第2行，red 映射到第3列
| 1 | 0 | 0 | 0 | ← 第3行，red 映射到第1列| 1 | 1 | 0 | 0 |
| 0 | 0 | 2 | 0 | ← 第3列被 red 和 blue 共用，产生碰撞
| 1 | 0 | 0 | 1 || 3 | 5 | 0 | 0 |
| 0 | 0 | 8 | 0 | ← red 和 blue 在此行始终碰撞，计数为 5+3=8
| 5 | 0 | 0 | 3 |查询：取最小值
1/N^H，以本例的参数为 1/64，参数选得越大，碰撞概率越低。Rust 实现：无锁，几行代码
pub struct Estimator {
estimator: Box<[(Box<[AtomicIsize]>, RandomState)]>,
}
impl Estimator {
pub fn incr<T: Hash>(&self, key: T, value: isize) -> isize {
let mut min = isize::MAX;
for (slot, hasher) in self.estimator.iter() {
let hash = hash(&key, hasher) as usize;
let counter = &slot[hash % slot.len()];
let current = counter.fetch_add(value, Ordering::Relaxed);
min = std::cmp::min(min, current + value);
}
min
}
}AtomicIsize 存储计数器，用 fetch_add 做原子加法，整个过程不需要任何互斥锁。性能对比：数字说话
Mutex<HashMap<u32, usize>>，每次操作都要抢锁DashMap<u32, AtomicUsize>，分片哈希表，减少锁粒度速度（每次 incr 操作耗时，越低越好）
pingora-limits naive optimized 单线程 10ns 51ns 43ns 八线程 212ns 1505ns 212ns 内存（越低越好）
峰值内存 总分配次数 总分配字节数 pingora-limits 26,184 字节 9 次 26,184 字节 naive 53,477,392 字节 20 次 71,303,260 字节 optimized 36,211,208 字节 491 次 71,307,722 字节 生产中怎么用
incr 增加计数；请求结束后再减回来（incr 支持负值）。若当前计数超过阈值，请求被拒绝。两阶段过滤：精度与效率兼顾
小结