網路限速的幾種方法

- 本文為內行人才知道的系統設計面試指南一書之閱讀筆記 -

關於網路限速

對於後端伺服器來說，防止大量請求突然湧入是保護伺服器的其中一個很重要的措施，除了避免突發大流量導致系統無法應付，也可以防止像 DDoS 此類讓伺服器癱瘓的攻擊行為。網路限速即是針對 API 的呼叫進行頻率上的限制來阻絕掉那些太頻繁的請求，通常會以 429 的狀態碼來回應。在實作面上一般會在一個 API 閘道裡放上限速的邏輯，搭配如 Redis 這種快取服務便可以應對分散式系統的限速需求，以下會介紹幾種常見的網路限速實作方法~

Token Bucket

Token Bucket 是一種簡單好理解的限速方法，在這個方法當中會有一個已經定義好容量的桶子，裡面裝滿了 Token，這個桶子會以固定的速率補充 Token，如果桶子滿了的話多的 Token 則會溢出來。

當有請求送進來的時候，系統就會去檢查這個桶子裡是否還有剩餘的 Token，如果有的話就消耗掉一個並且放行這個請求，反之則會直接丟棄請求 (回傳 429)。

這個方法會需要定義兩個參數，分別是桶子的容量以及Token 填入速度，而一個系統當中會需要用到幾個桶子會根據需求而有所不同，例如一個社群軟體對於讀取、搜尋的頻率可以放的比較寬一些，而發佈貼文可能就必須要限縮一點速度。另外理論上也需要針對不同的 IP 有著不同的桶子來管理，但如果系統的應對能力足夠大的時候，也可以將不同 IP 或不同類別甚至全部的請求放在同一個桶子來維護。

優點

• 實作簡單，且固定桶子的大小對於記憶體的消耗也較低

• 允許短時間內的爆炸流量，只要桶子內有足夠的 Token 就可以應付

缺點

• 對於兩個參數要如何調配可能會比較困難

• 針對不同 IP、API 類別等來分配桶子需要適當的配置

Leaking Bucket

Leaking Bucket 的做法和 Token Bucket 類似，不同的地方是它是以固定的速率來處理請求，通常它的 Bucket 會使用類似佇列 (queue) 的結構來維護，以符合 FIFO 的處理順序。當請求進來的時候會先檢查佇列是否還有空位，如果已經塞滿了就丟棄請求，還沒的話就把請求加入佇列等待被依序處理。這個方法也同樣會需要兩個參數，分別是桶子的容量以及請求流出的速度

優點

• 固定桶子的大小對於記憶體的消耗較低

• 適合需要穩定流出請求速度的應用類型

缺點

• 如果瞬間出現大量請求的話會塞滿佇列，後續新的請求的回應速度會受到影響

• 對於兩個參數要如何調配可能會比較困難

Fixed Window counter

Fixed Window counter 則是有別於前面兩種方法，以另一個角度來考慮限速。這個方法會將時間軸切分成長度相同的視窗，並且在每個視窗裡面設置一個計數器來使用，每個請求都會讓計數器 +1，超過計數器數量限制之後的請求會被丟棄，直到進入到下個視窗計數器歸零時才會重新接收新的請求，下面的示意圖是以每個視窗計數器限制為 3 的狀況。

優點

• 容易理解，且對於記憶體的要求也不高

• 單位時間內所能接收的請求數量是固定的，對於特點情境可能會適用

缺點

• 短時間內的瞬間流量可能會導致單位時間內的請求數量超過限制

• (下方的圖呈現了這種短暫超出限制的情形，以單位時間能接受 5 個請求為例，下圖在前後兩個視窗內都有符合最大請求數量的限制，但如果從中間來看的話這一個單位時間裡面卻出現了 10 個請求)

Sliding Window Blog

Sliding Window Blog 是將單位時間變為可動的視窗，它的特點是不管請求最後是被接收還是拒絕，都會將請求進入的時間點保留下來。當每次新的請求進來是會以當下的時間往前一個單位時間作為目前的視窗，並清除掉過時的記錄，最後檢查請求的數量有沒有超過限制來決定是否接收請求，下方的圖以 1 分鐘內 2 個請求的限制為例來演示這個方法的運作模式。

可以注意到 4 號的狀況，當 1:01:30 的請求進入時，此時的時間視窗是從 1:00:30 - 1:01:30，因此裡面的前兩筆記錄會因為過時而被移除，所以 1:01:30 的這個請求還是能夠在符合數量限制的狀況下被接收。

優點

• 實作出來的限速效果相當準確

• 不論在任何的單位時間視窗內，請求的數量都不會超過限制

缺點

• 對於記憶體的消耗量非常巨大

• 因為不論請求是否被接受，其時間戳都會被保存在記憶體裡直到過時

Sliding Window Counter

Sliding Window Counter 是結合了 Fixed Window Counter 和 Sliding Window Blog 所形成的一種方法，參考下面的圖為例，呈現了 Sliding Window Counter 其中一種實作的方式，它會根據當前的單位時間視窗內的請求數量和前一個單位時間視窗的請求數量結合時間佔比來進行滾動視窗內的請求數量估算，可以用以下的公式來表示：

$$\text{RequestCount}_{t} + \text{RequestCount}_{t-1}\times \text{WindowOverlapRatio}_{t-1}$$

對應到圖中的例子，在該滾動視窗內的請求數量可以被計算為：

$$2 + 4 \times 0.7 = 4.8$$

這邊可以利用無條件捨去或四捨五入等方法來得到最後的請求數量，並以此和設定的限制來比較決定是否接收最新的請求。

優點

• 對於記憶體的利用來說是有效率的

• 使用平前一個視窗的平均速度來計算可以減緩流量高峰的狀況

缺點

• 對於回溯視窗的限制並沒有非常嚴格，這種做法是假設前一個視窗的請求分布是均勻的

• 不過在 Cloudflare 所做的相關實驗裡發現這個方法的錯誤率比想像的還要低很多 (4 億次的請求裡錯誤率為 0.003%)