rate limiting 逐帧推演

令牌桶 · 漏桶 · 窗口计数

限流回答的问题是：单位时间内放行多少请求，超出的如何处置。它既用于保护后端不被突发流量打垮，也用于按套餐配额计费。难点不在计数，而在对时间的建模——同一串请求，五种算法给出的放行与拒绝结果可以完全不同。

本页把五种算法放在同一条到达序列上：令牌桶与漏桶约束速率，固定窗口、滑动日志与滑动计数约束窗口内的计数，末节并排对照给出五者的放行结果与选型。

1 · 令牌桶与突发容量

令牌桶（token bucket）把限速拆成两件独立的事：令牌以恒定速率 $r$ 注入桶中，桶至多存 $C$ 个，注满即弃；每个请求到达时取走一个令牌，取得到就放行，取不到就拒绝并回 HTTP 429。

教科书常把注入描述成一个按 $r$ 触发的后台定时任务。实现里没有这个任务：core/rl.ts 的 tokenBucketSim 在每个请求到达时才按距上次的流逝时间一次性补齐，即 $T \gets \min(C,\, T + \Delta t \cdot r)$ 。惰性补充与定时注入在判定上等价，却省掉了空闲期的全部定时器开销。

桶能累积令牌，这是它与窗口计数最大的不同。一段空闲之后桶被注满，随之而来的流量可以一次放行至多 $C$ 个，之后才回落到 $r$ 的稳态速率。写成约束：任意长为 $\tau$ 的区间内放行数不超过 $C + r\tau$ 。 $C$ 是允许的突发额度， $r$ 是长期平均速率的上限，两者互不干涉。

图 1-1 · 令牌桶沿时间轴的逐请求判定，左侧水位条为当前令牌数。可调 capacity 与 rate 观察突发额度与稳态速率的分离，并在突发与稀疏两条到达序列间切换。

警示 · 令牌桶约束的是长期平均速率，不是瞬时并发。 $C$ 越大越能吸收突发，后端也就越可能在极短时间内同时承受 $C$ 个请求。若下游怕的是瞬时峰值而非长期超量，该用漏桶把输出整流。

2 · 漏桶的排队整流

漏桶（leaky bucket）把请求视为灌进桶里的水：桶底以恒定速率 $l$ 漏出，漏出即请求被实际处理。新请求到达时若桶装得下就接纳并排队，装不下就溢出拒绝。桶充当缓冲队列，把突兀的到达削平成平滑的输出，代价是被接纳的请求要等：队列长 $C$ 、漏速 $l$ 时，最坏排队延迟为 $C / l$ 。

漏桶有两种形态，文献里分别叫 as a queue 与 as a meter [3]。上面描述的是前者：真的排队，真的匀速漏出。后者不排队，只用同一套水位算术判断到达是否合规，合规就立即放行，ATM 的 GCRA 即属此类。两者的关系是 as a queue 为 as a meter 的特例。

图 2-1 · 漏桶的逐请求判定，左侧水位条为当前积压水量，越接近顶部越接近溢出。可调 capacity 与 leak 观察积压的涨落。

注 · core/rl.ts 里的 leakyBucketSim 实现的是 as a meter 的水位算术，它与 tokenBucketSim 在镜像参数下逐点恒等。令 $L = C - T$ （ $T$ 为令牌数， $L$ 为水位）：补令牌 $T \gets \min(C, T + \Delta t\, r)$ 等价于漏水 $L \gets \max(0, L - \Delta t\, r)$ ；放行条件 $T \ge 1$ 等价于 $L + 1 \le C$ ；取走一个令牌等价于水位加一。穷举 7 种容量 $\times$ 5 种速率 $\times$ 7 条到达序列共 245 组，两者的判定序列全部逐点相同（core/rl.test.ts）。图 4-1 里 Token Bucket 与 Leaky Bucket 两条泳道因而永远一致：差别不在准入，在被接纳之后——令牌桶立即放行，漏桶把请求压在队列里等匀速漏出。时间轴只画准入判定，画不出这一层。

3 · 固定窗口与滑动窗口

窗口计数不跟踪速率，只在一段时间窗口内数数：窗内放行数达到 limit 即拒绝后续。窗口怎么切，直接决定行为。

3.1 · 对齐格子的独立计数

固定窗口把时间切成对齐的格子 $[0, W), [W, 2W), \dots$ ，每格独立计数，跨格清零。实现最省：一个整数加一个窗口编号。代价是交界处的两倍配额。limit 个请求排在一格末尾、另 limit 个排在下一格开头，两拨相隔可以任意短，而它们分属两格，都会放行。

