从零实现限流器：令牌桶、滑动窗口，以及它们的误差

21 分钟读完0 次浏览

固定窗口的边界双倍突发到底有多严重、滑动窗口计数怎么用分桶逼近、令牌桶的容量与速率是两件事——三个算法各给实现与实测方法，再给一份 Redis + Lua 的原子版和选型表。

限流我最早是照抄的：INCR 一下、到阈值就拒绝、顺手 EXPIRE 一下。跑了半年没出事，直到有一次运营做活动，某个接口在整分钟前后各来了一波流量，监控显示"配额的 2 倍"从同一批 IP 上过去了——那就是固定窗口的边界双倍突发，第一次被我在线上撞见。

这篇把三个算法各自精确的行为、Go 实现、分布式的原子做法、以及我自己打流测出来的误差量级写一遍。先声明：下面所有数字都是我本机的示例环境（8 核 / Go 1.22 / 本机回环，单进程），只用来说明量级和形状，不代表任何线上或厂商数据。

一、三个算法各自到底在做什么

固定窗口：把时间切成对齐挂钟的格子（now.Truncate(window)），格子里计数，到上限就拒，下一格计数归零。实现最省，但格子边界是它的全部问题：

limit = 100 / 1s，窗口边界对齐整秒

t=0.90s   ── 窗口 A ──  发 100 个 → 全过（A 用了 100/100）
t=1.00s   ── 窗口 B ──  计数归零
t=1.10s                 再发 100 个 → 全过（B 用了 100/100）
          ↑ 在 t∈[0.90, 1.10] 这 200ms 里通过了 200 个，是配额的 2 倍

注意这不是"某次运气不好"：卡着边界就能每格拿 2 倍，长期平均通过量是配额的 2 倍。

滑动窗口日志：把每个请求的通过时刻记下来，判断"过去 window 内的条数 < limit"。它是三个算法里唯一精确的，代价是内存 O(limit)——limit=10000 时每个 key 要存一万个时间戳（8 字节时间戳就是 80KB），这在 Redis 里是不可接受的。它适合"窗口很小、limit 很小"或者本地单机限流。

滑动窗口计数（加权近似）：只存两个计数器，用上一格的残留加权估算：

est = cur + prev × (1 - f)        f = 本格已过的比例（0 ≤ f < 1）

f→0 时几乎把上一格全算进来，f→1 时几乎不算。它把"记账"从 O(limit) 压到 O(1)，代价是假设上一格的流量是均匀分布的。这里要先记一笔：最坏情况是流量全堆在上一格的结尾（紧贴边界），此时区间 [t-W, t] 里上一格的真实贡献远大于 prev×(1-f)，估算偏低，仍然能放过接近 2×limit——它是把边界问题变小了而不是消灭了；真正消灭它的是下面那个分桶求和的版本，以及日志版。

令牌桶：桶里放"许可"，容量 b，补充速率 r。请求来取一个令牌，取不到就拒绝（或等待）。它的两个参数是两件事：r 决定长期平均速率，b 决定能承受多大的瞬时突发。实现上是惰性补充：

tokens(t) = min(b, tokens(t₀) + (t - t₀) × r)

没有后台定时器、不跑 ticker，只有请求到来时才算一次。所以它天然不会"整点发放"，令牌是连续补充的。

漏桶/队列式（常被和令牌桶混为一谈）：请求进队列，出口以固定速率 r 出队，队列长度就是缓冲区。和令牌桶最大的区别是输出行为：令牌桶"超了就拒绝"，漏桶"超了就排队"——它把突发变成了延迟，而不是拒绝。要控制出向速率（保护第三方接口、给网卡整形）时才用它；要保护自己时，排队只会把延迟堆到用户身上。把令牌桶的突发关掉（b=1）行为接近严格漏桶，但只会拒绝而不会延迟。

二、golang.org/x/time/rate 的正确用法

这是我最常推荐的方案：单机令牌桶，惰性补充，没有额外依赖。真正需要想清楚的是四个入口该用哪个：

