Sentinel架构篇 - 10分钟带你看滑动窗口算法的应用

限流算法

以固定时间窗口算法和滑动时间窗口算法为例，展开两种限流算法的分析。

固定时间窗口算法

在固定的时间窗口内，设置允许固定数量的请求进入。如果超过设定的阈值就拒绝请求或者排队。

具体的，按照时间划分为若干个时间窗口，每个时间窗口里面的设置的请求数量的阈值都是相同的。一旦某个时间窗口内的请求数量达到阈值，就会拒绝新的请求或者进入排队状态。

缺点是无法计算跨相邻时间窗口的请求数量是否达到阈值。

滑动时间窗口算法

在固定时间窗口的基础上，时间窗口的起点和终点不再固定，而是随着时间推移而不断变化，但是每个时间窗口的长度（终点-起点）始终是固定的，也就是说整体会随着时间的推移而不断滑动。

但是每次时间窗口的移动，都需要重新统计请求数量，会有一些重叠区域重复计算的问题，因此可以对时间窗口进行更细粒度的划分，增加一些子时间窗口，即样本窗口。这样对时间窗口内部的请求数量的计算就会变成对相应的样本窗口内部的请求数量的计算，再求和。如果超过阈值，同样会被限流。

源码分析

以 Sentinel 内部的 LeapArray 的 currentWindow 方法为例，解析如何根据指定时间获取对应的样本窗口。

流程概述

1、将指定时间 / 时间窗口的长度（默认500ms），再 % 样本窗口总数量，得到所属的新的样本窗口对应的下标 n。

2、再通过指定时间 - 指定时间 % 时间窗口的长度，得到对应样本窗口的开始时间。

3、从缓存中获取指定下标 n 的旧的样本窗口，如果该样本窗口不存在，则进行创建并返回。

4、比较新样本窗口的开始时间 t1 与旧样本窗口的开始时间 t2，分为三种情况。

• 如果 t1 = t2，说明新样本窗口与旧样本窗口是相同的，则返回旧样本窗口。
• 如果 t1 > t2，说明旧样本窗口的状态滞后，则重置旧样本窗口的所有指标，再使用 LongAdder 计算某一指标并进行更新，最后返回更新后的样本窗口。
• 如果 t1 < t2，说明时间发生了倒流（一般不会发生）则创建新的样本窗口并返回。

LeapArray

public WindowWrap<T> currentWindow(long timeMillis) {if (timeMillis < 0) {return null;}// 计算指定时间所属的样本窗口的下标int idx = calculateTimeIdx(timeMillis);// 计算指定时间所属的样本窗口的起始时间点long windowStart = calculateWindowStart(timeMillis);/** Get bucket item at given time from the array.** (1) Bucket is absent, then just create a new bucket and CAS update to circular array.* (2) Bucket is up-to-date, then just return the bucket.* (3) Bucket is deprecated, then reset current bucket and clean all deprecated buckets.*/while (true) {WindowWrap<T> old = array.get(idx);if (old == null) {/**     B0       B1      B2    NULL      B4* ||_______|_______|_______|_______|_______||___* 200     400     600     800     1000    1200  timestamp*                             ^*                          time=888*            bucket is empty, so create new and update** If the old bucket is absent, then we create a new bucket at {@code windowStart},* then try to update circular array via a CAS operation. Only one thread can* succeed to update, while other threads yield its time slice.*/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()) {/**     B0       B1      B2     B3      B4* ||_______|_______|_______|_______|_______||___* 200     400     600     800     1000    1200  timestamp*                             ^*                          time=888*            startTime of Bucket 3: 800, so it's up-to-date** If current {@code windowStart} is equal to the start timestamp of old bucket,* that means the time is within the bucket, so directly return the bucket.*/return old;} else if (windowStart > old.windowStart()) {/**   (old)*             B0       B1      B2    NULL      B4* |_______||_______|_______|_______|_______|_______||___* ...    1200     1400    1600    1800    2000    2200  timestamp*                              ^*                           time=1676*          startTime of Bucket 2: 400, deprecated, should be reset** If the start timestamp of old bucket is behind provided time, that means* the bucket is deprecated. We have to reset the bucket to current {@code windowStart}.* Note that the reset and clean-up operations are hard to be atomic,* so we need a update lock to guarantee the correctness of bucket update.** The update lock is conditional (tiny scope) and will take effect only when* bucket is deprecated, so in most cases it won't lead to performance loss.*/if (updateLock.tryLock()) {try {// 重置所有指标并计算PASS指标return resetWindowTo(old, windowStart);} finally {updateLock.unlock();}} else {Thread.yield();}} else if (windowStart < old.windowStart()) {// 注意：一般不会出现该情况，该情况属于时间倒流return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));}}
}

calculateTimeIdx

private int calculateTimeIdx(/*@Valid*/ long timeMillis) {// windowLengthInMs默认是500long timeId = timeMillis / windowLengthInMs;// array数组的长度默认是2return (int)(timeId % array.length());
}

计算指定时间所属的样本窗口的下标。

calculateWindowStart

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

计算指定时间所属的样本窗口的开始时间。

resetWindowTo

以 OccupiableBucketLeapArray 为例。

@Override
protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long time) {// 将windowStart设置为指定时间，即样本窗口的开始时间w.resetTo(time);// 获取样本窗口的统计数据MetricBucket borrowBucket = borrowArray.getWindowValue(time);if (borrowBucket != null) {// 重置所有指标w.value().reset();// 计算PASS指标w.value().addPass((int)borrowBucket.pass());} else {// 重置所有指标w.value().reset();}return w;
}

MetricBucket#reset

public MetricBucket reset() {for (MetricEvent event : MetricEvent.values()) {// 重置所有指标counters[event.ordinal()].reset();}// 初始化minRt属性initMinRt();return this;
}

MetricEvent 是一个枚举类，包括：PASS, BLOCK, EXCEPTION, SUCCESS, RT, OCCUPIED_PASS。

MetricBucket#initMinRt

private void initMinRt() {// 获取 csp.sentinel.statistic.max.rt 属性值（默认 5000），并初始化minRt属性this.minRt = SentinelConfig.statisticMaxRt();
}

MetricBucket#addPass

public void addPass(int n) {// 计算PASS指标add(MetricEvent.PASS, n);
}public MetricBucket add(MetricEvent event, long n) {// 底层使用LongAdder计算指标counters[event.ordinal()].add(n);return this;
}