调度与限流 #06：滑动窗口计数器

滑动窗口计数器将时间轴切成多个细粒度小格，始终统计最近 N 个格的请求总数，彻底消除固定窗口边界处双倍流量的突发问题；Nginx limit_req、Redis Cell、Sentinel 等限流组件均采用此思路。

相关文章：令牌桶 · 漏桶 · 滑动窗口日志

目录

问题背景

固定窗口的临界双倍突发

固定窗口计数器最朴素：每个时间窗口（如 1 秒）独立计数，超过 limit 则拒绝。
它有一个不可忽视的缺陷——窗口边界处可以打出 2 倍流量。

具体数字示例（limit = 100 req/s，窗口长度 = 1 s）：

窗口 A：[00:00.000 ~ 00:01.000)   窗口 B：[00:01.000 ~ 00:02.000)
                           ↑ 边界
  00:00.900 ~ 00:01.000 内打入 100 个请求  → 窗口 A 恰好用完配额 ✓
  00:01.000 ~ 00:01.100 内打入 100 个请求  → 窗口 B 刚开始，配额重置 ✓

结果：200ms 内通过了 200 个请求，是 limit 的 2 倍！

固定窗口对每个窗口独立计数，完全感知不到跨窗口的累积速率。

滑动窗口计数器的解法

将单个大窗口（如 1 s）拆成 N 个等宽小格（sub-window），每格宽度 = windowSize / N。
维护一个大小为 N 的环形数组，每格存一个计数器。
任意时刻，当前窗口 = 最近 N 个格，对这 N 个格的计数求和即为当前速率。

当时间推进，旧格自动"滑出"窗口并被清零，新格滑入，窗口始终覆盖最近 windowSize 时长，不存在硬性边界重置的问题。

核心数据结构

SlidingWindowCounter {
    buckets:        int[]   // 环形数组，长度 = N（N = windowSize / subWindowSize）
    currentSlot:    int     // 当前写入格的下标，范围 [0, N-1]
    lastSlotTime:   long    // currentSlot 对应的时间戳起点（毫秒），用于检测格切换
    totalCount:     int     // 最近 N 个格的请求总数（维护滚动和，避免每次遍历求和）
    windowSize:     long    // 整个滑动窗口的时长（毫秒），例如 1000
    subWindowSize:  long    // 每个小格的时长（毫秒），例如 100
    N:              int     // 格的数量 = windowSize / subWindowSize，例如 10
}

字段说明：

初始状态：buckets 全为 0，currentSlot = 0，lastSlotTime = now()，totalCount = 0。

record(request) 完整伪代码

function record(counter):
    lock(counter)
    try:
        now = currentTimeMillis()

        // --- 步骤 1：计算 now 落在哪个格 ---
        elapsed   = now - counter.lastSlotTime       // 距当前格起始过了多少 ms
        slotsDiff = elapsed / counter.subWindowSize  // 需要前进几格（整除）

        if slotsDiff >= counter.N:
            // 经过了完整窗口以上，全部格都已过期，直接清零
            for i in [0, N-1]:
                counter.buckets[i] = 0
            counter.totalCount   = 0
            counter.currentSlot  = (counter.currentSlot + slotsDiff) % counter.N
            counter.lastSlotTime = now - (now % counter.subWindowSize)
                                          // 对齐到格边界

        else if slotsDiff > 0:
            // 前进了 slotsDiff 格，逐一清除中间过期格
            for step in [1, slotsDiff]:
                nextSlot = (counter.currentSlot + step) % counter.N
                counter.totalCount  -= counter.buckets[nextSlot]  // 从总数中减去
                counter.buckets[nextSlot] = 0                      // 清零
            counter.currentSlot  = (counter.currentSlot + slotsDiff) % counter.N
            counter.lastSlotTime += slotsDiff * counter.subWindowSize

        // --- 步骤 2：在当前格计数 +1 ---
        counter.buckets[counter.currentSlot] += 1
        counter.totalCount                   += 1
    finally:
        unlock(counter)

设计要点：

• slotsDiff >= N：整个窗口都过期，一次性全清；不逐格清是因为历史格已无意义。
• 清格时同步更新 totalCount：维护滚动和，isAllowed 时无需 O(N) 遍历。
• lastSlotTime 对齐到格边界（now - now % subWindowSize）：确保格的划分是绝对时间对齐，不随首次请求到来时间漂移。

isAllowed(limit) 伪代码

function isAllowed(counter, limit):
    record(counter)               // 先推进窗口，清除过期格

    // record 内已持锁，totalCount 已是最新值
    // 注意：record 内部加锁，此处调用已在锁外；
    // 生产实现中可将 isAllowed 整体加锁，或将 totalCount 读取也纳入锁中
    lock(counter)
    try:
        return counter.totalCount <= limit
    finally:
        unlock(counter)

简化版（将 record 与判断合并在同一把锁内）：

