System Design Interview · 第 4 章Triton 覆蓋度:🟢 高Triton 線
Design A Rate Limiter
門口該放幾個人進來
原書把 Rate Limiter 當成「一個放在 Redis 上的計數器」。Triton 在線上搶票、手遊尖峰流量裡踩過的結論是:每個 request 都去問 Redis,Redis 會先死。這份簡報先把原書講白話,再看 Triton 哪裡不同意。
給文組
全程只用一家牛肉麵店,一階一階爬 11 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
最後一頁列出所有引述的出處檔案(materials/core)和原書段落對照。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📝 上課筆記
先用生活理解為什麼要限流
一家牛肉麵店,門外排了一千人
老闆會把一千人全放進去嗎?不會。店裡只有 20 個位子,全放進去的結果是所有人都吃不到。
「請跟那些百年牛肉麵老店老闆說,把門外排隊的客人全放進去,看看老闆砍不砍你~讓一千人全進一家牛肉麵小店,最終只會所有人都沒東西吃。」🗣️ Triton 本人說 051-concurrency.pdf.md · 「Rate-limiting」那頁
Rate Limiter 就是門口那個保全:超過店能消化的量,就請客人等一下,或直接說「今天客滿」。
學習地圖本章的概念階梯
今天爬 11 階。每一階只用前面講過的東西。
- 1request一張點單
- 2QPS每秒幾張單
- 3承受上限廚房煮得完嗎
- 4429「客滿」的牌子
- 5middleware保全站門口
- 6counter按壓計數器
- 7token bucket號碼牌筒
- 8Redis共用的白板
- 9race condition同時寫白板
- 10hotspot擠爆同一支電話
- 11local buffering一次拿一疊牌
第 1–4 階 · 一張點單進到廚房
要回答:為什麼不能全部放進來?
第 5–7 階 · 保全站哪、怎麼數
要回答:原書的五種數法差在哪?
第 8–9 階 · 好幾個門口
要回答:很多保全怎麼共用一個數字?
第 10–11 階 · Triton 的修法
要回答:白板自己被擠爆了怎麼辦?
全程只用一家店:老王牛肉麵(虛構)
每爬 2–4 階,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · request懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
用外送 app 點一碗麵,送出去的是什麼?
① 先想像
你在外送 app 按「下單」。手機把一張點單,送到老王店裡的電腦。
你猜猜看:你手滑連按「下單」10 次,店裡收到幾張點單?
每按一次就送出一張。店裡分不出你是真的要 10 碗,還是手滑。右邊按「連按 10 次」看看。
③ 這叫做 request、API
request:送出去的一張點單。API:店家公開的點餐窗口,例如 POST /order。
④ 跟這章的關係
Rate limiter 管的,就是 request 一張一張進來的速度。
② 動手玩:送出點單
延伸基礎第 2 階 · QPS懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
「店裡很忙」要怎麼用數字說?
① 先想像
下午兩點很閒。中午十二點一到,點單像雪片一樣飛來。
你猜猜看:老王一天收到 8,640 張點單,平均每秒幾張?
一天有 86,400 秒,8,640 ÷ 86,400 = 0.1。可是單子都擠在中午,尖峰那一秒可能有 8 張。
③ 這叫做 QPS
QPS(queries per second):每秒進來幾個 request。中文常說「流量」。
④ 跟這章的關係
限流的規則都寫成「每秒最多幾個」。要看的是尖峰,不是平均。
② 動手玩:同一家店,三個時段
延伸基礎第 3 階 · 承受上限懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
點單來得比廚房快,會發生什麼事?
① 先想像
廚房一秒做得出幾碗是固定的。單子來得再快,廚師也不會變快。
你猜猜看:廚房每秒做 5 碗,每秒來 8 張單。10 秒後有幾張單在排隊?
每秒多出 3 張做不完,10 秒累積 30 張。只要來得比做得快,隊伍只會越來越長。
③ 這叫做 server、database
server:真正做事的電腦,就是廚房。database:記錢和庫存的帳本,最慢、最不能錯。
④ 跟這章的關係
Rate limiter 就是替它們擋人的保全。上限要叫一群假客人來實際試出來,不是用猜的。
② 動手玩:廚房每秒固定做 5 碗
延伸基礎第 4 階 · 429懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
擋下客人時,要回他一句什麼?
① 先想像
點了單,店家一定要回你一句話:「收到」、「你點太多次了」、「廚房忙不過來」。
你猜猜看:一分鐘內按了 10 次下單被擋下,app 收到哪個號碼?
429 的意思就是「你送太多次了」。200 是成功,404 是找不到這個窗口。
③ 這叫做 HTTP、status code
HTTP:網路上大家約好的點單和回覆格式。status code:回覆單上的三位數號碼。
④ 跟這章的關係
Rate limiter 擋人時回 429 Too Many Requests。這個號碼整章都會出現。
② 動手玩:三種情況,三種回覆
到這裡你已經會了小結 1 / 4
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
到這裡你已經會了:為什麼不能全部放進來
- 每一張點單是一個 request,從客人的 app 送到店家的點餐窗口(API)。
- 每秒進來幾張叫 QPS。系統是在尖峰那一秒倒的,不是平均。
- 廚房(server)和帳本(database)有上限。超過就請客人等,或回 429。
下一階要解決的問題
保全要站在哪裡、怎麼數人?先看原書在面試一開始問了什麼。
原書 Step 1釐清需求
面試一開始:先問清楚要做哪一種 rate limiter
這一步要解決的問題擋誰、擋多少、在哪裡擋?沒問清楚就開始畫圖,畫錯的機率很高。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| Client-side 還是 server-side API rate limiter? | Server-side API |
| 依 IP、user ID,還是其他屬性來限制? | 要夠彈性,支援不同的規則組合 |
| 系統規模多大?新創還是大公司? | 要能處理大量 request |
| 會在分散式環境運作嗎? | 會 |
| 獨立服務,還是寫在應用程式裡? | 你決定 |
| 被限制的使用者要通知嗎? | 要 |
白話:client=客人那一端(手機 app);IP=網路上的門牌號碼;user ID=會員編號;分散式=好幾台電腦一起做。
📖 原書 為什麼要限流
- 擋 DoS(有人灌爆流量):原書舉 Twitter 每 3 小時最多 300 則推文、Google Docs API 每位使用者每 60 秒 300 次讀取
- 省錢:信用查核、付款、健康紀錄這類按次計費的第三方 API
- 防過載:擋掉 bot 或使用者誤用造成的多餘流量
📖 原書 需求清單
- 準確限制過量的 request 🗣️ Triton 不同意,見第 35 頁
- 低延遲:不能拖慢 HTTP 回應時間
- 盡量少用記憶體
- 分散式:多台 server、多個 process 共用
- 例外處理:被限制時給使用者清楚的訊息
- 高容錯:rate limiter 出問題(例如 cache server 掛了)不能拖垮整個系統
白話:cache server=放常用資料、讀得很快的那台機器(第 21 頁細講);process=電腦上跑著的一個程式。
延伸基礎第 5 階 · middleware懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
保全該站在廚房裡,還是門口?
① 先想像
10 位客人上門,只能放 5 位。保全可以站在廚房裡邊煮邊趕人,也可以站在門口。
你猜猜看:保全站在門口時,廚師要應付幾位客人?
被擋的 5 位在門口就回家了,廚師只看到放進來的 5 位。保全站在廚房裡,廚師就得一個一個停下來看 10 位。
③ 這叫做 middleware、API gateway
middleware:夾在客人和廚房中間、專做一件事的關卡。API gateway:雲端廠商賣的現成大門,內建保全。
④ 跟這章的關係
原書說 rate limiter 可以放在 server 裡,也可以做成 middleware(下兩頁)。
② 動手玩:保全站哪裡?
原書 Step 2保全要站在哪裡
Rate Limiter 放在 client、server,還是中間的 middleware?
這一步要解決的問題保全站哪裡,才擋得住、又不拖累廚房?
📖 原書 Client 端不可靠:request 很容易被偽造,client 的程式也不歸我們管。所以放在 server 端,或做成獨立的 rate limiter middleware。
📖 原書 怎麼選位置
- 看現有技術堆疊:語言、cache 服務能不能有效率地做
- 想完全掌控演算法 → 自己做;用第三方 gateway,選擇有限
- 已有 microservice + API gateway → 加在 gateway
- 人力不夠 → 買商用 API gateway
白話:microservice=把一個大系統拆成很多小服務,各自一扇門。
🗣️ Triton 補充 不是選一個位置,是每一層都要
- 「每一層都需要 rate-limiting:Load balancer、App. Server、Caching、Database。越早擋住過多的流量,就越能保護其後方系統。」051
- 「Per-IP limiting 請找 cloudflare 之類的供應商,別自己來。」059
- 「nginx 的 ratelimiting 是以 API 為單位的,這其實對一般系統很夠用了,沒事別作死。」087
在最外層擋掉,後面三層連看都不用看。
白話:CDN=最外面、離客人最近的接待處(Cloudflare 是賣這個的公司);load balancer(LB)=帶位員,把客人分到不同的廚房,nginx 是常見的一種;App server=廚房;DB=帳本。
原書 Step 2Figure 1–3
原書怎麼畫 rate limiter 的位置
這一步要解決的問題同一個保全,有哪幾種站法?原書用三張圖比較。
📖 原書 Figure 1:client 送 HTTP request,rate limiter 放在 API server 那一側(保全站在廚房裡)。
📖 原書 Figure 2:做成獨立的 rate limiter middleware,所有 request 先經過它(保全站在門口)。
📖 原書 Figure 3:API 每秒允許 2 個 request。一秒內來 3 個,前兩個轉給 API servers,第三個被擋下,回 429: Too many requests。雲端的 API gateway 就是內建這個功能的 middleware。
原書也說 client 端不可靠,所以三張圖都沒有把 rate limiter 放在 client。
延伸基礎第 6 階 · counter懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
保全手上的按壓計數器
① 先想像
保全手上一個計數器,每放一人按一下。規則:每分鐘最多 5 人,整點分鐘一到就歸零。
你猜猜看:12:00:50 已經按到 5,12:00:59 又來一位,放不放?
這一分鐘的 5 個名額用完了。再等一秒,計數器歸零,他就能進。
③ 這叫做 counter、window
counter:計數器,記這段時間放了幾個。window:多久歸零一次,例如每分鐘。
④ 跟這章的關係
這就是原書最簡單的 fixed window counter。它有個漏洞,第 16 頁揭曉。
② 動手玩:每分鐘最多 5 人
延伸基礎 · 動手玩第 7 階 · token bucket懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
桶子、號碼牌、和來拿牌的人
① 先想像
門口放一個號碼牌筒,最多 20 張,每秒自動補 10 張。拿到牌才能進門。
你猜猜看:筒裡是滿的 20 張,突然來 40 人,大概幾人能馬上進?
牌只有 20 張,先到的 20 人拿走;其他人要等補牌,或被擋。右邊按「突然來 40 人」驗證。
③ 這叫做 token bucket
token:號碼牌。bucket:裝牌的筒。筒多大叫 bucket size,多快補牌叫 refill rate。
④ 跟這章的關係
原書第一個介紹它。Triton 說高手和路人甲用的其實都是它(下一頁)。
② 動手玩:調桶子大小和補牌速度
原書 Step 2五種演算法
保全數人的五種方法
這一步要解決的問題計數器、號碼牌之外還有哪些數法?各自犧牲了什麼?
🗣️ Triton
「高手和路人甲,Ratelimiting 時其實都是 tokenBucket(和他的變種……)。但是最終系統效能(和是否真的以預期一樣運作),就是差了有沒有對 Rule QPS 作一次 sorting。」101
「對 Rule QPS 作 sorting」是什麼,第 38 頁講。
原書 Step 2Fixed window 的漏洞 · Sliding window log
每分鐘最多 5 個,為什麼會放進 10 個?
這一步要解決的問題計數器整點歸零,交界的那一分鐘會被鑽漏洞。怎麼補?
📖 原書 Figure 9 Fixed window counter
你猜猜看:每個整點分鐘都沒超過 5 個,有沒有某一分鐘放進了 10 個?
2:00:30–2:01:30 這一分鐘橫跨兩個視窗:後半 5 個 + 前半 5 個 = 10 個。拖下面的滑桿看看。
📖 原書 Figure 10 Sliding window log
補法:把每個人進門的時間都記下來。上限每分鐘 2 個,逐步按:
缺點:被拒絕的時間戳也留在 log 裡,很耗記憶體。原書說時間戳通常放在 Redis 的 sorted set(一種自動照時間排好的清單)。
🗣️ Triton「Sorted Set should be avoided at all cost」089
原書 Step 2Sliding window counter · 動手算
用上一分鐘的數字,估現在這一分鐘
這一步要解決的問題記下每個時間太耗記憶體。能不能只記兩個數字,又不被鑽漏洞?
📖 原書 Figure 11 互動版
📖 原書 公式:這一分鐘的數量 + 上一分鐘的數量 × 重疊比例
原書的例子:上限 7、上一分鐘 5 個、這一分鐘 3 個、現在在 30% 的位置 → 3 + 5 × 0.7 = 6.5,取整 6,放行。再來一個就到上限。
優點 / 缺點
- ✓ 用前一個視窗的平均速率,抹平尖峰
- ✓ 記憶體省
- ✗ 只適合不那麼嚴格的回溯視窗:它假設上一分鐘的 request 是平均分布的
- 原書引用 Cloudflare 的實驗:4 億個 request 裡只有 0.003% 被誤放或誤擋
原書 Step 2Token bucket · Figure 4、6
原書的 token bucket:補牌、溢出、四個時間點
這一步要解決的問題號碼牌筒實際怎麼運作?一個人要幾個筒?
📖 原書 要幾個桶?
- 每個 endpoint(API 窗口)通常各一個桶:每秒發 1 篇文、每天加 150 個好友、每秒按 5 個讚 → 每人 3 個桶
- 依 IP 限流 → 每個 IP 一個桶;全站每秒最多 10,000 → 一個所有人共用的 global bucket
- 缺點:兩個參數「不容易調好」
Triton 補充桶子該多大,原書沒說
桶子大小不是隨便填的
你猜猜看:老王的號碼牌筒,該放幾張?
牌比廚房吃得下的多,放進來的人還是吃不到。Triton 的答案在下面。
📖 原書 兩個參數
原書列出 bucket size 和 refill rate,說「用幾個桶子取決於需求」,但沒有說這兩個數字從哪來。
🗣️ Triton 本人說 看後面那台機器
「Token Bucket 的 Bucket size 的上限,是取決於:『如果你的 meowhub 之前完全閒置,那麼現在可以瞬間放多少個工作進來?』(假設 meowhub RESTful API 能同時處理 200 個 request,那麼 ratelimitor 的 Bucket size 就絕對不應該超過 200)」
「所以,如果你加開 AS / 加大 DB 機器,你的 bucket size 也應該相對地改動才對。」
「現實中的 ratelimitor,其流速很可能不是固定不變的……如果 HTTP request 的 latency 變大,或是你的 server CPU 變高,那麼你很可能需要降低你的 ratelimitor flow rate。」
142-喵談rate limit.md
文組翻譯
牌筒大小 = 廚房一口氣煮得下幾碗;補牌速度 = 廚房每秒出幾碗。規則要從廚房的能力反推。廚房今天手慢,保全就要放慢。
白話:AS=App server(廚房);latency=等多久才有回應;CPU=電腦的大腦,越忙越高。
Leaky bucket 的 buffer 也一樣
「你的 leaky bucket 的 buffer 上限,應該不能讓排隊時間過長,讓 items 失效了。」排太久的人早就走了,你還替他煮麵,是浪費。142 · 051
到這裡你已經會了小結 2 / 4
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
到這裡你已經會了:保全站哪、怎麼數
- 保全站在門口(middleware),被擋的人連廚房都碰不到。Triton:每一層都要有保全。
- 最簡單的數法是計數器(counter)整點歸零;交界的一分鐘會被鑽漏洞。
- 主流是號碼牌筒(token bucket)。筒多大、補多快,要從廚房的能力反推。
下一階要解決的問題
老王開了好幾個門口、好幾個保全。計數器要放在哪裡,大家才數得到同一個數字?
延伸基礎第 8 階 · Redis懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
開了三個門口,計數器要放哪?
① 先想像
老王開了三個門,每個門一位保全,各拿各的計數器。規則是全店每分鐘最多 5 人。
你猜猜看:三位保全各放了 2 人,都覺得「沒超過」。全店放了幾人?
2 + 2 + 2 = 6,超過了,但沒有人知道。所以要一塊大家都看得到的白板。
③ 這叫做 Redis、cache
Redis:放在記憶體裡的共用白板,大家讀寫都很快。cache:放在手邊的小抄,拿得快,但正本在 database。
④ 跟這章的關係
原書把計數器放在 Redis(下一頁)。Triton 之後會問:每位客人都去看白板,白板受得了嗎?
② 動手玩:全店每分鐘最多 5 人
原書 Step 2–3高階架構
原書的做法:每個 request 都去問 Redis
這一步要解決的問題好幾台機器要共用同一個計數器,放哪裡才夠快?
📖 原書 「使用資料庫並非好主意,因為磁碟存取速度較慢」,所以計數器放 Redis。
- client 送 request 到 rate limiter middleware
- middleware 從 Redis 對應的 bucket 讀計數器,檢查是否到上限
- 沒超過就 +1 寫回 Redis,放行
📖 原書 用兩個指令:INCR 把計數器 +1;EXPIRE 設定逾時,時間到計數器自動刪除。超過上限就拒絕。
文組版:每個客人進門前,保全都要打電話問總部「現在幾個人了?」,總部記一筆。
每一顆點是一個 request:先到 middleware,每一個都要去 Redis 讀寫計數器,才轉給 API servers。
原書 Step 3規則、HTTP headers、詳細設計
規則寫在設定檔,結果寫在 HTTP header
這一步要解決的問題規則寫在哪裡才好改?被擋的客人怎麼知道還要等多久?
📖 原書 規則的例子來自 Lyft 開源的 ratelimit,寫成設定檔存在磁碟上:
domain: messaging
descriptors:
- key: message_type
value: marketing
rate_limit:
unit: day
requests_per_unit: 5
行銷訊息每天最多 5 則。
domain: auth
descriptors:
- key: auth_type
value: login
rate_limit:
unit: minute
requests_per_unit: 5
每分鐘最多登入 5 次。
動手試:用上面的 login 規則登入
白話:HTTP header=回覆單最上面的幾行小標籤,寫著「上限幾次、還剩幾次、要等幾秒」。
📖 原書 詳細設計的流程
- 規則存在磁碟;worker(背景小幫手程式)定期把規則拉進 cache
- request 先到 rate limiter middleware
- middleware 從 cache 讀規則,從 Redis 讀計數器和上一次 request 的時間戳
- 沒超過 → 轉給 API server;超過 → 回 429,request 丟掉或轉進 queue(排隊區)
原書 Step 3Detailed design · Figure 13
原書的詳細設計圖
這一步要解決的問題把前面的零件組起來,一個 request 會走哪幾條路?按按鈕一條一條看。
白話:message queue=讓工作先排隊的號碼機,之後再一件一件慢慢處理。
原書 Step 3超過上限的 request 怎麼辦
被擋下來的訂單,要先排隊等一下嗎?
📖 原書 回 429,有時排進 queue
被限制的 request 回 429。「依使用情境,我們可能會把被限制的 request 排進 queue 稍後處理。例如部分訂單因系統過載被限制,我們可能保留這些訂單稍後處理。」
你猜猜看:被擋的訂單排在廚房(app server)自己的記憶體裡。尖峰一直來,會怎樣?
排隊的工作也要佔記憶體和連線。Triton 親身經歷過這種連環當機。
🗣️ Triton 本人說 等待不能太長,排隊也要錢
「每一層的 Ratelimiting 都不應該有太長的等候時間,因為用戶會等不了乾脆 <F5>。超過等待上限的,請直接回 HTTP 503。另外,等待中的工作,會持續佔用系統資源:TCP/IP connection、Main Memory、CPU Thread。」051
「打算以 C# 在 application server 上建立 task queue 的人……他們的 task queue 會不停變長,最後引發 application server 不夠 RAM 當機。然後因為一台 application server 當機,剩下的伺服機更忙而相繼當機。最終整個系統當得什麼也沒剩下 total outage。以上本人親人經歷。」126 · 補充
文組翻譯:客滿請客人在門口等可以,但隊伍不能無限長。排了 30 分鐘的客人早就走了,你還幫他留位子,是浪費;隊伍塞滿騎樓,連隔壁店都做不了生意。要排隊,就放在真正的 MQ(message queue)裡,而且要有上限。
延伸基礎第 9 階 · race condition懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
兩個保全同時看白板
① 先想像
白板上寫 3。保全 A 和 B 同時抬頭看到 3,各放一人,各自把 3 擦掉、寫上 4。
你猜猜看:白板最後寫幾?實際進了幾人?
兩人都寫 4,少算了一個人。人數越多、越常同時發生,白板就越不準。右邊自己排順序試試。
③ 這叫做 race condition、Lua script
race condition:兩人同時讀再各自寫回,有一筆被蓋掉。Lua script:把「讀+寫」打包給 Redis 一口氣做完,中間沒人能插隊。
④ 跟這章的關係
原書 Figure 14 就是這件事(下一頁)。
② 動手玩:你來決定誰先動
原書 Step 3分散式環境的兩個挑戰
一台變多台之後,原書遇到的兩個問題
這一步要解決的問題好幾個保全、好幾塊白板,數字怎麼不打架?
📖 原書 Figure 14 問題一:Race condition
流程是「讀計數器 → 檢查 +1 有沒有超過 → 寫回 +1」。兩個 request 同時讀,就會出事:
原書:用 lock(一次只准一人動白板)最直接,但「會顯著拖慢系統」。常見兩種解法:Lua script、Redis sorted set。
📖 原書 問題二:同步
- 不同步的話,rate limiter 1 不知道 client 2 的任何事
- Sticky session:原書說「不建議,不具擴展性也不夠彈性」;答案是集中式的 Redis
白話:stateless=門口不記客人,誰走哪個門都一樣;sticky session=同一位客人永遠只准走同一個門。
原書 Step 3Performance optimization · Figure 17
離使用者近一點:multi-data center
這一步要解決的問題客人在世界各地,離店太遠的人每一次都要等很久。
📖 原書 效能優化
- Multi-data center:離 data center 遠的使用者延遲高。原書舉 Cloudflare 在 2020/5/20 有 194 個 edge server,流量自動導到最近的一台
- 各地之間用 eventual consistency 同步資料
白話:data center=放一大堆電腦的機房;edge server=開在客人家附近的小分店;eventual consistency=各分店先各記各的,過一陣子再對帳,短時間內數字可能不一樣。
🗣️ Triton 多個 data center 是誰的需求?
「Uber 會使用 MySQL,很大的理由是其全球性業務和分散在多個地區的 database server。但是,對一般中小型公司來說,很多時 Master-Slave 是在同一 datacenter 內,而且資料可靠度比效能更加重要。」🗣️ Triton 本人說 136-喵談 pg mysql 的 replication.md
🔭 推論 這段是 Triton 談 DB replication,不是談 rate limiter。套過來:跨 data center 同步限流狀態是全球性業務才需要的成本;多數公司的服務在同一個 region,per-IP 這種邊緣限流交給 CDN/Cloudflare 就好(第 11 頁)。
到這裡你已經會了小結 3 / 4
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
到這裡你已經會了:原書的完整設計
- 好幾個保全要數同一個數字,就放在共用白板 Redis:讀寫快,放在記憶體裡。
- 兩人同時讀再寫回會少算(race condition),原書用 Lua script 一口氣做完。
- 原書的流程:每個 request 都去 Redis 讀寫一次,超過就回 429、丟掉或排隊。
下一階要解決的問題
全台一千個保全,每位客人都打電話問同一塊白板。白板自己受得了嗎?接下來是 Triton 的看法。
延伸基礎第 10 階 · hotspot懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
開了四支總機,為什麼還是只有一支被打爆?
① 先想像
白板改成總機,四支電話分工:每一家店的帳本,只放在其中一支。全台的保全都打來問老王這家店。
你猜猜看:尖峰時,另外三支總機在做什麼?
老王的帳本只在一支電話那裡,別支幫不上忙。多開幾支,只對「很多家店」有用。
③ 這叫做 cluster、hotspot
cluster:好幾台機器組成一隊分工。hotspot:大家都擠向同一台,只有它被打爆。
④ 跟這章的關係
Rate limiter 的計數器,就是那一本人人都要翻的帳本。
② 動手玩:同樣的來電量,兩種情況
Triton 不同意直球
❌ 原書 每個 request 問一次 Redis
你猜猜看:原書每個 request 都去 Redis 讀寫計數器。有人故意灌爆流量(DDoS),誰先倒?
保全要先問 Redis 才知道擋不擋,所以每一個假點單都會打到 Redis。廚房還沒事,白板先倒。
為什麼會死
- 流量 10 萬,Redis 就要吃 10 萬次。本來要保護別人,自己先被打爆。
- 同一個 key 只住一台,cluster 再大也沒用:就是上一頁的 hotspot。
- Redis 一次只做一件事(單執行緒),sorted set 又更慢。Triton:「Sorted Set should be avoided at all cost」089
「Performing redis call per request for ratelimiting is horribly bad idea — Your redis will fail during DDoS.」
「Be careful for hotspot in redis cluster.」🗣️ Triton 本人說 089-redis-ratelimit.pdf.md · Lessons learnt
「同一份的資料,如果你需要維持 strong consistency,最終你的 Write 是沒法 distributed,讓你的系統出現 hotspot 的……存有這一個用作 rate-limiting 資料結構的 redis-node 肯定會成為 hot-spot,最後炸掉當機。」🗣️ Triton 本人說 126-喵談 Keep it simple, stupid.md · 關鍵點 1
「如果每一個 request 都要問 redis 一下來決定是否放行,那麼系統流量就大約是 C10K 囉。(我們實戰數據)」🗣️ Triton 本人說 129-喵談 captcha 能擋高流量?.md
文組翻譯:每位客人都要打電話問同一位總機。總機先掛,所有保全都不知道該不該放人。要保護的是廚房,先死的卻是總機。
延伸基礎第 11 階 · local buffering懂的人可以跳過
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
一次拿一疊號碼牌放口袋
① 先想像
保全不要每位客人都打電話。一次跟總機要 10 張牌放口袋,發完再打。
你猜猜看:3 位保全、30 位客人,每次拿 10 張。總機要接幾通?
每位保全接 10 位客人,剛好打 1 通拿 10 張。3 位保全共 3 通,是原本 30 通的十分之一。
③ 這叫做 local buffering
local buffering:每台機器在自己身上(local)先存一小疊牌(buffer),用完再拿。
④ 跟這章的關係
這就是 Triton 的解法(下一頁)。代價是數字不再精準,Triton 說沒關係(第 35 頁)。
② 動手玩:3 位保全
Triton 的解法Local buffering
✅ Triton 一次拿一疊票放口袋
你猜猜看:每次拿 5 張。流量從每秒 1 萬變成 10 萬,Redis 被問的次數會?
放行的總數被限流上限卡住,拿票次數只跟上限有關;超過的人在本地就被擋。右邊把流量拉到 10 萬驗證。
「Application server 應該每次不是拿一個 token from redis,而是一次拿上 100……然後再把剩下來的 99 個存到 local memory 未來使用。這種 local buffering 雖然讓系統的 ratelimiting 沒法精準地停在每秒 900,但是現在就不止有 redis 上的一個資料結構而是同一時間每台 Application server 也有其 buffer,不會引發 hotspot。」🗣️ Triton 本人說 126 · 關鍵點 2
「The redis call MUST be independent of QPS.」這句是 089 整份投影片的目標。
「如果你系統有 80 台伺服,你的 redis max QPS 便是 80 + (100 / 5),跟系統流量沒關係。」🗣️ Triton 本人說 087-redis-2019.pdf.md · 案例 1
Triton 的解法拿不到票就先別問了
拿不到 token 的那 500ms,本地直接拒絕
你猜猜看:保全打給總機,總機說「沒牌了」。0.1 秒後又來一位客人,保全該?
剛剛才說沒牌,0.1 秒後多半也沒有。一直打,總機在最忙的時候被打得更兇。
「如果 Application server 從 redis 拿不到 token,未來 random(500ms) 時間內 Application server 應該直接回傳 http 419 / 503。配合第 2 點,在 ratelimiting 1000 下,redis 的每秒流量只會是 Application server 總數 + 1000 / 100。這樣子的 redis 才不會炸掉的。」🗣️ Triton 本人說 126 · 關鍵點 3
「如果 Application Server 一個 token 也拿不到,便乾脆拒絕所有同類 Request 1 秒。」🗣️ Triton 本人說 087 · 案例 1
文組翻譯:總機說「沒了」,接下來半秒保全不再打電話,直接跟來的人說客滿。總機得以喘口氣。
📝 上課筆記 2026 Q1 的 Q&A 筆記裡,Triton 的口述版本是「if redis return no token, mark NO_TOKEN flag 500ms in local AS;在接下來的 500ms 跟使用者說 too many request 就可以保護 redis」。007 · Roy 的上課筆記
Triton 不同意情境差異
原書擔心的「同步」,Triton 的看法是:不要精準
📖 原書 計數要準
需求第一條是「準確限制過量的 request」。所以 race condition 要用 Lua script 解、多台要靠集中式 Redis、多個 data center 要 eventual consistency。
這些都建立在同一個前提:每個 request 都要碰那一份集中的計數器。
你猜猜看:限流設每秒 900,口袋裡的牌讓實際放了 920。會怎樣?
保全只是讓廚房不要被擠爆。真正不能錯的帳,是 database 用交易(transaction)守的。
🗣️ Triton 本人說 差幾十個無所謂
「假設資料庫每秒寫入上限是 1000,那麼我們大約定下希望 900 左右的 rate-limiting 吧,而最終每秒是 920 還是 880,其實沒太關係的。(因為真正的交易在資料庫,不在這裡)」126 · 關鍵點 2
「In the world of >10K QPS, consistency is usually sacrificed for performance.」089 · More thought
保全數錯 2% 沒關係。放掉精準,hotspot 就不存在了。
Triton 自己也踩過 optimistic lock 的雷
089 的 v1 用 optimistic lock(先不鎖,寫回時發現被改過就重來)同步各台的 bloomfilter(記「見過誰」的省空間表),結果「The sync conflict increase exponential with app. server number」。v1.1:衝突就放棄這次寫入,反正每秒會再同步。「Optimistic lock is suitable if the conflict rate is very low.」
原書 Step 3–4監控
上線之後:規則太鬆、太緊,怎麼知道?
這一步要解決的問題規則上線了,怎麼知道它真的擋對了人?
📖 原書 Monitoring
要蒐集數據確認兩件事:演算法有效、規則有效。
- 規則太嚴,很多正常 request 被擋 → 放寬一點
- Flash sale(限時搶購)時突然爆量,限流失效 → 換成支援 burst(瞬間爆量)的演算法,例如 token bucket
🗣️ Triton 流速該跟著廚房變
「如果 HTTP request 的 latency 變大,或是你的 server CPU 變高,那麼你很可能需要降低你的 ratelimitor flow rate。」142
原書是看完數據後由人手動調;Triton 講的是流速本來就該跟著後端的狀態變。
原書 Step 4Wrap up · 收尾的討論點
面試最後可以多聊的四件事
這一步要解決的問題主體設計完,面試官常問:還有哪些變化和配套?
📖 原書 Hard vs soft
- Hard:request 數絕對不能超過門檻
- Soft:短時間內可以超過
📖 原書 不同層的限流
本章只談 application level(HTTP,OSI 第 7 層)。也可以在第 3 層用 iptables 依 IP 限流。
白話:OSI 七層=把網路傳輸從「電線」到「app」分成七層:Physical、Data link、Network、Transport、Session、Presentation、Application。iptables=Linux 內建的防火牆。
📖 原書 Client 端怎麼避免被限流
- 用 client cache,避免一直呼叫 API
- 了解限制,不要短時間送太多 request
- 寫好例外處理,讓 client 能優雅地恢復
- 重試邏輯要有足夠的 back off(等久一點再試)時間
🗣️ Triton 碰到 flash sale
Triton 的處方不是換演算法,而是 local buffering 避開 Redis hotspot(第 33–34 頁),再加上 CDN、connection pool 這些基本功。126
Triton 補充原書沒講到的細節
兩條規則、Captcha、和每一層的 max connection
多條規則:先扣哪一條?
你猜猜看:規則 1:每人每秒最多 1 次。規則 2:全部人合起來每秒最多 200 次。先扣哪條?
先扣全部人的,一個寫 bot 的人就能把 200 張牌吃光。
「先從比較小的 QPS 的 rule 開始扣掉!……如果是先從 rule2 開始扣掉,那麼如果用戶 A 現在寫了 bot,每秒發 300 個 Request 進來……Rule2 的 tokenBucket 卻會被同一個用戶 A 都吃光光,然後 endpoint XXX 所有用戶合起來的 QPS 便只剩下 1。」🗣️ 101
Captcha 不是 rate limiter
「這樣子在工程上不但解不了高流量的問題,而且還會帶來超高客戶仇恨值……今天的 AI 已經能破解掉大部份的 captcha……守規則的真正客戶反而貓毛也沒能搶到一條!」🗣️ 129
kktix、Amazon、PChome 都不這樣做。多一個 10 秒的步驟,客戶就去對手那邊了。
白話:captcha=「請點出所有紅綠燈」那種驗證。
基本功先做好
「你有測過資料庫的每秒流量上限,然後以此去正確設定資料庫的 max connection 嗎?還是吃到飽吃到當機為止?Application 上的 connection pool 有好好設定?……以上任何一個細節錯誤,就是你當機/performance bottleneck 的地方。」🗣️ 126
「除非你已經要面對 > C10K 人流,否則我不會建議你隨便套用一些花招。」129
白話:connection pool=事先開好、數量固定的幾條電話線;max connection=帳房最多同時接幾條線。
到這裡你已經會了小結 4 / 4
- request
- QPS
- 承受上限
- 429
- middleware
- counter
- token bucket
- Redis
- race condition
- hotspot
- local buffering
到這裡你已經會了:Triton 怎麼修
- 每個 request 都去問 Redis,計數器那一台會變成 hotspot,Redis 比廚房先倒。
- 改成一次拿一疊牌(local buffering),拿不到就本地拒絕 500ms:Redis 被問的次數跟流量無關。
- 代價是數字不精準。限流這層差 2% 沒關係,錢和庫存在 database 守。
11 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
不要每個人都跑去問總機,
先在門口拿一疊票。
原書對的地方
- 五種演算法的取捨,token bucket 是主流
- 放在 gateway / middleware,回 429 + X-Ratelimit headers
- 規則寫成設定檔(Lyft 格式)
- Race condition 的分析正確
Triton 不同意的地方
- 每個 request 一次 Redis 來回:Redis 先死
- 追求精準計數:不必要,而且製造 hotspot
- Sorted set:能不用就不用
- 被擋的 request 排隊:要有上限,別放在 AS 記憶體
Triton 的做法
- 一次拿 5–100 張 token 放本地
- 拿不到就本地拒絕 500ms
- 桶子大小從後端能力反推、壓測出來
- 每一層都限流,per-IP 交給 Cloudflare
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)
Triton 本人的講義 / 文章
- 089-redis-ratelimit.pdf.md — High Volume Ratelimiting with Redis(投影片):per-request Redis call、hotspot、bloomfilter 做 active user、optimistic lock 教訓、Sorted set 警告
- 126-喵談 Keep it simple, stupid.md — 關鍵點 1/2/3:strong consistency 的 write 無法 distributed、一次拿 100 token、拿不到就 500ms 拒絕
- 087-redis-2019.pdf.md — 案例 1 ratelimiting:nginx per-API 夠用、一次拿 5 個、80 + 100/5
- 142-喵談rate limit.md — token vs leaky bucket 的真正判準、bucket size ≤ 同時處理能力、流速應隨 latency/CPU 調整
- 101-其實C10K的架構….md — 多條規則先扣 QPS 小的
- 129-喵談 captcha 能擋高流量?.md — captcha 不是限流、per-request Redis ≈ C10K 上限
- 051-concurrency.pdf.md — 每一層都要 rate-limiting、牛肉麵店比喻、等待不能太長
- 059-ecom-system design.pdf.md — per-IP 找 Cloudflare、token bucket 只需一個 float + 20 行 lua
上課筆記(非本人原文):007-…triton_2026_Q1_.pdf.md — Roy 的 Q&A 筆記:local buffer +10 / redis −10、NO_TOKEN flag 500ms、load balancer 也要 rate limit。檔案後半貼了 ChatGPT 產生的程式碼,不引用。
原書對照
Alex Xu, System Design Interview Vol.1 Ch.4。Step 1 需求(第 9 頁)、Where to put 與 Figure 1–3(11–12)、Algorithms × 5 與 Figure 4–11(15–18)、High-level architecture 與 Figure 12(22)、Rules / HTTP headers / Detailed design / Exceeding the limit 與 Figure 13(23–25)、Distributed environment 與 Figure 14–16(27)、Performance optimization 與 Figure 17(28)、Monitoring 與 Wrap up(36–37)。17 張圖都依原書的圖說與描述重繪,不是原圖。sorted set 做法來自 ClassDojo 的 rolling rate limiter 文章;規則格式來自 Lyft ratelimit。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 11 階:request(4)、QPS(5)、承受上限(6)、429(7)、middleware(10)、counter(13)、token bucket(14)、Redis(21)、race condition(26)、hotspot(30)、local buffering(32);小結(8、20、29、39);名詞小卡(41)。老王牛肉麵是虛構的示範情境;QPS、總機上限等示意數字不是實測值。
一個可以直接問自己的問題
你的 rate limiter 每秒打 Redis 幾次?這個數字跟流量有關,還是跟伺服器台數有關?