最近在使用Alibaba Sentinel來做服務的限流、熔斷和降級。一直有一個比較好奇的點，Sentinel是如果做到高效的資料統計的。通過官方文檔介紹：
-
StatisticSlot: 則用于記錄、統計不同緯度的 runtime 名額監控資訊；（做實時統計）
-
Sentinel 底層采用高性能的滑動視窗資料結構
來統計實時的秒級名額資料，可以很好地支撐寫多于讀的高并發場景。
由此可以發現Sentinel使用了滑動視窗算法來做資料統計，并且具體實作是在
LeapArray
類中。
Sentinel 總體的架構如下:
通過架構圖我們可以看到
StatisticSlot
中的
LeapArray
采用了一個環性數組的資料結構，這個和一緻性hash算法的圖類似，如圖：
在這個結構中，每一個下标位就代表一個滑動視窗，至于這個視窗是怎麼滑動的我們可以結合原來看。
LeapArray 源碼
源碼路徑
StatisticSlot
作為統計的入口，在其
entry()
方法中我們可以看到
StatisticSlot
會使用
StatisticNode
，然後
StatisticNode
回去引用
ArrayMetric
，最終使用
LeapArray
。
根據目前時間擷取滑動視窗
public WindowWrap<T> currentWindow(long timeMillis) {
if (timeMillis < 0) {
return null;
}
// 根據目前時間計算出目前時間屬于那個滑動視窗的數組下标
int idx = calculateTimeIdx(timeMillis);
// 根據目前時間計算出目前滑動視窗的開始時間
long windowStart = calculateWindowStart(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) 如果擷取到的桶不為空，并且桶的開始時間大于剛剛算出來的開始時間，理論上不應該出現這種情況。
這裡有一個比較值得學習的地方是：
- 對并發的控制：當一個新桶的建立直接是使用的CAS的原子操作來保證并發；但是重置一個桶的時候因為很難保證其原子操作（1. 需要重置多個值；2. 重置方法是一個抽象方法，需要子類去做實作），是以直接使用一個
ReentrantLock
- 對
Thread.yield();
如何實作的滑動的
通過上面這個方法我們可以看到我們是如果根據目前時間擷取到一個桶的（滑動視窗）。但是如何實作滑動效果的呢？實作滑動效果主要看上面那個方法的如何找到桶的下标和如何更加目前時間找到目前桶的開始時間，如下：
// 根據目前時間計算出目前時間屬于那個滑動視窗的數組下标
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
這兩個方法巧妙的利用了除法取整和求餘原則實作了視窗的滑動。通過最上面的結構圖我們可以發現滑動視窗會根據時間戳順時針旋轉。