只有累積,沒有奇蹟

2022年5月1日 星期日

[Architecture] 架構設計 - 限流策略 Rate Limiting Strategies

前言
這一篇是紀錄閱讀 超大流量分佈式系統架構解決方案:人人都是架構師2.0 的讀書筆記,筆者在書中有介紹在面對大流量的請求洗禮時,常見的手段有以下幾種方式
  • 擴充
  • 靜態化
  • 限流
  • 緩存
  • 隊列
這篇文章是介紹上述方案中的限流方案章節筆記,在整理時內容加上自己理解的說明與圖片,其中若是自己有理解不正確的地方是錯誤的部分歡迎各位高手一同討論或給予指導


為什麼需要限流
大型電商網站主要技術挑戰可能來自短時間內客戶忽然的大流量與短時間內的高併發請求,像是之前大家在搶購的 Switch 動物之森主機(搶三次都沒搶到 怒),或是最近吵得很紅的 PS4 造型悠遊卡(搶不到again,怒怒),如果系統不對流量進行合理的管制,任意地讓所有的請求流量在短時間內衝擊系統,可能會導致一連串的問題發生,像是原本設定的 cache 機制因為超過負荷被撐爆、主機連線資源被耗盡,資料庫要處理大量的請求而造成回應時間變長,最後系統很有可能發生雪崩效應(Avalanche effect),造成服務的中斷。任何一個系統的容量都存在著上限,一旦用戶請求量過載超過上限,系統的吞吐量便會逐漸開始下降,流量管制的目的是保護系統,讓系統的負載壓力處於一個比較均衡的水位,有效的管理峰值的請求量。 從上圖可以得知,當處理大量的請求時前面可以使用 CDN (靜態資源),FrondEnd 或是 Backend 可以使用擴充的方式來承接更大的流量請求,但資料的異動最後還是會交由資料庫來進行處理,Database 數據庫的連線是一個非常昂貴且數量有限的底層資源,為了避免開發環境下連接數超過數據庫所能乘載的最大上限,合理的運用資料庫的連線池技術,確保系統在高併發時連接數不會超過資源的水位值(資源閥值)。

常見限流演算法
書中介紹常見的限流演算有令牌桶算法、漏桶算法以及計數器算法三種,以下就針對這三種作簡單介紹

令牌桶算法
令牌桶(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 意見:

張貼留言

Copyright © m@rcus 學習筆記 | Powered by Blogger

Design by Anders Noren | Blogger Theme by NewBloggerThemes.com