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 就是門口那個保全:超過店能消化的量,就請客人等一下,或直接說「今天客滿」。

0店內用餐中(上限 20)0門外排隊正常廚房狀態

學習地圖本章的概念階梯

今天爬 11 階。每一階只用前面講過的東西。

  1. 1request一張點單
  2. 2QPS每秒幾張單
  3. 3承受上限廚房煮得完嗎
  4. 4429「客滿」的牌子
  5. 5middleware保全站門口
  6. 6counter按壓計數器
  7. 7token bucket號碼牌筒
  8. 8Redis共用的白板
  9. 9race condition同時寫白板
  10. 10hotspot擠爆同一支電話
  11. 11local buffering一次拿一疊牌

第 1–4 階 · 一張點單進到廚房

要回答:為什麼不能全部放進來?

第 5–7 階 · 保全站哪、怎麼數

要回答:原書的五種數法差在哪?

第 8–9 階 · 好幾個門口

要回答:很多保全怎麼共用一個數字?

第 10–11 階 · Triton 的修法

要回答:白板自己被擠爆了怎麼辦?

全程只用一家店:老王牛肉麵(虛構)

客人的點單 = request廚房 = server門口保全 = rate limiter號碼牌 = token大家共用的白板 = Redis

每爬 2–4 階,有一頁「到這裡你已經會了」。

延伸基礎第 1 階 · request懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

用外送 app 點一碗麵,送出去的是什麼?

① 先想像

你在外送 app 按「下單」。手機把一張點單,送到老王店裡的電腦。

你猜猜看:你手滑連按「下單」10 次,店裡收到幾張點單?

③ 這叫做 request、API

request:送出去的一張點單。API:店家公開的點餐窗口,例如 POST /order。

④ 跟這章的關係

Rate limiter 管的,就是 request 一張一張進來的速度。

② 動手玩:送出點單


      
0店裡收到的點單(request)

延伸基礎第 2 階 · QPS懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

「店裡很忙」要怎麼用數字說?

① 先想像

下午兩點很閒。中午十二點一到,點單像雪片一樣飛來。

你猜猜看:老王一天收到 8,640 張點單,平均每秒幾張?

③ 這叫做 QPS

QPS(queries per second):每秒進來幾個 request。中文常說「流量」。

④ 跟這章的關係

限流的規則都寫成「每秒最多幾個」。要看的是尖峰,不是平均。

② 動手玩:同一家店,三個時段

—平均 QPS—尖峰 QPS(最忙那一秒)

延伸基礎第 3 階 · 承受上限懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

點單來得比廚房快,會發生什麼事?

① 先想像

廚房一秒做得出幾碗是固定的。單子來得再快,廚師也不會變快。

你猜猜看:廚房每秒做 5 碗,每秒來 8 張單。10 秒後有幾張單在排隊?

③ 這叫做 server、database

server:真正做事的電腦,就是廚房。database:記錢和庫存的帳本,最慢、最不能錯。

④ 跟這章的關係

Rate limiter 就是替它們擋人的保全。上限要叫一群假客人來實際試出來,不是用猜的。

② 動手玩:廚房每秒固定做 5 碗

3010 秒後還在排隊的單越積越多廚房狀態

延伸基礎第 4 階 · 429懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

擋下客人時,要回他一句什麼?

① 先想像

點了單,店家一定要回你一句話:「收到」、「你點太多次了」、「廚房忙不過來」。

你猜猜看:一分鐘內按了 10 次下單被擋下,app 收到哪個號碼?

③ 這叫做 HTTP、status code

HTTP:網路上大家約好的點單和回覆格式。status code:回覆單上的三位數號碼。

④ 跟這章的關係

Rate limiter 擋人時回 429 Too Many Requests。這個號碼整章都會出現。

② 動手玩:三種情況,三種回覆


      

到這裡你已經會了小結 1 / 4

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

到這裡你已經會了:為什麼不能全部放進來

