필사 모드: 限流算法怎么选 — 固定窗口、滑动窗口与令牌桶的真实差别

引言 — 按每分钟 100 次拦着，却进来了 200 次

你加上了限流。每个键每分钟 100 次。可是看监控，某个客户端在 200 毫秒之内放过去了 200 个请求。翻遍日志，代码也没有问题。

这不是 bug，而是固定窗口计数器被定义好的行为。而在不了解这一点的情况下上线的限流，恰恰保护不了它本想保护的东西。

限流看起来像一行中间件，实际上却是四个决定的集合：用哪种算法、以什么作为键、在分布式环境里把计数器放在哪里、对被拦下的客户端说什么。我们一个一个看。

四种算法与取舍

光看表格，选择范围就收窄了。滑动日志精确但昂贵，固定窗口便宜但不准。实务中剩下的是滑动窗口计数器和令牌桶这两个。

用数字看固定窗口的边界问题

假设上限是每分钟 100 次，窗口在每分钟的第 0 秒重置。客户端这样发。

10:00:59.900  100 个请求   → 10:00 窗口计数器 0 → 100。全部通过
10:01:00.100  100 个请求   → 10:01 窗口计数器 0 → 100。全部通过

200 毫秒之内通过了 200 个。按任意一段连续的 60 秒区间来看，就是上限的两倍。这就是固定窗口的上界。在任何一个 60 秒区间里，最多可能通过 2 倍。

上限越大，绝对损害越大。如果上限是每分钟 6000 次，瞬间就会进来 12000 个。到这个量级，你本想保护的后端会直接被压垮。

把窗口切得更短可以缓解。把每分钟 100 次改成每秒 2 次，边界处超出的绝对量就变小了。不过正常的突发也会被一起切掉，用户体验会变差。

滑动窗口计数器会把上一个窗口的计数按已过去的比例加权后加进来。

当前时刻是 10:01:15 (窗口已过去 25%)
上一个窗口(10:00)的计数 = 100
当前窗口(10:01)的计数 = 20

估算值 = 100 * (1 - 0.25) + 20 = 95
95 < 100 所以通过。再收 5 个就会被拦

这是一个假设上一个窗口的请求均匀分布的近似。就算假设偏了，误差也很小。Cloudflare 曾公开过用自家流量评估这种做法的结果，被错误放行或错误拦截的请求比例在 0.003 个百分点左右。等于用两个计数器拿到了接近滑动日志的精度。

滑动日志的成本也值得点一下。如果把每个请求的时间戳放进 Redis 有序集合，一个元素实际上要占几十字节到接近 100 字节。上限 100、活跃键 100 万个的话就是 1 亿个条目、好几个 GB。和只需要两个计数器的做法相比，是三个数量级的差距。

令牌桶 — 允许突发为什么正好适合 API

令牌桶由两个数字定义：桶的容量和每秒补充速度。请求来了就取出一个令牌，没有就拒绝。令牌按时间比例补充，但不会超过桶的容量。

补充不用定时器来做。请求到来时按经过的时间算出该补多少即可。所以要存的只有令牌数和最后一次补充时刻这两样。

function consume(state, now, capacity, refillPerSec, cost = 1) {
  const elapsed = (now - state.updatedAt) / 1000
  const tokens = Math.min(capacity, state.tokens + elapsed * refillPerSec)

  if (tokens < cost) {
    const wait = (cost - tokens) / refillPerSec
    return { allowed: false, retryAfter: Math.ceil(wait), state: { tokens, updatedAt: now } }
  }
  return { allowed: true, state: { tokens: tokens - cost, updatedAt: now } }
}

这里重要的是它把突发显式地定义了出来。桶容量 20、每秒补充 10 个的话，安静一阵之后一次打出 20 个是被允许的，而长期平均会被锁在每秒 10 个。

