调度与限流 #07：滑动窗口日志

滑动窗口日志为每个请求精确记录时间戳，判断「最近 windowSize 时间内的请求数」是否超限，实现零误差的速率控制；Twitter、Stripe、Cloudflare 等 API 网关广泛采用此方案处理严格限流场景。

相关文章：令牌桶 · 漏桶 · 滑动窗口计数器

目录

问题背景

滑动窗口计数器的近似误差

滑动窗口计数器将时间轴切成若干小格（sub-window），以格为粒度统计请求数。
这意味着它的精度受格宽约束——格宽内的请求分布被视为均匀，实际上并不均匀。

具体数字示例（windowSize = 1s，N = 10 格，limit = 100，格宽 = 100ms）：

格 0（T0 ~ T0+100ms）：100 个请求，均匀分布在前 50ms
格 1（T0+100ms ~ T0+200ms）：0 个请求

T0+150ms 时刻：窗口 = 格0 + 格1 + … + 格9 = 100 个请求，刚好通过

T0+199ms 时刻：下一个请求到来
  计数器看到 totalCount = 100，拒绝 ✗（正确）

但若格 0 的 100 个请求全集中在 T0+99ms（最后 1ms）：
  T0+199ms 的窗口实际包含了几乎全部 100 个请求，计数器也是 100，正确拒绝 ✓

问题场景：格 0 的 100 个请求集中在 T0+0ms（最开始 1ms）：
  T0+199ms 时，这 100 个请求实际上距今已 199ms，远在「真实滑动窗口」之外
  但计数器仍然统计格 0 的计数 = 100，错误地拒绝了新请求 ✗

这种格内均匀分布的假设导致了近似误差：实际请求更早发生，但计数器以为它们更新。

滑动窗口日志的解法

不做近似——为每个请求存储精确时间戳。

将所有请求的时间戳存入一个有序队列（deque）：

• 队头：最旧的时间戳
• 队尾：最新的时间戳

每次新请求到来时：

1. 清除队头所有早于 timestamp - windowSize 的过期时间戳
2. 检查队列大小是否已达 limit
3. 未达则将新时间戳加入队尾，放行；已达则拒绝

无需任何近似假设，精度达到时间戳的最小单位（毫秒或微秒）。

核心数据结构

SlidingWindowLog {
    log:         Deque<long>  // 有序时间戳队列，队头最旧（最小）、队尾最新（最大）
    windowSize:  long         // 窗口大小，单位毫秒，例如 1000
    limit:       int          // 窗口内允许的最大请求数，例如 3
}

字段说明：

与滑动窗口计数器的关键差异：

初始状态：log 为空队列。

isAllowed 完整伪代码

function isAllowed(log, timestamp, limit, windowSize):
    lock(log)
    try:
        // --- 步骤 1：清除队头所有过期时间戳 ---
        windowStart = timestamp - windowSize    // 窗口起始边界（不含）

        while log.isNotEmpty() AND log.peekFirst() <= windowStart:
            log.removeFirst()                   // 弹出队头过期时间戳

        // --- 步骤 2：判断当前窗口内请求数是否达到上限 ---
        if log.size() < limit:
            // --- 步骤 3：允许，将本次时间戳加入队尾 ---
            log.addLast(timestamp)
            return true    // 放行

        else:
            // 已达上限，拒绝——注意：不将 timestamp 加入 log
            return false   // 拒绝
    finally:
        unlock(log)

设计要点：

• 过期条件 <= windowStart：windowStart = timestamp - windowSize，严格意义上窗口是左开右闭 (windowStart, timestamp]，等于 windowStart 的时间戳已过期，应当移除。
• 拒绝时不加入 log：被拒绝的请求不占用 log 空间。若将被拒请求也加入 log，则拒绝期间 log 持续增长，下一批请求的过期清理成本会人为增大。
• 锁的粒度：整个 read-check-write 序列必须在同一把锁内，防止并发时多个线程同时读到 log.size() < limit，均执行 addLast，导致超限。
• 时间戳单调性：调用方需保证 timestamp 单调递增（或至少不早于队尾的时间戳），否则队列的有序性被破坏，peekFirst() 的清除逻辑失效。

执行追踪

参数：windowSize = 1000ms，limit = 3
初始状态：log = []

