Alibaba Sentinel LeapArray源码分析

本文主要介绍“阿里巴巴哨兵LeapArray源代码分析”。在日常操作中，相信很多人对阿里巴巴哨兵LeapArray的源代码分析有所怀疑。边肖查阅了各种资料，整理出简单易用的操作方法，希望能帮你解答“阿里巴巴哨兵LeapArray源代码分析”的疑惑！接下来，请和边肖一起学习！

最近，阿里巴巴哨兵被用来限制电流、熔断和降低服务质量。一直有一个好奇的点，哨兵是怎么做高效统计的。通过官方文件介绍：

StatisticSlot:用于记录和统计不同纬度运行时指标的监测信息。(做实时统计)

Sentinel底层采用高性能的滑动窗口数据结构LeapArray统计实时二级索引数据，可以很好的支持写多读的高并发场景。

可以发现Sentinel使用滑动窗口算法做数据统计，具体实现在LeapArray类。

哨兵的总体框架如下：

根据架构图，我们可以看到StatisticSlot中的LeapArray采用了循环数组的数据结构，类似于一致哈希算法的示意图，如图所示：

在这种结构中，每个下标代表一个滑动窗口。至于这个窗口是如何滑动的，我们可以结合原文来看。

00-

LeapArray 源码

源码路径

statistics slot是统计的入口。在它的entry()方法中，我们可以看到StatisticSlot将使用StatisticNode，然后StatisticNode将引用ArrayMetric，最后使用LeapArray。

根据当前时间获取滑动窗口

public windowwrapptcurrentwindow(longtimeMillis){ 0

if(timemillis 0){ 0

returnnull

}

//根据当前时间，计算当前时间所属滑动窗口的数组索引。

intidx=calculateTimeIdx(timeMillis)；

//根据当前时间计算当前滑动窗口的开始时间。

longwindowStart=calculatedwindowstart(timeMillis)；

/*

*根据底部标记获得圆形阵列的滑动窗口(桶)。

*

*(1)如果存储桶不存在，创建一个新的存储桶，并通过CAS将新的存储桶分配给数组下标。

*(2)如果获取的桶不是空的，并且桶的开始时间等于刚刚计算的时间，则返回当前获取的桶。

*(3)如果得到的桶不是空的，并且桶的开始时间小于刚刚计算的开始时间，则表示该桶在最后一圈使用，当前桶被重置。

*(4)如果获得的桶不是空的，并且桶的开始时间大于刚刚计算的开始时间，理论上这不应该发生。

*/

不间断空格

; 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)) {
                // 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();
            }
        } 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 {
                    // 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();
            }
        } else if (windowStart < old.windowStart()) {
            // Should not go through here, as the provided time is already behind.
            return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
        }
    }
}

根据下脚标在环形数组中获取滑动窗口（桶）的规则：

• (1) 如果桶不存在则创建新的桶，并通过CAS将新桶赋值到数组下标位。

• (2) 如果获取到的桶不为空，并且桶的开始时间等于刚刚算出来的时间，那么返回当前获取到的桶。

• (3) 如果获取到的桶不为空，并且桶的开始时间小于刚刚算出来的开始时间，那么说明这个桶是上一圈用过的桶，重置当前桶，并返回。

• (4) 如果获取到的桶不为空，并且桶的开始时间大于刚刚算出来的开始时间，理论上不应该出现这种情况。

这里有一个比较值得学习的地方是：

1. 对并发的控制：当一个新桶的创建直接是使用的CAS的原子操作来保证并发；但是重置一个桶的时候因为很难保证其原子操作（1. 需要重置多个值；2. 重置方法是一个抽象方法，需要子类去做实现），所以直接使用一个ReentrantLock锁来做并发控制。

2. 对Thread.yield();方法的使用，这个方法主要的作用是交出CPU的执行权，并重新竞争CPU执行权。这个方法再我们业务代码中其实很少用到。

如何实现的滑动的

通过上面这个方法我们可以看到我们是如果根据当前时间获取到一个桶的（滑动窗口）。但是如何实现滑动效果的呢？实现滑动效果主要看上面那个方法的如何找到桶的下标和如何更加当前时间找到当前桶的开始时间，如下：

// 根据当前时间计算出当前时间属于那个滑动窗口的数组下标
int idx = calculateTimeIdx(timeMillis);
// 根据当前时间计算出当前滑动窗口的开始时间
long windowStart = calculateWindowStart(timeMillis);

// 根据当前时间计算出当前时间属于那个滑动窗口的数组下标
private int calculateTimeIdx(/*@Valid*/ long timeMillis) {
    // 利用除法取整原则，保证了一秒内的所有时间搓得到的timeId是相等的
    long timeId = timeMillis / windowLengthInMs;
    // 利用求余运算原则，保证一秒内获取到的桶的下标位是一致的
    return (int) (timeId % array.length());
}
// 根据当前时间计算出当前滑动窗口的开始时间
protected long calculateWindowStart(/*@Valid*/ long timeMillis) {
    // 利用求余运算原则，保证一秒内获取到的桶的开始时间是一致的
    // 100 - 100 % 10 = 100 - 0 = 100
    // 101 - 101 % 10 = 101 - 1 = 100
    // 102 - 102 % 10 = 102 - 2 = 100
    return timeMillis - timeMillis % windowLengthInMs;
}

• timeMillis：表示当前时间的时间戳

• windowLengthInMs：表示一个滑动窗口的时间长度，根据源码来看是1000ms即一个滑动窗口统计1秒内的数据。

这两个方法巧妙的利用了除法取整和求余原则实现了窗口的滑动。通过最上面的结构图我们可以发现滑动窗口会根据时间戳顺时针旋转。

桶的数量就决定了滑动窗口的统计时长，根据源码来看是60个桶，即一个统计1分钟内的数据。

内部是利用并发工具类LongAdder的特性来实现的高效的数据的统计。

到此，关于“Alibaba Sentinel LeapArray源码分析”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！