ASP.NET Core中使用漏桶演算法限流

語言: CN / TW / HK

時間 2021-12-11 11:48:36 BOSSMA'S BLOG

漏桶演算法是限流的四大主流演算法之一，其應用場景各種資料中介紹的不多，一般都是說應用在網路流量控制中。這裡舉兩個例子：

1、目前家庭上網都會限制一個固定的頻寬，比如100M、200M等，一棟樓有很多的使用者，那麼運營商怎麼保證某些使用者沒有使用過多的頻寬，從而影響到別人呢？這時就可以使用漏桶演算法，限制每個使用者訪問網路的最大頻寬，當然實際會比這複雜很多。

2、有一個祖傳介面，當時寫的時候沒有任何保護措施，現在訪問量稍微大點就會崩潰，但是程式碼誰也改不動。這時候也可以用漏桶演算法，把這個介面封裝一下，將外部請求通過漏桶演算法進行整流，再轉發給這個介面，此時訪問頻率不會超過閾值，介面就不會崩潰了。

演算法原理

說了這麼多，那漏桶演算法到底是怎麼解決問題的呢？請看下圖。

接收到請求後，先把請求放到一個漏桶中，漏桶以恆定的速率漏出請求，然後漏出的請求被處理；如果接收請求的速度過快，導致漏桶滿了，則丟棄新的請求。

可以看出，漏桶演算法主要是通過恆速的方式輸出，給後續資料處理一個穩定的輸入。這樣它就能應對一定的突發流量，使系統不會因為請求量突增而導致崩潰，只不過是通過增加延遲的方式，會有那麼一點浪費資源，這和令牌桶的處理方式不同，關於令牌桶演算法可以看這篇文章： ASP.NET Core中使用令牌桶限流。

還有一個不常提及的好處，恆速的輸出有時候也可以提升效率，比如一次允許漏出兩個請求，則可以將兩次處理合併為一次處理，如果每次處理都涉及到網路IO，則合併處理就有機會減少網路IO的開銷。

演算法實現

這裡講兩種實現方法：程序內即記憶體漏桶演算法、基於Redis的漏桶演算法。

程序內即記憶體漏桶演算法

這裡在請求時計算漏出數量，沒有單獨的漏出處理，描述的演算法稍顯複雜，不過只需要增加一點耐心，也很容易理解。

先來定義幾個變數：

對於漏出速率，用 [每X時間週期Y個] 來表示。X時間週期一般是若干秒、分鐘、小時等時間跨度。
對於當前時間週期的開始時間用Ts表示，當前時間週期的結束時間用Te表示，當前時間用Ti表示。
對於漏桶容量，用Z來表示。
對於X時間內的所有請求數量，用N來表示。

當請求到達時，則可以按以下次序處理：

如果Ti-Ts<=X，說明還在當前時間週期內，先增加N的值：
- 比較N和Y，如果N<=Y，則請求無需等待，直接漏出，進入處理階段；
- 如果N>Y，則比較N與Y+Z：
  - 如果N<=Y+Z，則請求進入漏桶等待，等待時間為：(math.ceiling((N-Y)/Y)-1)*X+(Te – Ti)，等待結束後漏出，進入處理階段；
  - 如果N>Y+Z，則請求無法進入漏桶，只能丟棄掉，實現上就是拒絕請求；
如果Ti-Ts>X，則需要建立新的時間週期：
- 計算過去了幾個時間週期：Pn=math.ceiling((Ti-Te)/X)；
- 重設Ts和Te的值：Ts=上次的Ts+Pn*X，Te=Ts+X；
- 計算這段時間最大可以漏出的數量：Yo=Pn*Y；
- 計算N的值：N= N-Yo<=0 ? 0: N-Yo；
- 此時符合Ti-Ts<=X，又在當前時間週期內了，再回到上邊的步驟依次處理。

基於Redis的漏桶演算法

基於Redis也可以實現上述的演算法，只不過變數的表示方式換成了Redis KV，演算法邏輯還是一樣的。

