当前位置：首页 > news >正文

Sentinel核心算法解析の滑动窗口算法

news 来源：原创 2025/9/11 8:08:04

文章目录

前言
一、回顾：快速失败
二、固定窗口算法
三、滑动窗口算法
三、源码体现
- 3.1、ArrayMetric的初始化
- 3.2、addPass
- 3.2.1、currentWindow
- 3.2.2、wrap.value().addPass
总结

前言

在Sentinel中，流控效果有快速失败、预热和排队等待。其中快速失败的统计，利用的就是滑动窗口算法。

一、回顾：快速失败

什么是Sentinel快速失败的效果？例如我有一个接口：
在这里插入图片描述

进入Sentinel控制台，进行规则设置：
在这里插入图片描述

如果在1s中，查询次数大于1次，则触发快速失败：
在这里插入图片描述
当然也可以设置线程数：

使用压测工具，设置并发数为5，大于了阈值：
在这里插入图片描述
同样会触发快速失败：

二、固定窗口算法

如果需要实现接口限流，在对于精确度要求不高，并且请求分布较为平均的场景下，常规的计数器法即可满足要求：

在一个固定的时间窗口（比如1分钟）内允许最多 N 个请求（例如 100 个）；
记录第一个请求的时间，维护一个计数器；
如果在时间窗口内计数器超过阈值，则拒绝请求；
如果时间窗口过了，重置时间戳和计数器。

public class FixedWindowRateLimiter {private final int limit; // 限流次数private final long intervalMillis; // 时间窗口，单位：毫秒private int counter = 0; // 当前计数器private long windowStart; // 当前窗口开始时间public FixedWindowRateLimiter(int limit, long intervalMillis) {this.limit = limit;this.intervalMillis = intervalMillis;this.windowStart = System.currentTimeMillis();}/*** 尝试请求一次，如果允许返回true，否则返回false*/public synchronized boolean tryRequest() {long now = System.currentTimeMillis();if (now - windowStart >= intervalMillis) {// 超出当前时间窗口，重置计数器和窗口时间counter = 1;windowStart = now;return true;}if (counter < limit) {counter++;return true;} else {// 超过限制，拒绝请求return false;}}public static void main(String[] args) throws InterruptedException {FixedWindowRateLimiter limiter = new FixedWindowRateLimiter(5, 10000); // 10秒内最多5个请求for (int i = 1; i <= 10; i++) {boolean allowed = limiter.tryRequest();System.out.println("请求 " + i + ": " + (allowed ? "通过" : "被拒绝"));Thread.sleep(1000); // 每秒一个请求}}
}

但是这样的做法是存在弊端的，假如在固定的时间窗口内，请求的情况如下：
在这里插入图片描述
请求数量不是均匀分布的，虽然0-60s，61-120s这两个区间内的请求数量都没有超过100的阈值，但是在某一个时间段内，比如40s到90s之间，请求的数量超过了阈值（70+60=130）。
这个问题就是固定时间窗口算法的**“边界问题”**，因为它只在窗口边界上限流，而忽略了滑动区间的请求密度。问题源自于if **(now - windowStart >= intervalMillis) **这一段代码，即只统计了各自窗口边界内的流量。

三、滑动窗口算法

滑动窗口算法是针对固定窗口算法精度过低的改进。即将请求记录在每个小时间片内（比如每秒），然后滑动计算最近 N 秒内的总请求数，例如同样需要对60s内的请求进行统计和限流，与固定窗口算法不同的是，滑动窗口算法将60s划分成了n等分：
在这里插入图片描述
每过10s，窗格就会向右边移动一格：

每个区间，有着自己独立的计数器，在统计时会用该窗口内最后一个区间的计数 - 该窗口内第一个区间的计数和阈值进行比较。

那么这样划分，就能完全避免固定窗口算法存在的边界问题了吗？答案是否定的：假设在75s的时候，来了110个请求，而滑动窗口还在10-70s的区间内（目前的滑动窗口是每隔10s滑动一次），那么75s到15s之间的请求数量一定超过了阈值，但是按照目前的统计情况没有限制住。
在这里插入图片描述
这次的问题源于粒度。窗口划分的粒度越细，精度也就越高。（上面的案例，如果把精度划成5s，则问题得到了解决）但是相应的对于内存的开销也就越大，并且粒度不可能无限制细化。如果追求严格按时间滑动的统计，可以使用滑动日志算法
滑动窗口算法的代码简单实现：

