服务流控：解密 Sentinel 底层 LeapArray 环形数组与滑动窗口算法实现

在微服务的流量控制与系统自愈（如秒级限流与熔断）中，系统必须以极高的精确度统计“当前一秒内的 QPS”以及“当前响应耗时”。

在高并发环境下，如果采用传统的锁机制（如 ReentrantLock）或者全局计数器，多线程频繁竞争锁资源会导致 CPU 暴涨，限流器本身反而会成为系统的性能瓶颈。

为了在高并发下实现**无锁（Lock-free）、常数时间复杂度 O(1) 的秒级指标统计**，Alibaba Sentinel 设计了一套基于**环形数组（LeapArray）**的滑动窗口算法。

本文将系统拆解 Sentinel 滑动窗口的物理布局、LeapArray 环形寻址公式以及基于 CAS 的无锁时间槽重置原理。

一、 环形窗口物理布局：LeapArray 与 WindowWrap

Sentinel 的滑动窗口并非真正移动的物理结构，而是通过一个**固定长度的环形数组（LeapArray）**配合**时间戳定位**模拟出来的虚幻窗口：

      [ 整个滑动窗口周期 (Interval: 1000ms) ]
      ┌────────────────────────────────────────────────────────┐
      │                                                        │
   [ 时间槽 0 ]    [ 时间槽 1 ]    [ 时间槽 2 ]  ...  [ 时间槽 4 ]
   (0ms - 200ms)  (200ms-400ms)  (400ms-600ms)       (800ms-1000ms)
      ▲
      │ (当前时间戳 % 1000 / 200 = 索引 0)
   [ 时间戳定位寻址 ]

以默认统计 1 秒 QPS 且划分为 5 个时间槽（Bucket）为例：

• 窗口跨度（sampleCount）：5。代表环形数组的大小为 5。
• 时间槽跨度（windowLengthInMs）：200 毫秒（1000ms / 5）。每个格子代表 200 毫秒。
• WindowWrap 包装器：环形数组的每个位置存放一个 WindowWrap 对象，包含当前格子的开始时间戳（windowStart）以及具体的统计实体 MetricBucket。

二、 LeapArray 环形寻址与时间槽定位公式

当请求到达 StatisticSlot 时，Sentinel 会通过 currentWindow(long timeMillis) 方法定位当前时间戳对应的环形数组索引：

1. 索引寻址公式

$$idx = frac{timeMillis}{windowLengthInMs} pmod{sampleCount}$$

例如：时间戳 timeMillis = 1689000350，带入公式：(1689000350 / 200 = 8445001)，(8445001 pmod 5 = 1)。定位到数组索引为 1 的格子。

2. 时间槽判定与 CAS 重置流转

定位到格子后，会出现以下三种逻辑分流：

1. 格子为空（未初始化）：直接新建 WindowWrap 并通过 CAS（Compare And Swap） 抢占写入该格子。
2. 格子时间戳等于当前格子开始时间：说明当前时间仍在当前槽的统计范围内，直接在内存中累加 QPS。
3. 格子时间戳小于当前格子开始时间（格子过期）：说明时间已经进入下一个大周期，该格子存放的是 1 秒前的数据。此时触发**无锁时间槽重置**：通过 CAS 将格子的开始时间戳修改为当前时间，并调用 reset() 清空 1 秒前的旧指标，随后在干净的格子里进行累加。

三、 核心统计组件性能特征对比

滑动窗口算法之所以能承载百万级 QPS 拦截，完全得益于其底层组件的超低耗时特征：

四、 总结

Sentinel 的百万级流量统计神话，完全构建在其环形数组（LeapArray）的高效设计之上。

它通过**基于时间戳模除的 LeapArray 环形寻址公式，实现了常数时间下的时间槽秒级精确定位**；并通过**结合 CAS 无锁时间槽重置与 LongAdder 分段计数，彻底消除了全局锁竞争，保障了极高并发下的超低响应延迟**。掌握这套滑动窗口与无锁自旋机制，是解决分布式监控统计并发冲突、进行高频底层代码算法调优的核心功底！