漏桶算法是限流的四大主流算法之一欲侮，其應(yīng)用場(chǎng)景各種資料中介紹的不多崭闲，一般都是說(shuō)應(yīng)用在網(wǎng)絡(luò)流量控制中。這里舉兩個(gè)例子：

1威蕉、目前家庭上網(wǎng)都會(huì)限制一個(gè)固定的帶寬刁俭，比如100M、200M等韧涨，一棟樓有很多的用戶牍戚，那么運(yùn)營(yíng)商怎么保證某些用戶沒(méi)有使用過(guò)多的帶寬，從而影響到別人呢虑粥？這時(shí)就可以使用漏桶算法如孝，限制每個(gè)用戶訪問(wèn)網(wǎng)絡(luò)的最大帶寬，當(dāng)然實(shí)際會(huì)比這復(fù)雜很多娩贷。

2第晰、有一個(gè)祖?zhèn)鹘涌冢?dāng)時(shí)寫的時(shí)候沒(méi)有任何保護(hù)措施彬祖，現(xiàn)在訪問(wèn)量稍微大點(diǎn)就會(huì)崩潰但荤，但是代碼誰(shuí)也改不動(dòng)。這時(shí)候也可以用漏桶算法涧至，把這個(gè)接口封裝一下腹躁，將外部請(qǐng)求通過(guò)漏桶算法進(jìn)行整流，再轉(zhuǎn)發(fā)給這個(gè)接口南蓬，此時(shí)訪問(wèn)頻率不會(huì)超過(guò)閾值纺非，接口就不會(huì)崩潰了哑了。

算法原理

說(shuō)了這么多，那漏桶算法到底是怎么解決問(wèn)題的呢烧颖？請(qǐng)看下圖弱左。

WX20211211-073745@2x

接收到請(qǐng)求后，先把請(qǐng)求放到一個(gè)漏桶中炕淮，漏桶以恒定的速率漏出請(qǐng)求拆火，然后漏出的請(qǐng)求被處理；如果接收請(qǐng)求的速度過(guò)快涂圆，導(dǎo)致漏桶滿了们镜，則丟棄新的請(qǐng)求。

可以看出润歉，漏桶算法主要是通過(guò)恒速的方式輸出模狭，給后續(xù)數(shù)據(jù)處理一個(gè)穩(wěn)定的輸入。這樣它就能應(yīng)對(duì)一定的突發(fā)流量踩衩，使系統(tǒng)不會(huì)因?yàn)檎?qǐng)求量突增而導(dǎo)致崩潰嚼鹉，只不過(guò)是通過(guò)增加延遲的方式，會(huì)有那么一點(diǎn)浪費(fèi)資源驱富，這和令牌桶的處理方式不同锚赤，關(guān)于令牌桶算法可以看這篇文章：ASP.NET Core中使用令牌桶限流。

還有一個(gè)不常提及的好處褐鸥，恒速的輸出有時(shí)候也可以提升效率宴树，比如一次允許漏出兩個(gè)請(qǐng)求，則可以將兩次處理合并為一次處理晶疼，如果每次處理都涉及到網(wǎng)絡(luò)IO酒贬，則合并處理就有機(jī)會(huì)減少網(wǎng)絡(luò)IO的開銷。

算法實(shí)現(xiàn)

這里講兩種實(shí)現(xiàn)方法：進(jìn)程內(nèi)即內(nèi)存漏桶算法翠霍、基于Redis的漏桶算法锭吨。

進(jìn)程內(nèi)即內(nèi)存漏桶算法

這里在請(qǐng)求時(shí)計(jì)算漏出數(shù)量，沒(méi)有單獨(dú)的漏出處理寒匙，描述的算法稍顯復(fù)雜零如，不過(guò)只需要增加一點(diǎn)耐心，也很容易理解锄弱。

先來(lái)定義幾個(gè)變量：

