一、背景

1.1 當前的限流方案

隨著互聯(lián)網(wǎng)的發(fā)展及業(yè)務的增長，系統(tǒng)的流量和請求量越來越大，針對高并發(fā)系統(tǒng)，如果不對請求量進行限制，在流量突增時可能會導致系統(tǒng)崩潰或者服務不可用，影響用戶體驗。因此，系統(tǒng)需要引入限流來控制請求的流量，保證系統(tǒng)的可用性和穩(wěn)定性。當前推薦業(yè)務使用公司vsentinel 限流工具，主要使用 QPS 限流和熱點參數(shù)限流。

QPS 限流：對某個資源（通常為接口或方法，也可以自定義資源）的 QPS /并發(fā)數(shù)進行限流；
熱點參數(shù)限流：對某些具體的參數(shù)值進行限流，避免因為熱點參數(shù)的過度訪問導致服務宕機。

1.2 存在的問題

無論是 QPS 限流還是熱點參數(shù)限流，都是對資源/參數(shù)的定量限流，即對某個資源/參數(shù)設置固定閾值，超過閾值則進行限流。

回到業(yè)務，游戲推薦系統(tǒng)作為游戲分發(fā)的平臺，向公司內(nèi)所有主要流量入口（包括游戲中心、應用商店、瀏覽器等）分發(fā)游戲、小游戲、內(nèi)容和評論，具有大流量、高負載的業(yè)務特點。同時，游戲推薦系統(tǒng)對接的場景多（600+），單個性化接口有100+場景調(diào)用（場景可以理解為接口請求的一個基本請求參數(shù)）。當前的限流方案存在以下幾個問題：

1. 參數(shù)級別的限流，600+場景，無法做到每個場景精細化限流；
2. 接口級別的限流，不會區(qū)分具體的場景，無法保證核心場景的可用性；
3. 如果場景流量有變更，需要及時調(diào)整限流閾值，不易維護；
4. 場景的流量會實時變化，無法做到根據(jù)流量變化的動態(tài)限流。

鑒于以上限流問題，推薦系統(tǒng)需要一個能夠根據(jù)參數(shù)流量變化而動態(tài)調(diào)整限流閾值的精細化限流方案。

二、動態(tài)限流介紹

從配置方式上來看，動態(tài)限流和 QPS 限流、熱點參數(shù)限流最大的不同之處在于，動態(tài)限流不是通過配置固定閾值進行限流，而是配置每個參數(shù)的優(yōu)先級，根據(jù)參數(shù)的優(yōu)先級動態(tài)調(diào)整限流閾值。

動態(tài)限流將資源和參數(shù)進行綁定，首先配置資源（一般是接口/方法）總的限流閾值，進而配置資源下具體參數(shù)的優(yōu)先級，根據(jù)參數(shù)配置的優(yōu)先級和實時流量，決定當前請求pass or block。

下圖示例中，資源總的限流閾值為150，參數(shù)A、B、C、D的 QPS 均為100，且配置的參數(shù)優(yōu)先級 A>B>C>D。

• 參數(shù)A優(yōu)先級最高，且 QPS(A) = 100 < 限流閾值150，所以A的流量全部通過；
• 參數(shù)B優(yōu)先級僅次于參數(shù)A，且 QPS(A) = 100 < 限流閾值150、QPS(A)  + QPS(B)= 200 > 限流閾值150，所以參數(shù)B部分流量通過，pass : 50，block：50；
• 參數(shù)C和其它參數(shù)的優(yōu)先級低于參數(shù)B，且 QPS(A)  + QPS(B)= 200 > 限流閾值150，所以參數(shù)C和其它參數(shù)均被限流。

如果此時參數(shù)值A的 QPS 變?yōu)?00，B、C的 QPS 仍為100，通過動態(tài)限流實現(xiàn)：A請求部分通過，B請求全部攔截，C請求全部攔截；根據(jù)各參數(shù)值流量的變化，動態(tài)適配各參數(shù)值通過/攔截的流量，從而實現(xiàn)根據(jù)參數(shù)值動態(tài)限流的效果。

總結(jié)：動態(tài)限流本質(zhì)上是參數(shù)優(yōu)先級限流，支持對參數(shù)值配置優(yōu)先級，根據(jù)參數(shù)值的優(yōu)先級進行動態(tài)流控。當流量超過閾值后，優(yōu)先保證高優(yōu)先級參數(shù)通過，攔截優(yōu)先級低的參數(shù)請求。

三、sentinel 介紹

由于動態(tài)限流是基于 sentinel 進行二次開發(fā)，且動態(tài)限流的實現(xiàn)算法是基于 sentinel QPS 限流的優(yōu)化，這里首先介紹下 sentinel 實現(xiàn)原理和 sentinel QPS 限流的滑動窗口計數(shù)器限流算法。