─────────────────────────────────────────────────────────────────
T = 100ms：请求 R1 到来
  windowStart = 100 - 1000 = -900ms
  清除队头 <= -900ms：log 为空，无需清除
  log.size() = 0 < 3
  → addLast(100)，log = [100]
  → 放行 ✓

─────────────────────────────────────────────────────────────────
T = 400ms：请求 R2 到来
  windowStart = 400 - 1000 = -600ms
  清除队头 <= -600ms：log[0]=100 > -600，无需清除
  log.size() = 1 < 3
  → addLast(400)，log = [100, 400]
  → 放行 ✓

─────────────────────────────────────────────────────────────────
T = 800ms：请求 R3 到来
  windowStart = 800 - 1000 = -200ms
  清除队头 <= -200ms：log[0]=100 > -200，无需清除
  log.size() = 2 < 3
  → addLast(800)，log = [100, 400, 800]
  → 放行 ✓

─────────────────────────────────────────────────────────────────
T = 900ms：请求 R4 到来（超限，应被拒绝）
  windowStart = 900 - 1000 = -100ms
  清除队头 <= -100ms：log[0]=100 > -100，无需清除
  log.size() = 3，已达 limit=3
  → 不加入 log，log = [100, 400, 800]（不变）
  → 拒绝 ✗

─────────────────────────────────────────────────────────────────
T = 1200ms：请求 R5 到来（T=100 的时间戳已过期）
  windowStart = 1200 - 1000 = 200ms
  清除队头 <= 200ms：
    log[0] = 100 <= 200  → removeFirst()，log = [400, 800]
    log[0] = 400 > 200   → 停止清除
  log.size() = 2 < 3
  → addLast(1200)，log = [400, 800, 1200]
  → 放行 ✓

─────────────────────────────────────────────────────────────────
T = 1500ms：请求 R6 到来（T=400 已过期）
  windowStart = 1500 - 1000 = 500ms
  清除队头 <= 500ms：
    log[0] = 400 <= 500  → removeFirst()，log = [800, 1200]
    log[0] = 800 > 500   → 停止清除
  log.size() = 2 < 3
  → addLast(1500)，log = [800, 1200, 1500]
  → 放行 ✓

─────────────────────────────────────────────────────────────────
T = 1600ms：请求 R7 到来（窗口内已有 800、1200、1500 三个）
  windowStart = 1600 - 1000 = 600ms
  清除队头 <= 600ms：log[0]=800 > 600，无需清除
  log.size() = 3，已达 limit=3
  → 拒绝 ✗

─────────────────────────────────────────────────────────────────
T = 1900ms：请求 R8 到来（T=800 已过期）
  windowStart = 1900 - 1000 = 900ms
  清除队头 <= 900ms：
    log[0] = 800 <= 900  → removeFirst()，log = [1200, 1500]
    log[0] = 1200 > 900  → 停止清除
  log.size() = 2 < 3
  → addLast(1900)，log = [1200, 1500, 1900]
  → 放行 ✓
─────────────────────────────────────────────────────────────────

关键观察：

• 每次请求到来时，过期清理发生在判断之前，保证 log.size() 始终只反映当前窗口内的有效请求数。
• 拒绝请求（R4、R7）不修改 log，队列保持原样。
• 窗口是严格「最近 1000ms」的精确计算，不存在格粒度的近似误差。

内存开销分析

单个时间戳的存储成本

• Java long：8 字节
• Redis ZSET member（UUID 字符串）：约 36 字节；score（double）：8 字节；Redis 额外元数据：约 64 字节/成员
• 实际 Redis 内存：约 100～120 字节/请求

内存复杂度

最坏情况：log 内有 limit 个时间戳（窗口内全部请求都通过）
内存上界 = limit × (每条记录大小)

示例：
  limit = 1000 req/s，纯时间戳存储：1000 × 8 = 8 KB（极低）
  limit = 1000 req/s，Redis ZSET：1000 × 120 ≈ 120 KB（仍可接受）
  limit = 100000 req/s，Redis ZSET：100000 × 120 ≈ 12 MB（需关注）

关键结论：内存用量与 limit 成正比（O(limit)），与 windowSize 无关（过期记录随时清除）。

与滑动窗口计数器的内存对比

核心差异：

• 滑动窗口计数器的内存 = O(N)，固定，不随 limit 变化。
• 滑动窗口日志的内存 = O(limit)，随 limit 线性增长。

