转载

Alibaba Seninel 滑动窗口实现原理(文末附原理图)

点击上方 “中间件兴趣圈” ，选择 “设为星标”

做积极的人，越努力越幸运！

Alibaba Seninel 滑动窗口实现原理(文末附原理图) 要实现限流、熔断等功能，首先要解决的问题是如何实时采集服务(资源)调用信息。例如将某一个接口设置的限流阔值 1W/tps，那首先如何判断当前的 TPS 是多少？Alibaba Sentinel 采用滑动窗口来实现实时数据的统计。

温馨提示：如果对源码不太感兴趣，可以先跳到文末，看一下滑动窗口的设计原理图，再决定是否需要阅读源码。

1、滑动窗口核心类图

我们先对上述核心类做一个简单的介绍，重点关注核心类的作用与核心属性（重点需要探究其核心数据结构）。

Metric

指标收集核心接口，主要定义一个滑动窗口中成功的数量、异常数量、阻塞数量，TPS、响应时间等数据。
ArrayMetric

滑动窗口核心实现类。
LeapArray

滑动窗口顶层数据结构，包含一个一个的窗口数据。
WindowWrap

每一个滑动窗口的包装类，其内部的数据结构用 MetricBucket 表示。
MetricBucket

指标桶，例如通过数量、阻塞数量、异常数量、成功数量、响应时间，已通过未来配额（抢占下一个滑动窗口的数量）。
MetricEvent

指标类型，例如通过数量、阻塞数量、异常数量、成功数量、响应时间等。

2、滑动窗口实现原理

2.1 ArrayMetric

滑动窗口的入口类为 ArrayMetric ，我们先来看一下其核心代码。

private final LeapArray<MetricBucket> data;   // @1
public ArrayMetric(int sampleCount, int intervalInMs) {    // @2
    this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
}
public ArrayMetric(int sampleCount, int intervalInMs, boolean enableOccupy) {   // @3
    if (enableOccupy) {
        this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
    } else {
        this.data = new BucketLeapArray(sampleCount, intervalInMs);
    }
}

代码@1：ArrayMetric 类唯一的属性，用来存储各个窗口的数据，这个是接下来我们探究的重点。

代码@2，代码@3 该类提供了两个构造方法，其核心参数为：

int intervalInMs

表示一个采集的时间间隔，例如1秒，1分钟。
int sampleCount

在一个采集间隔中抽样的个数，默认为 2，例如当 intervalInMs = 1000时，抽象两次，则一个采集间隔中会包含两个相等的区间，一个区间就是滑动窗口。
boolean enableOccupy

是否允许抢占，即当前时间戳已经达到限制后，是否可以占用下一个时间窗口的容量，这里对应 LeapArray 的两个实现类，如果允许抢占，则为 OccupiableBucketLeapArray，否则为 BucketLeapArray。

注意，LeapArray 的泛型类为 MetricBucket，意思就是指标桶，可以认为一个 MetricBucket 对象可以存储一个抽样时间段内所有的指标，例如一个抽象时间段中通过数量、阻塞数量、异常数量、成功数量、响应时间，其实现的奥秘在 LongAdder 中，本文先不对该类进行详细介绍，后续文章会单独来探究其实现原理。

这次，我们先不去看子类，反其道而行，先去看看其父类。

2.2 LongAdder

2.2.1 类图与核心属性

LeapArray 的核心属性如下：

int windowLengthInMs

每一个窗口的时间间隔，单位为毫秒。
int sampleCount

抽样个数，就一个统计时间间隔中包含的滑动窗口个数，在 intervalInMs 相同的情况下，sampleCount 越多，抽样的统计数据就越精确，相应的需要的内存也越多。
int intervalInMs

一个统计的时间间隔。
AtomicReferenceArray> array

一个统计时间间隔中滑动窗口的数组，从这里也可以看出，一个滑动窗口就是使用的 WindowWrap< MetricBucket > 来表示。

上面的各个属性的含义是从其构造函数得出来的，请其看构造函数。

public LeapArray(int sampleCount, int intervalInMs) {
    AssertUtil.isTrue(sampleCount > 0, "bucket count is invalid: " + sampleCount);
    AssertUtil.isTrue(intervalInMs > 0, "total time interval of the sliding window should be positive");
    AssertUtil.isTrue(intervalInMs % sampleCount == 0, "time span needs to be evenly divided");
    this.windowLengthInMs = intervalInMs / sampleCount;
    this.intervalInMs = intervalInMs;
    this.sampleCount = sampleCount;
    this.array = new AtomicReferenceArray<>(sampleCount);
}

