ASP.NET Core中使用滑動視窗限流

語言: CN / TW / HK

滑動視窗演算法用於應對請求在時間週期中分佈不均勻的情況,能夠更精確的應對流量變化,比較著名的應用場景就是TCP協議的流量控制,不過今天要說的是服務限流場景中的應用。

演算法原理

這裡假設業務需要每秒鐘限流100次,先來看固定視窗演算法的兩個問題:

  • 漏檢

如下圖所示,單看第1秒和第2秒,其請求次數都沒有超過100,所以使用固定視窗演算法時不會觸發限流。但是第1秒的後500ms的請求數加上第2秒的前500毫秒的請求數就超過了100,這時候可能會給系統帶來傷害,使用固定視窗演算法時不能檢測到這種情況。

  • 太剛

針對漏檢的問題,你可能會說,可以把時間視窗設定為500ms,把限流閾值設定為50。那麼來看下圖,除了第2個計數週期超過了50,從而觸發限流,前後幾個計數週期的請求都很正常,甚至都不會超過閾值的50%,可能第2個計數週期的情況實在太特殊,1天都不會出現第2次,如果對系統不會造成影響,能不能通融下,做不到!固定視窗演算法這時候就會顯得太過剛性。

那麼滑動視窗如何來解決這兩個問題呢?還是先來看圖:

如上圖所示:

  • 滑動視窗的時間跨度是1秒,每個小計數週期的時間跨度是500ms,此處的滑動視窗包含2個小計數週期。
  • 隨著時間的前進,滑動視窗包含的小計數週期會以500ms為單位向前移動,但始終是包含2個小計數週期。
  • 判斷是否限流時,需要將當前滑動視窗包含的2個小計數週期的計數值加起來。
  • 相比固定視窗計數器演算法,滑動視窗可以有效減少漏檢,如上圖滑動視窗移動到了500-1500ms,發現總數超過100,則觸發限流;滑動視窗在0-1000ms、1000-2000ms時都不會觸發限流,即使其中某個小週期的計數值超過了閾值的半數,但是總數沒有超過100,就不會限流,能夠應對極少出現的突發流量情況。

從分析還可以看出,滑動視窗的小週期劃分的越多,則檢測越準確,但用於跟蹤的計數也越多,使用的記憶體和計算量都會增大。

演算法實現

這裡講兩種實現方法:程序內即記憶體滑動視窗演算法、基於Redis的滑動視窗演算法。

程序內即記憶體滑動視窗演算法

這裡介紹一種效能比較高的方法,使用陣列實現滑動視窗,這是環形佇列的一種特例,如下圖所示:

  • 假設滑動視窗需要5個小的計數週期,則初始化一個長度為5的整形陣列,數字表示陣列中的第幾個元素。
  • 我們知道佇列有頭有尾,從隊頭取出資料,向隊尾插入資料,帶括號的數字表示是佇列中的第幾個元素。
  • 滑動視窗向前移動時,隊尾向右移動1位,同時隊頭也向右移動1位。
  • 隊尾和隊頭向右移動都可能會溢位陣列,此時讓它們回到陣列的起始位置,即圖中陣列的第1個位置。

關於這個演算法的詳細介紹,可以看這篇文章: 如何使用陣列實現滑動視窗

基於Redis的滑動視窗演算法

基於Redis時也可以使用類似環形佇列的方法,比如定義5個KV作為陣列的5個元素。不過我之前實現時採用了一種更直觀的方式,每個小的計數週期都建立一個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 InProcessSlidingWindowAlgorithm(
                new[] {
                		// 建構函式有兩個引數:滑動視窗的時間長度、小計數週期的時間長度
                    new SlidingWindowRule(TimeSpan.FromSeconds(5), TimeSpan.FromSeconds(1))
                    {
                        ExtractTarget = context =>
                        {
                        		// 提取限流目標
                            return (context as HttpContext).Request.Path.Value;
                        },
                        CheckRuleMatching = context =>
                        {
                        		// 判斷當前請求是否需要限流處理
                            return true;
                        },
                        Name="sliding window limit rule",
                        LimitNumber=100, // 限流閾值,這裡即5秒最多100次請求
                    }
                })
            );
            ...
        }

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

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

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

  • 這裡使用程序內固定視窗演算法InProcessSlidingWindowAlgorithm,還可以使用RedisSlidingWindowAlgorithm,需要傳入一個Redis連線。兩種演算法都支援同步和非同步方法。
  • 限流閾值是100,限流滑動視窗是5秒,小計數週期是1秒。
  • 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

收穫更多架構知識,請關注公眾號 螢火架構。原創內容,轉載請註明出處。