当 limit 很小（≤ 10000）且需要精确控制时，滑动窗口日志的额外内存完全可接受；
当 limit 达到百万级时，滑动窗口日志的内存开销使其不再适用。

Redis 实现方案

数据结构选型

使用 Sorted Set（ZSET） 天然支持按分数（时间戳）排序，与滑动窗口日志的有序队列语义完美对应：

key:    rate_limit:{user_id}
member: 请求唯一 ID（UUID 或 timestamp + 随机数）
score:  请求时间戳（毫秒）

member 唯一性：同一毫秒内可能有多个请求，若 member 直接用时间戳字符串，同毫秒请求会覆盖彼此（ZADD 对相同 member 是更新 score，非追加）。解决方案：

• UUID.randomUUID().toString()：全局唯一，但生成有额外开销。
• timestamp + ":" + ThreadLocalRandom.nextInt(1000000)：轻量，碰撞概率极低。

Lua 脚本（原子性保证）

-- KEYS[1] = rate limit key（如 rate_limit:user123）
-- ARGV[1] = now（当前时间戳，毫秒）
-- ARGV[2] = windowSize（窗口大小，毫秒）
-- ARGV[3] = limit（允许的最大请求数）
-- ARGV[4] = member（本次请求唯一 ID）

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

-- 步骤 1：删除窗口外（score <= windowStart）的过期成员
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', windowStart)

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

-- 步骤 3：判断是否允许
if count < limit then
    -- 允许：将本次请求加入 ZSET
    redis.call('ZADD', KEYS[1], now, member)
    -- 设置 key 过期时间（windowSize 后自动删除，避免内存泄漏）
    redis.call('PEXPIRE', KEYS[1], windowSize + 1000)
    return 1   -- allowed
else
    return 0   -- rejected
end

Lua 保证原子性的原因：Redis 单线程执行模型，Lua 脚本在执行期间不会被其他命令打断，整个 ZREMRANGEBYSCORE + ZCARD + ZADD 序列是原子的。

Java 调用示例

// Spring Data Redis + Lua 脚本
private static final String LUA_SCRIPT =
    "local now = tonumber(ARGV[1])\n" +
    "local windowSize = tonumber(ARGV[2])\n" +
    "local limit = tonumber(ARGV[3])\n" +
    "local member = ARGV[4]\n" +
    "local windowStart = now - windowSize\n" +
    "redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', windowStart)\n" +
    "local count = tonumber(redis.call('ZCARD', KEYS[1]))\n" +
    "if count < limit then\n" +
    "  redis.call('ZADD', KEYS[1], now, member)\n" +
    "  redis.call('PEXPIRE', KEYS[1], windowSize + 1000)\n" +
    "  return 1\n" +
    "else\n" +
    "  return 0\n" +
    "end";

public boolean isAllowed(String userId, long limit, long windowSizeMs) {
    String key    = "rate_limit:" + userId;
    long   now    = System.currentTimeMillis();
    String member = now + ":" + ThreadLocalRandom.current().nextInt(1_000_000);

    Long result = redisTemplate.execute(
        new DefaultRedisScript<>(LUA_SCRIPT, Long.class),
        List.of(key),
        String.valueOf(now),
        String.valueOf(windowSizeMs),
        String.valueOf(limit),
        member
    );
    return Long.valueOf(1L).equals(result);
}

异常与边界场景

7.1 高 limit 下内存线性增长

问题：limit = 1,000,000 req/s 时，log 最多存储 100 万条时间戳。
Redis ZSET 每条成员约 120 字节，峰值内存 = 120MB，多个用户同时达峰则内存压力极大。

处理方式：

• 高 limit 场景改用滑动窗口计数器（内存 O(N) 固定）或令牌桶（内存 O(1)）。
• 若必须用滑动窗口日志，对 member 使用压缩存储（如纯 int32 递增序号，仅 4 字节/条）。
• 为每个 key 设置 PEXPIRE，防止非活跃用户的 ZSET 无限期占用内存。

7.2 时间戳精度（毫秒 vs 微秒）

问题：System.currentTimeMillis() 精度为毫秒，同一毫秒内的多个请求 score 相同，ZADD 对相同 member 是覆盖，可能导致计数偏少。

处理方式：

• member 加随机后缀（如 timestamp + ":" + random）保证唯一性，即使 score 相同也会作为独立成员存储。
• 改用 System.nanoTime() 或 Clock.systemUTC().instant().toEpochMilli() + 微秒补偿，提升 score 精度。
• Redis 6.2+ 的 ZADD NX 可结合使用，避免相同 member 的意外覆盖。

