要說現在工程師最重要的能力，我覺得工程能力要排第一。
就算現在大廠面試經常要手撕算法，也是更偏向考查代碼工程實作的能力，之前在群裡看到這樣的圖檔，就覺得很離譜。
在 Sentinel-Go 中，一個很核心的算法是流控（限流）算法。
流控可能每個人都聽過，但真要手寫一個，還是有些困難。為什麼流控算法難寫？以我的感覺是算法和工程實作上存在一定差異，雖然算法好了解，但卻沒法照着實作。
舉個例子，令牌桶算法很好了解，隻需給定一個桶，以恒定的速率往桶内放令牌，滿了則丢棄，執行任務前先去桶裡拿令牌，隻有拿到令牌才可以執行，否則拒絕。
如果實作令牌桶，按道理應該用一個單獨線程（或程序）往桶裡放令牌，業務線程去桶裡取，但真要這麼實作，怎麼保證這個單獨線程能穩定執行，萬一挂了豈不是很危險？
是以工程實作上和算法原本肯定存在一定的差異，這也是為什麼需要深入源碼的一個原因。
通常來說，流控的度量是按每秒的請求數，也就是 QPS
QPS：query per second，指每秒查詢數，當然他的意義已經泛化了，不再特指查詢，可以泛指所有請求。如果非要區分，TPS 指每秒事務數，即寫入數，或 RPS，每秒請求數，本文不分這麼細，統計叫QPS。
當然也有按并發數來度量，并發數的流控就非常簡單
并發是一個瞬時概念，它跟時間沒有關系。和程序中的線程數、協程數一樣，每次取的時候隻能拿到一個瞬間的快照，但可能很快就變化了。
并發數怎麼定義？可以近似認為進入業務代碼開始就算一個并發，執行完這個并發就消失。
這樣說來，實作就非常簡單了，隻需要定義一個全局變量，責任鍊開始時對這個變量原子增1，并擷取目前并發數的一個快照，判斷并發數是否超限，如果超限則直接阻斷，執行完了别忘了原子減1即可，由于太過簡單，就不需要放代碼了。
參考并發數流控，當需要度量 QPS 時，是否也可以利用這樣的思想呢？
由于 QPS 有時間的度量，第一直覺是和并發數一樣弄個變量，再起個單獨線程每隔 1s 重置這個變量。
但單獨線程始終不放心，需要稍微改一下。
如果系統有一個起始時間，每次請求時，擷取目前時間，兩者之差，就能算出目前處于哪個時間視窗，這個時間視窗單獨計數即可。
如果稍微思考下，你會發現問題不簡單，如下圖，10t 到20t 隻有60個請求，20t到30t之間隻有80個請求，但有可能16t到26t之間有110個請求，這就很有可能把系統打垮。
為了解決上面的問題，工程師想出了一個好辦法：别固定時間視窗，以目前時間往前推算視窗
但問題又來了，這該怎麼實作呢？
在工程實作上，可以将時間劃分為細小的采樣視窗，緩存一段時間的采樣視窗，這樣每當請求來的時候，隻需要往前拿一段時間的采樣視窗，然後求和就能拿到總的請求數。
前方代碼高能預警~
Sentinel-Go 是基于 <code>LeapArray</code> 實作的滑動視窗，其資料結構如下
再看下是如何寫入名額的，例如當流程正常通過時
取到相應的 bucket，然後寫入相應 event 的 count，對 RT 會特殊處理，因為有一個最小 RT 需要處理。
重點看是如何取到相應的 bucket 的：
舉個直覺的例子，看如何拿到 bucket：
假設 B2 取出來是 nil，則 new 一個 bucket 通過 compareAndSet 寫入，保證線程安全，如果别别的線程先寫入，這裡會執行失敗，調用 runtime.Gosched()，讓出時間片，進入下一次循環
假設取出 B2 的開始時間是3400，與計算的相同，則直接使用
假設取出的 B2 的開始時間小于 3400，說明這個 bucket 太舊了，需要覆寫，使用更新鎖來更新，保證線程安全，如果拿不到鎖，也讓出時間片，進入下一次循環
假設取出 B2 的開始時間大于3400，說明已經有其他線程更新了，而 bucketLengthInMs 通常遠遠大于鎖的擷取時間，是以這裡隻考慮隻有一個 bucket 的情況直接傳回，其他情況報錯
回到 QPS 計算：
該方法會先計算一個起始時間範圍
例如目前時間為3500，則計算出
end = 3400
start = 3400 - 1200 + 200 = 2400
然後周遊所有 bucket，把在這個範圍内的 bucket 都拿出來，計算 QPS，隻需要相加即可。
本節從滑動視窗流控算法的工程實作演進到 Sentinel-Go 裡滑動視窗的實作，從 Sentinel-Go 的實作上看到，還得考慮記憶體的使用，并發控制等等，如果完全寫出來，還是非常不容易的。
《Sentinel-Go源碼系列》已經寫了三篇，隻介紹了兩個知識點：責任鍊模式、滑動視窗限流，後續還有對象池等，但這其實和 Sentinel-Go 關系不是很大，到時候單獨成文，就不放在本系列裡了。
本文算是一個結束，與其說是結束，不如說是一個開始。
搜尋關注微信公衆号"捉蟲大師"，後端技術分享，架構設計、性能優化、源碼閱讀、問題排查、踩坑實踐。Sentinel-Go 源碼系列（三）滑動時間視窗算法的工程實作