StatisticSlot數(shù)據(jù)采集的原理

時(shí)間窗口

固定窗口

在固定的時(shí)間窗口內(nèi)，可以允許固定數(shù)量的請求進(jìn)入；超過數(shù)量就拒絕或者排隊(duì)，等下一個(gè)時(shí)間段進(jìn)入, 如下圖

• 時(shí)間窗長度劃分為1秒

• 單個(gè)時(shí)間窗的請求閾值為3
  

上述存在一個(gè)問題, 假如9:18:04:333-9:18:05:000產(chǎn)生了2個(gè)請求, 9:18:05:000-9:18:05:333產(chǎn)生了3個(gè)請求, 那么也就是說9:18:04:333-9:18:05:333這一秒內(nèi)產(chǎn)生5個(gè)請求, 正常來說這里已經(jīng)超出了閾值

但是由于是固定窗口, 也就是這里只能9:18:04:000-9:18:05:000, 9:18:05:000-9:18:06:000這樣子去處理, 所以實(shí)際上打達(dá)不到我們的要求的

滑動窗口

滑動窗口誕生的原因就在于解決固定窗口那個(gè)致命的問題，為什么我說固定窗口的問題是致命的？因?yàn)槲覀兿到y(tǒng)限流的目的是要在任意時(shí)間都能應(yīng)對突然的流量暴增，也就是說我的系統(tǒng)最大在1s內(nèi)能夠處理請求3，但如果使用固定窗口的算法，就會造成在9:18:04:333-9:18:05:333之間的請求無法限流，從而嚴(yán)重的話會導(dǎo)致服務(wù)雪崩

滑動窗口如下圖

• 時(shí)間窗長度劃分為1秒, 并且是滑動的

• 單個(gè)時(shí)間窗的請求閾值為3
  

如果要判斷請求是否能正常通過, 那么就要把當(dāng)前時(shí)間點(diǎn)作為終點(diǎn), 統(tǒng)計(jì)前1秒內(nèi)的請求數(shù), 判斷請求數(shù)是否達(dá)到閾值, 如果沒有達(dá)到閾值就放行, 如果達(dá)到閾值了就通過

上邊的問題是是解決了, 但是存在一些性能問題, 假設(shè)請求落在9:18:05:333, 往前移動1s距離, 那么就是以9:18:04:333作為起點(diǎn), 統(tǒng)計(jì)9:18:04:333-9:18:05:333之間的請求數(shù), 當(dāng)請求落在9:18:05:633, 那么就要統(tǒng)計(jì)9:18:04:633-9:18:05:633之間的請求數(shù), 發(fā)現(xiàn)9:18:04:633-9:18:05:333之間的數(shù)據(jù)上一次的時(shí)候就出現(xiàn)過了, 但是這里又得重新統(tǒng)計(jì), 也就說每移動一次窗口, 那么都要重新統(tǒng)計(jì)重復(fù)區(qū)域的請求數(shù)量, 從而導(dǎo)致浪費(fèi)大量系統(tǒng)資源, 如下圖, 黃色區(qū)域為重復(fù)統(tǒng)計(jì)區(qū)域

出現(xiàn)了問題, 就要解決

我們需要引入更加細(xì)粒度化的計(jì)算, 也就是說需要增加子時(shí)間窗口, 那么這里引入的子時(shí)間窗口, 我們稱為樣本窗口

1. 樣本窗口的長度必須小于滑動窗口長度，因?yàn)槿绻麡颖敬翱诘扔诨瑒哟翱陂L度的話，就和固定窗口沒啥區(qū)別了
2. 通常情況下滑動窗口的長度是樣本窗口的整數(shù)倍，比如：10 * 樣本窗口 = 1 個(gè)滑動窗口
3. 每個(gè)樣本窗口在到達(dá)終點(diǎn)時(shí)間時(shí)，會統(tǒng)計(jì)本樣本窗口中的流量數(shù)據(jù)并且記錄下來，用于復(fù)用
4. 當(dāng)一個(gè)請求到達(dá)時(shí)，系統(tǒng)會首先統(tǒng)計(jì)當(dāng)前請求時(shí)間點(diǎn)所在的樣本窗口內(nèi)的流量數(shù)據(jù)。接著，系統(tǒng)會檢查在當(dāng)前請求時(shí)間點(diǎn)之前的滑動窗口中的樣本窗口，將它們的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行求和。如果這個(gè)求和值沒有超出事先設(shè)定的閾值，請求將會被允許通過。然而，如果求和值超過了閾值，系統(tǒng)會觸發(fā)限流措施，拒絕該請求的訪問