下一階要解決的問題

保全要站在哪裡、怎麼數人?先看原書在面試一開始問了什麼。

原書 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 或使用者誤用造成的多餘流量

📖 原書 需求清單

  1. 準確限制過量的 request 🗣️ Triton 不同意,見第 35 頁
  2. 低延遲:不能拖慢 HTTP 回應時間
  3. 盡量少用記憶體
  4. 分散式:多台 server、多個 process 共用
  5. 例外處理:被限制時給使用者清楚的訊息
  6. 高容錯:rate limiter 出問題(例如 cache server 掛了)不能拖垮整個系統

白話:cache server=放常用資料、讀得很快的那台機器(第 21 頁細講);process=電腦上跑著的一個程式。

延伸基礎第 5 階 · middleware懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

保全該站在廚房裡,還是門口?

① 先想像

10 位客人上門,只能放 5 位。保全可以站在廚房裡邊煮邊趕人,也可以站在門口。

你猜猜看:保全站在門口時,廚師要應付幾位客人?

③ 這叫做 middleware、API gateway

middleware:夾在客人和廚房中間、專做一件事的關卡。API gateway:雲端廠商賣的現成大門,內建保全。

④ 跟這章的關係

原書說 rate limiter 可以放在 server 裡,也可以做成 middleware(下兩頁)。

② 動手玩:保全站哪裡?

10廚師要停下來應付的人

原書 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 1Rate limiter 放在 API server 這一側(依原書內容重繪)

📖 原書 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懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

保全手上的按壓計數器

① 先想像

保全手上一個計數器,每放一人按一下。規則:每分鐘最多 5 人,整點分鐘一到就歸零。

你猜猜看:12:00:50 已經按到 5,12:00:59 又來一位,放不放?

③ 這叫做 counter、window

counter:計數器,記這段時間放了幾個。window:多久歸零一次,例如每分鐘。

④ 跟這章的關係

這就是原書最簡單的 fixed window counter。它有個漏洞,第 16 頁揭曉。

② 動手玩:每分鐘最多 5 人

0 / 5計數器12:00現在這一分鐘

延伸基礎 · 動手玩第 7 階 · token bucket懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

桶子、號碼牌、和來拿牌的人

① 先想像

門口放一個號碼牌筒,最多 20 張,每秒自動補 10 張。拿到牌才能進門。

你猜猜看:筒裡是滿的 20 張,突然來 40 人,大概幾人能馬上進?

③ 這叫做 token bucket

token:號碼牌。bucket:裝牌的筒。筒多大叫 bucket size,多快補牌叫 refill rate。

④ 跟這章的關係

原書第一個介紹它。Triton 說高手和路人甲用的其實都是它(下一頁)。

② 動手玩:調桶子大小和補牌速度

0最近 5 秒放行0最近 5 秒拒絕(429)20桶內剩餘牌

原書 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 個?

📖 原書 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:補牌、溢出、四個時間點

這一步要解決的問題號碼牌筒實際怎麼運作?一個人要幾個筒?

📖 原書 Figure 4容量 4,每秒補 2 個;桶滿之後補進來的 token 溢出(依原書內容重繪)
📖 原書 Figure 6容量 4,每分鐘補 4 個(依原書內容重繪)

📖 原書 要幾個桶?

  • 每個 endpoint(API 窗口)通常各一個桶:每秒發 1 篇文、每天加 150 個好友、每秒按 5 個讚 → 每人 3 個桶
  • 依 IP 限流 → 每個 IP 一個桶;全站每秒最多 10,000 → 一個所有人共用的 global bucket
  • 缺點:兩個參數「不容易調好」

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

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

到這裡你已經會了:保全站哪、怎麼數

下一階要解決的問題

老王開了好幾個門口、好幾個保全。計數器要放在哪裡,大家才數得到同一個數字?

延伸基礎第 8 階 · Redis懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

