我第一次认真从头实现滑动窗口是在给一个内部接口做限流的时候。当时业务量一上来固定窗口限流每到时间片临界点就会明显出现一波“双倍放行”接口直接被瞬时流量打出了大量超时。折腾到半夜才意识到光换算法还不够还得用Lua脚本把“判断当前窗口计数”和“写入新记录”放进同一段原子操作里。也就是从那次开始我才算真正把“滑动窗口”从面经里的一个名词变成了一行行能跑的Lua代码。这篇文章聊的就是Lua脚本实现滑动窗口这个主题。我会按自己在生产环境里的落地经验把滑动窗口在限流、数据流聚合、数值滤波这三类最常见的场景分别拆开来讲给出可以直接抄作业的代码再把时间精度、内存、并发这些容易埋雷的细节单独拎出来说一遍。适合正在被限流算法困扰的后端开发也适合在Lua/OpenResty环境里做数据统计、监控面板或者信号处理的同学参考。1. 滑动窗口要解决的核心问题1.1 滑动窗口到底是什么滑动窗口的核心其实很简单在一条不断往前推进的时间轴或者数据流上划定一个固定宽度的区间只关心这个区间里的数据。窗口每前进一格就会把已经移出区间的旧内容丢掉同时纳入新到的内容。这个“只盯着最近一小块其他全部忽略”的思路可以把无穷无尽的数据流变成有边界、可计算、可预测的有限集合。很多人第一次接触这个概念是在算法题里给定一个数组找出每个长度为k的子数组的最大值或最小值还有一些人是在信道的滑动窗口重传协议里认识它的更多做后端的人则是在做系统限流时发现固定窗口的边界问题才想起来用滑动窗口做平滑统计。这几个场景看起来风马牛不相及但底层其实都是同一个抽象——在动态序列上维护一个固定大小的子集随着时间或者数据索引的推进不断更新这个子集。1.2 时间窗口和计数窗口怎么选按实现维度来分滑动窗口通常有两条路。一种是按事件数量来划窗口比如“最近10个请求内最多允许3次”另一种是按时间来划窗口比如“最近5秒内最多30次”。前者适合数据量有限、节奏相对稳定的场景用队列就能搞定后者更适合线上流量的限流控制因为时间粒度能更真实地还原压力分布。在Lua脚本里这两种路径的实现思路是一样的只是窗口的“边界”从一条条数据变成了时间戳。按事件数量的窗口用数组或者队列存最近N次事件的索引按时间划的窗口则要依赖时钟把当前时间戳和窗口长度相减得到一个下界凡是比这个下界更老的记录都可以清掉。很多人在时间窗口上踩坑不是算法不会写而是时间单位、时间来源没统一后面第4节会详细展开。1.3 滑动窗口和固定窗口的本质差异还有个特别容易被忽略的点滑动窗口和固定窗口之间有本质区别。固定窗口是每个时间片独立计数比如“每秒最多100次”用Redis的INCR加EXPIRE就能实现简单粗暴。但它天生有一个漏洞如果上一秒的最后10毫秒已经用了100次下一秒的前10毫秒又用了100次那这20毫秒内实际通过了200次相当于把限制放大了一倍。滑动窗口的价值就在于它不会因为时间片边界而放松统计。统计口径变成“从当前时刻回看一个窗口长度”等于把边界从“整秒的墙”换成了“流动的水”。流量控制这类讲究精确的场景几乎只能用滑动窗口这也是它常驻限流方案列表的根本原因。2. 限流场景基于时间戳的滑动窗口实现限流是Lua脚本实现滑动窗口最经典的生产场景。在OpenResty环境里Lua脚本既是业务的入口也是做限流的天然位置——它处在请求处理的早期阶段拦截成本最低。更重要的是OpenResty的Lua模块天生就能和Redis配合滑动窗口的计数可以统一存在Redis里多个worker、多台机器之间共享状态不会出现单机计数各算各的尴尬。2.1 为什么固定窗口限流不够用想理解滑动窗口限流为什么一定要写成Redis脚本可以先看看固定窗口的边界问题。假设限流策略是“每秒最多100次”常规做法是用INCR和EXPIRE在某个key上累加计数到点自动过期。这个方案足够简单但它的统计范围是死的从某个整秒起点到整秒终点。线上的请求分布不可能像节拍器一样均匀它总会集中在某些瞬间一旦相邻两个窗口边缘的数据叠加瞬时流量就会超过预期。更麻烦的是这种超出在监控面板上根本看不出来因为按秒拆开统计时每一秒的计数都没有超过100。只有把统计粒度细化到“从当前时间往前推5秒一共处理了多少请求”才能真正把“瞬时流量超过限流阈值”这个问题暴露出来并拦住。2.2 用Redis有序集合实现原子滑动窗口脚本实际生产里我最推荐用Redis的有序集合ZSET来存请求的时间戳。ZSET的score天然适合存时间ZREMRANGEBYSCORE可以一行命令删掉窗口之外的数据ZCARD能在常数时间内拿到窗口内记录数整套逻辑写成一段EVAL脚本交给Redis执行Redis单线程的特性会保证脚本原子运行不会出现两个请求同时读到同一个count然后双双放行的竞态。直接看代码这段Lua脚本可以作为EVAL的参数直接跑在Redis上-- KEYS[1]: 限流key通常取 rl: 用户ID或接口名 -- ARGV[1]: 当前时间(推荐毫秒) -- ARGV[2]: 窗口长度(毫秒) -- ARGV[3]: 窗口内最大请求数 local key KEYS[1] local current tonumber(ARGV[1]) local window_ms tonumber(ARGV[2]) local max_count tonumber(ARGV[3]) -- 1. 清理窗口之外的所有历史记录 redis.call(ZREMRANGEBYSCORE, key, 0, current - window_ms) -- 2. 统计窗口内的请求数 local count redis.call(ZCARD, key) -- 3. 判断是否允许通过 if count max_count then -- 加入一条新记录时间戳作为scoremember用时间戳:随机后缀 -- 避免同一毫秒内多个请求被当成同一个成员而互相覆盖 local tick redis.call(TIME) local now_ms tonumber(tick[1]) * 1000 math.floor(tonumber(tick[2]) / 1000) redis.call(ZADD, key, now_ms, current .. : .. math.random(1, 99999)) -- 给key设置一个略大于窗口长度的过期时间防止长期无流量时内存堆积 redis.call(PEXPIRE, key, window_ms * 2) return 1 end return 0调用方式很简单假设窗口5秒、最多30次命令行执行redis-cli EVAL $(cat sliding_limit.lua) 1 rl:user_123 1735689600000 5000 30返回1代表放行返回0代表本次请求被限流。这段脚本的核心步骤其实就是“清老记录、查数量、决定是否放行”这三步。有两个细节值得注意。第一ZSET的member必须唯一如果直接用当前时间戳做member同一毫秒两个并发请求会生成相同的时间戳ZADD就会用后一个覆盖前一个导致计数莫名丢失。第二过期时间我一般设置为窗口长度的2倍防止窗口边界处恰好key过期也防止没有流量的key一直占着内存。2.3 部署到OpenResty里的完整过程如果你用的是OpenResty可以把上面的脚本内嵌到content_by_lua_block里通过resty.redis模块执行。下面这段代码基本可以直接用作一个限流接口的骨架location /api/limited { content_by_lua_block { local redis require resty.redis local red redis.new() red:set_timeout(100) local ok, err red:connect(127.0.0.1, 6379) if not ok then ngx.say(限流服务不可用) return end local user_id ngx.var.arg_user or anonymous local script [[ local key KEYS[1] local current tonumber(ARGV[1]) local window_ms tonumber(ARGV[2]) local max_count tonumber(ARGV[3]) redis.call(ZREMRANGEBYSCORE, key, 0, current - window_ms) local count redis.call(ZCARD, key) if count max_count then redis.call(ZADD, key, current, current .. : .. math.random(1, 999999)) redis.call(PEXPIRE, key, window_ms * 2) return 1 end return 0 ]] local current_ms ngx.now() * 1000 local res, err red:evalsha_or_eval(script, 1, rl: .. user_id, current_ms, 5000, 30) if res 1 then ngx.say(ok) else ngx.status 429 ngx.say(too many requests) end } }这里千万要注意一点脚本内部的current时间应该从OpenResty的ngx.now()获取并统一转换成毫秒不要又用os.time()又用ngx.now()混着来。我曾经在真实项目里见过脚本里用os.time()取秒外层Redis的过期时间用毫秒最后限流完全失灵的例子。所有时间相关变量统一单位是最基本的要求。2.4 高并发场景下的“时间桶”改造ZSET这套方案精确度高但有一个小代价每个请求都要往ZSET里插入一条member窗口内请求数一多内存会跟着涨。如果窗口很短比如几秒钟那么窗口内的记录一般也就几百个完全没压力。但如果窗口是一小时甚至一天又希望能精确限流那ZSET的钱包会有点hold不住。这时候可以牺牲一点精度把时间离散成固定大小的桶比如每100毫秒一桶每桶只记一个计数器。窗口内需要维护的元素数量就从“请求数”降到了“桶数”内存占用会小很多。具体实现如下-- KEYS[1]: 限流key -- ARGV[1]: 当前毫秒 -- ARGV[2]: 窗口长度(毫秒) -- ARGV[3]: 最大请求数 local key KEYS[1] local current tonumber(ARGV[1]) local window_ms tonumber(ARGV[2]) local max_count tonumber(ARGV[3]) local bucket_ms 100 -- 每100毫秒一个桶 local current_bucket math.floor(current / bucket_ms) local oldest_bucket math.floor((current - window_ms) / bucket_ms) -- 清理窗口外的旧桶 redis.call(ZREMRANGEBYSCORE, key, 0, oldest_bucket) local count redis.call(ZCARD, key) if count max_count then -- 当前桶计数1 redis.call(ZINCRBY, key, 1, current_bucket) redis.call(PEXPIRE, key, window_ms * 2) return 1 end return 0时间桶方案的本质是“用桶的粒度换内存”统计误差最多一个桶100毫秒绝大多数业务完全可以接受。我在高并发接口上用的就是这套实测下来稳定性比全量ZSET好不少Redis的CPU占用也降下来了。3. 数据流场景滑动窗口的聚合计算与滤波除了限流另一类常见场景是用滑动窗口处理数值流。比如监控指标里计算最近N个数据点的平均值判断当前链路是否抖动比如传感器波形、股票K线需要在一串连续数据里找到滑动窗口的最大值、最小值。这一节我把三种最常用的运算单独讲清楚。3.1 先看最直白的遍历法最直接的做法是每来一个新数据就把窗口里所有元素重新遍历一遍。窗口大小为k每个数据点要付出O(k)的计算成本。数据量小、窗口短的时候没问题但数据量一大这个开销会让人看得心慌。以滑动窗口最大值为例-- 朴素版本每来一个新元素遍历整个窗口 local function sliding_max_naive(nums, k) local result {} for i k, #nums do local m nums[i - k 1] for j i - k 2, i do if nums[j] m then m nums[j] end end result[#result 1] m end return result end这个版本正确性没问题但窗口长度一旦上到几千每来一个数据都要几千次比较处理几百万条数据基本就跑不动了。所以在数据量大的场景里我不会直接用这个版本。3.2 用单调队列在O(1)内算出滑动最大值和最小值更高效的方法是维护一个单调双端队列让队首始终是当前窗口的最大值。每个元素最多入队一次、出队一次整体均摊复杂度是O(1)。Lua里没有原生的双端队列我用两个索引指针head和tail模拟效果一样代码也容易看懂-- 用单调队列计算滑动窗口最大值 local function sliding_max(nums, k) local result {} local q {} -- 队列存的是nums的下标 local head, tail 1, 0 for i 1, #nums do -- 1. 弹出已经滑出窗口的下标 while head tail and q[head] i - k do head head 1 end -- 2. 从队尾依次弹出所有比当前元素小或等于的下标 -- 保证队列内元素值严格递减 while head tail and nums[q[tail]] nums[i] do tail tail - 1 end -- 3. 当前下标入队 tail tail 1 q[tail] i -- 4. 窗口形成后队首就是当前窗口最大值 if i k then result[#result 1] nums[q[head]] end end return result end -- 验证 local nums {1, 3, -1, -3, 5, 3, 6, 7} local maxs sliding_max(nums, 3) -- 输出: 3, 3, 5, 5, 6, 7这段代码的核心思想是如果一个新到来的元素比队尾的某些元素都大那么那些老元素在后续滑动过程中永远不可能成为最大值了因为它们既更小又更早过期留着纯属浪费空间直接弹掉。维护这个单调递减队列之后队首永远指向窗口最大值代价极小。如果你要的是滑动窗口最小值就把第2步的条件从改成让队列变成单调递增即可。整个模板只有一个符号的差别非常方便。3.3 滑动平均值和指数加权滤波滑动平均也是最常见的滑动窗口应用之一比如仪表盘上的最近5分钟CPU平均值。用Lua实现时不需要维护队列只需要用一个累加器每次加新值、减掉滑出窗口的旧值-- 计算滑动窗口均值返回长度等于输入减去k1的结果数组 local function sliding_mean(values, k) local sum, result 0, {} for i 1, #values do sum sum values[i] if i k then sum sum - values[i - k] end if i k then result[#result 1] sum / k end end return result end这种等权滑动平均对窗口内所有数据一视同仁。但如果你希望越近的数据权重越大比如实时监控告警响应速度要求高那就更适合用指数加权滑动平均EWMA。它在Lua里实现起来更简单-- 指数加权滑动平均(EWMA) -- alpha取值0~1越大代表越偏向新数据 local function ewma(values, alpha) local result {} local avg values[1] result[1] avg for i 2, #values do avg alpha * values[i] (1 - alpha) * avg result[i] avg end return result endEWMA本质上是一个“权重按指数衰减”的滑动窗口旧数据永远留在平均值里只是权重越来越小。它在很多实时指标计算里非常实用代码量还少得惊人。3.4 窗口大小和权重怎么给定窗口大小是关键参数但很多人第一次直接拍脑袋定一个。窗口偏大数据趋势更平滑但滞后更明显窗口偏小响应更快但噪声滤不干净。做监控的时候我一般用两三秒的窗口做实时告警用三十到六十秒的窗口做趋势展示。如果是传感器滤波窗口大小通常由信号的频率决定比如采样频率是100Hz那10个点的窗口对应100毫秒足够滤掉一部分高频噪声。如果拿不准最务实的做法是把窗口大小和EWMA的alpha都做成配置项拿到真实数据以后再调参不要一开始就写死在代码里。阈值调参这种事纸上谈兵永远比不过实际跑出来的曲线。4. 写Lua滑动窗口时容易忽略的四个坑Lua滑动窗口看似代码量不大但真正上了生产环境坑全在细节里。时间精度、内存复用、并发竞态、数值误差……任何一个没处理到位窗口就是不“滑”的。4.1 时间精度不统一限流场景里窗口是“时间长度”必然要跟时间戳打交道。如果只精确到秒高并发限流就会出大问题。同一秒内两个请求如果被当成同一个时刻ZSET的member会冲突窗口内的计数也会失真。比如窗口5秒前4秒已经放了40个请求最后一秒突然进来100个请求秒级时间戳根本区分不了这100个请求的先后ZADD时大量member重复计数直接丢失。解决办法就是统一用毫秒甚至微秒。OpenResty的ngx.now()返回的是秒要乘以1000再取整。Redis脚本里也可以用redis.call(TIME)拿到服务器的秒数和微秒数自己拼一个毫秒时间戳这样整个判定过程用的是同一把“时钟”而不是传进来的外部时间。系统时钟和业务逻辑混用之前先对齐单位。4.2 用table.remove模拟队列的代价Lua没有原生队列很多新手习惯用table.remove(t, 1)把队首弹掉。这个写法在小窗口下没问题但窗口大、数据量大时table.remove会把数组中后面的所有元素整体前移时间复杂度是O(n)整个滑动窗口计算直接退化到O(n*k)。我在3.2节中用head和tail两个指针就是为了避开这个问题队首元素用指针移动代替物理删除。不过指针方案有个隐形成本head和tail会不断增大数组里会留下一些永远用不到的“空洞”。解决办法是定期重建数组比如每处理1万个元素就把q[head..tail]拷贝到新表然后重置指针。这个重建操作本身是O(窗口长度)均摊下来非常便宜。4.3 原子性、member唯一性和Redis阻塞回到限流场景很多人写Redis Lua脚本时容易漏掉一个细节同一毫秒两个并发请求会生成相同的时间戳memberZADD会互相覆盖计数丢失限流失效。所以member里一定要拼随机后缀或者其他唯一因子。另一个常见误解是对Redis原子性的理解。Redis是单线程执行EVAL脚本的脚本运行期间不会插入其他命令“检查count、ZADD”这两步天然是原子的不需要额外的分布式锁。但也正因为单线程如果脚本里有大循环或者一次处理几十万条ZSET记录整个Redis会被阻塞其他请求全部排队。滑动窗口限流脚本本身很轻问题不大可一旦你为了精确把窗口拉长到一小时ZSET里堆积的记录数以十万计每次请求都做ZREMRANGEBYSCORE加ZCARDCPU开销还是会涨上来。真到那一步就该果断换第2.4节的时间桶方案。4.4 浮点累加误差Lua里所有数字都是double做滑动均值时如果持续用sum sum - old new这种增量更新浮点误差会一点一点累积。数据跨度一大时序图上就会看到本不应该出现的“阶梯状”毛刺。这在监控场景里非常容易误导人。我的处理方式是每处理N个数据点主动重算一次窗口内的全量sum把误差周期性清零。N的选择取决于你对精度的容忍度一般取窗口长度的10倍即可。这样一个微小的重建代价换来了长期的数值稳定。5. 常见问题与排查实录5.1 先看一张问题速查表我把多个项目里遇到的典型问题整理成了一张速查表排查时基本可以按图索骥现象可能原因快速排查方式限流窗口刚过一半就大量拒绝请求时间戳单位不一致秒和毫秒混用打印ARGV[1]与Redis内的时间戳对比计数不准窗口内请求数明显偏少ZSET的member冲突同一时刻被覆盖ZADD时拼上随机后缀高频下Redis CPU飙升ZSET记录太多每请求全量清理改用时间桶方案滑动均值曲线出现台阶状毛刺浮点累加误差累积每N个点重算一次全量sum滑动最大值结果不正确单调队列维护方向反了输出每个i的q内容检查单调方向Redis偶发key提前过期过期时间设得比窗口短PEXPIRE设为窗口长度的2倍以上5.2 案例限流“失效”竟是时钟不同步有次上线滑动窗口限流测试环境一切正常放量后某个时段的瞬时流量却完全没被拦住。排查了很久逻辑没有任何问题最后发现是调用方传的“当前毫秒”用的是应用服务器的本地时间而Redis里存的时间戳是另一台机器的时间两台机器时钟差了200多毫秒。窗口边界一错位清理老记录的时候把不该清的清了计数统计自然就失效了。从那以后我养成了两个习惯一是所有机器统一做NTP对时偏差控制在几十毫秒内二是限流脚本里不再透传外部时间直接在Redis脚本里用redis.call(TIME)拿服务器时间保证整个判定过程用的是同一把“时钟”。时间来源不统一这个坑比算法本身的难度大得多。5.3 案例滑动平均曲线出现阶梯毛刺做某个传感器数据平滑时滑动平均曲线每隔一段时间就会出现一个不太明显的向上跳变。数据源是稳定的不是信号问题最后定位到是累加器一直在做sum sum - old new长时间跑下来浮点误差越积越大。我在窗口每推进1000个点后主动重新遍历窗口内数据算一次sum毛刺立刻消失了。很多时候看起来是数据问题实际是数值计算的细节问题。6. 最后的几点实操体会最后分享几个我觉得价值比较高的经验。第一Lua脚本里不要做“教科书式”的过度抽象。滑动窗口的核心逻辑就那么几段用函数包起来、参数暴露出来就够了没必要为了照顾通用性加一堆配置层后期反而没人敢改。第二任何跟时间相关的滑动窗口都要在脚本开头统一单位注释写清楚“本脚本默认毫秒”同事接手时就不用靠猜。第三加监控把“窗口内当前计数”作为一个指标暴露出来配合限流拒绝数你才能真正看清流量在窗口内的真实分布而不是等线上出了故障再去翻日志。在限流场景里如果你的量级不大滑动窗口甚至可以不用Redis直接在OpenResty的共享字典里存时间戳也能跑起来代码更轻。但要跨多个worker或者多台机器还是建议用Redis毕竟共享字典是每worker一份的多worker之间天然存在偏差。说到底滑动窗口只是一种算法怎么把它嵌进具体业务选什么存储、什么粒度、什么权重才是真实工程里更值得琢磨的部分。这个主题的后续扩展方向也很多给均值加上不同权重变成加权滑动平均配合时间桶降低高频场景的内存消耗在OpenResty里把整套逻辑封装成通用限流模块或者跟消息队列的消费速率联动做动态限流。我这边最近正在把手里的限流模块改成动态窗口窗口长度和阈值会根据系统当前负载自动调整基础逻辑已经跑通等稳定了再单独写一篇分享。