rate limiting 逐帧推演

令牌桶 · 漏桶 · 窗口计数 · 五法对照

限流回答一个问题：单位时间内放行多少请求、超出的怎么办。它保护后端不被突发流量打垮，也用于按套餐配额计费。难点不在「计数」，而在对时间的建模方式——同一串请求，不同算法给出的放行 / 拒绝结果可以完全不同：有的允许突发、有的强制整流、有的在窗口边界漏出双倍流量。每节给定一条请求到达序列，单步推进时间轴，看桶的水位 / 窗口计数随时刻变化，右侧代码逐行点亮。四节：令牌桶 → 漏桶 → 窗口计数 → 五法对照。

1 · 令牌桶：积攒令牌，允许 burst

令牌桶 (token bucket) 把「限速」拆成两件独立的事：一个后台进程以恒定速率 rate 往桶里投令牌（桶最多装 capacity 个，投满即弃）；每个请求到达时取走 1 个令牌，取得到就放行，取不到就拒绝。

关键在于桶能累积令牌：一段时间没有请求，令牌会累积到 capacity。于是当流量突然到来时，可以一次性放行多达一整桶 (burst)，之后才回落到 rate 的稳态速率。这正是它区别于漏桶的地方——令牌桶容忍突发，只约束长期平均速率。

下面给定一条请求到达序列（圆点 = 一个请求，横轴 = 时间）。调节桶容量与投放速率，单步推进：每个请求先按流逝时间补令牌，再判定放行 / 拒绝，左侧水位条是当前令牌数。

burst 的代价：capacity 越大，越能吸收突发，但也意味着后端可能在极短时间内承受 capacity 个并发。令牌桶约束的是长期平均速率，不是瞬时并发——若后端怕瞬时峰值，应改用下文的漏桶强制整流。

2 · 漏桶：排队，匀速漏出

漏桶 (leaky bucket) 把请求想象成灌进桶里的水：桶底有个孔，以恒定速率 leak 漏出（漏出 = 请求被实际处理）。新请求到达时若桶装得下就接纳并排队，装不下（已达 capacity）就溢出拒绝。

与令牌桶对照看：令牌桶约束的是取令牌的速率，桶满时能一次放行一整桶 → 容忍突发；漏桶约束的是漏出的速率，无论灌入多猛，出口永远是恒定的 leak → 强制整流。桶在这里是缓冲队列，把突兀的到达削平成平滑的输出。

下面同一条到达序列。调节桶容量（队列长度）与漏出速率，单步推进：每个请求先按流逝时间漏水，再看桶能否再容下 1 个。左侧水位条是当前积压的水量——越接近顶部越危险。

排队的代价是延迟：漏桶把请求压在队列里等匀速漏出，被接纳的请求可能要等待而非立即处理。它适合保护处理能力恒定的下游（如写入限速）；若希望「能快则快、只防长期超量」，前文的令牌桶更合适。

3 · 窗口计数：从固定窗口到滑动窗口

最直觉的限流是数数：每个时间窗口内最多放 limit 个。但「窗口」怎么切，直接决定了行为。这里把三种做法放在同一条序列上对照——用上方的 algorithm 下拉切换：

Fixed Window（固定窗口）：时间切成对齐的格子 $[0,W), [W,2W)\dots$ ，每格独立计数。实现最简，但有边界突刺。

Sliding Log（滑动日志）：为每个放行请求记时间戳，判定时只看最近 W 秒内的存量。精确，但要存下所有时间戳。

Sliding Counter（滑动计数）：只留当前窗与上一窗两个计数，用上一窗按重叠比例加权估算。 $O(1)$ 存储，近似抹平突刺。

先试 Fixed Window:默认序列里 6 个请求挤在 t=2 边界两侧（窗口 W=2）。固定窗口会在不到 1 秒内放行 2×limit 个——上一窗末尾放 limit 个、下一窗开头又放 limit 个。再切到 Sliding Log / Counter 看它们如何压住这股突刺。

**三者的取舍：**固定窗口存一个整数、最省，但边界处可瞬时放行 2×limit；滑动日志精确无突刺，但存储随流量增长；滑动计数只存两个整数，用线性加权把误差控制在很小范围——这是 Cloudflare 等大规模场景的常用折中。要严格平滑请改用前文的令牌桶 / 漏桶。

4 · 五法对照：同一串请求，谁放谁拒

把完全相同的一条到达序列，同时喂给五种算法（统一参数：容量 / 上限 = 3，桶速率 = 1/s，窗口 W = 2s）。每条泳道是该算法对这串请求的放行 / 拒绝结果，右侧是放行总数。切换序列，观察它们的差异何时显现。

4.1 · 选型对照

桶类约束「速率」、窗口类约束「窗口内计数」；前者天然平滑，后者实现简单。突发容忍一栏对窗口类不直接适用（取决于序列落点）。
算法	突发容忍	输出平滑度	存储成本	精确度	典型场景
Token Bucket	高（可 burst 一整桶）	中	O(1)	精确	API 网关默认；允许短时突发、只控长期均速
Leaky Bucket	无（强制整流）	最平滑	O(1)+队列	精确	保护处理能力恒定的下游；写入 / 出口整形
Fixed Window	—	差	O(1) 最省	边界放 2×	实现最简、粗粒度计数；对突刺不敏感的场景
Sliding Log	—	中	O（请求数）	精确无突刺	低频高价值接口（登录 / 短信），要求严格不超
Sliding Counter	—	较好	O(1) 两计数	近似（误差小）	大规模通用限流（Cloudflare 式）；省内存又抹平突刺

没有「最好」的限流算法，只有匹配需求的：要削峰整流选漏桶，要容忍突发选令牌桶，要简单计数选窗口类（在意突刺就用滑动计数）。生产系统常叠加多层——如网关层粗粒度固定窗口 + 业务层精细令牌桶。

**和别的系列串起来看：**限流是路由 / 网关层最常见的一道闸门；它的「桶」与「窗口」状态在分布式部署下要放进共享存储（如 Redis），与缓存淘汰同属「在有限资源下决定取舍」的系统设计基本功。