这个性质之所以适合 API，是因为真实的客户端并不会均匀地发请求。打开一个页面就会同时发出八个并行请求。用户打开列表再加个筛选，请求就会挤在很短的一段时间里。用严格的滑动窗口强制每秒 10 个，这类完全正常的页面加载就会被切掉。用户觉得服务坏了，而服务器其实很闲。

限流的目的不是把请求的间隔弄均匀，而是把长期负载压在上限之下。令牌桶精确地表达了这个目的。所以大多数公开 API 都用这种方式，并且在文档里直接公开桶容量和补充速度。

按成本加权也很自然地能接上。列表查询算 1 个令牌，生成报表算 20 个令牌，像这样给不同端点定不同的成本，限制的就不再是调用次数而是真实的资源消耗。GitHub 的 API 按查询复杂度给出不同分值，也是同一个思路。

分布式实现 — 原子操作与本地限流的误差

节点有多个就必须共享计数器，而一旦共享就会出现竞态。读取、判断、写入这三步之间被别的节点插进来，上限就被突破了。

Redis 里常用的那个组合也有坑。

# 危险 — INCR 之后进程一旦挂掉，就会永远留下一个没有 TTL 的键
INCR rl:user_8812:1784056020
EXPIRE rl:user_8812:1784056020 60

键要是不过期，那个用户就会带着已经打满的计数器被永久拦住。必须原子地处理。

-- 滑动窗口计数器。KEYS[1]=上一个窗口，KEYS[2]=当前窗口
-- ARGV: 1=上限，2=窗口长度(秒)，3=当前窗口已过去的比例
local prev = tonumber(redis.call('GET', KEYS[1]) or '0')
local curr = tonumber(redis.call('GET', KEYS[2]) or '0')
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local elapsed = tonumber(ARGV[3])

local estimated = prev * (1 - elapsed) + curr
if estimated >= limit then
  return {0, limit, 0}
end

curr = redis.call('INCR', KEYS[2])
if curr == 1 then
  redis.call('EXPIRE', KEYS[2], window * 2)
end
return {1, limit, math.floor(limit - estimated - 1)}

Lua 脚本在 Redis 里以单线程原子执行，所以判断和自增之间没有插队的余地。令牌桶也可以照同样的方式搬过去，而且较新的 Redis 还有为此准备的扩展模块。

那么给每个节点各放一份本地计数器的做法，会错多少呢？如果有 N 个节点，而负载均衡器完美均分，把上限按 N 分之一分给每个节点，总和是对得上的。问题有两个。

分配并不均匀。因为连接保持方式或基于哈希的路由，某个客户端的请求都压到了特定节点上，那么这个客户端只能用掉整体上限的 N 分之一就被拦。实际上限比对外宣称的小得多。

节点数会变。自动扩容让节点变多时，每个节点的份额需要重新计算，不重算的话总允许量就会随节点数成比例增长。给 10 个节点各挂每分钟 100，实际上限就是每分钟 1000。

所以实用的布置是两层。节点本地放一个保护自身的宽松上限，精确的按用户上限交给共享存储来判断。如果访问存储的往返成为负担，也可以让节点从中央桶里成批租用令牌、在本地消费。这是让出一点精度、大幅减少往返次数的折中。

Redis 挂掉时的行为也要事先定好。全部拦截会让限流存储的故障变成全面故障，全部放行则会在那一刻失去保护。通常的做法是放行，但保留节点本地的上限，同时报警。

以什么作为键

用 IP 作为键看起来像默认选项，但它会从好几个方向坏掉。

一个 IP 后面可能有几千个用户。公司网络、学校、运营商的大规模 NAT 都是这样。按 IP 收紧，正常用户群体会被整片拦下。

反过来，攻击者换 IP 很容易。在云上轮换 IP 几乎没有成本，而 IPv6 常常是一台主机就整块分到一个前缀，实质上是无限的。用 IPv6 作键时，必须按上层前缀聚合而不是按完整地址，才有起码的意义。