每个请求来的时候，把它的时间戳加入列表。
然后遍历 LinkedList，移除那些“窗口之外”的请求记录。
最后看当前列表里的元素个数是否超过限流阈值。

public class SlidingWindowLimiterWithLinkedList {private final int limit; // 窗口内最大请求数private final long windowSizeMillis; // 窗口长度（毫秒）private final LinkedList<Long> requestTimestamps = new LinkedList<>();public SlidingWindowLimiterWithLinkedList(int limit, long windowSizeMillis) {this.limit = limit;this.windowSizeMillis = windowSizeMillis;}public synchronized boolean tryRequest() {long now = System.currentTimeMillis();// 清理过期的请求while (!requestTimestamps.isEmpty() && now - requestTimestamps.peekFirst() > windowSizeMillis) {requestTimestamps.pollFirst(); // 移除最早的请求时间}if (requestTimestamps.size() < limit) {requestTimestamps.addLast(now);return true;} else {return false; // 超过限流阈值}}// 测试代码public static void main(String[] args) throws InterruptedException {SlidingWindowLimiterWithLinkedList limiter = new SlidingWindowLimiterWithLinkedList(5, 10000); // 10秒最多5个请求for (int i = 1; i <= 10; i++) {boolean allowed = limiter.tryRequest();System.out.println("请求 " + i + ": " + (allowed ? "通过" : "被拒绝"));Thread.sleep(1500); // 每1.5秒发一次请求}}
}

三、源码体现

在StatisticSlot节点的addPassRequest方法中，体现了Sentinel滑动窗口算法的实现。
在这里插入图片描述
支持分钟级别和秒级别的实现。

3.1、ArrayMetric的初始化

ArrayMetric在构造StatisticNode时初始化。
在这里插入图片描述
LeapArray类型的data属性，实际是OccupiableBucketLeapArray

在其父类LeapArray的构造方法中，对成员变量进行了赋值操作：

windowLengthInMs代表了每个窗格的大小，这里是1000 / 2 = 500ms
intervalInMs代表了窗格总大小，是1000ms
sampleCount代表了窗格个数，是2
array是一个存放了时间窗口对象的原子引用数组，默认容量为2（窗格的个数）

在这里插入图片描述
时间窗口对象WindowWrap< T >是对每个时间窗口的数据包装，泛型T代表窗口里保存的统计数据，比如MetricBucket
实际是这样的内存结构：

ArrayMetric└── LeapArray< MetricBucket > （字段：leapArray）└── FutureBucketLeapArray （子类实现）└── AtomicReferenceArray<WindowWrap< MetricBucket >>（字段：array）└── WindowWrap< MetricBucket >（每个时间窗口）└── MetricBucket（实际统计数据）

在这里插入图片描述

3.2、addPass

上面的初始化工作完成后，会进入ArrayMetric的addPass方法，在该方法中做了两件事：

找到当前时间点所属的那一段时间窗口，内部会根据系统时间计算当前时间落在哪个 WindowWrap 上。
把这次请求成功的数量加到当前窗口的统计值里，在这个窗口里累加通过的请求数量。

在这里插入图片描述

3.2.1、currentWindow

在调用currentWindow时，data的实际类型是OccupiableBucketLeapArray。这里传入的是当前时间：
在这里插入图片描述
currentWindow中的calculateTimeIdx，目的是为了计算当前的时间点会落在哪个时间窗格上：

currentWindow中的calculateWindowStart，目的是为了计算当前时间点落在的时间窗格的起始时间

例如传入的参数timeMillis获取到的是800，经过计算得出，会落在第一个时间窗格上，并且该窗格的起点是500：
在这里插入图片描述
接下来的逻辑都是根据上面计算出的结果，进行一系列的判断，首先从数组中获取计算出下标对应的的WindowWrap对象：

如果获取到的为空，则会初始化一个，然后通过CAS操作设置回数组对应的下标上（如果存在并发冲突，当前线程会出让时间片，让其他线程去CAS）：

在这里插入图片描述

当前时间点落在的时间窗格的起始时间，和从数组中获取计算出下标对应的的WindowWrap对象的起始时间相同，则直接返回该WindowWrap对象。

在这里插入图片描述