• 對(duì)于漏出速率考蕾，用 [每X時(shí)間周期Y個(gè)] 來(lái)表示。X時(shí)間周期一般是若干秒会宪、分鐘肖卧、小時(shí)等時(shí)間跨度。

• 對(duì)于當(dāng)前時(shí)間周期的開始時(shí)間用Ts表示掸鹅，當(dāng)前時(shí)間周期的結(jié)束時(shí)間用Te表示塞帐，當(dāng)前時(shí)間用Ti表示拦赠。

• 對(duì)于漏桶容量，用Z來(lái)表示葵姥。

• 對(duì)于X時(shí)間內(nèi)的所有請(qǐng)求數(shù)量荷鼠，用N來(lái)表示。

當(dāng)請(qǐng)求到達(dá)時(shí)榔幸，則可以按以下次序處理：

• 如果Ti-Ts<=X允乐，說(shuō)明還在當(dāng)前時(shí)間周期內(nèi)，先增加N的值：

  • 比較N和Y削咆，如果N<=Y牍疏，則請(qǐng)求無(wú)需等待，直接漏出态辛，進(jìn)入處理階段麸澜；
  • 如果N>Y挺尿，則比較N與Y+Z：
    • 如果N<=Y+Z奏黑，則請(qǐng)求進(jìn)入漏桶等待，等待時(shí)間為：(math.ceiling((N-Y)/Y)-1)*X+(Te - Ti)编矾，等待結(jié)束后漏出熟史，進(jìn)入處理階段；
    • 如果N>Y+Z窄俏，則請(qǐng)求無(wú)法進(jìn)入漏桶蹂匹，只能丟棄掉，實(shí)現(xiàn)上就是拒絕請(qǐng)求凹蜈；

• 如果Ti-Ts>X限寞，則需要?jiǎng)?chuàng)建新的時(shí)間周期：

  • 計(jì)算過(guò)去了幾個(gè)時(shí)間周期：Pn=math.ceiling((Ti-Te)/X)；
  • 重設(shè)Ts和Te的值：Ts=上次的Ts+Pn*X仰坦，Te=Ts+X履植；
  • 計(jì)算這段時(shí)間最大可以漏出的數(shù)量：Yo=Pn*Y；
  • 計(jì)算N的值：N= N-Yo<=0 ? 0: N-Yo悄晃；
  • 此時(shí)符合Ti-Ts<=X玫霎，又在當(dāng)前時(shí)間周期內(nèi)了，再回到上邊的步驟依次處理妈橄。

基于Redis的漏桶算法

基于Redis也可以實(shí)現(xiàn)上述的算法庶近，只不過(guò)變量的表示方式換成了Redis KV，算法邏輯還是一樣的眷蚓。

這些操作邏輯可以封裝在一個(gè)Lua script中鼻种，因?yàn)長(zhǎng)ua script在Redis中執(zhí)行時(shí)也是原子操作，所以Redis的限流計(jì)數(shù)在分布式部署時(shí)天然就是準(zhǔn)確的沙热。

應(yīng)用算法

這里以限流組件 FireflySoft.RateLimit 為例普舆，實(shí)現(xiàn)ASP.NET Core中的漏桶算法限流恬口。

1、安裝Nuget包

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

包管理器命令：

Install-Package FireflySoft.RateLimit.AspNetCore

或者.NET命令:

dotnet add package FireflySoft.RateLimit.AspNetCore

或者項(xiàng)目文件直接添加：

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

2、使用中間件

在Startup中使用中間件蛾洛，演示代碼如下（下邊會(huì)有詳細(xì)說(shuō)明）：

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

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

如上需要先注冊(cè)服務(wù)轧膘，然后使用中間件钞螟。

注冊(cè)服務(wù)的時(shí)候需要提供限流算法和對(duì)應(yīng)的規(guī)則：

