Sentinel滑动窗口核心LeapArray源码解析：环形数组与并发控制

做限流绕不开滑动窗口而读Sentinel这个开源限流组件的源码时LeapArray又绕不开。这个类名字直译过来就是“跳跃数组”但第一次看它的人多半会被绕晕环形数组、窗口重置、并发CAS、时钟回拨……每个点单独看都不难合在一起就容易卡壳。我最初啃这块源码时前前后后翻了十来篇文章最后干脆自己把每条分支都跑了一遍才算真正想明白。这篇文章就盯着LeapArray这一个类拆从它要解决什么问题到核心方法怎么实现再到我实际跑测试时踩过的坑一次性说透。适合刚开始接触Sentinel源码、或者被滑动窗口设计搞晕的同学看完你至少能回答三件事LeapArray为什么用环形数组、currentWindow()里每条分支在防什么、滑窗统计和固定窗口统计到底差在哪。1. 先搞清楚LeapArray解决的是什么问题1.1 固定窗口统计的先天缺陷在滑动窗口方案出现之前很多人用的是一秒一个统计桶。例如限流阈值是100QPS就每隔1000ms把计数器清零窗口内请求累加超过100就不让进。这种做法代码很简单但有一个非常典型的临界问题如果第1秒的最后100ms里来了80个请求第2秒的最前100ms里又来了80个请求固定窗口会认为这两个窗口各自都没有超过100于是全部放行。可在用户视角里这200ms内实际涌入了160个请求早就把后端打挂了。这个问题的根源是“窗口边界”是固定切好的流量尖峰刚好卡在边界两侧时会被分割到两个不共享计数的窗口里。要解决它最直接的想法是让窗口“动起来”不是每隔1秒整体切换而是每来一个请求都统计“当前时刻往前推1秒”这个区间内的总数。这就是滑动窗口的思路。1.2 从精确滑动日志到滑动窗口最朴素的滑动窗口实现是滑动日志把每个请求的时间戳都存下来统计时扫描所有时间戳去掉超过1秒的旧记录再数剩余的数量。这个方案在统计上最精确但代价也很高。每个请求都要存一条记录QPS一高内存立刻爆炸扫描删除过期时间戳还要消耗额外CPU限流器本身反而成了瓶颈。LeapArray的做法是在精度和成本之间找个平衡点。它把整个统计周期切成若干等长的小窗口例如把1000ms切成2格每格500ms。所有格子放在一个固定长度的环形数组中时间往前走格子也跟着往前走。新请求来了找到当前时间对应的那一个格子把计数累加到格子里统计“最近1秒的总数”时不再扫描时间戳而是把环形数组里所有“还没过期”的格子里的计数直接累加。内存是固定的因为格子数固定统计也很快因为只需要做有限次加法。1.3 LeapArray三个优势我简化成一句话如果不看源码LeapArray的设计价值可以这么总结用固定数量的“时间盒子”近似一个连续滑动的窗口格子数决定了近似精度环形复用决定了内存上限。官方实现里统计秒级指标默认切2格分钟级指标默认切120格这就是典型的“按场景调精度”的思路。理解了这一层再看类名里的数组、环形、窗口这些关键词脑子里就有画面了。2. LeapArray核心源码逐段拆解2.1 类结构与成员变量一个原子数组撑起整个窗口LeapArray是泛型基类核心成员变量非常少我把它精简成下面这个结构public abstract class LeapArrayT { // 窗口格子的数量环形数组的长度 protected final int sampleCount; // 整个统计窗口的时间跨度单位毫秒 protected final int intervalInMs; // 每个格子的时间长度等于 intervalInMs / sampleCount protected final int windowLengthInMs; // 核心存储结构原子引用的环形数组 protected final AtomicReferenceArrayWindowWrapT array; public LeapArray(int sampleCount, int intervalInMs) { this.sampleCount sampleCount; this.intervalInMs intervalInMs; this.windowLengthInMs intervalInMs / sampleCount; this.array new AtomicReferenceArray(sampleCount); } }真正存数据的是AtomicReferenceArrayWindowWrapT。为什么用原子引用数组而不是普通数组加锁因为在高并发下多个线程可能同时定位到同一个格子需要CAS无锁抢占普通数组配合synchronized也能做但锁粒度大、竞争多性能差不少。原子引用数组提供的是数组元素级别的原子可见性刚好匹配“一个格子被并发读写”的场景。WindowWrapT是每个格子的包装类里面有三个东西windowLengthInMs这个格子自身的时间跨度、windowStart这个格子的起始时间毫秒时间戳、value真正的统计桶一般是一个MetricBucket。所有围绕窗口的运算本质都是围绕windowStart和时间戳比较。2.2 时间如何映射到环形数组的下标环形数组最巧妙的地方是时间到下标的映射。给定当前时间戳计算它落在第几个格子只需要两步private int currentWindowIndex(long timeMillis) { long timeId timeMillis / windowLengthInMs; return (int) (timeId % sampleCount); }时间先除以格子长度得到一个“第几个格子周期”的编号再对格子总数取模就落到环形数组下标上。这里需要注意timeMillis / windowLengthInMs本身不是窗口起始时间因为除法结果包含余数。真正的窗口起始时间要再对齐一下private long currentWindowStart(long timeMillis) { return timeMillis - timeMillis % windowLengthInMs; }举例格子长度是500ms1010ms这个时刻会被映射到窗口[1000, 1500)起始时间是1000ms下标是(1010 / 500) % N。这句话看着简单但它是后面判断“这个格子是否过期”的基础。2.3 currentWindow()方法源码里最核心的一个方法整个LeapArray的操作入口就是currentWindow(long timeMillis)它返回当前时间对应的窗口包装类。方法本身不长但每条分支都有明确的并发场景我把核心逻辑用伪代码还原public WindowWrapT currentWindow(long timeMillis) { long windowStart currentWindowStart(timeMillis); int idx currentWindowIndex(timeMillis); WindowWrapT old array.get(idx); // 分支1格子还是空的CAS创建 if (old null) { WindowWrapT created new WindowWrap(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); if (array.compareAndSet(idx, null, created)) { return created; } // CAS失败说明其他线程抢先创建了直接返回别人创建好的 return array.get(idx); } // 分支2当前时间正好落在旧格子的窗口范围内直接复用 if (windowStart old.windowStart()) { return old; } // 分支3当前窗口起始时间比旧格子的起始时间更晚说明格子过期需要重置 if (windowStart old.windowStart()) { return resetWindowTo(old, windowStart); } // 分支4当前窗口起始时间比旧格子还早说明系统时钟回拨了 return null; }分支1最常见。两个线程同时拿到idx发现old null都去创建一个新窗口谁CAS成功了谁就返回自己创建的另一个人CAS失败后要重新从数组里读读到的就是胜出者创建的对象。注意这里失败的线程没有再创建第二个对象这是为了避免浪费和不一致。分支2是理想情况。同一个格子生命周期内所有请求都直接命中同一个窗口对象直接把计数累加进去就行连锁都不用。多数请求走的是这个分支所以性能才高。分支3是“窗口滚动”的核心。旧格子对应的窗口已经过去了但它还占着数组这个位置需要被重置成新的窗口把windowStart更新到最新时间同时把格子里的统计值清零。这里必须做并发保护不能多个线程一起重置这就是resetWindowTo()的事儿。分支4是很多文章会忽略的时钟回拨分支。机器时间被手动改回去、或者NTP同步导致时间倒退时当前时间算出来的windowStart反而比数组里已有格子还小此时无法把旧格子“回拨”复用。返回null后上层统计会选择放弃这次累加保证数据一致性优先。2.4 窗口重置的并发控制细节重置逻辑可以用下面这段描述protected WindowWrapT resetWindowTo(WindowWrapT window, long startTime) { // 避免多个线程同时重置同一个窗口 synchronized (window) { if (startTime window.windowStart()) { window.setWindowStart(startTime); window.setValue(newEmptyBucket()); return window; } else { return window; } } }关键点有两个。第一锁的对象是window本身而不是整个LeapArray。这样两个线程即使同时进入重置逻辑也只会锁住同一个格子其他格子不受影响并发度比全局锁高得多。第二进入锁内后还要再判断一次startTime window.windowStart()。为什么会有这种双检因为可能在等待锁的过程中另一个线程已经完成了重置并更新了windowStart。如果自己在锁内不做第二次判断直接重置就会把别人刚刚写好的一整格数据清零造成统计丢失。这个double-check模式凡是做过并发状态更新的人都应该熟悉。关于重置时是“复用旧对象”还是“新建对象”源码选择的是复用。新建一个WindowWrap对象和MetricBucket对象本身不复杂但在高QPS下窗口每秒切换好几次频繁创建对象会增加GC压力。复用旧对象只需要清空计数器、更新起始时间避免了大部分内存分配。这也是LeapArray在高并发下能保持稳定的原因之一。3. 从LeapArray到限流判定统计指标如何流转3.1 MetricBucket窗口里到底存了什么LeapArray的泛型参数T在真实实现里通常对应MetricBucket。这个桶内部维护了一组计数器按事件类型区分。我把常用的维度列一下事件类型含义PASS放行的请求数BLOCK被规则拦截的请求数EXCEPTION业务抛异常的次数SUCCESS执行成功的请求数RT请求总耗时代码层面MetricBucket通常会有一个LongAdder[]数组按MetricEvent枚举下标存储。为什么用LongAdder而不是AtomicLong因为AtomicLong在高并发写同一个计数器时会产生严重的CAS竞争缓存一致性协议会把所有线程打到同一份缓存行上。LongAdder通过内部维护一组 Cell把竞争分散到不同内存单元上读的时候再求和写多读少的场景下收益非常明显。限流统计正好是写多读少的典型场景每次请求都要加计数而只有判断阈值的时候才读一次总数。3.2 实时QPS是怎么算出来的先明确一个概念LeapArray里的“当前窗口”和“滑动窗口总和”是两回事。单个当前窗口只覆盖windowLengthInMs这段时间而限流判断需要的是整个统计周期内的总和。Sentinel在ArrayMetric这类封装中会通过list()方法把环形数组里所有未过期的格子取出来累加每个格子的计数。public ListT list() { long now System.currentTimeMillis(); ListT result new ArrayList(sampleCount); for (int i 0; i sampleCount; i) { WindowWrapT window array.get(i); if (window null || isWindowDeprecated(now, window)) { continue; } result.add(window.value()); } return result; }假如interval是1000ms、sampleCount是2那么当前时间附近的2个格子理论上恰好能覆盖最近约1秒的流量。把所有格子里的PASS计数加起来就是最近这个滑动周期内放行的总请求数再除以周期秒数就是QPS。这里的“约”字有讲究如果请求刚好落在边界上array里2个格子覆盖的绝对时间范围可能不是严格精确的1000ms。这是格子化近似的固有误差能接受但要知道它的存在。3.3 一次请求从进入到限流判断的完整链路我用一个请求的例子把链路串起来。假设一个资源被限流阈值为100QPS的规则保护。请求进入后先走责任链。在统计节点Sentinel会先找到当前请求对应的StatisticNode调用increasePassRequestCount()内部其实就是拿到当前的MetricBucket执行add(PASS, 1)。这一步就会触发我们上面讲的currentWindow()方法完成窗口定位、创建或重置最后计数落到格子里。随后进入流控规则判断FlowRuleChecker会调用节点上的passQps()方法也就是把LeapArray里所有未过期格子的PASS计数累加一遍得到当前滑动周期内的总请求数。如果这个数超过了100就抛出BlockException记住要把这个BLOCK计数也加到窗口的BLOCK维度里。请求通过后无论成功还是异常最终也会把SUCCESS、EXCEPTION、RT累计到对应的维度。这个链路揭示了一个很关键的细节Sentinel的限流判断里统计和判断是分离的LeapArray只是提供统计数据的能力至于怎么判断、拦截后干什么是上层规则引擎的事。这也是它为什么能被复用到多个场景的原因。4. 实操验证与踩坑记录4.1 如何用单元测试验证滑动窗口正确性我读源码时最怕的一种情况是“代码看懂了但不知道对不对”。测滑动窗口不能依赖肉眼要直接写单元测试去验证三个核心行为时间戳映射、窗口重置、总数滚动。时间戳映射很好测。比如sampleCount2、intervalInMs1000时时间戳100ms应该落在下标0时间戳600ms落在下标1时间戳1100ms又落回下标0。注意这里是“又落回”因为环形数组会把新一周期的时间映射到同一个槽位而槽位里的窗口对象会被重置。测试时可以用一个小技巧取当前时间戳的整秒对齐分别传入对齐点前后几毫秒的值断言返回的窗口起始时间符合预期。窗口重置的测试相对隐蔽。我实际写的时候是构造一个LeapArray先取当前窗口累加一些计数然后sleep到下一个窗口周期再次调用currentWindow()断言返回的是同一个窗口对象但内部计数已经被清空、起始时间已经更新。这个测试能证明重置分支确实复用了对象而不是新建。滑动总数的测试我是这么做的先向相邻的两个窗口分别打点再调用list()统计断言总数等于两个窗口计数之和。更严谨一点可以sleep跨过一个窗口过期时间再统计验证过期窗口已经被排除。这个测试对isWindowDeprecated的时间边界非常敏感跑几次就能体会“时间窗口左闭右开”的含义。提示写这类测试时不要依赖真实时间sleep太久否则测试变慢而且容易受环境干扰。可以考虑把“当前时间”抽象成一个可注入的时间源这是很多人做统计类测试时忽略的设计点。4.2 性能优化时间获取与伪共享LeapArray里每次取窗口都要计算当前时间戳。System.currentTimeMillis()在高频调用下并不是零成本的它涉及系统调用和时钟源读取在超高QPS压测环境下会成为可见的CPU热点。我见过一些高并发组件内部会维护一个“缓存时间”由一个后台线程每隔十几毫秒更新一次业务线程读取时需要判断单调性不能回退。Sentinel没有把时间获取全部改成缓存方式因为它还要保证窗口切换的实时精度但你在自研类似组件时可以把这个方案作为优化选项。伪共享是另一个容易踩的点。一个MetricBucket里如果有多个LongAdder多个线程并发更新不同维度的计数器这些计数器在内存上很可能落在同一个缓存行里。一个线程写PASS维度导致缓存行失效另一个线程写RT维度也不得不去内存重新加载性能就会莫名其妙下降。解决办法是加padding填充缓存行或者干脆让每个维度独立放在一个足够大的对象里。首次读Sentinel源码时注意不到这些但真正压测到百万QPS级别问题就会显形。4.3 场景选型滑窗、令牌桶还是并发信号量LeapArray给了你准实时的滑动窗口统计但它只是一个数据结构不等于限流算法。我经常看到有人混淆“滑动窗口限流”和“令牌桶限流”的适用场景简单区分一下。滑动窗口更适合“准实时统计当前速率并做出拒绝”。它只看窗口内的请求总量不具备平滑速率的能力。突发流量到来时只要总和在阈值内都会放行但一旦越过阈值立刻拦截。对抖动敏感的业务比如接口要求瞬时波动不能太大单纯用滑窗是不够的需要配合令牌桶或者排队模式。令牌桶限流Sentinel里的匀速排队模式则更适合“削峰填谷”。它不追求在每一个极短时刻都卡住阈值而是把超过速率的请求放到队列里以均匀的速度放行。底层同样可以使用LeapArray做实时指标统计但控制策略不同。这里顺便说一个选型心得如果你维护的是下游数据库这类不能扛突发的系统优先考虑匀速排队把速率压平如果下游是弹性扩容的云端服务反而可以利用滑动窗口允许突发的好处让峰值有一定释放空间提升体验。4.4 我自己踩过的一个并发坑我第一次改写LeapArray做多级时间窗口时重置窗口那块偷懒没有加锁以为统计多一点少一点无所谓。结果压测一上QPS统计值经常跳变某些窗口的计数明显偏大。排查后发现问题出在两个线程同时进入重置分支一个线程新创建的窗口刚被写入一个请求计数另一个线程马上重置了它的起始时间并把计数清空导致数据丢失。后来我老老实实按源码的思路锁住单个窗口对象锁内做二次时间判断现象立刻消失。这件事给我的教训是统计丢失在限流器里是非常隐蔽的它不会直接让系统崩溃但会让限流阈值形同虚设。你在自己实现类似组件时宁愿锁竞争多一点也不能让重置和写入并发。5. 常见问题速查表我在读源码和实际工程中使用LeapArray时整理过一张问题速查表分享给大家。现象可能原因排查与解决QPS统计值呈周期锯齿状格子数太少窗口切换瞬间旧格子的计数整体失效调大sampleCount让窗口粒度变细压测下统计值突然偏低窗口重置和统计写入并发数据被清空参考源码重置时锁住窗口对象并做二次判断系统时间被回拨后统计异常currentWindow返回null上层放弃统计监控时钟回拨尽量用单调时钟源高QPS下CPU占用很高时间戳获取和LongAdder竞争缓存时间、对计数数组做缓存行填充两个格子覆盖的1秒区间精度不够格子化近似导致窗口边界出现震荡明确场景需求秒级用2格够用分钟级需要更多格把滑窗阈值设成100但瞬时放过150这其实是正常的只要滚动周期总和没超100就放行需要严格限制突发时改用令牌桶匀速模式这里有两个点值得再展开。第一个是“为什么秒级统计默认用2格而不是20格”。从精度角度看格子越多越接近真正的滑动日志但从工程角度看格子越多窗口切换和重置越频繁每次统计要累加的格子也越多锁竞争概率也随之上升。2格秒级窗口已经能覆盖大多数场景的限流精度需求同时把性能损耗压到了极低这是官方在精度和性能之间做的取舍。第二个是“currentWindow返回null不应该是错误吗”。时钟回拨分支返回null之后上层通常会直接忽略这次统计。这个设计我认为是合理的当一个请求的时间戳无法安全映射到任何窗口时宁可少统计一次也不能让时间回拨把整个窗口的数据弄乱。真实环境里这种零星的时钟抖动很少触发所以不会对统计准确性造成明显影响。最后分享一点读源码的体会LeapArray这段源码我每次重读都有新收获。第一遍读觉得核心就是那个取模公式第二遍读发现窗口重置的并发处理才是灵魂第三遍再读才意识到那些看不见的取舍比如对象复用、格子数选择、时钟回拨处理每一个都来自线上真实痛点。如果你也想彻底吃透它建议不要停留在看解析文章花一个下午把源码拉下来按我的思路跑一遍单元测试亲手触发一次窗口重置再故意改坏并发保护看看统计会不会跳变。碰到源码卡壳时别急着往后看先画一画环形数组的时间线把时间戳标出来很多疑问会瞬间豁然开朗。