那我们继续来看 LeapArray 中的方法，深入探究滑动窗口的实现细节。

2.2.2 currentWindow() 详解

该方法主要是根据当前时间来确定处于哪一个滑动窗口中，即找到上图中的 WindowWrap，该方法内部就是调用其重载方法，参数为系统的当前时间，故我们重点来看一下重载方法的实现。

public WindowWrap<T> currentWindow(long timeMillis) { 
    if (timeMillis < 0) {
        return null;
    }
    int idx = calculateTimeIdx(timeMillis);  // @1
    long windowStart = calculateWindowStart(timeMillis); // @2
    while (true) { // 死循环查找当前的时间窗口，这里之所有需要循环，是因为可能多个线程都在获取当前时间窗口。
        WindowWrap<T> old = array.get(idx);  // @3
                if (old == null) {  // @4
            WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
                    if (array.compareAndSet(idx, null, window)) {  // @5
                return window;
                    } else {
                Thread.yield();
                    }
                } else if (windowStart == old.windowStart()) { // @6
            return old;
                } else if (windowStart > old.windowStart()) {  // @7
            if (updateLock.tryLock()) {
                            try {
                    return resetWindowTo(old, windowStart);
                        } finally {
                    updateLock.unlock();
                          }
                    } else {
                Thread.yield();
                    }
            } else if (windowStart < old.windowStart()) { // @8
                    return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
            }
        }
}

代码@1：计算当前时间会落在一个采集间隔 ( LeapArray ) 中哪一个时间窗口中，即在 LeapArray 中属性 AtomicReferenceArray > array 的下标。其实现算法如下：

首先用当前时间除以一个时间窗口的时间间隔，得出当前时间是多少个时间窗口的倍数，用 n 表示。
然后我们可以看出从一系列时间窗口，从 0 开始，一起向前滚动 n 隔得到当前时间戳代表的时间窗口的位置。现在我们要定位到这个时间窗口的位置是落在 LeapArray 中数组的下标，而一个 LeapArray 中包含 sampleCount 个元素，要得到其下标，则使用 n % sampleCount 即可。

代码@2：计算当前时间戳所在的时间窗口的开始时间，即要计算出 WindowWrap 中 windowStart 的值，其实就是要算出小于当前时间戳，并且是 windowLengthInMs 的整数倍最大的数字，Sentinel 给出是算法为 ( timeMillis - timeMillis % windowLengthInMs )。

代码@3：尝试从 LeapArray 中的 WindowWrap 数组查找指定下标的元素。

代码@4：如果指定下标的元素为空，则需要创建一个 WindowWrap 。其中 WindowWrap 中的 MetricBucket 是调用其抽象方法 newEmptyBucket (timeMillis)，由不同的子类去实现。

代码@5：这里使用了 CAS 机制来更新 LeapArray 数组中的元素，因为同一时间戳，可能有多个线程都在获取当前时间窗口对象，但该时间窗口对象还未创建，这里就是避免创建多个，导致统计数据被覆盖，如果用 CAS 更新成功的线程，则返回新建好的 WindowWrap ，CAS 设置不成功的线程继续跑这个流程，然后会进入到代码@6。

代码@6：如果指定索引下的时间窗口对象不为空并判断起始时间相等，则返回。

代码@7：如果原先存在的窗口开始时间小于当前时间戳计算出来的开始时间，则表示 bucket 已被弃用。则需要将开始时间重置到新时间戳对应的开始时间戳，重置的逻辑将在下文详细介绍。

代码@8：应该不会进入到该分支，因为当前时间算出来时间窗口不会比之前的小。

2.2.3 isWindowDeprecated() 详解

接下来我们来看一下窗口的过期机制。

public boolean isWindowDeprecated(/*@NonNull*/ WindowWrap<T> windowWrap) {
    return isWindowDeprecated(TimeUtil.currentTimeMillis(), windowWrap);
}
public boolean isWindowDeprecated(long time, WindowWrap<T> windowWrap) {
    return time - windowWrap.windowStart() > intervalInMs;
}

判断滑动窗口是否生效的依据是当系统时间与滑动窗口的开始时间戳的间隔大于一个采集时间，即表示过期。即从当前窗口开始，通常包含的有效窗口为 sampleCount 个有效滑动窗口。

2.2.4 getPreviousWindow() 详解

根据当前时间获取前一个有效滑动窗口，其代码如下：