開了三個門口,計數器要放哪?

① 先想像

老王開了三個門,每個門一位保全,各拿各的計數器。規則是全店每分鐘最多 5 人。

你猜猜看:三位保全各放了 2 人,都覺得「沒超過」。全店放了幾人?

③ 這叫做 Redis、cache

Redis:放在記憶體裡的共用白板,大家讀寫都很快。cache:放在手邊的小抄,拿得快,但正本在 database。

④ 跟這章的關係

原書把計數器放在 Redis(下一頁)。Triton 之後會問:每位客人都去看白板,白板受得了嗎?

② 動手玩:全店每分鐘最多 5 人

原書 Step 2–3高階架構

原書的做法:每個 request 都去問 Redis

這一步要解決的問題好幾台機器要共用同一個計數器,放哪裡才夠快?

📖 原書 「使用資料庫並非好主意,因為磁碟存取速度較慢」,所以計數器放 Redis。

  1. client 送 request 到 rate limiter middleware
  2. middleware 從 Redis 對應的 bucket 讀計數器,檢查是否到上限
  3. 沒超過就 +1 寫回 Redis,放行

📖 原書 用兩個指令:INCR 把計數器 +1;EXPIRE 設定逾時,時間到計數器自動刪除。超過上限就拒絕。

文組版:每個客人進門前,保全都要打電話問總部「現在幾個人了?」,總部記一筆。

📖 原書 Figure 12高階架構(依原書內容重繪)

每一顆點是一個 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=回覆單最上面的幾行小標籤,寫著「上限幾次、還剩幾次、要等幾秒」。

📖 原書 詳細設計的流程

  1. 規則存在磁碟;worker(背景小幫手程式)定期把規則拉進 cache
  2. request 先到 rate limiter middleware
  3. middleware 從 cache 讀規則,從 Redis 讀計數器和上一次 request 的時間戳
  4. 沒超過 → 轉給 API server;超過 → 回 429,request 丟掉或轉進 queue(排隊區)

原書 Step 3Detailed design · Figure 13

原書的詳細設計圖

這一步要解決的問題把前面的零件組起來,一個 request 會走哪幾條路?按按鈕一條一條看。

📖 原書 Figure 13rules、workers、cache、middleware、Redis、API servers、message queue(依原書內容重繪)

白話:message queue=讓工作先排隊的號碼機,之後再一件一件慢慢處理。

原書 Step 3超過上限的 request 怎麼辦

被擋下來的訂單,要先排隊等一下嗎?

📖 原書 回 429,有時排進 queue

被限制的 request 回 429。「依使用情境,我們可能會把被限制的 request 排進 queue 稍後處理。例如部分訂單因系統過載被限制,我們可能保留這些訂單稍後處理。」

你猜猜看:被擋的訂單排在廚房(app server)自己的記憶體裡。尖峰一直來,會怎樣?

🗣️ 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懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

兩個保全同時看白板

① 先想像

白板上寫 3。保全 A 和 B 同時抬頭看到 3,各放一人,各自把 3 擦掉、寫上 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。

📖 原書 問題二:同步

📖 原書 Figure 15左:各打各的 rate limiter;右:web tier stateless,client 會打到任何一台(依原書內容重繪)
  • 不同步的話,rate limiter 1 不知道 client 2 的任何事
  • Sticky session:原書說「不建議,不具擴展性也不夠彈性」;答案是集中式的 Redis

白話:stateless=門口不記客人,誰走哪個門都一樣;sticky session=同一位客人永遠只准走同一個門。

原書 Step 3Performance optimization · Figure 17

離使用者近一點:multi-data center

這一步要解決的問題客人在世界各地,離店太遠的人每一次都要等很久。

📖 原書 效能優化

📖 原書 Figure 17使用者被導到最近的 edge server(原圖來源:Cloudflare)(依原書內容重繪)
  • 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

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

到這裡你已經會了:原書的完整設計