lim := rate.NewLimiter(rate.Limit(100), 200) // 100 rps，允许瞬时突发 200

// ① Allow：不等待，立刻返回能不能走 —— 对外接口的默认选择
if !lim.Allow() {
	writeTooMany(w, resetAfter) // 429 + Retry-After
	return
}

// ② AllowN：一次要 n 个令牌（比如这个请求按业务权重折算成 10 次配额）
if !lim.AllowN(time.Now(), 10) { ... }

// ③ Reserve：先问"最早什么时候能走"，自己决定怎么处理这个等待
r := lim.Reserve()
if !r.OK {
	return errors.New("n 超过 burst，永远等不到") // ReserveN 里 n > burst 时 OK=false
}
if d := r.Delay(); d > 0 {
	setRetryAfter(w, d) // 拿来当 Retry-After，或者丢进自己的延迟队列/定时器
	r.Cancel()          // 决定不等了，必须 Cancel 把令牌还回桶里
	return
}

// ④ Wait：内部就是 Reserve + sleep，受 ctx 约束 —— 出向调用、后台任务
if err := lim.Wait(ctx); err != nil {
	return err // ctx 被取消，或 deadline 早于"可以放行"的时刻
}

几个我踩过的点：

  • Reserve 拿 Delay() 做什么：它是"从现在起还要等多久"，可以直接换算成 Retry-After 返回给客户端；也可以放进自己的延迟队列，避免像 Wait 那样占住一个 goroutine。但决定不使用这次预留时必须 Cancel()，否则令牌被白白扣走，等于自己给自己制造幽灵占用。
  • Wait 会占 goroutine：每个等待者一个 goroutine 加一个定时器。高并发下用 runtime/metrics 的 /sched/goroutines:goroutines 盯一下就明白了；Wait 适合的是"调用方本来就在 goroutine 里且可以等"，不是"入口处拦流量"。
  • 桶初始是满的：tokens = b。服务刚启动、或者限流配置刚生效时，会立刻放 b 个请求过去。b 设得太随意，等于给了攻击者一个免费的突刺。
  • SetLimit / SetBurst 支持运行时热更新，但把 burst 改小不会收回已经发出去的令牌；rate.Every(200*time.Millisecond) 可以把"每 200ms 一个"写成 Limit。另外 Delay 依赖 Go 的运行时时器，只有毫秒级精度，别指望微秒级。

三、自己写一个滑动窗口计数

x/time/rate 解决的是"单机 + 允许突发"，但当我要的是"任意 1 秒不超过 100 次"这种承诺时，令牌桶给不了——它给的是"长期平均 100/s + 最多突发 b"。这时候我会用分桶版滑动窗口，把窗口切成 buckets 个桶，按桶滚动淘汰：

type Window struct {
	mu      sync.Mutex
	win     time.Duration // 窗口总长
	bucket  time.Duration // 单桶长度 = win / buckets
	limit   int64
	counts  []int64
	total   int64 // running total：避免每次请求都 O(buckets) 求和
	cur     int
	curFrom time.Time
}

func (w *Window) Allow(now time.Time) bool { // now 作为参数，测试时可注入
	w.mu.Lock()
	defer w.mu.Unlock()
	w.advance(now)
	if w.total >= w.limit {
		return false
	}
	w.counts[w.cur]++
	w.total++
	return true
}

func (w *Window) advance(now time.Time) {
	if w.curFrom.IsZero() {
		w.curFrom = now.Truncate(w.bucket)
		return
	}
	elapsed := now.Sub(w.curFrom)
	if elapsed >= w.win { // 空闲超过整个窗口：全清，别逐桶推进
		clear(w.counts) // Go 1.21+ 的内置 clear；老版本循环置零
		w.total, w.cur, w.curFrom = 0, 0, now.Truncate(w.bucket)
		return
	}
	for elapsed >= w.bucket {
		w.cur = (w.cur + 1) % len(w.counts)
		w.total -= w.counts[w.cur] // 关键：清桶时用减法维护总和
		w.counts[w.cur] = 0
		w.curFrom = w.curFrom.Add(w.bucket)
		elapsed -= w.bucket
	}
}

