這禮拜繼續讀 <System Design Interview- An insider’s guide> 第四章。

Chapter 4: 設計 Rate Limiter

這章開始作者用實戰的方法帶大家了解，每一種不同的系統的特性是什麼、以及要設計這樣的元件可以怎麼去做思考。

首先第一個設計的元件就是 Rate Limiter (網路限速器、限流器)。如果面試時，被要求設計一個 rate limiter，你可以怎麼做？

所謂的 rate limiter簡單來說，就是一個可以限制 client 在指定時段內發送 request 數量的元件。比如：user 每秒可以發幾則貼文、user 每天只能領幾次的獎勵。他的優點是可以防止 server overload, 進而優化資源分配、降低server成本、並避免 dos 攻擊。

第一步驟：瞭解問題，並確立設計的範圍

可以問的問題有：

哪一種 rate limiter: client side or server side?
- 這個問題屬於明知故問型的提問，因為 client side rate limiter 可控性不高、可靠性也不高。
是否要根據 ip, user_id etc 去追蹤 api request?
系統的規模大小？for 大公司 or 小新創?
系統是否需要運作於分散式環境？
這個 rate limiter 需要做成一個單獨的服務、或是實作於應用程式中？
是否需要通知受到限制的 user?

根據回答，可能可以匯總的系統需求如下：

必須要準確限制 request -> (：演算法選擇)
必須要盡可能使用少一點記憶體 -> (：演算法選擇)
因為系統運作於分散式環境，所以採用分散式做法：多 server 共用一個 rate limiter -> (：rate limiter 實作位置選擇)
others: 需要高容錯、異常處理

第二步驟：提出高階設計，並取得認可

這邊主要要思考兩點：(1) rate limiter 施作位置 (2) rate limiter 演算法選擇

1. rate limiter 施作位置

這邊主要考量的是：放置於api server, 或是施作於 api gateway（microservice 中的一個中介元件，用途廣泛，功能包含身份驗證、白名單etc）.

書中列出幾個可以拿出來討論的點：

目前公司是否已經使用微服務架構、並且此架構已用到 api gateway? 有的話，或許可以考慮直接施作於 api gateway.
所選用的演算法，是否可以於 api gateway中選用，或是需要自製於 server 端？

-> 2-1. 目前公司使用的程式語言，是否支援實作 server 端 rate limiter?

-> 2-2. 目前公司提供的時間、成本，是否支援開發 server 端 rate limiter?

2. rate limiter 演算法選擇

有五個比較常見的演算法如下：

(1) Token Bucket

步驟：有兩個控制變數，分別是 bucket 容量、token 填入速度。
- 每當一個 request 進來，系統檢查 bucket
  - 如果 token 數量足夠，則消耗一個 token 給該 request，並使 request 通過。
  - 如果 token 數量不足夠，則不使 request 通過。
- 固定一個時間之內 refill bucket
一個系統可以設計一或多個 bucket
- 多個 bucket 的狀況：要針對每一個 api 做比較嚴格的 rate limit
- 一個 bucket 的狀況：系統很鬆，每秒可以接收極大量的 total requests
優點：
- 容易實作
- bucket 大小固定、有限，因此有比較好的 memory usage
- 可以允許短時間內的流量爆炸：它不限定某個時間只能有幾個request, 只要 bucket 裡面還有refilled tokens, 就可以通過 request
缺點：
- 書中提到說要 tune 這兩個參數不是一件容易的事
應用該演算法的公司：Amazon, Stripe

(2) Leaking Bucket

步驟：有兩個控制變數，分別是 queue 容量、request 處理速度。
- 每當一個 request 進來，系統檢查 queue
  - 如果 queue not full, 便把 request 加入 queue
  - 如果 queue full, 便丟棄 request
- 固定一個 request process rate
優點：
- queue 大小固定、有限，因此有比較好的 memory usage
- request process rate 是固定速率，所以適合需要穩定 outflow rate 、不會有突然流量爆炸的狀況。
- (somehow 書中沒有提到這個作法是容易實作的)
缺點：
- 如果流量爆炸，新 request 處理效率會變很差
- 書中提到說要 tune 這兩個參數也不是一件容易的事
應用該演算法的公司：Shopify