3.1 sentinel 原理介紹

sentinel 是阿里開源的一款面向分布式、多語言異構(gòu)化服務架構(gòu)的流量治理組件。主要以流量為切入點，從流量路由、流量控制、流量整形、熔斷降級、系統(tǒng)自適應過載保護、熱點流量防護等多個維度來幫助開發(fā)者保障微服務的穩(wěn)定性。(官網(wǎng)描述)

sentinel 主要通過責任鏈模式實現(xiàn)不同模式的限流功能，責任鏈由一系列 ProcessorSlot 對象組成，每個 ProcessorSlot 對象負責不同的功能。

ProcessorSlot  對象可以分為兩類：一類是輔助完成資源指標數(shù)據(jù)統(tǒng)計的 slot，一類是實現(xiàn)限流降級功能的 slot。

輔助資源指標數(shù)據(jù)統(tǒng)計的  ProcessorSlot：

• NodeSelectorSlot：負責收集資源路徑，并將調(diào)用路徑樹狀存儲，用于后續(xù)根據(jù)調(diào)用路徑來限流降級；
• ClusterBuilderSlot：負責存儲資源的統(tǒng)計信息以及調(diào)用者信息，例如該資源的 RT、QPS、線程數(shù)等等，作為多維度限流、降級的依據(jù)；
• StatisticSlot：負責實現(xiàn)指標數(shù)據(jù)統(tǒng)計，從多個維度（入口流量、調(diào)用者、資源）統(tǒng)計響應時間、并發(fā)線程數(shù)、處理失敗數(shù)量、處理成功數(shù)量等指標信息。

實現(xiàn)限流降級功能的 slot：

• ParamFlowSlot：用于根據(jù)請求參數(shù)進行限流（熱點參數(shù)限流），例如根據(jù)某個參數(shù)的 QPS 進行限流，或者根據(jù)某個參數(shù)的值進行限流；
• SystemSlot：用于根據(jù)系統(tǒng)負載情況進行限流，例如 CPU 使用率、內(nèi)存使用率等。
• AuthoritySlot：用于根據(jù)調(diào)用者身份進行限流，例如根據(jù)調(diào)用者的 IP 地址、Token 等信息進行限流。
• FlowSlot：用于根據(jù) QPS 進行限流，例如每秒最多只能處理多少請求。
• DegradeSlot：用于實現(xiàn)熔斷降級功能，例如當某個資源出現(xiàn)異常時，可以將其熔斷并降級處理。

除了上述原生 ProcessorSlot，sentinel 還支持 SPI 插件功能，通過實現(xiàn) ProcessorSlot 接口自定義 slot，從而能實現(xiàn)個性化功能拓展。動態(tài)限流正是基于 sentinel SPI 插件方式實現(xiàn)。

3.2 滑動窗口計數(shù)器算法

sentinel 的 QPS 限流采用滑動窗口計數(shù)器算法，下面我們簡單介紹下這個算法原理。

首先介紹一下計數(shù)器算法。

3.2.1 計數(shù)器

計數(shù)器算法：維護一個固定單位時間的計數(shù)器來統(tǒng)計請求數(shù)，在計數(shù)小于限流閾值時通過請求，計數(shù)到達限流閾值后攔截請求，直到下一個單位時間再重新計數(shù)。
假設資源限制 1 秒內(nèi)的訪問次數(shù)不能超過 100 次。

• 維護一個計數(shù)器，每次有新的請求過來，計數(shù)器加 1；
• 收到新請求后，如果計數(shù)器的值小于限流值，并且與上一次請求的時間間隔還在 1秒內(nèi)，允許請求通過，否則拒絕請求；如果超出了時間間隔，要將計數(shù)器清零。

計數(shù)器算法存在一個問題：窗口切換時可能會出現(xiàn)流量突刺（最高2倍）。
極端情況下，假設每秒限流100，在第1s和第2s分別通100個請求，且第1s的請求集中在后半段，第2s的請求集中在前半段，那么其實在500ms到1500ms這個1s的時間段，通過了200個請求。

為了解決這個問題，引入了基于滑動窗口的計數(shù)器算法。

3.2.2 滑動窗口計數(shù)器

滑動窗口計數(shù)器算法是計數(shù)器算法的改進，解決了固定窗口的流量突刺問題。算法原理：

• 將時間劃分為細粒度的區(qū)間，每個區(qū)間維持一個計數(shù)器，每進入一個請求則將計數(shù)器加1；
• 多個區(qū)間組成一個時間窗口，每到一個區(qū)間時間后，則拋棄最老的一個區(qū)間，納入新區(qū)間；
• 若當前窗口的區(qū)間計數(shù)器總和超過設定的限制數(shù)量，則本窗口內(nèi)的后續(xù)請求都被丟棄。