• 這里使用進(jìn)程內(nèi)漏桶算法InProcessLeakyBucketAlgorithm，還可以使用RedisLeakyBucketAlgorithm谎碍，需要傳入一個(gè)Redis連接鳞滨。兩種算法都支持同步和異步方法。
• 漏桶的容量是20蟆淀，單位時(shí)間漏出的數(shù)量10拯啦，漏出的單位時(shí)間是1秒。也就是說(shuō)1秒漏出10個(gè)熔任，1秒內(nèi)超出10個(gè)請(qǐng)求就會(huì)被延遲處理褒链，加上漏桶的容量，1秒內(nèi)超出30個(gè)請(qǐng)求就會(huì)被限流疑苔。
• ExtractTarget用于提取限流目標(biāo)甫匹，這里是每個(gè)不同的請(qǐng)求Path，可以根據(jù)需求從當(dāng)前請(qǐng)求中提取關(guān)鍵數(shù)據(jù)惦费，然后設(shè)定各種限流目標(biāo)兵迅。如果有IO請(qǐng)求螟蒸，這里還支持對(duì)應(yīng)的異步方法ExtractTargetAsync迹缀。
• CheckRuleMatching用于驗(yàn)證當(dāng)前請(qǐng)求是否限流贝椿，傳入的對(duì)象也是當(dāng)前請(qǐng)求趁耗，方便提取關(guān)鍵數(shù)據(jù)進(jìn)行驗(yàn)證天梧。如果有IO請(qǐng)求邻眷，這里還支持對(duì)應(yīng)的異步方法CheckRuleMatchingAsync鼓鲁。
• 默認(rèn)被限流時(shí)會(huì)返回HttpStatusCode 429翎嫡，可以在AddRateLimit時(shí)使用可選參數(shù)error自定義這個(gè)值臀突，以及Http Header和Body中的內(nèi)容勉抓。

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

如果還是基于傳統(tǒng)的.NET Framework候学，則需要在Application_Start中注冊(cè)一個(gè)消息處理器RateLimitHandler藕筋，算法和規(guī)則部分都是共用的，具體可以看Github上的使用說(shuō)明：https://github.com/bosima/FireflySoft.RateLimit#aspnet

FireflySoft.RateLimit 是一個(gè)基于 .NET Standard 的限流類庫(kù)梳码，其內(nèi)核簡(jiǎn)單輕巧隐圾，能夠靈活應(yīng)對(duì)各種需求的限流場(chǎng)景伍掀。

其主要特點(diǎn)包括：

• 多種限流算法：內(nèi)置固定窗口、滑動(dòng)窗口暇藏、漏桶蜜笤、令牌桶四種算法，還可自定義擴(kuò)展盐碱。
• 多種計(jì)數(shù)存儲(chǔ)：目前支持內(nèi)存把兔、Redis兩種存儲(chǔ)方式。
• 分布式友好：通過(guò)Redis存儲(chǔ)支持分布式程序統(tǒng)一計(jì)數(shù)瓮顽。
• 限流目標(biāo)靈活：可以從請(qǐng)求中提取各種數(shù)據(jù)用于設(shè)置限流目標(biāo)县好。
• 支持限流懲罰：可以在客戶端觸發(fā)限流后鎖定一段時(shí)間不允許其訪問(wèn)。
• 動(dòng)態(tài)更改規(guī)則：支持程序運(yùn)行時(shí)動(dòng)態(tài)更改限流規(guī)則暖混。
• 自定義錯(cuò)誤：可以自定義觸發(fā)限流后的錯(cuò)誤碼和錯(cuò)誤消息缕贡。
• 普適性：原則上可以滿足任何需要限流的場(chǎng)景。

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

收獲更多架構(gòu)知識(shí)拣播，請(qǐng)關(guān)注公眾號(hào) 螢火架構(gòu)晾咪。原創(chuàng)內(nèi)容，轉(zhuǎn)載請(qǐng)注明出處诫尽。