public WindowWrap<T> getPreviousWindow(long timeMillis) {
    if (timeMillis < 0) {
        return null;
    }
    int idx = calculateTimeIdx(timeMillis - windowLengthInMs); // @1
    timeMillis = timeMillis - windowLengthInMs;
    WindowWrap<T> wrap = array.get(idx);
    if (wrap == null || isWindowDeprecated(wrap)) {                 // @2
        return null;
    }
   if (wrap.windowStart() + windowLengthInMs < (timeMillis)) {   // @3
        return null;
    }
    return wrap;
}

其实现的关键点如下：

代码@1：用当前时间减去一个时间窗口间隔，然后去定位所在 LeapArray 中数组的下标。

代码@2：如果为空或已过期，则返回 null。

代码@3：如果定位的窗口的开始时间再加上 windowLengthInMs 小于 timeMills ，说明失效，则返回 null，通常是不会走到该分支。

2.2.5 滑动窗口图示

经过上面的分析，虽然还有一个核心方法 (resetWindowTo) 未进行分析，但我们应该可以画出滑动窗口的实现的实现原理图了。

接下来对上面的图进行一个简单的说明：下面的示例以采集间隔为 1 s，抽样次数为 2。

首先会创建一个 LeapArray，内部持有一个数组，元素为 2,一开始进行采集时，数组的第一个，第二个下标都会 null，例如当前时间经过 calculateTimeIdx 定位到下标为 0，此时没有滑动窗口，会创建一个滑动窗口，然后该滑动窗口会采集指标，随着进入 1s 的后500ms，后会创建第二个抽样窗口。

然后时间前进 1s，又会定位到下标为 0 的地方，但此时不会为空，因为有上一秒的采集数据，故需要将这些采集数据丢弃 ( MetricBucket value )，然后重置该窗口的 windowStart，这就是 resetWindowTo 方法的作用。

在 ArrayMetric 的构造函数出现了 LeapArray 的两个实现类型 BucketLeapArray 与 OccupiableBucketLeapArray。

其中 BucketLeapArray 比较简单，在这里就不深入研究了，我们接下来将重点探讨一下 OccupiableBucketLeapArray 的实现原理，即支持抢占未来的“令牌”。

3、OccupiableBucketLeapArray 详解

所谓的 OccupiableBucketLeapArray ，实现的思想是当前抽样统计中的“令牌”已耗尽，即达到用户设定的相关指标的阔值后，可以向下一个时间窗口，即借用未来一个采样区间。接下来我们详细来探讨一下它的核心实现原理。

3.1 类图

我们重点关注一下 OccupiableBucketLeapArray 引入了一个 FutureBucketLeapArray 的成员变量，其命名叫 borrowArray，即为借用的意思。

3.2 构造函数

public OccupiableBucketLeapArray(int sampleCount, int intervalInMs) {
    super(sampleCount, intervalInMs);
    this.borrowArray = new FutureBucketLeapArray(sampleCount, intervalInMs);
}

从构造函数可以看出，不仅创建了一个常规的 LeapArray，对应一个采集周期，还会创建一个 borrowArray ，也会包含一个采集周期。

3.3 newEmptyBucket

public MetricBucket newEmptyBucket(long time) {
    MetricBucket newBucket = new MetricBucket();   // @1
    MetricBucket borrowBucket = borrowArray.getWindowValue(time);  // @2
    if (borrowBucket != null) {  
        newBucket.reset(borrowBucket);  
    }
    return newBucket;
}

我们知道 newEmptyBucket 是在获取当前窗口时，对应的数组下标为空的时会创建。

代码@1：首先新建一个 MetricBucket。

代码@2：在新建的时候，如果曾经有借用过未来的滑动窗口，则将未来的滑动窗口上收集的数据 copy 到新创建的采集指标上，再返回。

3.4 resetWindowTo

protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long time) {      
    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;
}

遇到过期的滑动窗口时，需要对滑动窗口进行重置，这里的思路和 newEmptyBucket 的核心思想是一样的，即如果存在已借用的情况，在重置后需要加上在未来已使用过的许可，就不一一展开了。

3.5 addWaiting

public void addWaiting(long time, int acquireCount) {
    WindowWrap<MetricBucket> window = borrowArray.currentWindow(time);
    window.value().add(MetricEvent.PASS, acquireCount);
}

经过上面的分析，先做一个大胆的猜测，该方法应该是当前滑动窗口中的“令牌”已使用完成，借用未来的令牌。将在下文给出证明。

滑动窗口的实现原理就介绍到这里了。大家可以按照上面的代码结合下图做一个理解。