這些操作邏輯可以封裝在一個Lua script中，因為Lua script在Redis中執行時也是原子操作，所以Redis的限流計數在分散式部署時天然就是準確的。

應用演算法

這裡以限流元件 FireflySoft.RateLimit 為例，實現ASP.NET Core中的漏桶演算法限流。

1、安裝Nuget包

有多種安裝方式，選擇自己喜歡的就行了。

包管理器命令：

Install-Package FireflySoft.RateLimit.AspNetCore

或者.NET命令:

dotnet add package FireflySoft.RateLimit.AspNetCore

或者專案檔案直接新增：

<ItemGroup>
<PackageReference Include="FireflySoft.RateLimit.AspNetCore" Version="2.*" />
</ItemGroup>

2、使用中介軟體

在Startup中使用中介軟體，演示程式碼如下（下邊會有詳細說明）：

public void ConfigureServices(IServiceCollection services)
        {
           ...
           app.AddRateLimit(new InProcessLeakyBucketAlgorithm(
                new[] {
                        // 三個引數：漏桶的容量、單位時間漏出的數量、漏出的單位時間
                    new LeakyBucketRule(20,10, TimeSpan.FromSeconds(1))
                    {
                        ExtractTarget = context =>
                        {
                                // 提取限流目標
                            return (context as HttpContext).Request.Path.Value;
                        },
                        CheckRuleMatching = context =>
                        {
                                // 判斷當前請求是否需要限流處理
                            return true;
                        },
                        Name="leaky bucket limit rule",
                    }
                })
            );
            ...
        }

public void Configure(IApplicationBuilder app, IWebHostEnvironment env)
        {
            ...
            app.UseRateLimit();
            ...
        }

如上需要先註冊服務，然後使用中介軟體。

註冊服務的時候需要提供限流演算法和對應的規則：

這裡使用程序內漏桶演算法InProcessLeakyBucketAlgorithm，還可以使用RedisLeakyBucketAlgorithm，需要傳入一個Redis連線。兩種演算法都支援同步和非同步方法。
漏桶的容量是20，單位時間漏出的數量10，漏出的單位時間是1秒。也就是說1秒漏出10個，1秒內超出10個請求就會被延遲處理，加上漏桶的容量，1秒內超出30個請求就會被限流。
ExtractTarget用於提取限流目標，這裡是每個不同的請求Path，可以根據需求從當前請求中提取關鍵資料，然後設定各種限流目標。如果有IO請求，這裡還支援對應的非同步方法ExtractTargetAsync。
CheckRuleMatching用於驗證當前請求是否限流，傳入的物件也是當前請求，方便提取關鍵資料進行驗證。如果有IO請求，這裡還支援對應的非同步方法CheckRuleMatchingAsync。
預設被限流時會返回HttpStatusCode 429，可以在AddRateLimit時使用可選引數error自定義這個值，以及Http Header和Body中的內容。

基本的使用就是上邊例子中的這些了。

如果還是基於傳統的.NET Framework，則需要在Application_Start中註冊一個訊息處理器RateLimitHandler，演算法和規則部分都是共用的，具體可以看Github上的使用說明： http://github.com/bosima/FireflySoft.RateLimit#aspnet

FireflySoft.RateLimit 是一個基於 .NET Standard 的限流類庫，其核心簡單輕巧，能夠靈活應對各種需求的限流場景。

其主要特點包括：

多種限流演算法：內建固定視窗、滑動視窗、漏桶、令牌桶四種演算法，還可自定義擴充套件。
多種計數儲存：目前支援記憶體、Redis兩種儲存方式。
分散式友好：通過Redis儲存支援分散式程式統一計數。
限流目標靈活：可以從請求中提取各種資料用於設定限流目標。
支援限流懲罰：可以在客戶端觸發限流後鎖定一段時間不允許其訪問。
動態更改規則：支援程式執行時動態更改限流規則。
自定義錯誤：可以自定義觸發限流後的錯誤碼和錯誤訊息。
普適性：原則上可以滿足任何需要限流的場景。

Github開源地址： http://github.com/bosima/FireflySoft.RateLimit

「其他文章」