7.3 分布式多实例如何共享同一日志

问题：多个服务实例各自维护本地 log，相互不可见，全局请求数可能超过 limit 但每个实例单独看都未超。

集中化方案（推荐）：

• 所有实例共用同一个 Redis ZSET（中心化存储），Lua 脚本保证原子性。
• 代价：每次请求都有一次 Redis 网络 RTT（通常 1～5ms）。

本地近似方案（高性能场景）：

• 每个实例维护本地滑动窗口日志，设置本地 limit = globalLimit / instanceCount。
• 优点：无 Redis 网络开销。缺点：实例数量变化时需动态调整本地 limit；单实例故障会导致配额重分配不均。

双层限流方案（生产推荐）：

• 本地快速预判（粗粒度，limit = globalLimit × 1.2 / instanceCount），拒绝明显超限请求。
• 通过本地判断的请求再访问 Redis 做精确全局判断。
• 大幅减少 Redis 压力，同时保持全局精确性。

7.4 时钟不同步导致 member 排序错乱

问题：分布式环境中，不同实例的系统时钟可能有几毫秒到几秒的漂移（NTP 调整、闰秒等）。
实例 A 的时间戳为 T+500ms，实例 B 的时间戳为 T+300ms（时钟落后），两者写入同一 ZSET 后，ZREMRANGEBYSCORE 清除的范围基于「当前时间」，而不同实例对「当前时间」的判断不一致。

具体危害：

• 实例 B（时钟落后）计算的 windowStart 偏小，不清除实例 A 应清除的过期记录，导致 log 偏大，误拒合法请求（过于严格）。
• 实例 A（时钟超前）计算的 windowStart 偏大，清除了实例 B 本应有效的记录，导致 log 偏小，放过了应拒绝的请求（过于宽松）。

处理方式：

• 使用 Redis 服务器时间（redis.call('TIME')）作为唯一时间源，消除客户端时钟差异。
• 部署 NTP/PTP 时钟同步，将漂移控制在 1ms 以内。
• 在 Lua 脚本中以 redis.call('TIME') 替代客户端传入的 now：

local time   = redis.call('TIME')          -- {秒, 微秒}
local now    = time[1] * 1000 + math.floor(time[2] / 1000)  -- 转为毫秒
-- 后续逻辑不变

精确度 vs 性能权衡

三种限流方案核心对比

生产选型指南

limit 较小（≤ 10000）且要求精确无误差？
  → 滑动窗口日志（Redis ZSET + Lua）

limit 较大（> 10000）且可接受 ≤ 1 格宽的近似误差？
  → 滑动窗口计数器（Redis 多 key 或本地环形数组）

需要允许短时突发、长期平均达标（如 CDN 回源、批量写入）？
  → 令牌桶（内存 O(1)，无近似误差，支持突发配置）

需要严格匀速输出、保护下游不受突发冲击？
  → 漏桶（固定出队速率，队列满则丢弃）

实际工程中的组合策略：

• 外层：令牌桶（允许合理突发，O(1) 内存，保护系统稳定性）
• 内层：滑动窗口日志（精确统计高价值 API 的细粒度使用量，limit 通常较小）

参考资料

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

2. Figma Engineering：An alternative approach to rate limiting https://www.figma.com/blog/an-alternative-approach-to-rate-limiting/ — 详细对比滑动窗口日志（ZSET）与计数器方案的内存开销与精度差异。

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

4. Redis 官方文档：TIME 命令 https://redis.io/commands/time/ — 获取 Redis 服务器当前时间，用于消除分布式客户端时钟漂移。

5. Stripe Engineering：Rate Limiters https://stripe.com/blog/rate-limiters — Stripe 生产环境中滑动窗口日志的实践经验，包括 Redis Lua 脚本设计与多层限流架构。

6. Cloudflare：How we built rate limiting capable of scaling to millions of domains https://blog.cloudflare.com/counting-things-a-lot-of-different-things/ — 超大规模下从精确日志到近似计数器的演进过程，解释了精确度与性能的工程权衡。

7. RFC 6585 — Additional HTTP Status Codes（429 Too Many Requests） https://datatracker.ietf.org/doc/html/rfc6585 — 速率限制的 HTTP 标准响应码定义，包含 Retry-After 头的规范用法。