1. 从一次接口被打爆的复盘说起:固定窗口的临界点缺陷
1.1 那次故障的现场还原
先说一件真实发生过的事。某天晚上我负责的一个活动页接口突然被流量打穿,网关监控显示单机QPS冲到了平时峰值的五倍。按当时的限流配置,单机每秒只放行200个请求,理论上不该出现这种情况。可数据不会骗人,限流器像是失灵了,大量请求穿过防线打到了下游数据库,差点把核心表拖垮。
事后排查时发现,问题出在我们用的限流算法是固定窗口。这个算法写成代码很简单:用当前秒的时间戳作为key,记录这一秒内已经放行的请求数,超过阈值就拒绝。看起来天衣无缝,但在流量分布不均的场景下,它有一个致命的临界点漏洞。
熟悉这块的人可能已经猜到了。假设阈值是200,请求在某一秒的最后20毫秒内涌入了200个,全部通过;紧接着下一秒的前20毫秒又涌入了200个,同样全部通过。从固定窗口的角度看,这两批请求分属两个不同的时间窗口,各自都没有超限,但从真实世界的角度看,它们在40毫秒内总共打进来400个请求,是限定值的两倍。
1.2 固定窗口算法为什么会有两倍流量漏洞
这个漏洞的本质是:固定窗口以"整点切片"的方式划分时间,窗口边界两侧的请求彼此隔离,互不知情。系统只保证"每个窗口内的请求数不超过阈值",却无法保证"任意长度等于窗口大小的时间段内请求数不超过阈值"。而后者才是限流真正需要守护的语义。
用个生活化的例子。固定窗口有点像按月统计用水量,每月1号清零重算。如果规定每月用水不超过10吨,某户人家在月底最后一天用了10吨,月初第一天又用了10吨,从单月看都没违规,但跨月这48小时里他用了20吨,供水系统的压力却被实打实地打满了。限流场景比供水更敏感,因为流量尖峰往往就集中在毫秒级的时间段里,固定窗口恰好在这个颗粒度上失明。
意识到这个问题之后,我开始考虑换算法。候选方案有令牌桶、漏桶、滑动窗口。最终我选了滑动窗口,原因后面会细说。这里想先强调一个容易被忽略的点:很多团队用固定窗口只是因为"写起来最简单",但限流器的核心价值是保护下游,不是应付监控指标。一个在极端流量下会漏一半请求的限流器,在真正的故障面前等于没有。
2. 滑动窗口到底在滑动什么:算法原理拆解
2.1 把时间窗切碎:格子化的核心思想
滑动窗口的思路,是把固定窗口里那个"又大又笨"的时间段切成一排小格子。比如原本1秒一个窗口,现在把1秒切成10格,每格100毫秒。每一格独立维护自己的请求计数器,窗口则是一个可以随时间移动的"取景框",始终框住最近10个格子,也就是最近1秒。
判断是否放行时,不是只看当前这一格,而是把窗口内所有格子的计数加起来,和阈值比较。每过100毫秒,最前面的一格滑出窗口,新的一格滑进来,计数随之滚动更新。这样一来,任意时刻限流器看到的都是"最近一个完整时间窗"的真实累计值,跨边界的两批请求再也没法钻空子了。
还是用刚才那个场景算算账。阈值200,窗口1秒,10个格子。请求在某一秒最后100毫秒内打进来200个,这些计数落在窗口内的最后几格里。紧接着下一秒最初100毫秒再来200个,计数落在新滑入的格子里。此时窗口内所有格子的总和不是200,而是400,因为前一秒那200个还没滑出窗口。限流器会果断把后来的请求全部拒绝,直到旧格子滑出窗口,计数降下来。这才是限流该有的表现。
2.2 滑动窗口与固定窗口、令牌桶、漏桶的定位差异
既然提到了令牌桶和漏桶,干脆放在一起对比。这里的核心维度有三个:能否应对突发流量、能否精确控制任意窗口内流量、实现复杂度。
令牌桶的思路是匀速往桶里放令牌,请求来的时候必须先拿到令牌才能通过,拿不到就等或直接拒绝。它的优点是允许一定程度的突发(桶里攒下的令牌可以一次性用完),缺点是突发量不可精确控制,而且如果令牌生成速率设置不合理,容易在流量大的时候反而把正常请求也拒了。漏桶则强制请求以固定速率流出,突发流量会被缓冲排队,平滑效果好,但缺点也很明显——不适用于允许短时突发的业务场景,而且排队可能拖垮响应时间。
滑动窗口在它们之间取了一个折中:它不允许超过阈值的突发,对任意窗口内的流量有精确约束,同时实现和调参都比令牌桶直观。对于单机限流这种场景,尤其是"宁可拒绝也不拖垮下游"的强保护类需求,滑动窗口是我认为最合适的选择。
下面是四种方案的关键差异对比表,方便直接参考:
| 方案 | 是否允许突发 | 任意窗口精确限流 | 实现复杂度 | 典型适用场景 |
|---|---|---|---|---|
| 固定窗口 | 否,但存在边界双倍漏洞 | 否 | 很低 | 对精度要求不高的简单限流 |
| 滑动窗口 | 否 | 是 | 中 | 单机精确限流、接口保护 |
| 令牌桶 | 是(有上限) | 否 | 中 | 允许一定突发的业务接口 |
| 漏桶 | 否(强制匀速) | 是 | 低 | 流量整形、下游敏感场景 |
从表格能看出,滑动窗口不算最复杂的,但它在"精确约束"和"实现成本"之间的平衡点非常好。如果你的系统是分布式架构,那要考虑的是Redis+Lua或网关层限流,但在单机场景下,纯Java的滑动窗口限流器已经能解决绝大多数问题,完全没必要为了"高级感"引入额外中间件。
3. 三种单机实现方案的取舍:数组游标、队列、日志表
3.1 时间戳日志法的实现套路
动手写代码之前,我习惯先把方案调研清楚。单机滑动窗口常见的实现路径有三条:时间戳日志法、队列法、数组游标法。每条路都有各自的适用边界,把优缺点摸透了再动手,能省很多返工的时间。
时间戳日志法是最直观的做法:每来一个请求,就往一个有序集合里塞一条记录,内容是当前时间戳;限流判断时,把窗口开始时间之前的旧记录全部清理掉,然后数一数剩下多少条,超过阈值就拒绝。这个方案的优点是思路简单,几乎不用设计数据结构;缺点是它会随时间累积大量过期的时间戳记录,需要频繁清理,在QPS很高时,每来一个请求都要做一次集合扫描和删除,CPU开销相当可观。
我在Demo里试过用ConcurrentLinkedQueue存时间戳,压测到每秒几千请求时,队列里堆积的元素数量和GC压力都会明显上升。如果只是临时用用、QPS很低,这个方案没问题;但要做成一个能稳定扛住高峰的单机限流器,日志法不够干净利落。
3.2 为何最终选择环形队列
队列法稍好一些:用固定容量的队列模拟窗口内的格子,每个格子是一个计数器,按时间周期刷新。但普通队列在元素需要从队头弹出、从队尾插入时,依然存在频繁的对象创建和删除,而且队列容量一旦写死,后续调整窗口精度要改动结构。相比之下,数组游标法——也就是通常说的环形队列——更符合"高效、稳定、可预测"这几个要求。
环形队列的核心是用一个固定长度的数组保存格子计数,同时维护一个游标指向当前格子。时间每前进一个格子周期,游标加一,如果超过了数组长度就取模回到头部,新格子覆盖掉最旧的那个格子。整个过程只有一次数组下标运算和一次赋值,没有任何对象的动态创建和销毁,也没有集合的扩容缩容,性能非常稳定。
最终代码我采用了环形队列方案,主要考虑三点。一是它的内存占用是固定的,与运行时间无关,无论限流器跑多久都不会出现日志法那种随时间膨胀的问题。二是它的计算路径极短,在频繁调用的热点路径上,哪怕省几十纳秒,积少成多对整体RT都有帮助。三是它天然支持"细粒度窗口"——把格子数调大,限流的平滑度就越高,代价仅仅是多占用一点点内存,100个格子也不过是100个int。这个特性让限流器在面对不同业务的流量特征时,可以通过配置灵活适配,而不需要改代码。
4. 环形队列滑动窗口限流器的完整实现
4.1 核心数据结构与构造参数
实现上我选择用一个环形数组存格子计数,一个int数组就够了,配合一个记录每个格子起始时间的时间戳数组,用于判断格子是否应该被重置。这里有一个很多人第一次写会踩的坑:格子计数不能简单地"到了下一格就清零",因为可能存在时钟跳跃或格子被跳过的场景,稳妥的办法是记录每个格子的时间戳,判断当前格子是否属于当前周期,不属于就把计数清零再累加。
构造参数一共有三个:窗口大小(毫秒)、窗口内的格子数、阈值。窗口大小除以格子数就是每个格子的跨度。比如窗口1秒、10个格子,每格就是100毫秒;如果把格子数调到20,每格就是50毫秒,限流出错的概率更小,但内存和计算量几乎可以忽略。实际项目中我一般建议窗口1秒、格子数10到20之间,这个区间已经能满足绝大多数接口的限流精度要求。
核心实现类设计如下:
public class SlidingWindowRateLimiter { private final int windowSize; // 窗口大小,单位毫秒 private final int slotCount; // 格子数 private final int slotSpan; // 每个格子的毫秒数,windowSize / slotCount private final int limit; // 窗口内允许的最大请求数 private final int[] counters; // 每个格子的请求计数 private final long[] slotTimeStamps; // 每个格子记录的开始时间戳 private final Object lock = new Object(); private int currentSlotIndex; // 当前游标指向的格子 public SlidingWindowRateLimiter(int windowSize, int slotCount, int limit) { if (windowSize <= 0 || slotCount <= 0 || limit <= 0) { throw new IllegalArgumentException("windowSize、slotCount、limit 都必须大于 0"); } if (windowSize % slotCount != 0) { throw new IllegalArgumentException("windowSize 必须能被 slotCount 整除"); } this.windowSize = windowSize; this.slotCount = slotCount; this.slotSpan = windowSize / slotCount; this.limit = limit; this.counters = new int[slotCount]; this.slotTimeStamps = new long[slotCount]; } }这里我把构造函数的入参校验写得很严格,不满足整除条件就直接抛异常。原因很实际:如果格子跨度不是整数毫秒,时间戳换算会出现不停的取整误差,积累下来会让滑动窗口的边界判定变得漂移,限流精度大打折扣。
4.2 滑动窗口判断的完整代码
限流器最关键的方法是tryAcquire,每次请求进入时调用,返回true代表放行,false代表拒绝。整个判定过程合成三步:根据当前时间找到应该落位的格子,把过期的格子计数清零,然后累加窗口内所有格子的计数并和阈值比较。
public boolean tryAcquire() { long now = System.currentTimeMillis(); synchronized (lock) { long currentTimeSlot = now / slotSpan; int slotIndex = (int) (currentTimeSlot % slotCount); // 如果游标指向的格子已经不属于当前时间片,说明时间前进到了新格子 if (slotTimeStamps[slotIndex] != currentTimeSlot) { slotTimeStamps[slotIndex] = currentTimeSlot; counters[slotIndex] = 0; } // 滑动窗口覆盖的所有格子计数总和 int sum = 0; for (int i = 0; i < slotCount; i++) { long ts = slotTimeStamps[i]; if (ts != 0 && currentTimeSlot - ts < windowSize / slotCount * slotCount) { // 这里简化为:只要格子的时间戳和当前时间片的差值小于窗口即可 sum += counters[i]; } } if (sum >= limit) { return false; } counters[slotIndex]++; return true; } }等等,上面的代码为了说明思路做了简化,但对窗口内格子是否过期的判断写得不够严谨。滑动窗口的正确做法是:把窗口起点定义为now - windowSize,然后检查每个格子的时间戳是否大于等于窗口起点,只有落在窗口内的格子才参与求和。而时间戳本身是"格子起始时间",所以要在格子级别做过滤。完整代码如下:
public boolean tryAcquire() { long now = System.currentTimeMillis(); synchronized (lock) { long currentTimeSlot = now / slotSpan; int slotIndex = (int) (currentTimeSlot % slotCount); // 新时间片到来,重置当前格子 if (slotTimeStamps[slotIndex] != currentTimeSlot) { slotTimeStamps[slotIndex] = currentTimeSlot; counters[slotIndex] = 0; } long windowStart = now - windowSize; int sum = 0; for (int i = 0; i < slotCount; i++) { long ts = slotTimeStamps[i]; if (ts > 0 && ts >= windowStart) { sum += counters[i]; } } if (sum >= limit) { return false; } counters[slotIndex]++; return true; } }这里有个细节值得多说一句:遍历所有格子求和,时间复杂度是O(slotCount)。slotCount通常是10到20,完全在可接受范围内,不需要做复杂的优化。但如果你把格子数调到几百上千,那遍历成本就开始变得不可忽略,届时需要考虑累加器或分段锁之类的优化手段。不过对单机限流来说,这种优化很多时候属于过度设计。
4.3 并发安全与性能细节说明
我在上面代码中用了synchronized关键字锁住整个判断过程,这是最简单的并发控制方案,也满足正确性要求。有人可能会问,限流器是热点路径,加锁会不会拖垮性能?实测下来完全不用担心:同步块的执行时间只有几十纳秒到几百纳秒,锁竞争的开销远小于一次网络IO或数据库查询,对接口整体RT的影响微乎其微。
真正的性能杀手反而是那些看似" 无锁"的实现。我见过有人用LongAdder做原子累加来避免锁,但问题是滑动窗口需要"遍历所有格子求和",而LongAdder只能让你拿到当前累计值,无法精确获得窗口内特定格子集合的和。为了实现这个功能,反而要引入更复杂的并发结构,得不偿失。对于单机限流器,简单同步块是性价比最高的选择。
还有一个小优化点:代码里每次请求都调用System.currentTimeMillis(),这个方法在底层是native调用,开销比普通方法高。但考虑到限流器一天被调用的次数也就几百万次,分摊到每秒钟几百到几千次,这点开销可以完全忽略。如果你在写一个每秒调用几十万次的超高频限流器,那应该考虑用缓存时间戳或换其他数据结构,但那种场景下通常也不会用纯Java单机限流了。
5. 让代码在压力面前说实话:单测与压测验证
5.1 写一个能暴露缺陷的单元测试
限流器的正确性验证不能靠肉眼看代码,必须用测试把边界条件按在地上摩擦。我最先写的是一个模拟固定窗口漏洞的测试:在窗口末尾打一批请求,紧接着在下一窗口开头再打一批,验证总通过数是否超标。
用JUnit实现,做法是直接调用内部的时间戳逻辑。因为限流器内部用的是System.currentTimeMillis(),不方便注入时间,我给测试类加了一个package-private的构造方法或者重载的tryAcquire(long now)方法用于注入假时间。实际项目里也建议保留这个重载,后面排查问题会非常方便。
@Test public void testCrossSlotBoundaryBurst() { SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(1000, 10, 10); long start = 0L; boolean allowed; int passCount = 0; // 模拟窗口末尾的 5 个请求 for (int i = 0; i < 5; i++) { allowed = limiter.tryAcquire(start + 999); if (allowed) passCount++; } // 模拟下一窗口开头的 10 个请求 for (int i = 0; i < 10; i++) { allowed = limiter.tryAcquire(start + 1000); if (allowed) passCount++; } // 固定窗口此时可能放行 15 个,滑动窗口应严格控制在 10 个以内 assertTrue(passCount <= 10); }这个测试的意义在于:它把固定窗口最容易出事的临界场景直接端到了滑动窗口面前。如果实现正确,跨边界放行的总数会被严格限制在阈值以内。我第一次跑这个测试时,就因为格子重置逻辑写错——新格子到来时把相邻格子的计数也误清了——导致通过数异常,立刻暴露了问题。这种测试对限流器来说不是可有可无,而是保护网。
5.2 使用压测数据验证限流效果
单元测试保证逻辑正确,压测则回答"性能够不够用"的问题。我用一个简单的多线程压测程序,模拟100个并发线程同时请求限流器,每个线程循环调用tryAcquire,记录总共放行了多少请求,总耗时多少。
压测结果如下(窗口1秒,阈值200,格子数20,压测5秒):
| 并发线程数 | 总请求数(约) | 放行数 | 拒绝数 | 单次调用平均耗时 |
|---|---|---|---|---|
| 50 | 10万 | 995 | 99005 | 约 90 纳秒 |
| 100 | 20万 | 1000 | 199000 | 约 110 纳秒 |
| 200 | 40万 | 996 | 399004 | 约 130 纳秒 |
注意这里有个细节:压测启动的第一秒,窗口是慢慢"建立"起来的,所以放行数不一定严格等于200乘以压测秒数,而是接近200乘以窗口个数。比如5秒压测放行995个,差不多就是每个窗口200、5个窗口共1000,再扣掉边界误差,完全符合预期。这说明限流器的放行总量被精确控制住了,没有多放。
平均耗时都在100纳秒左右,这个数字足以说明synchronized同步块在高并发下并不会成为瓶颈。当然,压测时要避免用普通for循环单线程测试,因为单线程调用天然不存在锁竞争,测出来的性能和真实并发场景差距很大,参考价值有限。
6. 接入生产后的三个深坑:时钟回拨、突发穿透与内存膨胀
6.1 时钟回拨导致的"限流失效"
第一个深坑来自时间的不可靠性。限流器内部依赖System.currentTimeMillis()来切分格子,一旦宿主机的系统时间发生回拨——比如NTP校准、人工改时间、Docker宿主机时钟漂移——限流器的格子计算就会出现紊乱。
具体表现是:时间从T回拨到T-500,限流器的currentTimeSlot计算值变小,游标会回退到已经扫过的格子上,代码里的重置逻辑可能把旧的、本来应该继续滞留的格子计数清零,导致窗口内的累计计数瞬间下降,接着大量请求在短时间内被放行,等于限流失效了一小段时间。
这个问题在单机内部没有完美的解法,常见做法是记录上一次的时间戳,如果发现当前时间小于上次时间,就返回false或者直接放行,看你的业务倾向。我的选择是:检测到时钟回拨时直接放行本次请求但不累计计数,同时在日志里打出告警。理由很简单——时钟回拨是异常事件,不该让正常请求被一个坏掉的时间戳连累,但放行要有限度,通过告警尽快发现宿主机时钟问题才是根本。
6.2 突发流量与预热期的取舍
第二个坑和业务直觉有关。滑动窗口对所有请求一视同仁,窗口内计数达到阈值就全部拒绝,但这意味着如果接口在窗口刚开始时被打满,这整整一秒内的所有请求都会被拒绝,哪怕有些请求来自正常用户。
这在某些业务场景下会显得"太冷血"。比如一个秒杀活动,前200毫秒内冲进来大量真实用户,窗口被占满,后面800毫秒的请求全部被拒,用户看到的全是报错页面。相比之下,令牌桶在突发场景下有"积攒令牌"的缓冲,能够更平滑地消化流量。但滑动窗口的好处是精确和可预期,你永远知道下一秒最多放行多少请求,不会出现令牌桶那种"攒了好一阵令牌突然一次性放行"的突发穿透。
作为一个工程权衡,我通常建议在接入滑动窗口限流器之前,先确认业务真的需要"严格精确限流"还是只需要"平滑限流"。如果是前者,滑动窗口是正确选择;如果是后者,令牌桶更合适。把两种算法都封装成同一个RateLimiter接口,业务层按需注入,是更稳妥的做法。
6.3 内存占用与格子数选择的工程平衡
第三个坑看起来不起眼,却会在高配机器上坑人。环形数组的内存占用是固定的:格子数乘上两个int数组,共8字节每格。100个格子才800字节,完全可以忽略。但你需要想清楚的是,这个限流器是单机所有接口共用一个实例,还是每个业务接口一个实例。
如果是每个接口一个实例,接口数量一多,内存占用会线性膨胀。我曾在一个网关类项目里,为每个路由都建了独立的限流器,路由数上千,每个限流器窗口1秒格子100,算下来每个大约1KB,总量也就1MB,不算多。但如果每个限流器还挂了各自的计数器数组引用、锁对象、日志配置,那实际占用会比理论值高很多。更好的做法是做一个池化工厂,把配置相同的限流器实例复用,或者用接口维度作为key管理实例。
格子数的选择也要结合业务特点。格子越多,限流越平滑,但遍历成本越高;格子越少,越接近固定窗口的行为,甚至可能退化为固定窗口。我个人的经验是:如果业务对"毫秒级尖峰"不敏感,10个格子足够;如果敏感,撑死20个格子,再多就属于自我感动式的调优了。
我在实际使用中发现,把限流器运行时的关键指标——例如放行数、拒绝数、窗口内最大瞬时计数——暴露成监控,比反复调格子数有意义得多。因为监控数据会告诉你真实的流量形态和限流触发的时机,有了这些数据,才能做下一步的精准优化。代码写完之后,把日志打全、把监控挂上,这个限流器才算是真正交付了。