几个实现细节值得单独说：

  • running total 是必须的。如果每次请求都 for _, c := range counts { sum += c }，桶数是 60 就是每个请求 60 次加法，还都在锁里——P99 会被它拖出来。
  • 桶数决定误差，误差上限就是一个桶。N 个桶覆盖的区间是"N-1 个满桶 + 当前这个只填了一部分的桶"，所以实际窗口在 win - bucket 到 win 之间抖动：桶越少，窗口越短越"严"，流量平滑时表现为偶尔多拒几个。这就是"用误差换内存和推进开销"。
  • 别把桶数设成和 limit 一样大。limit=10000/min 时，60 个桶每 key 是 60×8 = 480 字节计数，加上结构体开销大约 600 字节；100 万个 key 就是 600MB。反过来，只存两个计数器的加权版每 key 只要十几字节——同一条规则下内存差 40 倍。
  • time.Time.Truncate 会剥掉单调时钟读数（它按墙上时钟取整）。对时间跳变敏感的场景，我改成自己存一个 start 时间点、用差值算，避免 NTP 回拨把桶推进弄乱。
  • 每个 key 一把锁会成为瓶颈。高 QPS 下按 key 哈希分片（比如 256 个 shard，每个 shard 一把锁 + 一张 map），比全局 map + 全局锁好得多；分片后记得给 map 加淘汰（TTL 或 LRU），否则 key 无限增长就是内存泄漏。

四、分布式版：Redis + Lua 的原子实现

多实例部署时，每个实例本地各算一份配额等于把总量放大了 N 倍，所以必须有一个共享计数器。固定窗口的 Lua 版我长这样：

-- KEYS[1] = key 前缀（如 rl:uid:42）  ARGV[1] = limit  ARGV[2] = 窗口毫秒
-- 返回 {allowed, remaining, reset_ms}
local t  = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local win, limit = tonumber(ARGV[2]), tonumber(ARGV[1])
local slot  = math.floor(now / win)          -- 窗口序号进 key，天然隔离各窗口
local key   = KEYS[1] .. ':' .. slot
local reset = (slot + 1) * win - now         -- 距窗口结束还有多少毫秒

local n = redis.call('INCR', key)
if n == 1 then
  redis.call('PEXPIRE', key, win * 2)        -- 多留一个窗口，防边界误判
end
if n > limit then
  return {0, 0, reset}
end
return {1, limit - n, reset}

为什么必须 Lua。 不用脚本就得写 INCR 然后 EXPIRE，而这中间有一段窗口期：进程被 kill、连接断开、或者恰好赶上 key 刚过期，都会留下一个没有 TTL 的计数器 key——那个用户从此被永久限流。这是个自伤式故障（自己把自己封死），而且会静静地累积。另一种写法是先 GET 判断再 INCR，那连"判断"和"写"都不是原子的，并发下必然超发。放进 Lua 之后，Redis 单线程执行脚本、中途不会被其他命令插入，读-判断-写就是一个原子操作；顺带把 2~3 次 RTT 压成 1 次。

Redis 7 的 EXPIRE key seconds NX（只在没有 TTL 时设置）能避免 TTL 被反复刷新，但 INCR 和 EXPIRE 仍然是两条命令，中间出事照样漏 TTL——所以我还是走 Lua，细节以 Redis 文档为准。