滑動窗口本質(zhì)上是固定窗口更細粒度的限流，將單位時間劃分多個窗口，劃分的窗口越多，數(shù)據(jù)越精確。

四、基于 sentinel 的動態(tài)限流方案

動態(tài)限流是基于 sentinel 的二次開發(fā)，具體實現(xiàn)流程和 sentinel 的 QPS 限流類似，可以歸納為三步：數(shù)據(jù)統(tǒng)計、規(guī)則管理、流量校驗。

• 數(shù)據(jù)統(tǒng)計：統(tǒng)計資源（接口/方法/參數(shù)）的流量；
• 規(guī)則管理：管理限流規(guī)則，維護資源的限流閾值及參數(shù)值優(yōu)先級；
• 流量校驗：對比統(tǒng)計到的流量和對應的限流規(guī)則，決定當前請求 pass or block。

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

動態(tài)限流的數(shù)據(jù)統(tǒng)計同 sentinel 流量控制模塊一樣，使用滑動窗口計數(shù)器算法統(tǒng)計當前的流量。

具體來講，sentinel 流量控制中的數(shù)據(jù)統(tǒng)計，是將1s的時間窗細分為多個窗口，按窗口維度統(tǒng)計資源信息，包括請求總數(shù)、成功總數(shù)、異常總數(shù)、總耗時、最小耗時、最大耗時等。

動態(tài)限流的數(shù)據(jù)統(tǒng)計，同樣是將1s的時間窗細分為多個窗口，不同的是窗口的統(tǒng)計維度是各個參數(shù)值通過的總流量。

具體實現(xiàn)上，每個資源有唯一的 bucket，bucket 內(nèi)維護一個固定數(shù)量的滑動窗口，窗口中的 value 是一個 hash 結(jié)構(gòu)，hash key 為限流參數(shù)的參數(shù)值，value 為參數(shù)值在當前時間窗口的請求量。

參數(shù)值流量統(tǒng)計流程：

1. 系統(tǒng)收到請求后，首先找到當前資源的 bucket；
2. 再根據(jù)當前時間戳對 bucket 內(nèi)的窗口數(shù)量取余，定位到當前時間窗；
3. 當前時間窗內(nèi)參數(shù)值的請求量+1。

4.2 規(guī)則管理

規(guī)則管理模塊：配置和管理限流規(guī)則。

限流規(guī)則通過zk實現(xiàn)從后臺到端上的同步。后臺配置好限流規(guī)則后，將限流規(guī)則同步到zk；客戶端監(jiān)聽zk消息變更，同步最新的限流規(guī)則。

4.3 流量校驗

4.3.1  參數(shù)臨界點

對于動態(tài)限流而言，參數(shù)的限流閾值不是固定的，只有參數(shù)優(yōu)先級的概念，所以校驗的第一步是要找到限流閾值優(yōu)先級的臨界點。

如果參數(shù)優(yōu)先級臨界點已知，只需要判斷流量參數(shù)的優(yōu)先級大小。如果請求的優(yōu)先級高于閾值參數(shù)的優(yōu)先級，pass；反之，如果請求的優(yōu)先級低于閾值參數(shù)的優(yōu)先級，block；優(yōu)先級相等，按接口閾值限流。

那么如何確認當前限流的優(yōu)先級呢？

4.3.2 細分窗口

當前限流閾值配置一般為秒級別的限流，細分滑動窗口，就是將1s的窗口劃分為N個更小的時間窗，只要N足夠大，就可以將前N-1個窗口已經(jīng)統(tǒng)計到的參數(shù)流量近似當做這一秒的流量，進而就可以計算出臨界參數(shù)的優(yōu)先級。
具體來講，每一個窗口中都記錄了參數(shù)的請求數(shù)量，所以只要將前N-1個窗口的流量累加，就可以得到各個參數(shù)在當前這1s內(nèi)的總請求量；之后按照參數(shù)的優(yōu)先級從高到低，依次累加流量并與閾值比較，如果累加到某個參數(shù)時大于限流閾值，則這個參數(shù)對應的優(yōu)先級即為限流閾值優(yōu)先級的臨界點。

上面分析都是基于最理想情況：將1s的窗口無限細分?？紤]到滑動窗口粒度越小，統(tǒng)計數(shù)據(jù)計算的越準確，但同時占用的資源也越多，計算越復雜，時延也越高，所以在實際應用中，1s的窗口不可能無限細分，是否有更好的優(yōu)化方案呢？

4.3.3 動態(tài)預測

上面是將1s的窗口劃分為N個更小的時間窗，將前N-1個窗口近似看成1s，利用前N-1個窗口的統(tǒng)計數(shù)據(jù)，來判斷當前窗口是否需要限流。

N-1→ N → 1s，N越大誤差越小，反之N越小誤差就越大，為了彌補N大小引起的計算誤差，將統(tǒng)計窗口朝前挪一個，即用最近1s已有的統(tǒng)計數(shù)據(jù)，來判斷當前窗口是否需要限流。

