Sentinel 是基于滑動視窗實作的實時名額資料統計，要深入了解 Sentinel 的限流實作原理，首先我們得要了解其名額資料統計的實作，例如如何統計 QPS。
為了簡單，我們不直接分析 Sentinel 的源碼，而是分析經過改造後的“qps-helper”工具包的代碼。總體上是一樣的，筆者去掉了一些不需要的名額統計，以及将 Sentinel 一些自定義的類替換成 JDK 提供的類，封裝成通用的 QPS 統計工具包。當然，您也可以直接看 Sentinel 的源碼，差别不大，源碼在 sentinel-core 的 slots 包下。
Bucket
Sentinel 使用 Bucket 統計一個視窗時間内的各項名額資料，這些名額資料包括請求總數、成功總數、異常總數、總耗時、最小耗時、最大耗時等，而一個 Bucket 可以是記錄一秒内的資料，也可以是 10 毫秒内的資料，這個時間長度稱為視窗時間。qps-helper 隻統計請求成功總數、請求異常數、總耗時。
public class MetricBucket {
/**
* 存儲各事件的計數，比如異常總數、請求總數等
*/
private final LongAdder[] counters;
/**
* 這段事件内的最小耗時
*/
private volatile long minRt;
}
如上面代碼所示，Bucket 記錄一段時間内的各項名額資料用的是一個 LongAdder 數組，LongAdder 保證了資料修改的原子性，并且性能比 AtomicInteger 表現更好。數組的每個元素分别記錄一個時間視窗内的請求總數、異常數、總耗時，如下圖所示。
Sentinel 用枚舉類型 MetricEvent 的 ordinal 屬性作為下标，ordinal 的值從 0 開始，按枚舉元素的順序遞增，正好可以用作數組的下标。在 qps-helper 中，LongAdder 被替換為 j.u.c 包下的 atomic 類了，并且隻保留 EXCEPTION、SUCCESS、RT，代碼如下。
// 事件類型
public enum MetricEvent {
EXCEPTION,// 異常 對應數組下标為 0
SUCCESS, // 成功 對應數組下标為 1
RT // 耗時 對應數組下标為 2
}
當需要擷取 Bucket 記錄總的成功請求數或者異常總數、總的請求處理耗時，可根據事件類型（MetricEvent）從 Bucket 的 LongAdder 數組中擷取對應的 LongAdder，并調用 sum 方法擷取總數，如下代碼所示。
// 假設事件為 MetricEvent.SUCCESS
public long get(MetricEvent event) {
// MetricEvent.SUCCESS.ordinal()為 1
return counters[event.ordinal()].sum();
}
當需要 Bucket 記錄一個成功請求或者一個異常請求、處理請求的耗時，可根據事件類型（MetricEvent）從 LongAdder 數組中擷取對應的 LongAdder，并調用其 add 方法，如下代碼所示。
// 假設事件為 MetricEvent.RT
public void add(MetricEvent event, long n) {
// MetricEvent.RT.ordinal()為 2
counters[event.ordinal()].add(n);
}
滑動視窗
如果我們希望能夠知道某個接口的每秒處理成功請求數（成功 QPS）、每秒處理失敗請求數（失敗 QPS），以及處理每個成功請求的平均耗時（avg RT），我們隻需要控制 Bucket 統計一秒鐘的名額資料即可。我們隻需要控制 Bucket 統計一秒鐘内的名額資料即可。但如何才能確定 Bucket 存儲的就是精确到 1 秒内的資料呢？
最 low 的做法就是啟一個定時任務每秒建立一個 Bucket，但統計出來的資料誤差絕對很大。Sentinel 是這樣實作的，它定義一個 Bucket 數組，根據時間戳來定位到數組的下标。假設我們需要統計每 1 秒處理的請求數等資料，且隻需要儲存最近一分鐘的資料。那麼 Bucket 數組的大小就可以設定為 60，每個 Bucket 的 windowLengthInMs（視窗時間）大小就是 1000 毫秒（1 秒），如下圖所示。
由于每個 Bucket 存儲的是 1 秒的資料，假設 Bucket 數組的大小是無限大的，那麼我們隻需要将目前時間戳去掉毫秒部分就能得到目前的秒數，将得到的秒數作為索引就能從 Bucket 數組中擷取目前時間視窗的 Bucket。
一切資源均有限，是以我們不可能無限的存儲 Bucket，我們也不需要存儲那麼多曆史資料在記憶體中。當我們隻需要保留一分鐘的資料時，Bucket 數組的大小就可以設定為 60，我們希望這個數組可以循環使用，并且永遠隻儲存最近 1 分鐘的資料，這樣不僅可以避免頻繁的建立 Bucket，也減少記憶體資源的占用。
這種情況下如何定位 Bucket 呢？我們隻需要将目前時間戳去掉毫秒部分得到目前的秒數，再将得到的秒數與數組長度取餘數，就能得到目前時間視窗的 Bucket 在數組中的位置（索引），如下圖所示：
根據目前時間戳計算出目前時間視窗的 Bucket 在數組中的索引，算法實作如下：
private int calculateTimeIdx(long timeMillis) {
/**
* 假設目前時間戳為 1577017699235
* windowLengthInMs 為 1000 毫秒（1 秒）
* 則
* 将毫秒轉為秒 => 1577017699
* 映射到數組的索引為 => 19
*/
long timeId = timeMillis / windowLengthInMs;
return (int) (timeId % array.length());
}
calculateTimeIdx 方法中，取餘數就是實作循環利用數組。如果想要擷取連續的一分鐘的 Bucket 資料，就不能簡單的從頭開始周遊數組，而是指定一個開始時間和結束時間，從開始時間戳開始計算 Bucket 存放在數組中的下标，然後循環每次将開始時間戳加上 1 秒，直到開始時間等于結束時間。
由于循環使用的問題，目前時間戳與一分鐘之前的時間戳和一分鐘之後的時間戳都會映射到數組中的同一個 Bucket，是以，必須要能夠判斷取得的 Bucket 是否是統計目前時間視窗内的名額資料，這便要數組每個元素都存儲 Bucket 時間視窗的開始時間戳。
比如目前時間戳是 1577017699235，Bucket 統計一秒的資料，将時間戳的毫秒部分全部替換為 0，就能得到 Bucket 時間視窗的開始時間戳為 1577017699000。
計算 Bucket 時間視窗的開始時間戳代碼實作如下：
protected long calculateWindowStart(long timeMillis) {
/**
* 假設視窗大小為 1000 毫秒，即數組每個元素存儲 1 秒鐘的統計資料
* timeMillis % windowLengthInMs 就是取得毫秒部分
* timeMillis - 毫秒數 = 秒部分
* 這就得到每秒的開始時間戳
*/
return timeMillis - timeMillis % windowLengthInMs;
}
WindowWrap
因為 Bucket 自身并不儲存時間視窗資訊，是以 Sentinel 給 Bucket 加了一個包裝類 WindowWrap，用于記錄 Bucket 的時間視窗資訊，WindowWrap 源碼如下。
public class WindowWrap<T> {
/**
* 視窗時間長度（毫秒）
*/
private final long windowLengthInMs;
/**
* 開始時間戳（毫秒）
*/
private long windowStart;
/**
* 統計資料
*/
private T value;
public WindowWrap(long windowLengthInMs, long windowStart, T value) {
this.windowLengthInMs = windowLengthInMs;
this.windowStart = windowStart;
this.value = value;
}
}
如前面所說，假設 Bucket 以秒為機關統計名額資料，那麼 Bucket 統計的就是一秒内的請求總數、異常總數這些名額資料。換算為毫秒為機關，比如時間視窗為 [1577017699000,1577017699999)，那麼 1577017699000 就被稱為該時間視窗的開始時間（windowStart）。一秒轉為毫秒是 1000，是以 1000 就稱為視窗時間大小（windowLengthInMs）。
windowStart + windowLengthInMs = 時間視窗的結束時間
隻要知道時間視窗的開始時間和視窗時間大小，隻需要給定一個時間戳，就能知道該時間戳是否在 Bucket 的視窗時間内，代碼實作如下。
/**
* 檢查給定的時間戳是否在目前 bucket 中。
*
* @param timeMillis 時間戳，毫秒
* @return
*/
public boolean isTimeInWindow(long timeMillis) {
return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
}
通過時間戳定位 Bucket
Bucket 用于統計各項名額資料，WindowWrap 用于記錄 Bucket 的時間視窗資訊，記錄視窗的開始時間和視窗的大小，WindowWrap 數組就是一個滑動視窗。
當接收到一個請求時，可根據接收到請求的時間戳計算出一個數組索引，從滑動視窗（WindowWrap 數組）中擷取一個 WindowWrap，進而擷取 WindowWrap 包裝的 Bucket，調用 Bucket 的 add 方法記錄相應的事件。
根據目前時間戳定位 Bucket 的算法實作如下。
/**
* 根據時間戳擷取 bucket
*
* @param timeMillis 時間戳（毫秒）
* @return 如果時間有效，則在提供的時間戳處顯示目前存儲桶項；如果時間無效，則為空
*/
public WindowWrap<T> currentWindow(long timeMillis) {
if (timeMillis < 0) {
return null;
}
// 擷取時間戳映射到的數組索引
int idx = calculateTimeIdx(timeMillis);
// 計算 bucket 時間視窗的開始時間
long windowStart = calculateWindowStart(timeMillis);
// 從數組中擷取 bucket
while (true) {
WindowWrap<T> old = array.get(idx);
// 一般是項目啟動時，時間未到達一個周期，數組還沒有存儲滿，沒有到複用階段，是以數組元素可能為空
if (old == null) {
// 建立新的 bucket，并建立一個 bucket 包裝器
WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
// cas 寫入，確定線程安全，期望數組下标的元素是空的，否則就不寫入，而是複用
if (array.compareAndSet(idx, null, window)) {
return window;
} else {
Thread.yield();
}
}
// 如果 WindowWrap 的 windowStart 正好是目前時間戳計算出的時間視窗的開始時間，則就是我們想要的 bucket
else if (windowStart == old.windowStart()) {
return old;
}
// 複用舊的 bucket
else if (windowStart > old.windowStart()) {
if (updateLock.tryLock()) {
try {
// 重置 bucket，并指定 bucket 的新時間視窗的開始時間
return resetWindowTo(old, windowStart);
} finally {
updateLock.unlock();
}
} else {
Thread.yield();
}
}
// 計算出來的目前 bucket 時間視窗的開始時間比數組目前存儲的 bucket 的時間視窗開始時間還小，
// 直接傳回一個空的 bucket 就行
else if (windowStart < old.windowStart()) {
return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
}
}
}
上面代碼實作的是，通過目前時間戳計算出目前時間視窗的 Bucket（New Buket）在數組中的索引（cidx），以及 Bucket 時間視窗的開始時間，通過索引從數組中取得 Bucket（Old Bucket）。
- 當索引（cidx）處不存在 Bucket 時，建立一個新的 Bucket，并且確定線程安全寫入到數組 cidx 處，将此 Bucket 傳回；
- 當 Old Bucket 不為空時，且 Old Bucket 時間視窗的開始時間與目前計算得到的 New Buket 的時間視窗開始時間相等時，該 Bucket 就是目前要找的 Bucket，直接傳回；
- 當計算出 New Bucket 時間視窗的開始時間大于目前數組 cidx 位置存儲的 Old Bucket 時間視窗的開始時間時，可以複用這個 Old Bucket，確定線程安全重置 Bucket，并傳回；
- 當計算出 New Bucket 時間視窗的開始時間小于目前數組 cidx 位置存儲的 Old Bucket 時間視窗的開始時間時，直接傳回一個空的 Bucket，因為時間不會倒退。
擷取目前時間戳的前一個 Bucket
根據目前時間戳計算出目前 Bucket 的時間視窗開始時間，用目前 Bucket 的時間視窗開始時間減去一個視窗時間大小就能定位出前一個 Bucket。
由于是使用數組實作滑動視窗，數組的每個元素都會被循環使用，是以目前 Bucket 與前一個 Bucket 會有相差一個完整的滑動視窗周期的可能，如下圖所示。
目前時間戳對應的 Bucket 的時間視窗開始時間戳為 1595974702000，而前一個 Bucket 的時間視窗開始時間戳可能是 1595974701000，也可能是一個滑動視窗周期之前的 1595974641000。是以，在擷取到目前 Bucket 的前一個 Bucket 時，需要根據 Bucket 的時間視窗開始時間與目前時間戳比較，如果跨了一個周期就是無效的。
總結
- WindowWrap 用于包裝 Bucket，随着 Bucket 一起建立。
- WindowWrap 數組實作滑動視窗，Bucket 隻負責統計各項名額資料，WindowWrap 用于記錄 Bucket 的時間視窗資訊。
- 定位 Bucket 實際上是定位 WindowWrap，拿到 WindowWrap 就能拿到 Bucket。