這一篇是紀錄閱讀 超大流量分佈式系統架構解決方案:人人都是架構師2.0 的讀書筆記,筆者在書中有介紹在面對大流量的請求洗禮時,常見的手段有以下幾種方式
- 擴充
- 靜態化
- 限流
- 緩存
- 隊列
為什麼需要限流
大型電商網站主要技術挑戰可能來自短時間內客戶忽然的大流量與短時間內的高併發請求,像是之前大家在搶購的 Switch 動物之森主機(
常見限流演算法
書中介紹常見的限流演算有令牌桶算法、漏桶算法以及計數器算法三種,以下就針對這三種作簡單介紹
令牌桶算法
令牌桶(Token Bucket)算法在 wiki 說明敘述如下
每 1/r 秒會新增一個令牌(Token)到桶(bucket)中 桶(bucket)中最多可容納 b 令牌。如果桶已滿時則丟棄該令牌(Token) 當傳送 n bytes 封包時,桶(bucket)中如果有 n 個令牌(token >= n),封包將會送至網路 當可用的 token < n 時,不會從桶(bucket)刪除任何 token,該封包會被視為不合格的
圖片來源 https://gateoverflow.in/39720/gate2016-1-54
令牌桶算法的原理是會以固定的速度將令牌(token)放入桶(bucket)中,當要處理請求時首先會先到桶(bucket)中取得是否有足夠的令牌(token),當桶(bucket)中的令牌(token)用完時則拒絕服務。
從上述原理可以得知桶(bucket)的容量大小就是系統的最大併發數;可能的瓶頸是令牌桶算法中會有一個執行緒專門在產生/更新令牌(token)數,如果要在很短的時間內要產生大量的令牌數量的話會消耗系統 CPU 資源,舉例來說如果需求是每 1ms 就產生一次 Token 數量,該執行緒就會頻繁的佔用系統 CPU 資源來產生需要的 Token 數量,關於更多令牌桶算法的討論可以參考此討論串 GATE2016-1-54,裡面有更多詳細關於該算法的速率解說與範例算式說明。
漏桶算法
漏桶(Leaky bucket)算法在 wiki 說明敘述如下
請求進入漏桶(bucket)裡,桶(bucket)容量是固定的 當桶(bucket)中的水量(請求)為空時,則不在流出水滴 流出水滴的速率為固定的,桶(bucket)滿了則會溢出
圖片來源 https://developpaper.com/rate-limit-scheme-of-gateway/
漏桶算法的原理較為簡單,水滴(請求)進入漏水桶(bucker),漏水桶流出水滴的速度為固定的,當水滴進入水桶的速度太快時就直接溢出。漏桶算法提供的機制是限制流量數據的流出速度,且流出速度是持續保持固定的。
上述是介紹 Leaky bucket 中的 meter 版本,在 wiki 中還有另外一種是 queue 版本
水滴(請求)進入漏桶(bucket)裡,桶(bucket)容量是固定的 當超過桶(bucket)容量限制時,排隊或者被丟棄 桶(bucket)流出水滴的速率為固定的
計數器算法
計數器算法算式最單純的限流算法,應用層面相當的廣泛,原理如下
在單位時間之內由一個計數器專門負責計算,當新的請求來的時候會與閥值(水位)進行比較,當請求數達到閥值或水位時,便會觸發限流機制的邏輯。舉例來說,假設限流策略為每分鐘為 5 個請求數,每請求一次計數器便會遞增加一,單位時間內計數器與限流閥值相等時,後續的請求將會被執行限流處理,當單位時間過後計數器便會進行重置的動作,新的請求才可以繼續訪問,示意圖如下
漏桶算法 v.s 令牌算法
從本質上來看兩者算法都可以用於高併發與大流量的場景下進行流量管制,不會因為瞬間的大流量而讓系統被打爆。但需要注意這兩者的現流方向是相反的,令牌桶(Token Bucket)算法限制的是流量的平均流入速率,並允許一定程度上的突發狀況(大流量);而漏桶(Leaky bucket)算法限制的是流量的流出速率,而非流入速度,這種流出速度還是保持固定不變的;令牌桶算法的極限可能會是桶的容量加上生成令牌處理程式的最大併發能力。
HTTP Status
上面提到了一些常用的限流算法,接著來看 HTTP 協定中有提到定義當達到限流機制的 Status Code 代碼,在達到閥值(水位)值時,開發者可以使用 429 Too Many Request 告訴呼叫端(用戶)特定時間內發送太多的請求,並在 Response 中說明觸發條件的詳細訊息,以及多久後可以再進行重試(Retry-After),範例如下
HTTP/1.1 429 Too Many Requests Content-Type: text/html Retry-After: 3600 Too Many Requests I only allow 50 requests per hour to this Web site per logged in user. Try again soon.
ASP.NET Core 實現限流策略
身為一位不專業的工程師,上面介紹這麼多之後當然也要介紹在 ASP.NET 好用的限速策略 Library 其中比較推薦的是 AspNetCoreRateLimit 套件,使用與設定上相當簡單,也可以根據不同情境像是 Request IP 或是 Client ID 進行限流的策略,Github wiki 介紹頁面如下
以上若有問題歡迎一起討論,或是有錯誤的地方也請高手大大們給予指導予糾正,謝謝
參考
Rate limiting
Scaling your API with rate limiters
High-performance rate limiting
An alternative approach to rate limiting
Leaky bucket
Rate limit scheme of gateway
流量调整和限流技术
rate limiting 之 leaky bucket
想通关「限流」?只要这一篇
0 意見:
張貼留言