3.2 · 逐条时间戳的回望

滑动日志为每个放行的请求记一条时间戳，判定时先剔除落在 $(t - W,\, t]$ 之外的旧戳，再看存量是否小于 limit。任意长为 $W$ 的回望窗口内放行数都不超过 limit，交界处不存在放宽。

它的存储成本常被写成「随请求数增长」，那只对「连被拒的请求也记戳」的变体成立。本页的实现只给放行的请求记戳，存量因而恒不超过 limit：边界突刺与突发两条演示序列下时间戳峰值正好触到 3，均匀序列下只到 2。真正的代价在时间，每次判定要扫一遍窗口内的戳。

3.3 · 两窗计数的加权估算

滑动计数只保留当前窗与上一窗两个计数，用上一窗按重叠比例加权，估算最近 $W$ 秒的请求数：

\mathrm{est} = \mathrm{prev} \cdot \frac{W - (t - t_{\mathrm{win}})}{W} + \mathrm{cur}

存储回到 $O(1)$ ，交界处的放宽被近似抹平。加权假设上一窗内的请求均匀分布，所以只是估计：实际分布越集中，偏差越大。

图 3-1 · 三种窗口切法在同一条序列上的逐请求判定，虚线为窗口边界。可用 algorithm 下拉切换算法、调 limit，并在边界突刺与均匀两条序列间对比。

警示 · 边界突刺序列把 6 个请求排在 $t = 1.6, 1.7, 1.8, 2.0, 2.1, 2.2$ ，取 $W = 2$ 、limit 为 3。固定窗口全部放行：前三个填满 $[0, 2)$ ，后三个落进新格重新计数，0.6 秒内放行 6 个，是配额的两倍。同一序列下滑动日志放行 3 个；滑动计数放行 4 个，加权估算在 $t = 2.1$ 处给出 $3 \times 0.95 = 2.85 < 3$ ，漏掉了一个。

4 · 同一序列下的算法对照

把同一条到达序列同时喂给五种算法，容量与上限统一取 $N$ ，桶速率 1/s，窗口 $W = 2$ s。

图 4-1 · 五种算法在同一条序列上的放行 / 拒绝结果，右侧为各自的放行总数。可调容量上限

N

并在三条序列间切换。

取 $N = 3$ ：12 个请求的突发序列（ $t = 0$ 处 6 个，随后 $t = 1, 2, 3$ 各 1 个， $t = 7$ 处 3 个）下，令牌桶与漏桶各放行 9 个，固定窗口与滑动日志各 8 个，滑动计数 7 个；边界突刺序列下固定窗口放行全部 6 个，滑动计数 4 个，其余三者各 3 个；每秒一个请求的均匀序列下五者全部放行。差异只在到达集中时显现，均匀流量分不出算法。

4.1 · 选型对照

桶类约束速率，窗口类约束窗口内计数。「最坏连续放行」一栏给出各算法在最不利的到达分布下能连发多少个请求，是选型时真正要看的量。
算法	最坏连续放行	输出平滑度	存储成本	精度	典型场景
Token Bucket	$C$ 个	无整形	O(1) 两个数	精确	API 网关默认；容忍短时突发、只控长期均速
Leaky Bucket	入口 $C$ 个，出口恒为 $l$	最平滑	O(1) + 长 $C$ 的队列	精确	保护处理能力恒定的下游；写入 / 出口整形
Fixed Window	$2 \times$ `limit` 个	差	O(1) 最省	交界处放宽一倍	粗粒度计数；对交界突刺不敏感的场景
Sliding Log	`limit` 个	中	O(`limit`) 条时间戳	精确	低频高价值接口（登录 / 短信），要求严格不超
Sliding Counter	约 `limit` 个	较好	O(1) 两个计数	近似	大规模通用限流；省内存又抹平交界突刺 [2]

没有一种算法在所有列上占优。要削峰整流选漏桶，要吸收突发选令牌桶，只需粗粒度计数选窗口类，在意交界突刺就在窗口类里选滑动计数。生产系统常叠加多层，如网关层用固定窗口做粗筛、业务层再用令牌桶按配额精算。分布式部署下，桶的水位与窗口的计数都要放进共享存储，读写这份状态的开销往往比算法本身更值得优化——这一点与缓存淘汰面对的是同一类问题。

5 · 参考文献

Turner, J. S. (1986). New directions in communications (or which way to the information age?). IEEE Communications Magazine, 24(10), 8–15.
Cloudflare. (2017). How we built rate limiting capable of scaling to millions of domains. The Cloudflare Blog.
Wikipedia contributors. Leaky bucket. Wikipedia.