限流算法详解 - 滑动窗口算法深入理解

滑动窗口算法详解专门针对滑动窗口算法从原理到精确限流的实现细节做一个深入剖析。一、核心思想固定窗口在时间边界处会出现“计数突跳”原因是窗口的边界是硬重置的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 越细限流越精确但内存和计算开销也越大。实际工程中 N10~100 已经很精确。方式2基于有序时间戳集合精确但不高效将所有请求的时间戳存入一个有序集合如 Redis ZSET。每次请求时删除窗口外的过期时间戳ZREMRANGEBYSCORE然后统计集合大小ZCARD。优点理论上完全精确无 slot 量化误差。缺点内存占用随请求量线性增长高并发下性能差。很少用于生产限流更多用于精确分析。三、与固定窗口的对比关键场景固定窗口滑动窗口slot100ms窗口长度 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_timetonumber(ARGV[3])localwindow_startcurrent_time-tonumber(ARGV[1])-- 删除窗口外的旧请求redis.call(ZREMRANGEBYSCORE,KEYS[1],0,window_start)-- 统计当前窗口内请求数localcurrent_countredis.call(ZCARD,KEYS[1])ifcurrent_counttonumber(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秒流量”不会被人卡点突击。