其它几个工程点：

  • 时间用 Redis 的 TIME，不用应用机的 time.Now()：多个实例时钟有漂移时，同一秒可能被算进两个不同的格子。Redis 5 起脚本用效果复制，非确定性命令可用，更早的版本需要 redis.replicate_commands()。
  • SCRIPT LOAD + EVALSHA：省掉每次把脚本体传过去；遇到 NOSCRIPT（脚本被清）要回退到 EVAL 重新加载。Cluster 下同一脚本的所有 key 必须在同一个 slot，单 key 天然满足，多 key 用 hash tag（{uid:42}:api）。
  • 把剩余配额返回给前端：Lua 里顺手算出来的 remaining 和 reset_ms，正好映射成 X-RateLimit-Remaining 与 Retry-After，前端不必靠猜。
  • 代价是网络：每次检查一次 Redis 往返，同机房 0.2~1ms，跨机房几毫秒到几十毫秒，这直接就是限流器的分辨率下限：你的窗口再精确到毫秒也没用，粒度其实是 RTT。10 万 QPS 都打一次 Redis，连接数和单线程 CPU 都吃不消。想要更细的平滑度可以用 GCRA（redis-cell 那个模块的思路）把令牌桶写进 Lua，但一样逃不掉 RTT。

所以我线上的常见形态是两级：本地用 x/time/rate 放行（配额按实例数分摊），每隔一小段时间从一个共享的"全局余额"里续借。误差就等于同步间隔内的超发量，换来的是把 RTT 从关键路径上彻底拿掉。

五、误差实测：怎么测，测出什么

先说测量方法，因为我第一版测量本身是错的：

  • 打流不要用 time.Sleep(interval)，它会累积漂移（每次都要加上调度开销，越跑越慢）。要用绝对时刻对齐：算好第 i 个请求的目标时刻，然后 sleep 到那个时刻。
  • 统计要按"滑动窗口"看，不能只按整秒看。按整秒统计正好会被固定窗口的边界对齐掩盖掉——两边切法一样，突刺就"消失"了。所以要额外维护一个"任意 1 秒内最大通过数"。
// 打流：绝对时刻对齐，避免累积漂移
interval := time.Second / time.Duration(qps)
start := time.Now()
for i := 0; i < total; i++ {
	if d := time.Until(start.Add(time.Duration(i) * interval)); d > 0 {
		time.Sleep(d)
	}
	fire() // 别在这里无限起 goroutine，用固定大小 worker pool
}

下面是示例环境下打出来的形状（limit = 100 / 1s，客户端在 t=0.90s 和 t=1.10s 各打一波 100）：

算法t=0.90s 通过t=1.10s 通过这 200ms 内合计
固定窗口（对齐整秒）100100200
滑动窗口计数（60 桶）1000~2约 100
滑动窗口日志1000100

持续打流时三个算法的平均表现是一样的（都稳定在 100/s，超出的部分被拒），差别全在"任意滑动窗口内的最大值"。这一列才是限流器真正的指标：

算法任意 1s 滑动窗口内最大通过数（配额 100）说明
固定窗口约 200卡边界即可复现，每格都能拿 2 倍
滑动窗口计数（10 桶）约 110~120桶粗，量化误差大
滑动窗口计数（60 桶）约 100~105误差收敛到一个桶
滑动窗口日志100精确，代价是内存
令牌桶 b=100, r=100/s约 200，但只有第一次突发一次性用完，之后严格按 r 补充；不承诺"任意窗口 ≤ 100"

最后一行是我做了这个测试才发现的事：令牌桶在数值上也能在一个滑动秒里放过 200 个（一次突发 100 + 这一秒补充的 100）。它和固定窗口的区别不在数字，而在突发的性质：固定窗口的 2 倍突发是边界对齐造成的，可以被重复卡点，长期平均就是 2 倍配额；令牌桶的突发是一次性的、与挂钟边界无关，用完以后长期平均精确等于 r。想同时要"任意窗口 ≤ N"和"允许突发"，只能选滑动窗口日志，或者把 b 调到 1 附近。

六、选型表与限流的维度

