简单理解 Sentinel 滑动窗口实现原理-CSDN博客

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

theme: serene-rose

1. 引言

Hi你好我是有清

对于刚经历过双 11 的电商人来说限流这个词肯定在 10.24 的晚 20.00 点被提起过

限流作为保护我们系统不被流量冲垮的手段之一建议每个电商人深入了解学习什么你不是电商人那你也得了解一下不然怎么在金三银四和面试官大胆对线

目前市面上比较流行的流量治理框架是 Sentinel在本文中我们先复习一下常见八股-限流算法有哪些然后再理解一下 Sentinel 的是如何使用滑动窗口

2. 常见限流算法

2.1. 令牌桶

令牌桶顾名思义具有一个桶存放着令牌系统会以恒定的速率往桶里放令牌拿到令牌的请求才可进行后续操作如果你没有拿到sorry你的请求将被抛弃如图所示

无标题-2023-08-07-1113

我们可以借助 Guava 的 RateLimiter 来实现令牌桶优点在于使用令牌桶放过的流量比较均匀有利于保护系统不被流量冲垮当然令牌桶的弊端在于对于持续的峰值流量无法应对。由于令牌桶算法是以恒定速率添加令牌当持续时间内产生大量请求时可能无法及时获取到足够的令牌导致请求被拒绝

2.2. 漏桶

漏桶算法我们可以理解为存在一个水龙头持续往桶里滴水然后这个桶可以匀速往外滴水平移到我们的项目实践中即我们可以维护一个有界队列作为漏桶用来承接进来的网络请求系统均匀处理队列中的网络请求一旦队列满了就触发限流策略如图所示

漏桶算法的弊端在于无法处理突如其来的大流量假设我们当前处理的速率为 1000 qps 桶容量 5000 现在来了一波持续 10s 的 2000 qps那么后几秒的网络请求将都会被抛弃

2.3. 固定窗口

固定窗口算法即系统会维护一个计数器在固定的时间段内流量进来计数器计数一旦超过上限则进行限流相关拒绝策略在下一个窗口计数器又将会被置零如图所示

固定

固定窗口的算法弊端在于我们统一假设当前的窗口限制为 1000 qps 的流量窗口间隔为 5s。第一个弊端在于边界问题在第5 s 和第 6 s分别进来了1000qps 流量相当于窗口切换的 0.1 s 内系统接受了 2000 qps 的流量很容易piaji系统挂了第二个问题在于流量突发的情况在第一秒进来了 1001 的 qps那么在 4 - 5 s 的时间内系统流量都将被限制带给用户的感觉就是这个系统怎么这么垃圾

2.4. 滑动窗口

滑动窗口算法其实就是为了解决固定窗口的弊端大窗口依然不变但是大窗口内会分为 n 个小窗口每个小窗口内维护计数器大窗口随着时间的移动不断抛弃和拾取小窗口从而达到限流的目的。

Snipaste2023-11-0511-35-34

Snipaste2023-11-0511-35-34

滑动窗口依然无法避免边界问题并且小窗口数需要开发者进行仔细的考量

3. 滑动窗口核心实现类

铺垫了这么久终于要进入正戏了

Sentinel 目前采取的就是滑动窗口算法根据上文的介绍我们来一起分析一下滑动窗口的核心实现类有哪些

LeapArrayleap 四级单词务必掌握这个单词意思是间隔leapArray 即为间隔数组我们可以简单理解为一个大窗口大窗口可以包含小窗口小窗口的数量为 sampleCount 、间隔时间大小 windowLengthInMs 都是由此数据结构控制再来一个数学公式 sampleCount = intervalInMs / windowLengthInMs

提问 intervalInMs 代表什么含义

WindowWrapwrap 四级单词务必掌握包裹整体单词意思为窗口包装类理解为一个小窗口
Metric继续来学习单词这个不知道是几级单词因为我也不会理解为指标该接口用来标识一些指标信息诸如 qps、rt、tps 等等
ArrayMetric已经有聪明的同学开始抢答了该类意为数组指标即我们滑动窗口的核心实现类对就是男一号
MetricBucket指标桶用来滑动窗口中实际统计数据

