游戲推薦業務中基于sentinel的動態限流實踐
一、背景
1.1 當前的限流方案
隨著互聯網的發展及業務的增長，系統的流量和請求量越來越大，針對高并發系統，如果不對請求量進行限制，在流量突增時可能會導致系統崩潰或者服務不可用，影響用戶體驗。因此，系統需要引入限流來控制請求的流量，保證系統的可用性和穩定性。當前推薦業務使用公司vsentinel 限流工具，主要使用 QPS 限流和熱點參數限流。
QPS 限流：對某個資源（通常為接口或方法，也可以自定義資源）的 QPS /并發數進行限流；
熱點參數限流：對某些具體的參數值進行限流，避免因為熱點參數的過度訪問導致服務宕機。
1.2 存在的問題
無論是 QPS 限流還是熱點參數限流，都是對資源/參數的定量限流，即對某個資源/參數設置固定閾值，超過閾值則進行限流。
回到業務，游戲推薦系統作為游戲分發的平臺，向公司內所有主要流量入口（包括游戲中心、應用商店、瀏覽器等）分發游戲、小游戲、內容和評論，具有大流量、高負載的業務特點。同時，游戲推薦系統對接的場景多（600+），單個性化接口有100+場景調用（場景可以理解為接口請求的一個基本請求參數）。當前的限流方案存在以下幾個問題：
- 參數級別的限流，600+場景，無法做到每個場景精細化限流；
- 接口級別的限流，不會區分具體的場景，無法保證核心場景的可用性；
- 如果場景流量有變更，需要及時調整限流閾值，不易維護；
- 場景的流量會實時變化，無法做到根據流量變化的動態限流。
鑒于以上限流問題，推薦系統需要一個能夠根據參數流量變化而動態調整限流閾值的精細化限流方案。
二、動態限流介紹
從配置方式上來看，動態限流和 QPS 限流、熱點參數限流最大的不同之處在于，動態限流不是通過配置固定閾值進行限流，而是配置每個參數的優先級，根據參數的優先級動態調整限流閾值。
動態限流將資源和參數進行綁定，首先配置資源（一般是接口/方法）總的限流閾值，進而配置資源下具體參數的優先級，根據參數配置的優先級和實時流量，決定當前請求pass or block。
下圖示例中，資源總的限流閾值為150，參數A、B、C、D的 QPS 均為100，且配置的參數優先級 A>B>C>D。
- 參數A優先級最高，且 QPS(A) = 100 < 限流閾值150，所以A的流量全部通過；
- 參數B優先級僅次于參數A，且 QPS(A) = 100 < 限流閾值150、QPS(A) + QPS(B)= 200 > 限流閾值150，所以參數B部分流量通過，pass : 50，block：50；
- 參數C和其它參數的優先級低于參數B，且 QPS(A) + QPS(B)= 200 > 限流閾值150，所以參數C和其它參數均被限流。
如果此時參數值A的 QPS 變為200，B、C的 QPS 仍為100，通過動態限流實現：A請求部分通過，B請求全部攔截，C請求全部攔截；根據各參數值流量的變化，動態適配各參數值通過/攔截的流量，從而實現根據參數值動態限流的效果。
總結：動態限流本質上是參數優先級限流，支持對參數值配置優先級，根據參數值的優先級進行動態流控。當流量超過閾值后，優先保證高優先級參數通過，攔截優先級低的參數請求。
三、sentinel 介紹
由于動態限流是基于 sentinel 進行二次開發，且動態限流的實現算法是基于 sentinel QPS 限流的優化，這里首先介紹下 sentinel 實現原理和 sentinel QPS 限流的滑動窗口計數器限流算法。
3.1 sentinel 原理介紹
sentinel 是阿里開源的一款面向分布式、多語言異構化服務架構的流量治理組件。主要以流量為切入點，從流量路由、流量控制、流量整形、熔斷降級、系統自適應過載保護、熱點流量防護等多個維度來幫助開發者保障微服務的穩定性。(官網描述)
sentinel 主要通過責任鏈模式實現不同模式的限流功能，責任鏈由一系列 ProcessorSlot 對象組成，每個 ProcessorSlot 對象負責不同的功能。
ProcessorSlot 對象可以分為兩類：一類是輔助完成資源指標數據統計的 slot，一類是實現限流降級功能的 slot。
輔助資源指標數據統計的 ProcessorSlot：
- NodeSelectorSlot：負責收集資源路徑，并將調用路徑樹狀存儲，用于后續根據調用路徑來限流降級；
- ClusterBuilderSlot：負責存儲資源的統計信息以及調用者信息，例如該資源的 RT、QPS、線程數等等，作為多維度限流、降級的依據；
- StatisticSlot：負責實現指標數據統計，從多個維度（入口流量、調用者、資源）統計響應時間、并發線程數、處理失敗數量、處理成功數量等指標信息。
實現限流降級功能的 slot：
- ParamFlowSlot：用于根據請求參數進行限流（熱點參數限流），例如根據某個參數的 QPS 進行限流，或者根據某個參數的值進行限流；
- SystemSlot：用于根據系統負載情況進行限流，例如 CPU 使用率、內存使用率等。
- AuthoritySlot：用于根據調用者身份進行限流，例如根據調用者的 IP 地址、Token 等信息進行限流。
- FlowSlot：用于根據 QPS 進行限流，例如每秒最多只能處理多少請求。
- DegradeSlot：用于實現熔斷降級功能，例如當某個資源出現異常時，可以將其熔斷并降級處理。
除了上述原生 ProcessorSlot，sentinel 還支持 SPI 插件功能，通過實現 ProcessorSlot 接口自定義 slot，從而能實現個性化功能拓展。動態限流正是基于 sentinel SPI 插件方式實現。
3.2 滑動窗口計數器算法
sentinel 的 QPS 限流采用滑動窗口計數器算法，下面我們簡單介紹下這個算法原理。
首先介紹一下計數器算法。
3.2.1 計數器
計數器算法：維護一個固定單位時間的計數器來統計請求數，在計數小于限流閾值時通過請求，計數到達限流閾值后攔截請求，直到下一個單位時間再重新計數。
假設資源限制 1 秒內的訪問次數不能超過 100 次。
- 維護一個計數器，每次有新的請求過來，計數器加 1；
- 收到新請求后，如果計數器的值小于限流值，并且與上一次請求的時間間隔還在 1秒內，允許請求通過，否則拒絕請求；如果超出了時間間隔，要將計數器清零。
計數器算法存在一個問題：窗口切換時可能會出現流量突刺（最高2倍）。
極端情況下，假設每秒限流100，在第1s和第2s分別通100個請求，且第1s的請求集中在后半段，第2s的請求集中在前半段，那么其實在500ms到1500ms這個1s的時間段，通過了200個請求。
為了解決這個問題，引入了基于滑動窗口的計數器算法。
3.2.2 滑動窗口計數器
滑動窗口計數器算法是計數器算法的改進，解決了固定窗口的流量突刺問題。算法原理：
- 將時間劃分為細粒度的區間，每個區間維持一個計數器，每進入一個請求則將計數器加1；
- 多個區間組成一個時間窗口，每到一個區間時間后，則拋棄最老的一個區間，納入新區間；
- 若當前窗口的區間計數器總和超過設定的限制數量，則本窗口內的后續請求都被丟棄。
滑動窗口本質上是固定窗口更細粒度的限流，將單位時間劃分多個窗口，劃分的窗口越多，數據越精確。
四、基于 sentinel 的動態限流方案
動態限流是基于 sentinel 的二次開發，具體實現流程和 sentinel 的 QPS 限流類似，可以歸納為三步：數據統計、規則管理、流量校驗。
- 數據統計：統計資源（接口/方法/參數）的流量；
- 規則管理：管理限流規則，維護資源的限流閾值及參數值優先級；
- 流量校驗：對比統計到的流量和對應的限流規則，決定當前請求 pass or block。
4.1 數據統計
動態限流的數據統計同 sentinel 流量控制模塊一樣，使用滑動窗口計數器算法統計當前的流量。
具體來講，sentinel 流量控制中的數據統計，是將1s的時間窗細分為多個窗口，按窗口維度統計資源信息，包括請求總數、成功總數、異?？倲?、總耗時、最小耗時、最大耗時等。
動態限流的數據統計，同樣是將1s的時間窗細分為多個窗口，不同的是窗口的統計維度是各個參數值通過的總流量。
具體實現上，每個資源有唯一的 bucket，bucket 內維護一個固定數量的滑動窗口，窗口中的 value 是一個 hash 結構，hash key 為限流參數的參數值，value 為參數值在當前時間窗口的請求量。
參數值流量統計流程：
- 系統收到請求后，首先找到當前資源的 bucket；
- 再根據當前時間戳對 bucket 內的窗口數量取余，定位到當前時間窗；
- 當前時間窗內參數值的請求量+1。
4.2 規則管理
規則管理模塊：配置和管理限流規則。
限流規則通過zk實現從后臺到端上的同步。后臺配置好限流規則后，將限流規則同步到zk；客戶端監聽zk消息變更，同步最新的限流規則。
4.3 流量校驗
4.3.1 參數臨界點
對于動態限流而言，參數的限流閾值不是固定的，只有參數優先級的概念，所以校驗的第一步是要找到限流閾值優先級的臨界點。
如果參數優先級臨界點已知，只需要判斷流量參數的優先級大小。如果請求的優先級高于閾值參數的優先級，pass；反之，如果請求的優先級低于閾值參數的優先級，block；優先級相等，按接口閾值限流。
那么如何確認當前限流的優先級呢？
4.3.2 細分窗口
當前限流閾值配置一般為秒級別的限流，細分滑動窗口，就是將1s的窗口劃分為N個更小的時間窗，只要N足夠大，就可以將前N-1個窗口已經統計到的參數流量近似當做這一秒的流量，進而就可以計算出臨界參數的優先級。
具體來講，每一個窗口中都記錄了參數的請求數量，所以只要將前N-1個窗口的流量累加，就可以得到各個參數在當前這1s內的總請求量；之后按照參數的優先級從高到低，依次累加流量并與閾值比較，如果累加到某個參數時大于限流閾值，則這個參數對應的優先級即為限流閾值優先級的臨界點。
上面分析都是基于最理想情況：將1s的窗口無限細分?？紤]到滑動窗口粒度越小，統計數據計算的越準確，但同時占用的資源也越多，計算越復雜，時延也越高，所以在實際應用中，1s的窗口不可能無限細分，是否有更好的優化方案呢？
4.3.3 動態預測
上面是將1s的窗口劃分為N個更小的時間窗，將前N-1個窗口近似看成1s，利用前N-1個窗口的統計數據，來判斷當前窗口是否需要限流。
N-1→ N → 1s，N越大誤差越小，反之N越小誤差就越大，為了彌補N大小引起的計算誤差，將統計窗口朝前挪一個，即用最近1s已有的統計數據，來判斷當前窗口是否需要限流。
換一種說法：用最近1s已有的統計數據計算臨界點參數，預測當前窗口的請求是否需要限流。如果當前請求參數的優先級高于臨界點參數，pass；低于臨界點參數，block；等于臨界點參數，部分通過。
綜上：動態限流采用細分窗口+動態預測的方法計算當前限流參數的優先級閾值。
舉例說明：對方法 method(String param) 配置動態限流，限流閾值為120，配置 param 具體參數值的優先級為A→ 1, B→ 2, C→ 3（按重要程度劃分 A > B > C）；假設窗口大小為100ms，即1s細分為10個滑動窗口。
每次開始新窗口流量計數時，先統計前10個窗口中各參數的請求量，繼而按照優先級從高到低進行累加，確認優先級閾值；
比如統計到前10個窗口中參數A, B, C的請求量均為100，因為A的流量100 < 閾值120，A + B的流量200 > 閾值120，所以此時臨界參數為B；
窗口接收到新請求后，比較請求參數和臨界參數的優先級，比如參數A的請求，因為A的優先級高于B, pass；參數B的臨界參數請求，允許部分流量通過；參數C的優先級低于臨界參數，block。
4.3.4 double check
經過上面的分析可知，通過滑動窗口+動態預測的方案就可以找到臨界點參數，進而根據參數優先級決定當前請求 pass or block。但是在實際時間窗和統計時間窗之間，有一個時間 gap，在這個時間窗內的流量計算有一定的滯后性，比如上面的例子，在新窗口中A的請求全部 pass，如果此時A的流量突刺到1000，那么總體通過的流量就會超過閾值，如下圖所示。
由上圖可知，在流量突增的一個時間窗內，當前方案通過的流量會有突刺，為了解決流量突增帶來的突刺問題，使用 double check 進行校驗；check1 為細分窗口+動態預測方案，通過 check1 的流量可能會有突刺；增加 check2 對資源進行限流，保證被保護資源通過的總流量不超過閾值。
double check 流量在應對流量突增時的流量情況：
4.4 整體架構
復用 sentinel 責任鏈+ SPI 架構，使用獨立 SDK 打包方式嵌入動態限流模板，不影響原 sentinel 處理流程，按需引入。
4.5 實現效果
動態限流配置生效后，可通過監控查看各配置參數通過/拒絕的請求量，實現限流功能的可視化。
如上圖所示，配置某個資源的單機限流閾值為50，這一秒內的總請求量為74，通過50個請求，拒絕14個請求（其中配置限流的參數 xx.scene.priority1、xx.scene.priority2、xx.scene.priority3 在這一秒通過的請求數量分別為2個、16個、2個；其它參數通過30個請求，拒絕14個請求）。
解釋：在這一秒內，配置的三個參數總請求量為20（2+16+2），小于閾值50，全部通過；其它參數總流量為44，這一秒的總請求量為64（20+44），大于限流閾值50，所以其它參數共通過30個請求，拒絕14個請求。
五、總結
本文介紹了一種基于 sentinel 進行二次開發的動態限流解決方案，提供更細粒度、能夠根據流量動態調整限流閾值的參數級限流方法，是對 sentinel 限流功能的補充和拓展。
- 對比 sentinel 的 QPS 限流，動態限流方案提供了更細粒度的參數級別的限流；
- 對比 sentinel 的熱點參數限流，熱點參數限流是對參數的定量限流，適用于參數大流量場景，比如對某個頻繁請求的參數（id/商品）進行限流；
動態限流根據配置的參數優先級（重要程度）進行限流，限流的閾值參數會根據資源的流量動態調整，pass 高優參數，block 低優參數，限流重點是“保核心”。
綜上，動態限流是對 sentinel 限流功能的補充，用戶可以結合具體場景配置不同的限流方案。