假設(shè)

• 時(shí)間窗長度為1s
• 一個(gè)時(shí)間窗內(nèi)包含三個(gè)樣本窗口
• 閾值為30

那么10:00:00:000-10:00:01:000內(nèi)請求數(shù)為10 + 5 + 10 = 25 < 30, 所以大膽放行

那么10:00:00:333-10:00:01:333內(nèi)請求數(shù)為5 + 10 + 7= 22 < 30, 繼續(xù)放行

那么10:00:00:666-10:00:01:666內(nèi)請求數(shù)為10 + 7 + 30= 47 > 30, 這里就要限流了

限流

那么10:00:01:000-10:00:02:000內(nèi)請求數(shù)為7 + 30 + 7= 40 > 30, 這里就要限流了

那么10:00:01:333-10:00:02:333內(nèi)請求數(shù)為30 + 7 + 34 = 71 > 30, 這里就要限流了

ps: 樣本窗口的數(shù)量影響著滑動窗口算法的精度，依然有時(shí)間片的概念，無法根本解決臨界點(diǎn)問題

數(shù)據(jù)統(tǒng)計(jì)

底層數(shù)據(jù)結(jié)構(gòu)

StatisticSlot.entry() 中的 node.addPassRequest(count)方法

public void addPassRequest(int count) {// 增加當(dāng)前入口的DefaultNode中的數(shù)據(jù)super.addPassRequest(count);// 增加當(dāng)前資源的 ClusterNode 中的全局統(tǒng)計(jì)數(shù)據(jù)this.clusterNode.addPassRequest(count);
}@Override
public void addPassRequest(int count) {// 為滑動計(jì)數(shù)器增加本次請求rollingCounterInSecond.addPass(count);rollingCounterInMinute.addPass(count);
}

rollingCounterInSecond 就是一個(gè)真正保存數(shù)據(jù)的計(jì)量器，數(shù)據(jù)類型為 ArrayMetric，也就是說 Sentinel 在統(tǒng)計(jì)數(shù)據(jù)上采取的是一個(gè)名為 ArrayMetric 的 Java 類，如下

// 定義了一個(gè)使用數(shù)組保存數(shù)據(jù)的計(jì)量器，樣本窗口數(shù)量為2(SAMPLE_COUNT)，時(shí)間窗口長度為1000ms(INTERVAL)
private transient volatile Metric rollingCounterInSecond = new ArrayMetric(SampleCountProperty.SAMPLE_COUNT, IntervalProperty.INTERVAL);

那么 ArrayMetric 類又是如何存儲數(shù)據(jù)的呢？

// 這是一個(gè)使用數(shù)組保存數(shù)據(jù)的計(jì)量器類，數(shù)據(jù)就保存在data中
public class ArrayMetric implements Metric {// 真正存儲數(shù)據(jù)的地方private final LeapArray<MetricBucket> data;
}public abstract class LeapArray<T> {// 樣本窗口的長度protected int windowLengthInMs;// 一個(gè)時(shí)間窗口包含的樣本窗口數(shù)量，公式 intervalInMs / windowLengthInMs，也就是時(shí)間窗口長度 / 樣本窗口長度protected int sampleCount;// 時(shí)間窗口長度protected int intervalInMs;// 也是時(shí)間窗口長度，只是單位為sprivate double intervalInSecond;// WindowWrap ： 樣本窗口類// 這是一個(gè)數(shù)組// 這里的泛型T實(shí)際類型為 MetricBucketprotected final AtomicReferenceArray<WindowWrap<T>> array;
}