todo补充一个 uml 类图

4. 滑动窗口实现原理

在核心类中我们认识了 ArrayMetric 。接下来我们就围绕着 ArrayMetric 展开说明 Sentinel 的限流实现原理

4.1. ArrayMetric 构造

我们先看下如何构造 ArrayMetric

```

public ArrayMetric(int sampleCount, int intervalInMs) { this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs); }

public ArrayMetric(int sampleCount, int intervalInMs, boolean enableOccupy) { if (enableOccupy) { this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs); } else { this.data = new BucketLeapArray(sampleCount, intervalInMs); } } ```

ArrayMetric 提供了两个构造方法我们先来看一下参数sampleCount 在上文提到的即为小窗口数继续搬出我们的公式sampleCount = intervalInMs / windowLengthInMsintervalInMs 即每个大窗口的间隔时间enableOccupy 意为是否允许抢占即是否允许抢占下一个窗口的资源允许的话构造的子类即为 OccupiableBucketLeapArray否则为 BucketLeapArray具体二者区别我们下文再展开

在 ArrayMetric 方法中无论是 pass、rt 还是 block 都需要获取当前小窗口信息调用的方法为 data.currentWindow();

/** * Get the bucket at current timestamp. * * @return the bucket at current timestamp */ public WindowWrap<T> currentWindow() { return currentWindow(TimeUtil.currentTimeMillis()); }

通过注释我们可以看出该方法是根据当前时间戳获取小窗口信息

继续点进下一步实现类之前我们可以先想一下如果是我们去写这样一个获取小窗的方法我们会怎么实现

是不是需要取获取到当前时间戳命中的窗口下标如果其他线程已经创建过同等的时间戳窗口是否可以直接复用如果当前时间戳大于之前已经生成的窗口的时间戳如何处理

4.2. 获取当前窗口

带着这几个问题我们继续看下源码

public WindowWrap<T> currentWindow(long timeMillis) { if (timeMillis < 0) { return null; } int idx = calculateTimeIdx(timeMillis); long windowStart = calculateWindowStart(timeMillis); while (true) { WindowWrap<T> old = array.get(idx); if (old == null) { WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); if (array.compareAndSet(idx, null, window)) { return window; } else { Thread.yield(); } } else if (windowStart == old.windowStart()) { return old; } else if (windowStart > old.windowStart()) { if (updateLock.tryLock()) { try { return resetWindowTo(old, windowStart); } finally { updateLock.unlock(); } } else { Thread.yield(); } } else if (windowStart < old.windowStart()) { return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); } } }

首先生成窗口下标

``` int idx = calculateTimeIdx(timeMillis);

private int calculateTimeIdx(/@Valid/ long timeMillis) { long timeId = timeMillis / windowLengthInMs; // Calculate current index so we can map the timestamp to the leap array. return (int)(timeId % array.length()); } ```

来继续做数学题timeMillis 意味当前时间戳windowLengthInMs 小窗间隔时间假设当前时间戳为 666小窗间隔时间为 200看图

Snipaste2023-11-0416-34-19

Snipaste2023-11-0416-34-19

接下来计算小窗的起始时间

protected long calculateWindowStart(/*@Valid*/ long timeMillis) { return timeMillis - timeMillis % windowLengthInMs; }

小窗的起始时间计算的方法其实很简单了 666 - 666 % 200 = 600 对照上图一目了然

接下来分成三种情况我们一一来讨论一下

不存在旧窗口

这种情况比较简单我们直接生成新窗口即可此处采取了 CAS 来进行窗口生成保证线程一致

WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); if (array.compareAndSet(idx, null, window)) { // Successfully updated, return the created bucket. return window; } else { // Contention failed, the thread will yield its time slice to wait for bucket available. Thread.yield(); }

命中旧窗口

这种情况就更简单了直接返回旧窗口即可

当前时间戳大于旧窗口时间戳

这种情况是当 A 线程生成小窗的时候时间戳命中了 B1 窗口此时 B 线程的时间戳命中 B5 窗口即当前窗口就为 B5需要进行窗口重置我们来看代码

``` if (updateLock.tryLock()) { try { // Successfully get the update lock, now we reset the bucket. return resetWindowTo(old, windowStart); } finally { updateLock.unlock(); } } else { // Contention failed, the thread will yield its time slice to wait for bucket available. Thread.yield(); }

@Override protected WindowWrap resetWindowTo(WindowWrap w, long startTime) { // Update the start time and reset value. w.resetTo(startTime); w.value().reset(); return w; } ```

这边可以看到处理的方式就是将当前的时间的起始时间和统计值全部进行重置处理

其实还有一种情况就是当前时间小于旧窗口的起始时间但是一般不存在这种情况我们不进行讨论

4.3. 获取上一个窗口

获取上一个窗口的实现类中同样是取去计算窗口的下标但是计算下标的时候传入的不是当前的时间戳而是减去一个小窗间隔的时间戳

``` public WindowWrap getPreviousWindow(long timeMillis) { if (timeMillis < 0) { return null; } int idx = calculateTimeIdx(timeMillis - windowLengthInMs); timeMillis = timeMillis - windowLengthInMs; WindowWrap wrap = array.get(idx);

if (wrap == null || isWindowDeprecated(wrap)) { return null; }

if (wrap.windowStart() + windowLengthInMs < (timeMillis)) { return null; }

return wrap; } ```

4.4. 窗口是否废弃

如果当前的时间减去窗口的起始时间大于一整个大窗口的时间即该窗口已失效

public boolean isWindowDeprecated(long time, WindowWrap<T> windowWrap) { return time - windowWrap.windowStart() > intervalInMs; }

4.5. OccupiableBucketLeapArray

LeapArray 的重点方法我们都分析完毕了我们看下子类针对于这些方法是否有进行重写

4.5.1. 构造方法

其实在上文我们已经看到过构造 OccupiableBucketLeapArray 需要 sampleCount 和 intervalInMs但其实真正构造 OccupiableBucketLeapArray还会去构造一个 FutureBucketLeapArray 对象该对象也是继承 LeapArray结合上文说的抢占的意思可以推测出这是一个未来时间窗口的 LeapArray

``` private final FutureBucketLeapArray borrowArray;

public OccupiableBucketLeapArray(int sampleCount, int intervalInMs) { // This class is the original "CombinedBucketArray". super(sampleCount, intervalInMs); this.borrowArray = new FutureBucketLeapArray(sampleCount, intervalInMs); } ```

4.5.2. newEmptyBucket

newEmptyBucket 顾名思义用来创建一个新的空的小窗它作用的地方在于我们获取当前窗口的时候看个图

这边的实现也很简单借助到我们在构造函数的时候生成的 borrowArray如果 borrowArray 存在当前时间戳的数据则直接拿到 borrowArray 中的计数数据

``` public MetricBucket newEmptyBucket(long time) { MetricBucket newBucket = new MetricBucket();

MetricBucket borrowBucket = borrowArray.getWindowValue(time); if (borrowBucket != null) { newBucket.reset(borrowBucket); }

return newBucket; } ```

4.5.3. resetWindowTo

重置窗口在上文中我们已经介绍过了在该类实现中其实也就是判断是否 borrowArray 是否存在数据存在的话需要加上 borrowArray 中的通过线程数

``` protected WindowWrap resetWindowTo(WindowWrap w, long time) { // Update the start time and reset value. w.resetTo(time); MetricBucket borrowBucket = borrowArray.getWindowValue(time); if (borrowBucket != null) { w.value().reset(); w.value().addPass((int)borrowBucket.pass()); } else { w.value().reset(); }

return w; } ```