(3) Fixed Window Counter

步驟：每個固定的 time slot (eg: 1分鐘、5分鐘) 有固定的 request capacity 與一個 counter
- 每當一個 request 進來，系統
  - counter ++
  - 如果 ++ 之後 capacity 超過，則丟棄 request
  - 如果 ++ 之後 capacity 未超過，則通過 request
- 重要特性（問題）：
  - 兩個 time slot request 如果恰恰好是 capacity 最大值（意即極高需求狀況），則中間切分點之 time slot(滾動視窗) 會允許了 capacity 兩倍的 request進來，導致超乎 loading 的需求被處理了。
優點：
- 容易實作
- request capacity 固定、有限，因此有比較好的 memory usage
- 可以被 Redis 支援
缺點：流量激增會有超過 loading 的需求被處理

(4) Sliding Window Log

這是一個有趣的演算法。

步驟：
- 每當一個 request 進來，系統
  - 將這個 request的 time stamp 加入日誌中
  - 檢查目前日誌中、「新 request 的一個 time slot」以前，是否還存有其他老request的 time stamps
    - 有則刪除
  - 檢查目前日誌中，time stamp capacity 是否超標
    - 無則 approve request
    - 有則 reject request
優點：
- 限速效果十分準確：很可以確保滾動的 time slot 也可以穩定的不超標
缺點：
- 必須要額外花很多的 memory 紀錄每一個 request 的 time stamp，不會因為 request 被丟棄而消失

(5) Sliding Window Counter

這是一個融合 Fixed Window Counter 和 Sliding Windoe Log 的做法

它主要的目的是解決 Fixed Window Counter 遇到的問題，透過施作一個「百分比公式」:

滾動視窗的 total request = 目前視窗 request + 前一視窗 request * 前一視窗佔滾動視窗的百分比。
優點：
- 不會讓滾動視窗突有超高流量出現
- 因此有比較好的 memory usage
缺點：限速效果不會到非常精確（不過也不會到非常不精確，根據 Cloudflare實驗結果錯誤率是 0.003% in 4b requests）

3. rate limiter 資料儲存地點

通常會把資料放在 cache: (1)存取速度快 (2)支援過期策略。

Redis 是一個常被施用的元件，如果使用 Fixed Window Counter，可以用到他的 INCR(counter ++)指令與 EXPIRE(使 counter 過期)指令。

第三步驟：深入設計

根據所設計的 rate limiter 架構，延伸的問題通常有以下兩者：

1. basic question: 如果超出 rate limit

solution: API 回傳

429 error response
X-Ratelimit-After

補充: rate limiter 常傳送的 HTTP headers

X-Ratelimit-Remaing: window 內剩餘的可用 request數
X-Ratelimit-Limit: 一個 window 總共可用的 request數
X-Ratelimit-After: 當獲得 429 error, 多久之後可以再次重新發送 request

2. advanced questions 1: 當分散式系統有並行的 request, 如何避免 race condition

solution:

Lock
Lua script
Redis ordered data structure

3. advanced questions 2: 當分散式系統有多個 rate limiters, 如何同步每個 rate limiter, 讓所有資料都存在於元件中，使 rate limiting可以正常運作？

solution:

Utilize Redis as centralized data storage

4. advanced questions others: 效能最佳化

solution:

地理位置上，設置多資料中心
使用 eventual consistency model 同步資料
監控 rate limiter表現，隨時思考演算法選擇的恰當性
rate limiter設置不同策略：硬限制、軟限制
不僅在 HTTP 第七層實作，也可以往底下去實作 rate limiter. eg: Ip Table rate limiter.

Conclusion

我覺得這章蠻有趣的，不僅初步認識與理解 rate limiter的實作概念，也知道要怎麼去討論一個 rate limiter 的設計方式。很好奇有哪些公司會選用 Sliding Window Log 這種很精細又高成本的算法的。除了算法的選擇上，如何做好 trade-off 不是一件容易的事情之外，要怎麼針對每個 follow up question 去提出適合的解決方法，比如說如何使用 Redis 解決 race condition 問題又是需要額外 survey的議題。