LeapArray 類似于一個(gè)樣本窗口管理類，而真正的樣本窗口類是 WindowWrap<T>，對于樣本窗口的概念我們肯定不陌生了，其包含：單個(gè)樣本窗口的長度、樣本窗口的開始時(shí)間戳，如下所示：

// 樣本窗口類，泛型T為MetricBucket
public class WindowWrap<T> {// 單個(gè)樣本窗口的長度private final long windowLengthInMs;// 樣本窗口的起始時(shí)間戳private long windowStart;// 當(dāng)前樣本窗口的統(tǒng)計(jì)數(shù)據(jù)，類型為 MetricBucketprivate T value;
}

關(guān)于泛型真實(shí)類型為 MetricBucket 也很簡單，可以從前面代碼 ArrayMetric#LeapArray<MetricBucket> 得出。接下來就看真實(shí)類型 MetricBucket 是個(gè)什么東西

// 統(tǒng)計(jì)數(shù)據(jù)的封裝類
public class MetricBucket {// 統(tǒng)計(jì)的數(shù)據(jù)真實(shí)存放在LongAdder里// 但是為什么要數(shù)組？直接用LongAdder+1不就行了？因?yàn)榻y(tǒng)計(jì)的數(shù)據(jù)是多維度的，這些維度類型在MetricEvent枚舉中。private final LongAdder[] counters;private volatile long minRt;
}

這里有一個(gè)巧妙的設(shè)計(jì)，就是為什么用LongAdder[]而不是用LongAdder，正是因?yàn)榻y(tǒng)計(jì)的數(shù)據(jù)是多維度的，比如：統(tǒng)計(jì)通過的 QPS、統(tǒng)計(jì)失敗的 QPS 等，因此設(shè)計(jì)成數(shù)組，我們就可以將不同類型放到不同的數(shù)組下標(biāo)里

關(guān)系如下圖

addPass()方法

@Override
public void addPassRequest(int count) {// 為滑動計(jì)數(shù)器增加本次請求rollingCounterInSecond.addPass(count);rollingCounterInMinute.addPass(count);
}public void addPass(int count) {// 獲取當(dāng)前時(shí)間點(diǎn)所在的樣本窗口WindowWrap<MetricBucket> wrap = data.currentWindow();// 將當(dāng)前請求的計(jì)數(shù)量添加到當(dāng)前樣本窗口的統(tǒng)計(jì)數(shù)據(jù)中wrap.value().addPass(count);
}

其主要分為三部分：

1. 當(dāng)前時(shí)間所在的樣本窗口如果還沒創(chuàng)建，則需要初始化。
2. 若當(dāng)前樣本窗口的起始時(shí)間與計(jì)算出的樣本窗口起始時(shí)間相同，則說明這兩個(gè)是同一個(gè)樣本窗口，直接獲取就行。
3. 若當(dāng)前樣本窗口的起始時(shí)間大于計(jì)算出的樣本窗口起始時(shí)間，說明計(jì)算出來的樣本窗口已經(jīng)過時(shí)了，需要將原來的樣本窗口替換為新的樣本窗口。數(shù)組的環(huán)形數(shù)組，不是無限長的，比如存 1s，1000 個(gè)樣本窗口，那么下 1s 的 1000 個(gè)時(shí)間窗口會覆蓋上一秒的。
4. 若當(dāng)前樣本窗口的起始時(shí)間小于計(jì)算出的樣本窗口起始時(shí)間，一般不會出現(xiàn)，因?yàn)闀r(shí)間不會倒流，除非人為修改系統(tǒng)時(shí)間導(dǎo)致時(shí)鐘回?fù)?/code>