換一種說法：用最近1s已有的統(tǒng)計數(shù)據(jù)計算臨界點參數(shù)，預測當前窗口的請求是否需要限流。如果當前請求參數(shù)的優(yōu)先級高于臨界點參數(shù)，pass；低于臨界點參數(shù)，block；等于臨界點參數(shù)，部分通過。

綜上：動態(tài)限流采用細分窗口+動態(tài)預測的方法計算當前限流參數(shù)的優(yōu)先級閾值。

舉例說明：對方法 method(String param) 配置動態(tài)限流，限流閾值為120，配置 param 具體參數(shù)值的優(yōu)先級為A→ 1, B→ 2, C→ 3（按重要程度劃分 A > B > C）；假設窗口大小為100ms，即1s細分為10個滑動窗口。
每次開始新窗口流量計數(shù)時，先統(tǒng)計前10個窗口中各參數(shù)的請求量，繼而按照優(yōu)先級從高到低進行累加，確認優(yōu)先級閾值；
比如統(tǒng)計到前10個窗口中參數(shù)A, B, C的請求量均為100，因為A的流量100 < 閾值120，A + B的流量200 > 閾值120，所以此時臨界參數(shù)為B；
窗口接收到新請求后，比較請求參數(shù)和臨界參數(shù)的優(yōu)先級，比如參數(shù)A的請求，因為A的優(yōu)先級高于B, pass；參數(shù)B的臨界參數(shù)請求，允許部分流量通過；參數(shù)C的優(yōu)先級低于臨界參數(shù)，block。

4.3.4 double check

經(jīng)過上面的分析可知，通過滑動窗口+動態(tài)預測的方案就可以找到臨界點參數(shù)，進而根據(jù)參數(shù)優(yōu)先級決定當前請求 pass or block。但是在實際時間窗和統(tǒng)計時間窗之間，有一個時間 gap，在這個時間窗內(nèi)的流量計算有一定的滯后性，比如上面的例子，在新窗口中A的請求全部 pass，如果此時A的流量突刺到1000，那么總體通過的流量就會超過閾值，如下圖所示。

由上圖可知，在流量突增的一個時間窗內(nèi)，當前方案通過的流量會有突刺，為了解決流量突增帶來的突刺問題，使用 double check 進行校驗；check1 為細分窗口+動態(tài)預測方案，通過 check1 的流量可能會有突刺；增加 check2 對資源進行限流，保證被保護資源通過的總流量不超過閾值。

double check 流量在應對流量突增時的流量情況：

4.4 整體架構(gòu)

復用 sentinel 責任鏈+ SPI 架構(gòu)，使用獨立 SDK 打包方式嵌入動態(tài)限流模板，不影響原 sentinel 處理流程，按需引入。

4.5 實現(xiàn)效果

動態(tài)限流配置生效后，可通過監(jiān)控查看各配置參數(shù)通過/拒絕的請求量，實現(xiàn)限流功能的可視化。

如上圖所示，配置某個資源的單機限流閾值為50，這一秒內(nèi)的總請求量為74，通過50個請求，拒絕14個請求（其中配置限流的參數(shù) xx.scene.priority1、xx.scene.priority2、xx.scene.priority3 在這一秒通過的請求數(shù)量分別為2個、16個、2個；其它參數(shù)通過30個請求，拒絕14個請求）。

解釋：在這一秒內(nèi)，配置的三個參數(shù)總請求量為20（2+16+2），小于閾值50，全部通過；其它參數(shù)總流量為44，這一秒的總請求量為64（20+44），大于限流閾值50，所以其它參數(shù)共通過30個請求，拒絕14個請求。

五、總結(jié)

本文介紹了一種基于 sentinel 進行二次開發(fā)的動態(tài)限流解決方案，提供更細粒度、能夠根據(jù)流量動態(tài)調(diào)整限流閾值的參數(shù)級限流方法，是對 sentinel 限流功能的補充和拓展。

• 對比 sentinel 的 QPS 限流，動態(tài)限流方案提供了更細粒度的參數(shù)級別的限流；
• 對比 sentinel 的熱點參數(shù)限流，熱點參數(shù)限流是對參數(shù)的定量限流，適用于參數(shù)大流量場景，比如對某個頻繁請求的參數(shù)（id/商品）進行限流；
  動態(tài)限流根據(jù)配置的參數(shù)優(yōu)先級（重要程度）進行限流，限流的閾值參數(shù)會根據(jù)資源的流量動態(tài)調(diào)整，pass 高優(yōu)參數(shù)，block 低優(yōu)參數(shù)，限流重點是“保核心”。

綜上，動態(tài)限流是對 sentinel 限流功能的補充，用戶可以結(jié)合具體場景配置不同的限流方案。