当前时间点落在的时间窗格的起始时间，大于从数组中获取计算出下标对应的的WindowWrap对象的起始时间，则会触发更新操作，这也是Sentinel窗口滑动的体现，什么情况会进入这个分支？最典型的，timeMillis为1600，计算出的idx为1，但是windowStart为1500。（idx为1的窗格，时间范围应该是500-1000）

在这里插入图片描述
选择OccupiableBucketLeapArray的实现：

在该方法中，实现了旧窗口计数迁移到新窗口的逻辑：

首先将windowStart属性，设置为calculateWindowStart计算出的当前时间点落在的时间窗格的起始时间

在这里插入图片描述

返回原WindowWrap的MetricBucket （尝试从 borrowArray 中借用历史值）

在这里插入图片描述
- 如果历史值不为空，重置当前窗口的统计对象，然后从 borrowBucket 中把 pass 数拿过来加到当前窗口。
- 如果历史值为空，只做一个完全的清空。

在这里插入图片描述
这时的时间窗口：

在Sentinel中滑动窗口的更新，体现在数组的每个下标窗格的起始时间和结束时间的更新
currentWindow方法最后还有一种情况，是针对时钟回拨：
在这里插入图片描述

为什么初始化WindowWrap使用CAS，而更新操作加锁？我想是因为初始化操作耗时短、且只需要成功一次，所以可以用轻量的 CAS。而更新操作逻辑复杂、涉及共享数据的一致性，所以需要加锁来确保线程安全。

3.2.2、wrap.value().addPass

在currentWindow操作中，拿到了当前时间所在时间窗格的对象WindowWrap后，首先会获取value，这里获取到的是MetricBucket。
MetricBucket中有一个LongAdder[] 原子数组，存放的是当前窗格中请求的数量。
在这里插入图片描述

调用addPass，n就是请求个数。

MetricEvent是一个枚举类，标识了不同类型的请求：

然后调用add方法，给某个类型的指标增加 n 个值。（每个枚举类型，都代表LongAdder[]的一个下标）

MetricEvent 枚举	ordinal 值	counters 下标	含义
PASS	0	counters[0]	记录通过的请求数
BLOCK	1	counters[1]	记录被拒绝的请求数
SUCCESS	2	counters[2]	记录成功的请求数
EXCEPTION	3	counters[3]	记录发生异常的次数
RT	4	counters[4]	记录响应时间（累计值）

总结

Sentinel 流控中的快速失败模式，基于其实现的一套滑动窗口算法，支持以 QPS（每秒请求数）或线程数作为控制指标。
窗口算法分为两种：固定窗口算法与滑动窗口算法。其中，固定窗口实现简单，但存在精度较低和边界问题严重的缺陷。滑动窗口是对固定窗口的改进方案：将统计周期进一步细分为多个小窗口，并以固定的时间间隔向前滑动，从而大幅减轻边界问题。窗口越小，精度越高，边界问题越不明显，但也意味着更高的内存开销。
在 Sentinel 的底层实现中，滑动窗口由 ArrayMetric 负责。其内部维护了一个固定大小为 2 的 WindowWrap 数组（不支持扩容），每个窗口内部包含一个 LongAdder[] 原子数组用于统计数据。该数组中的每个索引对应一个枚举定义的指标项，例如：通过数、阻塞数、异常数、响应时间等。
Sentinel 在进行实时统计时，主要执行以下两个步骤：

根据当前时间定位所属的时间窗口；
对该窗口内的 LongAdder[] 执行累加操作。

具体流程如下：

首先根据当前系统时间，计算出其所在时间窗格的索引及该窗格的起始时间；
然后从 WindowWrap 数组中获取对应下标的对象；
接着对比当前时间窗口的起始时间与 WindowWrap 对象的起始时间，分为三种情况：
1. 获取到的窗口为空： 说明该位置尚未初始化，需要创建新窗口；
2. 起始时间一致： 表示该窗口仍处于有效期内，可直接复用；
3. 当前窗口起始时间晚于旧窗口： 表示窗口已过期，需要进行重置并替换原有数据。

以上机制确保了 Sentinel 能够在高并发环境下，以较低开销实现高精度的流量统计与控制。

文章目录

前言

一、回顾：快速失败

二、固定窗口算法

三、滑动窗口算法

三、源码体现

3.1、ArrayMetric的初始化

3.2、addPass

3.2.1、currentWindow

3.2.2、wrap.value().addPass

总结

相关文章：