public WindowWrap<T> currentWindow(long timeMillis) {if (timeMillis < 0) {return null;}// 計(jì)算當(dāng)前時(shí)間所在的樣本窗口index，也就是樣本窗口的下標(biāo)，即在計(jì)算數(shù)組LeapArray中的下標(biāo)int idx = calculateTimeIdx(timeMillis);// Calculate current bucket start time.// 計(jì)算當(dāng)前樣本窗口的開始時(shí)間點(diǎn)long windowStart = calculateWindowStart(timeMillis);while (true) {// 獲取到當(dāng)前時(shí)間所在的樣本窗口WindowWrap<T> old = array.get(idx);// 代表當(dāng)前時(shí)間所在的樣本窗口沒有，需要創(chuàng)建if (old == null) {/**     B0       B1      B2    NULL      B4* ||_______|_______|_______|_______|_______||___* 200     400     600     800     1000    1200  timestamp*                             ^*                          time=888*            		bucket為空, 所以新建并更新** 如果舊的bucket不存在，那么我們在windowStart創(chuàng)建一個(gè)新的bucket，然后嘗試通過CAS操作* 更新循環(huán)數(shù)組。只有一個(gè)線程可以成功更新，而其他線程爭奪這個(gè)時(shí)間片*/// 創(chuàng)建一個(gè)時(shí)間窗口WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));// CAS 將新建窗口放入LeapArrayif (array.compareAndSet(idx, null, window)) {// 更新成功，返回創(chuàng)建的bucketreturn window;} else {// 獲取鎖失敗, 線程將放棄其時(shí)間片以等待可用的bucketThread.yield();}} else if (windowStart == old.windowStart()) { // 若當(dāng)前樣本窗口的起始時(shí)間與計(jì)算出的樣本窗口起始時(shí)間相同，則說明這兩個(gè)是同一個(gè)樣本窗口，直接獲取就行/**     B0       B1      B2     B3      B4* ||_______|_______|_______|_______|_______||___* 200     400     600     800     1000    1200  timestamp*                             ^*                          time=888*            桶3的起始時(shí)間: 800，所以它是最新的** 如果當(dāng)前windowStart等于舊bucket的開始時(shí)間戳，則表示時(shí)間在bucket內(nèi)，因此直接返回bucket*/return old;} else if (windowStart > old.windowStart()) { // 若當(dāng)前樣本窗口的起始時(shí)間大于計(jì)算出的樣本窗口起始時(shí)間。說明計(jì)算出來的樣本窗口已經(jīng)過時(shí)了，需要將原來的樣本窗口替換為新的樣本窗口。 數(shù)組的環(huán)形數(shù)組，不是無限長的，比如存1s，1000個(gè)樣本窗口，那么下1s的1000個(gè)時(shí)間窗口會覆蓋上一秒的/**   (old)*             B0       B1      B2    NULL      B4* |_______||_______|_______|_______|_______|_______||___* ...    1200     1400    1600    1800    2000    2200  timestamp*                              ^*                           time=1676*          Bucket 2的startTime: 400，已棄用，應(yīng)重置** 如果舊bucket的開始時(shí)間戳落后于當(dāng)前時(shí)間，則表示該bucket已棄用。我們必須將bucket重置為當(dāng)前的windowStart。請注意，重置和清理操作很難是原子的，所以我們需要一個(gè)更新鎖來保證bucket更新的正確性** 更新鎖是有條件的(小范圍)，只有當(dāng)桶被棄用時(shí)才會生效，所以在大多數(shù)情況下它不會導(dǎo)致性能損失*/if (updateLock.tryLock()) {try {// 成功獲取更新鎖，現(xiàn)在我們重置bucket// 替換老的樣本窗口return resetWindowTo(old, windowStart);} finally {updateLock.unlock();}} else {// 獲取鎖失敗，線程將放棄其時(shí)間片以等待可用的bucketThread.yield();}} else if (windowStart < old.windowStart()) { // 若當(dāng)前樣本窗口的起始時(shí)間小于計(jì)算出的樣本窗口起始時(shí)間，一般不會出現(xiàn)，因?yàn)闀r(shí)間不會倒流，除非人為修改系統(tǒng)時(shí)間(即時(shí)鐘回?fù)?return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));}}
}