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

語言: CN / TW / HK

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

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上的使用說明: https://github.com/bosima/FireflySoft.RateLimit#aspnet

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

其主要特點包括:

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

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