function isAllowed(counter, limit):
    lock(counter)
    try:
        now       = currentTimeMillis()
        slotsDiff = (now - counter.lastSlotTime) / counter.subWindowSize

        // 清除过期格（同 record 逻辑）
        if slotsDiff >= counter.N:
            fill_all_zero(counter)
        else if slotsDiff > 0:
            clear_expired_slots(counter, slotsDiff)

        // 判断是否允许
        if counter.totalCount >= limit:
            return false            // 已达上限，拒绝

        // 允许，计数 +1
        counter.buckets[counter.currentSlot] += 1
        counter.totalCount                   += 1
        return true
    finally:
        unlock(counter)

关键：判断与计数必须在同一把锁内完成，否则并发时多个线程同时读到 totalCount < limit，都执行 +1，导致超限。

执行追踪

参数：windowSize = 1000ms，N = 10（每格 100ms），limit = 100
初始状态：buckets = [0,0,0,0,0,0,0,0,0,0]，currentSlot = 0，lastSlotTime = T0，totalCount = 0

─────────────────────────────────────────────────────────────────
T0+0ms   : 60 个请求到来
  slotsDiff = 0，无格切换
  buckets[0] += 60  →  buckets = [60,0,0,0,0,0,0,0,0,0]
  totalCount = 60
  isAllowed(100)？  60 <= 100 → ✓ 全部放行

─────────────────────────────────────────────────────────────────
T0+50ms  : 30 个请求到来
  slotsDiff = 50/100 = 0，仍在格 0
  buckets[0] += 30  →  buckets = [90,0,0,0,0,0,0,0,0,0]
  totalCount = 90

─────────────────────────────────────────────────────────────────
T0+100ms : 20 个请求到来
  slotsDiff = 100/100 = 1，切换到格 1
  清除格 1（原值 0）→ totalCount 不变 = 90
  currentSlot = 1，lastSlotTime = T0+100ms
  buckets[1] += 20  →  buckets = [90,20,0,0,0,0,0,0,0,0]
  totalCount = 110
  isAllowed(100)？  110 > 100 → ✗ 拒绝（窗口内已有 110 个请求）

─────────────────────────────────────────────────────────────────
T0+200ms : 5 个请求到来
  slotsDiff = 1（切换到格 2），清除格 2（值 0）
  currentSlot = 2，totalCount = 110
  isAllowed(100)？  110 > 100 → ✗ 继续拒绝

─────────────────────────────────────────────────────────────────
T0+1100ms: 10 个请求到来
  slotsDiff = (1100-100)/100 = 10 = N，整窗口过期
  全部清零：buckets = [0,0,0,0,0,0,0,0,0,0]，totalCount = 0
  currentSlot = (1 + 10) % 10 = 1，lastSlotTime = T0+1100ms
  buckets[1] += 10  →  totalCount = 10
  isAllowed(100)？  10 <= 100 → ✓ 放行

─────────────────────────────────────────────────────────────────
T0+1150ms: 30 个请求到来
  slotsDiff = 50/100 = 0，仍在格 1
  buckets[1] += 30  →  totalCount = 40
  isAllowed(100)？  40 <= 100 → ✓ 放行

  注意：即使 T0+100ms 附近曾经 totalCount=110，
  随着旧格[0]（含 90 个请求）在 T0+1000ms 后完全滑出窗口，
  计数自然回落，无需手动清理。
─────────────────────────────────────────────────────────────────

关键观察：

• 格切换时只清除即将复用的格（环形覆盖），不清除所有格。
• totalCount 以增量方式维护，每次清格时减去旧值，避免 O(N) 遍历。
• 临界区内不存在两个相邻窗口叠加 2×limit 的问题：窗口是连续滑动的。

Redis 实现方案

方案 A：ZSET 精确滑动窗口

用 Sorted Set 存储每个请求的时间戳作为 score，实现真正意义上的滑动窗口：

key:  rate_limit:{user_id}
member: 请求唯一 ID（或时间戳字符串）
score:  请求时间戳（毫秒）

Lua 脚本（原子执行，保证 count + judge 的原子性）：

-- KEYS[1] = rate limit key
-- ARGV[1] = now (ms)
-- ARGV[2] = windowSize (ms)
-- ARGV[3] = limit
-- ARGV[4] = unique request id

local now        = tonumber(ARGV[1])
local windowSize = tonumber(ARGV[2])
local limit      = tonumber(ARGV[3])
local reqId      = ARGV[4]
local windowStart = now - windowSize

-- 删除窗口外的旧请求
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', windowStart)

-- 统计当前窗口内的请求数
local count = redis.call('ZCARD', KEYS[1])

if count < tonumber(limit) then
    -- 允许：将本次请求加入 ZSET
    redis.call('ZADD', KEYS[1], now, reqId)
    redis.call('EXPIRE', KEYS[1], math.ceil(windowSize / 1000) + 1)
    return 1   -- allowed
else
    return 0   -- rejected
end

优点：精确到毫秒，无近似误差。
缺点：每个请求都存一条记录，高 QPS 下 ZSET 内存占用显著（O(limit) 条记录）。

方案 B：多 key 近似桶方案

用多个独立 key 存储每个时间格的计数，key 名携带格的时间戳：