在代理后面读取客户端 IP 的做法也经常出错。X-Forwarded-For 是客户端可以随意填写的值，所以直接相信列表最前面那个，攻击者就能每个请求都声称一个不同的 IP，把限流架空。必须数清可信代理的数量，从后往前取对应位置上的值。

优先级这样定。如果是已认证的请求，用户标识符或 API 密钥排第一。因为它与套餐挂钩，还要一并加上租户级配额。在认证之前的阶段，也就是登录、注册这类端点，除了 IP 也没什么好用的，那就用 IP，但把上限放宽些，另外再叠加一层按账号标识符的上限。登录尝试必须同时挂上按 IP 的上限和按账号的上限，才能把撞库和针对单个账号的暴力破解一起挡住。

把多层键叠加时，要从最窄的开始检查，并且把命中了哪条上限记进响应里，这样才有可能调试。

429 与客户端的重试

超过上限时用 429。503 表示服务器过载，403 表示没有权限，含义都不一样。要把信息随响应带上，好让客户端能判断自己的处境。

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 12
RateLimit-Limit: 600
RateLimit-Remaining: 0
RateLimit-Reset: 12
Cache-Control: no-store

Retry-After接受秒数或 HTTP 日期，客户端应当把这个值置于自己的退避计算之上。RateLimit 系列的头是 IETF 正在推进标准化的字段，用来告知剩余次数和距离重置还有多久。既有服务一直在用的 X-RateLimit 前缀版本仍然广泛存在，所以两套都发出去也是个办法。

429 响应本身应该很便宜。如果在被拦下的请求里查数据库或做很重的序列化，攻击流量就直接变成了负载。限流判定尽量在前端环节就结束，响应体保持简短。另外不要给 429 加缓存头。中间缓存把 429 存了下来、再返给状态正常的客户端，这种事故是真的会发生的。

接下来是客户端这边。关键在于：被拦下的客户端如果按固定间隔重试，会发生什么。

假设服务器抖了一下，1000 个客户端同时失败。所有人都在 1 秒后重试，那么 1 秒后就会同时到达 1000 个。服务器再抖一下，再在 2 秒后重试，2 秒后又同时到达 1000 个。就算加了指数退避，只要间隔是确定的，重试就仍然是一波同步的浪。这就是惊群。

解法是随机性。

// 不要这么做 — 所有客户端会在同一瞬间醒来
const delay = Math.min(cap, base * 2 ** attempt)

// 全抖动 — 在 0 与上界之间随机取
const delay = Math.random() * Math.min(cap, base * 2 ** attempt)

在 AWS 公开的退避对比实验里，全抖动同时减少了重试总次数和整体完成时间。它甚至优于「先铺上一半上界、只把余下部分随机化」的做法。看上去违反直觉，但把等待时间摊得更开，对减少碰撞就是更有效。

重试实现里还有几条要一并遵守的。服务器给了Retry-After就照它的值来。设定最大尝试次数和整体截止时间，避免无限重试。429 和 5xx 重试，4xx 的其余部分不重试。另外，重试非幂等的请求时必须带上幂等键，防止重复执行。因超时而失败的支付请求如果直接重试，可能会被扣两次款。

结语 — 比算法更该先定的事

加限流时最先要定的不是算法，而是你想保护什么。如果是要守住后端容量，那就该用按成本加权的令牌桶；如果目的是公平分配，那就该用租户级配额；如果是要挡暴力破解，那就该用账号与 IP 叠加起来的窄上限。目的不同，键和上限都会不同。

固定窗口任何时候都可能放过两倍于上限的量，而换成两个计数器的滑动窗口，成本几乎为零。之后剩下的就是把状态告诉客户端这件事。把剩余次数和可重试时刻准确地发下去，做得好的客户端会自己退让。什么都不说，大家就会在同一瞬间再来敲门。