ASP.NET Core中使用滑動窗口限流
滑動窗口演算法用於應對請求在時間周期中分布不均勻的情況，能夠更精確的應對流量變化，比較著名的應用場景就是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上的使用說明：//github.com/bosima/FireflySoft.RateLimit#aspnet
FireflySoft.RateLimit 是一個基於 .NET Standard 的限流類庫，其內核簡單輕巧，能夠靈活應對各種需求的限流場景。
其主要特點包括：
- 多種限流演算法：內置固定窗口、滑動窗口、漏桶、令牌桶四種演算法，還可自定義擴展。
- 多種計數存儲：目前支援記憶體、Redis兩種存儲方式。
- 分散式友好：通過Redis存儲支援分散式程式統一計數。
- 限流目標靈活：可以從請求中提取各種數據用於設置限流目標。
- 支援限流懲罰：可以在客戶端觸發限流後鎖定一段時間不允許其訪問。
- 動態更改規則：支援程式運行時動態更改限流規則。
- 自定義錯誤：可以自定義觸發限流後的錯誤碼和錯誤消息。
- 普適性：原則上可以滿足任何需要限流的場景。
Github開源地址：//github.com/bosima/FireflySoft.RateLimit
收穫更多架構知識，請關注公眾號 螢火架構。原創內容，轉載請註明出處。
