Alibaba Sentinel LeapArray源碼分析

這篇文章主要介紹“Alibaba Sentinel LeapArray源碼分析”，在日常操作中，相信很多人在Alibaba Sentinel LeapArray源碼分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Alibaba Sentinel LeapArray源碼分析”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

最近在使用Alibaba Sentinel來做服務(wù)的限流、熔斷和降級。一直有一個比較好奇的點，Sentinel是如果做到高效的數(shù)據(jù)統(tǒng)計的。通過官方文檔介紹：

• StatisticSlot: 則用于記錄、統(tǒng)計不同緯度的 runtime 指標監(jiān)控信息；（做實時統(tǒng)計）

• Sentinel 底層采用高性能的滑動窗口數(shù)據(jù)結(jié)構(gòu) LeapArray來統(tǒng)計實時的秒級指標數(shù)據(jù)，可以很好地支撐寫多于讀的高并發(fā)場景。

由此可以發(fā)現(xiàn)Sentinel使用了滑動窗口算法來做數(shù)據(jù)統(tǒng)計，并且具體實現(xiàn)是在LeapArray類中。

Sentinel 總體的框架如下:

通過架構(gòu)圖我們可以看到StatisticSlot中的LeapArray采用了一個環(huán)性數(shù)組的數(shù)據(jù)結(jié)構(gòu)，這個和一致性hash算法的圖類似，如圖：

在這個結(jié)構(gòu)中，每一個下標位就代表一個滑動窗口，至于這個窗口是怎么滑動的我們可以結(jié)合原來看。

LeapArray 源碼

源碼路徑

StatisticSlot作為統(tǒng)計的入口，在其entry()方法中我們可以看到StatisticSlot會使用StatisticNode，然后StatisticNode回去引用ArrayMetric，最終使用LeapArray。

根據(jù)當前時間獲取滑動窗口

public WindowWrap<T> currentWindow(long timeMillis) {
    if (timeMillis < 0) {
        return null;
    }
    // 根據(jù)當前時間計算出當前時間屬于那個滑動窗口的數(shù)組下標
    int idx = calculateTimeIdx(timeMillis);
    // 根據(jù)當前時間計算出當前滑動窗口的開始時間
    long windowStart = calculateWindowStart(timeMillis);

    /*
     * 根據(jù)下腳標在環(huán)形數(shù)組中獲取滑動窗口（桶）
     *
     * (1) 如果桶不存在則創(chuàng)建新的桶，并通過CAS將新桶賦值到數(shù)組下標位。
     * (2) 如果獲取到的桶不為空，并且桶的開始時間等于剛剛算出來的時間，那么返回當前獲取到的桶。
     * (3) 如果獲取到的桶不為空，并且桶的開始時間小于剛剛算出來的開始時間，那么說明這個桶是上一圈用過的桶，重置當前桶
     * (4) 如果獲取到的桶不為空，并且桶的開始時間大于剛剛算出來的開始時間，理論上不應(yīng)該出現(xiàn)這種情況。
     */
    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));
        }
    }
}

根據(jù)下腳標在環(huán)形數(shù)組中獲取滑動窗口（桶）的規(guī)則：

• (1) 如果桶不存在則創(chuàng)建新的桶，并通過CAS將新桶賦值到數(shù)組下標位。

• (2) 如果獲取到的桶不為空，并且桶的開始時間等于剛剛算出來的時間，那么返回當前獲取到的桶。

• (3) 如果獲取到的桶不為空，并且桶的開始時間小于剛剛算出來的開始時間，那么說明這個桶是上一圈用過的桶，重置當前桶，并返回。

• (4) 如果獲取到的桶不為空，并且桶的開始時間大于剛剛算出來的開始時間，理論上不應(yīng)該出現(xiàn)這種情況。

這里有一個比較值得學(xué)習(xí)的地方是：

1. 對并發(fā)的控制：當一個新桶的創(chuàng)建直接是使用的CAS的原子操作來保證并發(fā)；但是重置一個桶的時候因為很難保證其原子操作（1. 需要重置多個值；2. 重置方法是一個抽象方法，需要子類去做實現(xiàn)），所以直接使用一個ReentrantLock鎖來做并發(fā)控制。

2. 對Thread.yield();方法的使用，這個方法主要的作用是交出CPU的執(zhí)行權(quán)，并重新競爭CPU執(zhí)行權(quán)。這個方法再我們業(yè)務(wù)代碼中其實很少用到。

如何實現(xiàn)的滑動的

通過上面這個方法我們可以看到我們是如果根據(jù)當前時間獲取到一個桶的（滑動窗口）。但是如何實現(xiàn)滑動效果的呢？實現(xiàn)滑動效果主要看上面那個方法的如何找到桶的下標和如何更加當前時間找到當前桶的開始時間，如下：

// 根據(jù)當前時間計算出當前時間屬于那個滑動窗口的數(shù)組下標
int idx = calculateTimeIdx(timeMillis);
// 根據(jù)當前時間計算出當前滑動窗口的開始時間
long windowStart = calculateWindowStart(timeMillis);

// 根據(jù)當前時間計算出當前時間屬于那個滑動窗口的數(shù)組下標
private int calculateTimeIdx(/*@Valid*/ long timeMillis) {
    // 利用除法取整原則，保證了一秒內(nèi)的所有時間搓得到的timeId是相等的
    long timeId = timeMillis / windowLengthInMs;
    // 利用求余運算原則，保證一秒內(nèi)獲取到的桶的下標位是一致的
    return (int) (timeId % array.length());
}

// 根據(jù)當前時間計算出當前滑動窗口的開始時間
protected long calculateWindowStart(/*@Valid*/ long timeMillis) {
    // 利用求余運算原則，保證一秒內(nèi)獲取到的桶的開始時間是一致的
    // 100 - 100 % 10 = 100 - 0 = 100
    // 101 - 101 % 10 = 101 - 1 = 100
    // 102 - 102 % 10 = 102 - 2 = 100
    return timeMillis - timeMillis % windowLengthInMs;
}

• timeMillis：表示當前時間的時間戳

• windowLengthInMs：表示一個滑動窗口的時間長度，根據(jù)源碼來看是1000ms即一個滑動窗口統(tǒng)計1秒內(nèi)的數(shù)據(jù)。

這兩個方法巧妙的利用了除法取整和求余原則實現(xiàn)了窗口的滑動。通過最上面的結(jié)構(gòu)圖我們可以發(fā)現(xiàn)滑動窗口會根據(jù)時間戳順時針旋轉(zhuǎn)。

桶的數(shù)量就決定了滑動窗口的統(tǒng)計時長，根據(jù)源碼來看是60個桶，即一個統(tǒng)計1分鐘內(nèi)的數(shù)據(jù)。

內(nèi)部是利用并發(fā)工具類LongAdder的特性來實現(xiàn)的高效的數(shù)據(jù)的統(tǒng)計。

到此，關(guān)于“Alibaba Sentinel LeapArray源碼分析”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>