key:  rate_limit:{user_id}:{slot_timestamp}
value: 计数（整数）
TTL: windowSize + 1 个格宽度（自动过期，无需手动清理）

Lua 脚本：

-- KEYS[1] = 当前格 key（如 rate_limit:u1:16900000）
-- ARGV[1] = limit
-- ARGV[2] = 所有格 key 的列表（用于求和）
-- ARGV[3] = TTL（秒）

local total = 0
-- 遍历 N 个格 key 求和（等价于 totalCount）
for i = 1, #KEYS do
    local v = redis.call('GET', KEYS[i])
    if v then total = total + tonumber(v) end
end

if total < tonumber(ARGV[1]) then
    redis.call('INCR', KEYS[1])
    redis.call('EXPIRE', KEYS[1], tonumber(ARGV[2]))
    return 1
else
    return 0
end

优点：内存占用固定（O(N) 个 key，N = 格数），不随 QPS 增长。
缺点：格宽带来近似误差（同固定窗口，但误差缩小为 1/N）。

两种方案对比

异常与边界场景

7.1 格粒度与精度的权衡

格越小（N 越大），滑动窗口越精确，误差越小：

• N = 1：退化为固定窗口，最大误差 = windowSize（临界双倍问题复现）。
• N = 10：误差 ≤ 100ms（窗口 1s 时），通常够用。
• N = 1000：误差 ≤ 1ms，但需要 1000 个格的内存，且 slotsDiff 循环清格的开销增大。

实践建议：N 取 10～60，格宽 ≥ 10ms，在精度与内存/CPU 之间取得合理平衡。

7.2 并发计数的原子性

问题：两个线程同时执行 isAllowed，均读到 totalCount = 99 < 100，均执行 +1，实际通过了 101 个请求。

解决方案：

• 单机：synchronized / ReentrantLock 保护 read-then-write 的完整序列。
• Redis：使用 Lua 脚本将 ZREMRANGEBYSCORE + ZCARD + ZADD（或 GET + INCR）打包为原子操作，Redis 单线程保证串行执行。
• Redis + Redisson：RRateLimiter（基于令牌桶）或自定义 Lua 脚本均可保证原子性。

7.3 窗口大小动态调整

业务高峰期需临时将 limit 从 100 调到 200，或将 windowSize 从 1s 调到 5s。

处理方式：

• limit 变更：无需重建数据结构，下次 isAllowed 时使用新 limit 即可。
• windowSize 或 subWindowSize 变更：需重建环形数组（N 变了），历史计数不可直接复用。
  实践中通常以"配置版本号"区分新旧窗口，等旧窗口自然过期后新窗口生效。

7.4 分布式环境下多实例计数聚合

单机滑动窗口计数器无法感知其他实例的请求量：

• 3 个实例各自维护独立计数，每个实例的 totalCount = 33，实际全局已有 99 个请求，但单机看起来远未达到 limit=100，导致全局超限。

解决方案：

• 集中式：将计数存储在 Redis（共享状态），所有实例读写同一 ZSET 或同一组格 key。
• 本地 + 全局双层限流：每个实例设置本地 limit = globalLimit / instanceCount（粗粒度），超过本地 limit 再访问 Redis 做全局判断（减少 Redis 压力）。
• Gossip 协议近似聚合：实例间定期广播本地计数，聚合后得到近似全局计数（CAP 权衡，允许短暂超限）。

滑动窗口 vs 令牌桶 vs 漏桶

选型指南：

• 需要**严格「N 秒内不超过 M 次」**的速率保证 → 滑动窗口计数器。
• 需要允许短时突发、长期平均达标（如 CDN 回源、数据库批量写入）→ 令牌桶。
• 需要严格匀速输出、保护下游（如消息队列消费、网络带宽整形）→ 漏桶。

参考资料

1. Figma Engineering：An alternative approach to rate limiting https://www.figma.com/blog/an-alternative-approach-to-rate-limiting/ — 详细介绍滑动窗口计数器与固定窗口的对比，ZSET 实现方案。

2. Cloudflare：How we built rate limiting capable of scaling to millions of domains https://blog.cloudflare.com/counting-things-a-lot-of-different-things/ — 近似滑动窗口在 CDN 边缘节点的工程实践。

3. Redis 官方文档：Sorted Sets https://redis.io/docs/data-types/sorted-sets/ — ZREMRANGEBYSCORE、ZCARD、ZADD 命令详解。

4. 《System Design Interview Vol.1》Alex Xu — Chapter 4: Design a Rate Limiter — 固定窗口、滑动窗口日志、滑动窗口计数器三种方案的工程对比。

5. Sentinel 源码：SlidingWindowMetric https://github.com/alibaba/Sentinel/blob/master/sentinel-core/src/main/java/com/alibaba/csp/sentinel/slots/statistic/base/LeapArray.java — 阿里巴巴 Sentinel 的 LeapArray（环形数组）实现，是本文数据结构的工业级参考。

6. RFC 2697 — A Single Rate Three Color Marker https://datatracker.ietf.org/doc/html/rfc2697 — IETF 对令牌桶和窗口计数在流量着色中的规范定义。