下一階要解決的問題

全台一千個保全,每位客人都打電話問同一塊白板。白板自己受得了嗎?接下來是 Triton 的看法。

延伸基礎第 10 階 · hotspot懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

開了四支總機,為什麼還是只有一支被打爆?

① 先想像

白板改成總機,四支電話分工:每一家店的帳本,只放在其中一支。全台的保全都打來問老王這家店。

你猜猜看:尖峰時,另外三支總機在做什麼?

③ 這叫做 cluster、hotspot

cluster:好幾台機器組成一隊分工。hotspot:大家都擠向同一台,只有它被打爆。

④ 跟這章的關係

Rate limiter 的計數器,就是那一本人人都要翻的帳本。

② 動手玩:同樣的來電量,兩種情況

Triton 不同意直球

❌ 原書 每個 request 問一次 Redis

你猜猜看:原書每個 request 都去 Redis 讀寫計數器。有人故意灌爆流量(DDoS),誰先倒?

為什麼會死

  • 流量 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懂的人可以跳過

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

一次拿一疊號碼牌放口袋

① 先想像

保全不要每位客人都打電話。一次跟總機要 10 張牌放口袋,發完再打。

你猜猜看:3 位保全、30 位客人,每次拿 10 張。總機要接幾通?

③ 這叫做 local buffering

local buffering:每台機器在自己身上(local)先存一小疊牌(buffer),用完再拿。

④ 跟這章的關係

這就是 Triton 的解法(下一頁)。代價是數字不再精準,Triton 說沒關係(第 35 頁)。

② 動手玩:3 位保全

Triton 的解法Local buffering

✅ Triton 一次拿一疊票放口袋

你猜猜看:每次拿 5 張。流量從每秒 1 萬變成 10 萬,Redis 被問的次數會?

「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 整份投影片的目標。

5,000Redis 每秒最多被問幾次正常Redis 狀態(示意上限 20,000)

「如果你系統有 80 台伺服,你的 redis max QPS 便是 80 + (100 / 5),跟系統流量沒關係。」🗣️ Triton 本人說 087-redis-2019.pdf.md · 案例 1

Triton 的解法拿不到票就先別問了

拿不到 token 的那 500ms,本地直接拒絕

你猜猜看:保全打給總機,總機說「沒牌了」。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

每 100ms 來一個 request;平常每個都去 Redis 拿票
0本地直接拒絕0這段期間打到 Redis

文組翻譯:總機說「沒了」,接下來半秒保全不再打電話,直接跟來的人說客滿。總機得以喘口氣。

📝 上課筆記 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。會怎樣?

🗣️ 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 次。先扣哪條?

「先從比較小的 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

  1. request
  2. QPS
  3. 承受上限
  4. 429
  5. middleware
  6. counter
  7. token bucket
  8. Redis
  9. race condition
  10. hotspot
  11. local buffering

到這裡你已經會了:Triton 怎麼修

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

本章名詞小卡課後複習用 · 每個名詞一句白話

今天出現的名詞,一句話講完

request送出去的一張點單
client客人那一端:手機 app、瀏覽器
API店家公開的點餐窗口,例如 POST /order
QPS每秒進來幾個 request;看尖峰,不看平均
server真正做事的電腦,就是廚房(App server、AS)
database(DB)記錢和庫存的帳本,最慢、最不能錯
壓力測試叫一群假客人來,量出廚房的真正上限
HTTP網路上大家約好的點單和回覆格式
status code回覆單上的三位數號碼
200 / 429 / 503成功/你送太多次了/店家暫時無法接單
DoS、DDoS有人故意用大量假 request 灌爆服務
IP、user ID網路上的門牌號碼/會員編號

給工程師的重點出處與標籤

引述來源(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 幾次?這個數字跟流量有關,還是跟伺服器台數有關?

← → 翻頁 · S 講者備註 · D 深/淺色
1 / 1目錄