限流算法#

一句话答案#

五种限流算法：计数器、固定窗口、滑动窗口、漏桶（匀速）、令牌桶（允许突发，最灵活），Sentinel 用滑动窗口。

令牌桶 vs 漏桶：实现机制#

令牌桶——惰性补令牌 + 桶内积攒： 核心是不需要后台线程定时放令牌，而是请求到来时按时间差「惰性」补：

newTokens = (now - lastRefillTime) × rate   // 这段时间本该生成的令牌数
tokens = min(capacity, tokens + newTokens)  // 补进桶，但不超过容量
lastRefillTime = now
if (tokens >= n) { tokens -= n; 放行 } else { 拒绝/排队 }

• 为什么允许突发： 空闲时段令牌在桶里积攒到 capacity，一旦来一批请求可以瞬间消耗掉这批存量令牌，故能容忍 capacity 大小的突发。
• 匀速近似： 突发过后桶被掏空，后续只能按 rate 补令牌的速度放行，长期平均速率仍是 rate。

漏桶——固定速率出队，恒速整流： 请求先入队（桶），由固定速率的「出水口」匀速取出处理：

• 出队速率恒为 rate，与流入速率无关，故输出绝对平滑、不容突发；桶满则丢弃（或拒绝）新请求。
• 代价：突发流量被强行削平后排队，增加延迟；空闲时也不会「攒额度」，无法利用历史空闲。

一句话区别： 令牌桶限的是平均速率且放过突发（桶里有票就走），漏桶限的是瞬时输出速率（出水口卡死恒定）。

滑动窗口如何消除临界突刺#

固定窗口的临界问题： 窗口 [0:00, 1:00) 限 100 QPS，攻击者在 0:59 打满 100 个、在 1:01 又打满 100 个——这 2 秒内实际通过了 200 个，达到限额的 2 倍，因为固定窗口在整点「硬重置」计数，跨窗口的流量不互相计入。

滑动窗口做法： 把 1 个大窗口切成 N 个小格（如 60 个 1 秒格），每格独立计数；统计「当前时刻往前一个完整窗口」覆盖的所有格子之和，随时间逐格向前滑动。

• 格子越多，统计粒度越细、临界误差越小（N 格时误差上界约 1/N），代价是内存与计算量增加。
• Sentinel 的 LeapArray 就是这种环形数组实现，每个桶（WindowWrap）记一段时间的统计值，过期桶被复用覆盖。

各算法实现要点#

计数器/固定窗口： 一个原子计数器 + 窗口起始时间戳；请求到来 count++，超阈值拒绝；到下一窗口整点把 count 清零。最简单，但有临界突刺。

令牌桶： 见上，存 tokens 和 lastRefillTime 两个值，惰性补令牌。

漏桶： 维护一个队列 + 定速消费线程（或记录「上次漏水时间」按时间差算可漏出量），队列满则拒绝。

滑动窗口（Redis + Lua 的 ZSET 实现）： 用一个 ZSET 存请求记录，score = 请求时间戳，member = 唯一请求 id，整段逻辑放 Lua 脚本保证原子：

-- KEYS[1]=限流key  ARGV: now, window, limit, reqId
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)  -- 滑掉窗口外的过期记录
local cnt = redis.call('ZCARD', KEYS[1])                   -- 统计窗口内请求数
if cnt < limit then
    redis.call('ZADD', KEYS[1], now, reqId)               -- 记录本次请求
    redis.call('PEXPIRE', KEYS[1], window)                -- 兜底过期，防 key 泄漏
    return 1   -- 放行
end
return 0       -- 拒绝

• 关键点： ZREMRANGEBYSCROE 把 [0, now-window] 的旧记录删掉，等价于「窗口向前滑动」；Lua 单线程执行保证「统计 + 判断 + 写入」三步原子，避免并发超发。
• 缺点：每个请求都在 ZSET 里存一条，高 QPS 下内存占用大；可改用「分桶计数 Hash」版滑动窗口降低存储。