限流算法详解 - 滑动窗口算法深入理解
滑动窗口算法详解
专门针对滑动窗口算法，从原理到精确限流的实现细节做一个深入剖析。
一、核心思想
固定窗口在时间边界处会出现“计数突跳”，原因是窗口的边界是硬重置的（0→1秒末清空，1→2秒初重新计数）。
滑动窗口的核心改进是：窗口不再整段重置，而是随当前时间“滑动”，始终统计“过去一个完整窗口长度”内的请求总数。
大白话：你不是只看“这一分钟从0秒到60秒”，而是任何时候都回头看“刚才过去的60秒”。即窗口不是固定的 [00:00, 00:60)、[01:00, 02:00) 这样的整分区间，而是始终以当前时刻为终点，往前推 60 秒。这样就不存在边界漏洞。
二、如何做到精确限流？
精确限流的本质是：任意时刻 T，系统能够准确统计出[T - windowSize, T)这段时间内的请求数量，并且这个统计的计算代价不能太高。
滑动窗口通过两种方式实现：
方式1：基于时间片（槽位）的滑动窗口（工程最常用）
这是对“无穷细粒度滑动”的近似，但在工程上可控且高效。
数据结构：
- 将窗口长度
W分成N个等长的小时间片（slot），每个 slot 对应一个计数器。 - 例如：窗口长度 1 秒，分成 10 个 slot，每个 slot 代表 100 毫秒。
算法步骤：
- 当请求在时间
t到达，计算当前 slot 索引：slotIndex = floor(t / slotDuration) % N - 如果该 slot 不是当前活跃 slot（即时间已经推进到了下一个 slot），则清零过时的 slot。
- 将该 slot 的计数器加1。
- 统计当前窗口内的总请求数 = 所有 N 个 slot 的计数器之和（因为窗口恰好覆盖 N 个 slot）。
- 如果总和 < 阈值，放行；否则拒绝。
为什么能精确限流？
因为任意时刻，窗口覆盖的是完整的 N 个连续 slot。当时间从t1移动到t2时，滑动算法会逐渐淘汰最老的 slot，加入最新的 slot。这避免了固定窗口的“整体重置”问题，边界请求被分散到相邻 slot 中，不会产生突发尖峰。
精度分析：
- 误差 ≤
slotDuration。比如 slot = 100ms，最多有 100ms 内的请求可能被统计到稍早或稍晚的窗口边界上，但相比固定窗口的整段误差（可高达一个完整窗口的突发），这个误差很小。 - N 越大（slot 越细），限流越精确，但内存和计算开销也越大。实际工程中 N=10~100 已经很精确。
方式2：基于有序时间戳集合（精确但不高效）
将所有请求的时间戳存入一个有序集合（如 Redis ZSET）。每次请求时，删除窗口外的过期时间戳（ZREMRANGEBYSCORE），然后统计集合大小（ZCARD）。
- 优点：理论上完全精确（无 slot 量化误差）。
- 缺点：内存占用随请求量线性增长，高并发下性能差。很少用于生产限流，更多用于精确分析。
三、与固定窗口的对比（关键）
| 场景 | 固定窗口 | 滑动窗口（slot=100ms） |
|---|---|---|
| 窗口长度 1s，阈值 100 | 在第1秒的最后10ms内到达100个请求，第2秒的最初10ms内到达100个请求 → 200ms内共200个请求，全部放行，压垮系统。 | 第1秒最后10ms的请求计入第1秒的第10个slot；第2秒最初10ms的请求计入第2秒的第1个slot。窗口滑动后，这200ms的请求会被分别归属到两个窗口组合中，不会同时出现在同一个1秒窗口，因此最多放行100个/秒。 |
| 是否允许边界突刺 | 严重允许 | 基本消除（误差限于 slot 粒度） |
大白话对比：固定窗口像是“每过1分钟就清零重算”，钻空子的人正好在清零前后狂刷。滑动窗口像是“你有60个收银台，每个台负责1秒中的一小段，任何时候我只看最近60个台子的总人数”，没人能跨过60个台子。
四、实际实现示例（Redis + Lua 的滑动窗口）
常见的高性能分布式滑动窗口实现（伪代码）：
-- KEYS[1] = 限流key， ARGV[1] = 窗口长度(ms)， ARGV[2] = 阈值， ARGV[3] = 当前时间戳(ms)localcurrent_time=tonumber(ARGV[3])localwindow_start=current_time-tonumber(ARGV[1])-- 删除窗口外的旧请求redis.call('ZREMRANGEBYSCORE',KEYS[1],0,window_start)-- 统计当前窗口内请求数localcurrent_count=redis.call('ZCARD',KEYS[1])ifcurrent_count<tonumber(ARGV[2])then-- 未超限，添加当前请求时间戳redis.call('ZADD',KEYS[1],current_time,current_time..'_'..math.random())-- 设置过期时间，避免内存无限增长redis.call('PEXPIRE',KEYS[1],tonumber(ARGV[1]))return1-- 放行elsereturn0-- 拒绝end这个实现是精确的（无 slot 量化），因为直接用 ZSET 存储每个请求的时间戳。但它有缺点：高并发下 ZSET 的内存和排序开销较大，只适合中小规模或需要绝对精确的场景。
五、滑动窗口的优缺点总结
| 优点 | 缺点 |
|---|---|
| 解决固定窗口的边界突发问题 | 实现比固定窗口复杂 |
| 限流精度可调（通过调整 slot 数量） | 需要存储多个 slot 的计数（内存高于固定窗口） |
| 对流量突发有很好的平滑效果 | 如果使用 ZSET 方式，性能和内存会随请求线性增长 |
| 适用分布式场景（配合 Redis） | – |
六、实际选择建议
- 需要极高精度、流量不大→ 用 ZSET 精确滑动窗口。
- 高并发、可容忍毫秒级误差→ 用 slot 化滑动窗口（slot 数 10~100）。
- 对边界突发不敏感→ 固定窗口更简单。
- 需要平滑速率 + 允许突发→ 令牌桶，比滑动窗口更合适。
大白话总结：滑动窗口就像一个滚动的监控摄像头，永远盯着刚过去的那个时间区间。它不像固定窗口那样“到点就忘”，而是边走边忘——忘掉最老的，记住最新的。这样就能精确控制任何时刻的“最近N秒流量”，不会被人卡点突击。