场景我的选择理由
保护自己的下游/DB（单机）x/time/rate 令牌桶 + Wait零网络开销、允许突发、Wait 就是背压
对外 API 按用户/租户配额Redis 固定窗口（Lua）一次 RTT、内存最小、能顺带返回剩余配额
必须"任意窗口 ≤ N"滑动窗口日志唯一精确的方案，代价是内存 O(N)
长期平均 + 允许突发令牌桶（本地为主 + Redis 定期同步）容量换突发，速率换均值
控制出向速率、保护第三方漏桶/队列整形要平滑输出，代价是排队延迟
流量极大、允许小误差本地分片配额 + 定期同步把 RTT 从关键路径拿掉，误差 = 同步间隔

维度上，我一般同时挂三层：全局（保护整个集群）、租户/用户（配额计费单位）、接口/路由（防止一个慢接口吃掉全部配额）。几个容易做错的地方：

  • IP 不是人：NAT 后面一整栋办公楼共用一个出口 IP，按 IP 做严格配额等于误伤一大片；它适合做粗粒度防御，不适合做业务配额。IPv6 还要考虑按前缀聚合。
  • UID 要先认证：没认证时 UID 是攻击者自己填的，等于没有维度；这种情况下限流只能退化成 IP 维度 + 全局兜底。用户"注册即送配额"也是同一个问题。
  • 组合键会放大 key 数量：uid + path 让 Redis key 数直接相乘，一定要给 TTL 或冷热淘汰，否则内存比流量先出问题。
  • 别把高基数维度塞进指标：限流的命中数按 path、租户或状态码打标签可以，按 uid 打标签会让时间序列直接爆炸。

七、被限流之后：429 要给出路

限流器拒绝请求的方式，和限流算法一样重要。我的响应固定带这几个东西：

w.Header().Set("Retry-After", strconv.Itoa(retryAfterSeconds)) // 整数秒，或 HTTP-date
w.Header().Set("X-RateLimit-Limit", strconv.FormatInt(limit, 10))
w.Header().Set("X-RateLimit-Remaining", strconv.FormatInt(remaining, 10))
w.Header().Set("X-RateLimit-Reset", strconv.FormatInt(resetUnix, 10))
w.WriteHeader(http.StatusTooManyRequests) // 429

Retry-After 要来自限流器实际算出的 reset 时刻（Lua 里那个 reset_ms，或者 Reserve().Delay()），不要写死成一个"看起来合理"的常数。客户端侧必须指数退避 + 随机抖动（full jitter），否则被拒的请求会立刻再回来，把限流变成重试风暴，本来就紧张的容量被重试打穿——这是自激振荡，比原故障更难恢复。另外限流要尽量放在网关层：拒绝本身必须便宜，如果为了返回 429 还要起进程、连数据库，限流器就成了新的故障点。还有一点必须说清楚：限流不是防刷的全部。 它只限制速率，不判断请求是否合法——慢速攻击（low and slow）每个 IP 都在配额之内，分布式 IP 池可以绕过 IP 维度，批量注册可以绕过 UID 维度。真正防刷是分层的：认证与鉴权 → 幂等与去重 → 风控规则（设备指纹、行为特征）→ 验证码/挑战 → 黑名单 → 计量与成本（让刷的人付出代价）。限流的目标是"被滥用时不崩"，不是"阻止滥用"——把它当成唯一手段，等于用一把尺子去量所有问题。

小结

三个算法的区别其实只有两个变量：允许多大的突发，以及窗口边界是否对齐挂钟。固定窗口对齐挂钟，所以能被卡点；令牌桶不对齐，但它不承诺任意窗口；滑动窗口日志两边都满足，代价是内存。选型就是回答这两个问题。

至于误差，我现在的理解是：任何"分桶"或"双计数器"的实现都是用误差换内存和 RTT，而误差量级大致等于一个桶（或一个同步间隔）。所以别追求"精确限流"，先想清楚你真正要保护的是什么——是平均速率、是任意窗口的上限，还是下游能承受的瞬时并发。这三个问题的答案会指向不同的算法，而不是同一个算法的不同参数。

标签：#限流#算法#Redis#Go

/RELATED

返回博客列表