System Design Interview Vol. 2 · 第 2 章Triton 覆蓋度:🟡 中Triton 線
Nearby Friends
朋友的位置是「門鈴」,不是「包裹」
原書設計 Facebook「附近的朋友」:手機每 30 秒經 WebSocket 回報位置,最新位置放在有 TTL 的 Redis,再發佈到每人一個的 Redis Pub/Sub 頻道,由訂閱的朋友各自算距離。Triton 沒寫過這一章,但他的〈MQ 淺談〉剛好給了這章的關鍵詞:這種「丟了也沒差」的即時更新是 Signal,Redis Pub/Sub 就夠了。
給文組
全程用「演唱會散場找朋友」,一階一階爬 12 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
第 4–37 頁完整講原書(15 張圖全部重繪,Figure 1 截圖改畫線框),之後是 Triton 的同意、情境差異與推論,最後一頁列出所有出處(materials/core)。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📅 2026 補充
先用生活理解演唱會散場,誰還在附近?
朋友一直在走;你需要多常知道他們在哪?
散場的時候大家都在移動。如果每個朋友每秒都跟你報一次位置,手機電池和伺服器都會哭;但人走路很慢,30 秒報一次,地圖上的點只差幾步路。
藍色圈是 5 英里的「附近」。綠點是在圈裡、而且還在線上的朋友;灰點是在圈外;虛線點是「他現在實際的位置」,實心點是「上一次回報的位置」。
試試看:切換回報頻率,比較「伺服器每分鐘收到幾次更新」和「位置誤差」。再按「小明關掉 App」:他不會馬上消失,10 分鐘沒回報才從名單上拿掉(這就是等一下的 TTL)。點地圖可以移動你自己。
學習地圖本章的概念階梯
今天爬 12 階。每一階只用前面講過的東西。
- 1位置回報每 30 秒報一次
- 2半徑5 英里內才算
- 3fan-out一則轉給很多人
- 4WebSocket不掛斷的對講機
- 5TTL會自己撕掉的便利貼
- 6pub/sub每人一台小電台
- 7shard白板分成好幾塊
- 8consistent hashing圓形大樓找教室
- 9hotspot擠爆同一支電話
- 10geohash地圖格子編號
- 11Signal門鈴不是包裹
- 12batch收滿一袋再送
第 1–3 階 · 位置怎麼送、多近算附近
要回答:一次報位置,系統要轉幾份?
第 4–6 階 · 原書的三個零件
要回答:連線、最新位置、轉送各用什麼?
第 7–10 階 · 規模變大
要回答:上百台機器怎麼分工、哪裡會擠爆?
第 11–12 階 · Triton 的看法
要回答:哪些可以丟、哪些要湊一批?
全程只用一個情境:演唱會散場找朋友(虛構)
每爬 3–4 階,有一頁「到這裡你已經會了」。前幾章講過的詞(WebSocket、shard、hotspot…)只複習一頁,並附上原本那一章的連結。
原書開場Figure 1 · 和 Proximity Service 差在哪
附近的朋友:清單上有距離,也有「多久前更新」
這一步要解決的問題找朋友和找餐廳差在哪?為什麼要另開一章?
📖 原書 為「附近的朋友」這個新功能設計可擴展的後端。使用者選擇加入(opt-in)並授權位置後,App 顯示地理位置接近的朋友清單。真實例子是 Facebook App 的同名功能(原書參考 [1] TechCrunch 2014 年的報導)。
📖 原書 為什麼要另開一章?
看起來像上一章的 proximity service,但有一個關鍵差異:
| Proximity service | Nearby friends | |
|---|---|---|
| 要找的東西 | 商家 | 朋友 |
| 位置 | 靜態,地址不會變 | 動態,使用者位置經常改變 |
白話:opt-in=自己按「我要用」才開;後端=手機看不到、在機房裡做事的那一端。
文組翻譯:找餐廳像查電話簿,翻一次就好;找朋友像看即時轉播,要一直有人告訴你最新位置。所以這章的主角不是「索引」,而是「怎麼把更新送出去」。
延伸基礎第 1 階 · 位置回報懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
散場了,你怎麼讓朋友知道你在哪?
① 先想像
你在群組裡說「我在 B 出口」。走了幾步,過 30 秒再報一次。人走路很慢,30 秒只差幾十步。
你猜猜看:1,000 人每 30 秒各報一次位置,伺服器每秒收到幾則?
1,000 ÷ 30 ≈ 33。報得越勤,伺服器越累;報得太少,朋友的點會「跳格」。右邊自己調看看。
③ 這叫做 location update、經緯度
location update:手機定期送出「我現在在哪」。經緯度(latitude/longitude):地球上的座標,像棋盤的第幾行、第幾列。
④ 跟這章的關係
原書:1,000 萬人同時在線、每 30 秒報一次,每秒約 33 萬則(第 8 頁)。
② 動手玩:多少人、多久報一次
延伸基礎第 2 階 · 半徑懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
多近才算「附近」?以你為中心畫一個圓
① 先想像
你說:「5 公里內的朋友,一起去吃宵夜。」要先知道每個朋友離你多遠。
你猜猜看:小美在你東邊 3 公里、北邊 4 公里。直線距離幾公里?
直角三角形:3 × 3 + 4 × 4 = 25,開根號是 5。走路要繞路可能是 7,但這章只算直線。
③ 這叫做 radius、直線距離
radius(半徑):從你畫出去的那個圓有多大。直線距離:不管路怎麼繞,兩點之間拉一條直線量。
④ 跟這章的關係
原書:半徑 5 英里、可以設定;用直線距離,中間隔一條河也不管(第 7 頁)。距離由 server 幫你算(第 17 頁第 7 步)。
② 動手玩:拉半徑,點朋友看怎麼量
原書 Step 1Understand the problem and establish design scope
面試一開始:多近算附近?不活躍的朋友怎麼辦?
這一步要解決的問題多近算附近?不活躍的人怎麼辦?先問清楚,後面的設計都從這幾個答案長出來。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 多近才算「附近」? | 5 英里,這個數字要可以設定 |
| 距離可以用兩人之間的直線距離嗎?現實中中間可能隔一條河,實際路程更長 | 可以,合理的假設 |
| 有多少使用者?可以假設 10 億人、其中 10% 用這個功能嗎? | 可以 |
| 要存位置歷史嗎? | 要,位置歷史對機器學習等用途很有價值 |
| 朋友超過 10 分鐘不活躍,就從清單消失?還是顯示最後已知位置? | 不活躍的朋友不再顯示 |
| 要擔心 GDPR、CCPA 這類隱私法規嗎? | 好問題,為了簡化先不用 |
📖 原書 功能需求
- 使用者能在手機上看到附近的朋友;每一筆都有距離和距離最後更新的時間戳
- 附近朋友清單每幾秒更新一次
📖 原書 非功能需求
- Low latency:朋友的位置更新不能延遲太久
- Reliability:整體要可靠,但偶爾遺失資料點可以接受
- Eventual consistency:位置資料不需要強一致;不同 replica 之間差幾秒可以接受
白話:latency=等多久;replica=資料的副本;eventual consistency=各副本先各記各的,過幾秒再一致;GDPR/CCPA=歐盟、加州的個資法。
先把第二條劃線:「偶爾遺失可以接受」。後面整個設計(Redis、Pub/Sub、cache 掛了就換一台空的)都靠這句話。Triton 的 Signal vs Message 在第 41 頁接這句。
原書 Step 1Back-of-the-envelope estimation
1,000 萬人同時在線、每 30 秒一次:每秒 334,000 次更新
這一步要解決的問題每秒到底有多少則位置更新?這個數字決定後面每一個元件要多大。
📖 原書 限制與假設
- 附近 = 位置在 5 英里半徑內的朋友
- 位置每 30 秒刷新:人走路慢(平均每小時 3–4 英里),30 秒走的距離對這個功能沒什麼差
- 平均每天 1 億人使用這個功能
- 同時在線是 DAU 的 10%,所以 1,000 萬人
- 平均每人 400 個朋友,假設全部都用這個功能
- App 每頁顯示 20 個附近的朋友,需要時再載入更多
| DAU | 100 million |
| Concurrent users | 10% × 100 million = 10 million |
| 回報頻率 | 每 30 秒一次 |
| Location update QPS | 10 million ÷ 30 = ~334,000 |
動手算:刷新間隔換成多少才合理?
333,333
location update QPS
原書寫 ~334,000(無條件進位)。這個數字後面會一直出現:location cache 要扛它、Redis Pub/Sub 要把它乘上朋友數。
延伸基礎第 3 階 · fan-out懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
你報一次位置,系統要轉給幾個人?
① 先想像
你有 400 個朋友,此刻在線上的有 40 個。你每報一次,系統就要把它複製 40 份,一份一份送出去。
你猜猜看:你每 30 秒報一次,有 40 個在線朋友。一分鐘內系統要送出幾份?
一分鐘報 2 次,每次 40 份,2 × 40 = 80。進來的只有 2 則,送出去的是 40 倍。
③ 這叫做 fan-out
fan-out(扇出):一則進來,複製成很多份送出去,像扇子打開。
④ 跟這章的關係
原書:每秒 33 萬則 × 每則約 40 份 ≈ 每秒 1,400 萬次轉送(下一頁)。「乘上朋友數」整章都會出現。
② 動手玩:一則進來,幾份出去
原書 Step 2High-level design · Figure 2、3
朋友之間直接連線?不切實際;改成共用的後端
這一步要解決的問題一則位置更新,要怎麼送到所有朋友手上?
📖 原書 原書這章先講高階設計,再講 API 和資料模型:因為要把位置推給所有朋友,client 和 server 之間不會是單純的 HTTP,不先懂架構就說不清 API 長怎樣。
📖 原書 概念上是高效率的訊息傳遞。理論上可以純 peer-to-peer:每人和附近每個在線朋友維持一條持久連線(Figure 2)。但手機連線不穩、耗電預算很緊,不實際;不過這個想法點出了方向。
📖 原書 Figure 3 後端的責任
- 接收所有活躍使用者的位置更新
- 每次更新,找出所有應該收到它的活躍朋友,轉送到他們的裝置
- 兩人距離超過門檻,就不轉送
📖 原書 聽起來簡單,難在規模:每秒 334K 次更新 × 400 個朋友 × 約 10% 在線且在附近 = 每秒轉送 1,400 萬次。所以原書先畫一個小規模的設計,再到 deep dive 擴展。
白話:peer-to-peer=手機之間直接連,不經過伺服器;持久連線=接通後一直不掛斷;deep dive=深入細節那一段。
到這裡你已經會了小結 1 / 4
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
到這裡你已經會了:位置怎麼送、多近算附近
- 手機每 30 秒送一次 location update(經緯度+時間);1,000 萬人就是每秒 33 萬則。
- 「附近」是以你為圓心、半徑 5 英里的圓,用直線距離量。
- 每則更新要轉給在線朋友:fan-out 之後,變成每秒 1,400 萬份。
下一階要解決的問題
手機和伺服器之間要用什麼線連著,伺服器才能隨時把朋友的新位置「推」過來?
延伸基礎 · 複習第 4 階 · WebSocket第 12 章講過懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
一直打電話問,還是對講機一直開著?
① 先想像
你想知道小美在哪。可以每 5 秒打一次電話問她;也可以兩人的對講機一直開著,她一動就說。
你猜猜看:小美每 30 秒才換一次位置。你每 5 秒打電話問,5 分鐘內有幾通是白問?
5 分鐘打 60 通,她只換了 10 次位置,60 − 10 = 50 通白問。對講機開著,就不用一直問。
③ 這叫做 WebSocket、stateful(複習)
④ 跟這章的關係
原書:位置更新全走 WebSocket;WebSocket server 是 stateful,要拿掉一台得先「排空」(第 13、22 頁)。
② 動手玩:5 分鐘內,你的手機做了什麼
原書 Step 2Proposed design · Figure 4、5
兩條路:WebSocket 管位置,RESTful API 管其他
這一步要解決的問題「位置更新」和「加朋友」這兩種事,要不要走同一條路?
📖 原書 先畫一個較小規模、能滿足功能需求的設計(Figure 4),逐一看元件。
📖 原書 Load balancer:站在 RESTful API servers 和 stateful、雙向的 WebSocket servers 前面,把流量平均分散。
📖 原書 RESTful API servers:一群 stateless 的 HTTP server,處理一般的 request/response(Figure 5):加減朋友、更新個人資料等輔助工作。原書說這很常見,不細講。
📖 原書 WebSocket servers:一群 stateful 的 server,處理朋友位置的近即時更新。每個 client 和其中一台維持一條持久 WebSocket 連線;有半徑內的朋友更新位置時,就從這條連線送給 client。
📖 原書 WebSocket server 的另一個責任是 client 初始化:把所有附近在線朋友的位置先送給手機(第 23 頁)。本章「WebSocket connection」和「WebSocket connection handler」是同義詞。
白話:load balancer=帶位員(第 1 章);RESTful API=一般「問一次、答一次」的窗口;stateless=不記得你,誰接都一樣;connection handler=server 上替一位使用者守著那條線的小程式。
延伸基礎第 5 階 · TTL懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
集合點白板上的便利貼,10 分鐘沒換就撕掉
① 先想像
散場後大家在集合點白板貼便利貼:「小明 · B 出口 · 21:30」。規定:10 分鐘沒貼新的,就撕掉。
你猜猜看:小明 21:30 貼完最後一張就沒電關機。21:35 白板上還有他嗎?21:41 呢?
21:30 + 10 分鐘 = 21:40。在那之前還看得到他最後的位置,之後自動消失,不用有人去撕。
③ 這叫做 cache、TTL
cache:放手邊的小抄,拿得快(第 1 章)。TTL(time to live):小抄的保存期限,時間到自動消失。
④ 跟這章的關係
原書:location cache 每人一筆最新位置、TTL 10 分鐘,每次回報就刷新。TTL 到了,就是「不活躍就不顯示」(第 20 頁)。
② 動手玩:點名字讓他關機,再按「過 1 分鐘」
延伸基礎第 6 階 · pub/sub懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
每人一台小電台,朋友把收音機調過來
① 先想像
每個人有一台只播自己位置的小電台。想知道小美在哪,就把收音機調到「小美台」。
你猜猜看:你的電台有 2 個朋友在聽,其中阿傑關機了。你播一次位置,阿傑開機後聽得到這一次嗎?
電台只負責「現在」播出去,不錄音。阿傑要等你下一次播,或自己去白板看最新的便利貼。
③ 這叫做 pub/sub、channel
pub/sub:publish(播出)+ subscribe(訂閱)。channel:頻道,這章是一人一個。
④ 跟這章的關係
原書:每人一個 Redis pub/sub 頻道,朋友那邊的 handler 訂閱它(下一頁 Figure 6)。Redis 就是放在記憶體裡的共用白板(第 4 章)。
② 動手玩:誰在聽你的電台?
原書 Step 2其餘元件 · Figure 6
Redis 存最新位置;Redis Pub/Sub 當訊息匯流排
這一步要解決的問題最新位置放哪?一則更新怎麼同時送給很多朋友?
📖 原書 Redis location cache:存每個活躍使用者的最新位置,每筆都設 TTL;TTL 到期代表這個人不活躍了,位置從 cache 清掉。每次更新都刷新 TTL。其他支援 TTL 的 KV store 也可以。
📖 原書 User database:使用者資料與好友關係;關聯式或 NoSQL 都可以。
📖 原書 Location history database:使用者的歷史位置。和「附近的朋友」功能沒有直接關係。
📖 原書 Redis pub/sub server:非常輕量的訊息匯流排。頻道(channel,也叫 topic)建立成本很低,一台有幾 GB 記憶體的現代 Redis 可以放幾百萬個頻道。
📖 原書 這個設計怎麼用它
WebSocket server 收到的位置更新,發佈到使用者自己的頻道。每個活躍朋友都有一個專屬的 WebSocket connection handler 訂閱這個頻道。有更新時 handler 被呼叫,重新計算距離;在半徑內,就把新位置和時間戳從 WebSocket 送給那位朋友的 client。其他有輕量頻道的訊息匯流排也可以。
白話:KV store=用「名字 → 內容」存資料的櫃子;NoSQL=不是傳統表格的那一類資料庫;訊息匯流排=大家把訊息丟上去、由它轉送的公共管道。
一個頻道可以有很多訂閱者:User 2 的頻道有兩個訂閱者。
文組翻譯:每個人有一台自己的「廣播電台」,只播自己的位置。朋友把收音機調到你的頻率;你一開口,所有正在聽的朋友同時聽到。沒人在聽的時候,你講的話就散在空氣裡。
原書 Step 2Periodic location update · Figure 7
一次位置更新,從手機到朋友的手機要走 8 步
這一步要解決的問題把前面的零件串起來:一次更新到底經過哪幾站?按「下一步」一站一站看。
- 手機把位置更新送到 load balancer
- LB 把它轉給這個 client 在 WebSocket server 上的持久連線
- WebSocket server 把位置存進 location history database
- 更新 location cache 裡的新位置並刷新 TTL;同時存在這個使用者的 connection handler 變數裡,給之後算距離用
- 發佈到 Redis pub/sub 裡這個使用者的頻道。步驟 3–5 可以平行執行
- Redis pub/sub 把更新廣播給所有訂閱者(WebSocket connection handlers),也就是這個人所有在線的朋友
- handler 所在的 WebSocket server 計算距離:發送者的位置在訊息裡,訂閱者的位置在 handler 的變數裡
- (圖上沒畫)距離沒超過半徑,就把新位置和最後更新時間送給訂閱者的 client;否則丟掉
原書 Step 2具體例子 · Figure 8
User 1 動了:User 2、3、4 的 handler 各自算一次距離
這一步要解決的問題換成具體的人:誰會收到、誰被丟掉?
📖 原書 假設
- User 1 的朋友:User 2、3、4
- User 5 的朋友:User 4、6
- User 1 位置改變,更新送到握著 User 1 連線的 WebSocket server
- 位置發佈到 Redis pub/sub 裡 User 1 的頻道
- Redis pub/sub 廣播給所有訂閱者,這裡是 WebSocket connection handlers(User 1 的朋友們)
- 發送者(User 1)和訂閱者(User 2)的距離沒超過半徑,就把新位置送給 User 2 的 client
📖 原書 每個訂閱者都重複這個計算。平均 400 個朋友、假設 10% 在線且在附近,每次位置更新約要轉送 40 筆。
注意 User 4:他同時是 User 1 和 User 5 的朋友,所以他的 handler 訂閱了兩個頻道,兩邊的更新都會收到。
原書 Step 2API design
WebSocket 上至少要有 5 個 API;其他走 HTTP
這一步要解決的問題手機和 server 在那條 WebSocket 上,要說哪幾種話?
| # | WebSocket API | Request | Response / 送出的資料 |
|---|---|---|---|
| 1 | Periodic location update | client 送 latitude、longitude、timestamp | 無 |
| 2 | Client receives location updates | — | 朋友的位置資料和時間戳 |
| 3 | WebSocket initialization | client 送 latitude、longitude、timestamp | client 收到朋友們的位置資料 |
| 4 | Subscribe to a new friend | WebSocket server 送 friend ID | 朋友最新的 latitude、longitude、timestamp |
| 5 | Unsubscribe a friend | WebSocket server 送 friend ID | 無 |
📖 原書 HTTP requests:API servers 處理加減朋友、更新個人資料等,很常見,原書不細講。
點左表任一列,看它在連線上大概長什麼樣:
🔭 示意 原書只列欄位,沒有訊息格式;右邊的 JSON 是為了說明而寫的,欄位名稱不是原書的。
有趣的一點:第 4、5 個 API 的 request 是「WebSocket server 送 friend ID」。也就是說,加了新朋友之後,是 server 端的 handler 去訂閱新朋友的頻道(第 33 頁會講 client 怎麼通知它)。
原書 Step 2Data model · Table 1
每人只存一個最新位置,TTL 到了就消失
這一步要解決的問題最新位置要存成什麼樣子?歷史位置又放哪?
| key | value |
|---|---|
user_id | {latitude, longitude, timestamp} |
📖 原書 存所有開啟這個功能的活躍使用者的最新位置,用 Redis。
📖 原書 為什麼不用資料庫存位置?
- 這個功能只在乎現在的位置,每人只要存一筆
- Redis 讀寫超快,而且支援 TTL,用來自動清掉不再活躍的人
- 現在位置不需要持久保存。Redis 掛了就換一台空的,讓新的更新把它填滿;活躍使用者可能錯過朋友一兩個週期的更新,可以接受的取捨(deep dive 再談怎麼減少影響)
📖 原書 Location history database
| user_id | latitude | longitude | timestamp |
|---|
要能扛大量寫入、可以水平擴展:Cassandra 是好選擇。也可以用關聯式資料庫,但歷史資料放不進一台,要 shard;最基本是依 user ID 分片,負載平均、維運也簡單。
白話:Cassandra=擅長大量寫入、可以一直加機器的資料庫;shard/分片=依 user ID 分到好幾台(第 24 頁複習)。
到這裡你已經會了小結 2 / 4
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
到這裡你已經會了:原書的三個零件
- 手機和 server 之間開一條不掛斷的 WebSocket;接著這條線的 server 是 stateful。
- 每人最新位置放 location cache,TTL 10 分鐘:不活躍的人自己消失。
- 位置發佈到自己的 pub/sub 頻道;在線朋友的 handler 訂閱、收到後算距離。
下一階要解決的問題
1,000 萬人、每秒 1,400 萬次轉送,一台 Redis 一定撐不住。要怎麼分給上百台機器,又不在加減機器時天下大亂?
原書 Step 3How well does each component scale? · API servers、WebSocket servers
WebSocket server 是 stateful 的:要拿掉一台,先讓它「排空」
這一步要解決的問題連線接在某一台 server 上,那台要下線時怎麼辦?
📖 原書 原書先承認這個高階設計在多數情況都能用,但在我們的規模下大概會壞。deep dive 一邊加大規模、一邊找瓶頸、一邊解掉它。
📖 原書 API servers:stateless,擴展方式很成熟,可以依 CPU、負載或 I/O 自動擴展,不細講。
📖 原書 WebSocket servers:依用量自動擴展不難,但它們是 stateful,移除節點要小心:
- 在 load balancer 把節點標成 “draining”,新的 WebSocket 連線不再導過去
- 等現有連線全部關閉(或等一段合理的長時間)
- 再移除這台 server
📖 原書 在 WebSocket server 上發佈新版本也要同樣小心。有效地自動擴展 stateful server 是好的 load balancer 的工作,多數雲端 LB 都做得很好。
白話:draining=「這台不再接新連線」,等舊的自己走;發佈新版本=把新程式換上去,要重啟。
原書 Step 3Client initialization
連上 WebSocket 的那一刻,handler 要做 7 件事
這一步要解決的問題剛打開 App、什麼都還沒收到,畫面上的朋友從哪來?
📖 原書 手機啟動時和某一台 WebSocket server 建立持久連線。每條連線都跑很久;多數現代語言都能用很小的記憶體維持大量長連線。連線初始化時 client 送出初始位置,server 在 connection handler 裡:
- 更新 location cache 裡這個人的位置
- 把位置存在 handler 的變數裡,給之後計算用
- 從 user database 載入這個人所有的朋友
- 對 location cache 發一個批次 request 拿所有朋友的位置。TTL 等於不活躍逾時,不活躍的朋友不會在 cache 裡
- 對 cache 回傳的每個位置算距離;在半徑內,就把朋友的 profile、位置、最後更新時間從 WebSocket 回給 client
- 訂閱每個朋友在 Redis pub/sub 的頻道。建頻道很便宜,所以活躍和不活躍的朋友都訂閱;不活躍的只佔一點記憶體,不吃 CPU 和 I/O(他們不發佈)
- 把自己現在的位置發佈到自己的頻道
白話:批次 request=一次問 400 個朋友,不是問 400 次;profile=名字、大頭貼這些個人資料。
延伸基礎 · 複習第 7 階 · shard第 1 章講過懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
一塊白板貼不下:依會員編號分成四塊
① 先想像
1,000 萬張便利貼,一塊白板貼不下,一個人也寫不完。改成四塊白板,看會員編號除以 4 的餘數決定貼哪一塊。
你猜猜看:會員編號 1,002 的便利貼貼在第幾塊?(從第 0 塊算起,看除以 4 的餘數)
1,002 = 4 × 250 + 2,餘數 2。每個人永遠去同一塊,大家平均分。
③ 這叫做 shard、standby(複習)
④ 跟這章的關係
原書:location cache 依 user ID shard 到幾台 Redis,每台配一台 standby;user DB 也依 user ID shard(第 25 頁)。
② 動手玩:會員編號 → 第幾塊白板
原書 Step 3User database · Location cache
記憶體 1 GB 就放得下;每秒 33 萬次寫入才是問題
這一步要解決的問題1,000 萬人的最新位置,一台 Redis 放得下、寫得動嗎?
📖 原書 User database
兩組資料:使用者 profile(user ID、username、profile URL 等)和好友關係。以這個規模大概放不進一台關聯式資料庫,好消息是可以依 user ID shard 水平擴展,這是很常見的技術。
附帶一提:這個規模下,使用者和好友資料大概由專門的團隊管理、透過內部 API 提供;WebSocket server 改呼叫內部 API 而不是直接查資料庫。功能和效能上差別不大。
📖 原書 Location cache
每個 key 都設 TTL,每次更新刷新,所以記憶體有上限:尖峰 1,000 萬活躍使用者 × 每筆不超過 100 bytes,一台有很多 GB 記憶體的現代 Redis 輕鬆放得下。
但每秒 334K 次更新對一台高階 server 也「可能有點太高」。幸好每個人的位置互相獨立,依 user ID shard 到幾台 Redis 就能平均分散。為了可用性,每個 shard 複製到一台 standby,primary 掛了就快速升級 standby。
白話:primary/standby=正本和備用機(第 24 頁複習);內部 API=公司裡別的團隊開的窗口。
原書 Step 3Redis pub/sub server
每人一個頻道;一上線就把所有朋友的頻道都訂閱
這一步要解決的問題每人一個頻道、全部朋友都先訂閱,會不會太浪費?
📖 原書 pub/sub server 是路由層:把一個人的位置更新導向他所有在線的朋友。選 Redis pub/sub 是因為建立新頻道非常輕量:
- 有人訂閱時就建立新頻道
- 發佈到沒有訂閱者的頻道,訊息直接丟掉,幾乎不造成負載
- 頻道建立時 Redis 用一點記憶體維護一個 hash table 和 linked list 追蹤訂閱者 [3]
- 使用者離線、頻道沒有更新時,建好之後不用任何 CPU
📖 原書 設計上怎麼利用
- 每個用這個功能的人都有一個唯一的頻道。App 初始化時訂閱每一個朋友的頻道,不管朋友在不在線。後端不用在朋友上線時才訂閱、下線時取消,設計變簡單
- 代價是多用記憶體。後面會看到記憶體不太可能是瓶頸;用較高的記憶體換較簡單的架構,在這裡值得
白話:路由層=負責「這則該送去哪」的那一層;hash table、linked list=Redis 內部記訂閱者名單的兩種方式。
猜猜看:Redis 要花多少力氣?
點卡片看答案。最後一張就是下一頁計算機的公式。
文組翻譯:把所有朋友的電台都先存進收音機的「我的最愛」。沒開播的電台不會發出任何聲音,也不耗電,只是佔一格清單。
原書 Step 3 · 動手算How many Redis pub/sub servers do we need?
記憶體 2 台就夠,CPU 要 140 台:瓶頸是 CPU
這一步要解決的問題要幾台 Redis pub/sub?卡在記憶體還是 CPU?
📖 原書 Memory usage
每個用功能的人一個頻道:10 億 × 10% = 1 億個頻道。平均每人 100 個也用這功能的活躍朋友(附近或不附近都算),每個訂閱者在 hash table 和 linked list 裡約 20 bytes 指標:
100M × 20 B × 100 ÷ 109 = 200 GB → 100 GB 的機器約 2 台
📖 原書 CPU usage
前面算過每秒約推 1,400 萬次。沒有 benchmark 很難準確估一台 Redis 每秒能推多少,但一台一定扛不住。保守假設一台有 gigabit 網路的 server 每秒約推 100,000 次(訊息很小,這個數字大概偏保守):
14M ÷ 100K = 140 台(大概太保守,實際可能少很多)
📖 原書結論 ① Redis pub/sub 的瓶頸是 CPU,不是記憶體;② 要支撐這個規模,需要分散式 Redis pub/sub cluster。
延伸基礎 · 複習第 8 階 · consistent hashing第 5 章講過懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
加開一台機器,要搬多少個頻道?
① 先想像
頻道用「除以 4 的餘數」分給 4 台機器。人變多,加成 5 台,改成「除以 5」。
你猜猜看:「除以 4」改成「除以 5」,大概多少頻道要換機器?
只有兩種算法剛好餘數一樣的才不用搬。編號 0–19 自己算:只有 0、1、2、3 不動,其他 16 個都要搬。
③ 這叫做 consistent hashing(複習)
④ 跟這章的關係
原書:上百台 pub/sub server 排成 hash ring(第 29 頁)。加減一台只影響隔壁那一段。
② 動手玩:12 個頻道、加一台機器
原書 Step 3Distributed Redis pub/sub server cluster · Figure 9、10
幾百台 pub/sub server:用 service discovery 存一個 hash ring
這一步要解決的問題上百台 pub/sub server,每個頻道要去哪一台找?
ash(channel)、箭頭從 Channel 2 指向 WebSocket servers,這裡依內文畫成 WebSocket server 發佈到 Channel 2)📖 原書 頻道彼此獨立,依發佈者的 user ID shard 到多台 server 相對容易。但幾百台 server 一定會不時當機,要說清楚怎麼做才好維運。於是加入 service discovery(最常見的是 etcd [4] 和 Zookeeper [5])。只需要兩個基本功能:
- 在 service discovery 裡存一份 server 清單,有簡單的 UI 或 API 可以更新。本質上它是存設定的小 KV store:
Key: /config/pub_sub_ring Value: ["p_1", "p_2", "p_3", "p_4"]
- client(這裡是 WebSocket servers)可以訂閱 Value 的任何更新
📖 原書 這個 key 底下存的是所有活躍 pub/sub server 的 hash ring(Vol.1 一致性雜湊那章)。發佈者和訂閱者都用它決定每個頻道找哪台。例如 Figure 9 的頻道 2 在 server 1。
📖 原書 Figure 10:① WebSocket server 查 hash ring 決定寫哪台(真相在 service discovery,但每台 WS server 可以在記憶體裡快取一份,並訂閱 ring 的更新);② 發佈到那台上的使用者頻道。訂閱也用同一套機制。
白話:service discovery=記「現在有哪些 server」的通訊錄;hash ring=第 28 頁的圓環。
原書 Step 3Scaling considerations for Redis pub/sub servers
pub/sub cluster 要當成 stateful 看:別每天擴縮
這一步要解決的問題pub/sub 的機器,可以像一般 server 一樣每天加減嗎?
📖 原書 要不要像 stateless server 一樣每天依流量擴縮?那種做法風險低又省錢。先看 pub/sub cluster 的特性:
- 頻道上的訊息不存在記憶體也不寫磁碟,送給訂閱者就移除,沒訂閱者就丟掉。這個意義上,流過的資料是 stateless
- 但 server 上確實有狀態:每個頻道的訂閱者清單。頻道一搬家(server 被換掉、ring 加減 server),所有訂閱者都要知道,從舊 server 取消、到新 server 重新訂閱。這個意義上它是 stateful
📖 原書 所以把它當成像儲存 cluster 的 stateful cluster:擴縮有維運負擔和風險,要仔細規劃;通常超額配置,讓每日尖峰也有餘裕,避免不必要的擴縮。
白話:超額配置=平常就多準備幾台;dashboard=看機器狀態的儀表板。
📖 原書 真的要擴縮時
- 很多頻道會搬到別台;service discovery 通知所有 WS server 後,會有大量重新訂閱
- 這段期間 client 可能漏掉一些更新;偶爾漏掉可接受,但要盡量少
- 所以在一天用量最低的時候做
步驟:① 決定新的 ring 大小,擴充就先準備好新 server ② 用新內容更新 hash ring 的 key ③ 看 dashboard,WebSocket cluster 的 CPU 應該會有一波尖峰。
原書 Step 3Operational considerations · Figure 11
換掉一台壞掉的 server,風險低得多
這一步要解決的問題一台 pub/sub 壞掉了,怎麼換掉又不驚動全部人?
📖 原書 替換一台既有的 pub/sub server,不會讓大量頻道搬家,只有被替換那台上的頻道要處理。這很好,因為 server 一定會當機、要定期替換。
- pub/sub server 掛掉時,監控軟體通知值班人員(怎麼監控超出本章範圍)
- 值班人員更新 service discovery 裡的 hash ring key,把死掉的節點換成一台新的 standby
- WebSocket servers 收到通知,再通知各自的 connection handlers 到新 server 重新訂閱
- 每個 handler 都保有自己訂閱過的頻道清單,逐一對照 hash ring,判斷哪些頻道要到新 server 重新訂閱
Old: ["p_1", "p_2", "p_3", "p_4"] New: ["p_1_new", "p_2", "p_3", "p_4"]
白話:值班人員(on-call operator)=輪值待命、半夜會被叫醒的工程師。
文組翻譯:電台換發射塔。只有原本在那座塔收聽的人要重新調頻,其他電台的聽眾完全不受影響。
延伸基礎 · 複習第 9 階 · hotspot第 4 章講過懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
一個頻道只住一台:太多人聽同一台會怎樣?
① 先想像
四支總機各管一部分電台。大部分人只有幾十個朋友在聽;某位大明星的電台,卻有 100 萬人在聽。
你猜猜看:大明星每 30 秒播一次,100 萬人在聽。他那支總機每秒要送幾份?
100 萬 ÷ 30 ≈ 3.3 萬份/秒,全壓在同一支總機。其他三支再閒,也幫不上忙。
③ 這叫做 hotspot(複習)
④ 跟這章的關係
原書:朋友上限 5,000、而且是雙向好友,不會有 100 萬人聽同一台(第 33 頁)。Triton 會在第 44 頁指出真正的熱點在哪。
② 動手玩:四支總機,每秒各送幾份
原書 Step 3Adding/removing friends · Users with many friends
5,000 個朋友的大戶,會不會壓垮某一台?
這一步要解決的問題加減朋友時怎麼通知 server?朋友特別多的人,會不會壓垮某一台?
📖 原書 加 / 刪朋友
加了新朋友,server 上這個 client 的 WebSocket handler 要被通知,才能訂閱新朋友的頻道。這個功能活在一個更大的 App 裡,所以可以在手機上註冊 callback:加朋友時,callback 送訊息給 WebSocket server 訂閱新朋友的頻道;server 也回傳新朋友最新位置和時間戳(如果他活躍)。刪朋友同理:callback 請 server 取消訂閱。朋友選擇加入或退出位置分享時,也可以用同一組 callback。
📖 原書 朋友很多的使用者
假設朋友數有硬上限(例如 Facebook 是 5,000)。好友關係是雙向的,不是名人有幾百萬追蹤者的 follower 模型。
- 幾千個朋友時,訂閱者散在 cluster 裡很多台 WebSocket server 上,更新負載也分散,不太會造成 hotspot
- 這個人的頻道所在的那台 pub/sub server 會多一點負載;有 100 多台 pub/sub server,這些「whale」使用者也會分散開,增加的負載不會壓垮任何一台
白話:callback=事情發生時自動通知的小鈴鐺;hotspot=大家擠向同一台(第 32 頁);whale=朋友特別多的大戶。
延伸基礎第 10 階 · geohash懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
把地圖切成格子,每格一個編號
① 先想像
像郵遞區號:同一區的地址,開頭幾碼一樣。把地圖切成棋盤格、每格給一個編號;格子再切細,編號就多一碼。
你猜猜看:A 的格子是 9q8znd、B 是 9q8znf、C 是 9r2kpb。誰比較可能離 A 很近?
開頭一樣的碼越多,通常越近。但小心:剛好在格子邊界兩側的人很近、編號卻可能差很多,所以要連隔壁格一起看。
③ 這叫做 geohash、鄰格
geohash:地圖格子的編號,碼數越多格子越小。鄰格:你這格周圍的 8 格。
④ 跟這章的關係
原書的加分題「附近的陌生人」:用 geohash 格子當 pub/sub 頻道,每人訂閱自己這格加周圍 8 格(第 35 頁)。上一章 Proximity Service 也用同一招找店。
② 動手玩:點你站的那一格
原書 Step 3Nearby random person · Figure 12、13、14
加分題:顯示附近的陌生人?改用 geohash 當頻道
這一步要解決的問題加分題:想看到附近的陌生人,頻道要怎麼切?
📖 原書 可以當成 extra credit,不在原本的功能需求裡:如果面試官想顯示選擇分享位置的隨機陌生人呢?
📖 原書 沿用現有設計:加一組依 geohash 劃分的 pub/sub 頻道(geohash 見 Proximity Service 那章)。Figure 12 把一個區域分成四個 geohash 格子,每格一個頻道;格子裡的每個人都訂閱同一個頻道。
- 以 9q8znd 為例(Figure 13):User 2 更新位置時,handler 算出他的 geohash ID,把位置送到那個 geohash 的頻道
- 附近訂閱這個頻道的人(不包括發送者)都收到位置更新
📖 原書 靠近格子邊界的人怎麼辦?每個 client 訂閱自己所在的格子和周圍 8 格(Figure 14)。
這和上一章的「自己這格 + 8 鄰格」是同一招,只是從「查詢」變成「訂閱」。geohash 的格子見第 34 頁。
原書 Step 3Alternative to Redis pub/sub
原書自己說:Erlang 其實比 Redis pub/sub 更好,只是人難找
這一步要解決的問題除了 Redis pub/sub,還有更好的做法嗎?
📖 原書 有沒有好的替代方案?答案是肯定的:Erlang [8] 很適合這個問題,原書認為它比上面的 Redis pub/sub 更好。但 Erlang 很小眾,好的 Erlang 工程師很難請;如果團隊有這個專長,這是很好的選擇。
📖 原書 這裡說的 Erlang 是整個生態系:語言(Erlang 或 Elixir [9])、執行環境和函式庫(虛擬機 BEAM [10]、執行函式庫 OTP [11])。
- 強項是輕量的 process:跑在 BEAM 上,建立成本比 Linux process 低好幾個數量級。最小的 Erlang process 約 300 bytes,一台現代 server 可以跑幾百萬個;沒事做時完全不用 CPU
- 所以把 1,000 萬個活躍使用者每人建模成一個 Erlang process 非常便宜
- 很容易分散到多台 Erlang server,維運負擔低,有很好的工具可以安全地除錯線上問題,部署工具也很強
📖 原書 怎麼用:WebSocket service 用 Erlang 寫,整個 Redis pub/sub cluster 換成一個分散式 Erlang 應用。每個使用者是一個 process,從 WebSocket server 收到自己的位置更新,並訂閱朋友們的 process;訂閱是 Erlang/OTP 的原生功能。這形成一張網,把一個人的更新有效率地送給很多朋友。
白話:process=電腦上一個獨立在跑的小程式;BEAM、OTP=Erlang 的執行環境和工具箱。
原書 Step 4Wrap up · Chapter summary
原書的收尾:把一個人的位置,有效率地送給他的朋友
這一步要解決的問題回頭看一遍:這章到底解決了什麼?
📖 原書 核心元件:
- WebSocket:client 和 server 之間的即時通訊
- Redis:位置資料的快速讀寫
- Redis pub/sub:路由層,把一個人的位置更新導向所有在線的朋友
📖 原書 先在較小規模提出高階設計,再討論規模變大時的挑戰,探討了怎麼擴展:RESTful API servers、WebSocket servers、資料層、Redis pub/sub servers,以及 Redis pub/sub 的替代方案。
📖 原書 最後討論了朋友很多的使用者可能造成的瓶頸,並提出「附近隨機陌生人」的設計。
原書最後一句:恭喜你讀到這裡,給自己拍拍肩膀。
到這裡你已經會了小結 3 / 4
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
到這裡你已經會了:規模變大之後
- 資料太多就 shard:location cache 依 user ID 分到幾台,各配一台 standby。
- 上百台 pub/sub 排成 consistent hashing 的圓環:加一台只搬隔壁一段。
- 一個頻道只住一台,太多人擠同一台就是 hotspot;陌生人功能用 geohash 格子當頻道。
下一階要解決的問題
原書的部分講完了。Triton 會問:這些位置可以丟嗎?丟了要補嗎?哪一台最容易被擠爆?
Triton 觀點先看全貌
Triton 同意 Redis Pub/Sub 和 TTL;在意的是 WebSocket 裡放了多少邏輯
✅ 一致 原書做對的地方
- 即時位置「偶爾遺失可接受」→ 是 Signal,用 Redis Pub/Sub 正確(第 41 頁)078
- 最新位置只放 Redis、一定設 TTL、掛了換一台空的:正是 Redis 的正確用法(第 45 頁)087 · 088
- 初始化用批次 request 拿 400 個朋友的位置(第 45 頁)088
- Redis 瓶頸在 CPU、要分到很多台(第 44 頁)087 · 088
- 用 consistent hashing、把 pub/sub cluster 當 stateful(第 47 頁)087 · 017
- geohash + 周圍 8 格(第 44 頁)064
🔭 情境差異 / 原書沒講
- WebSocket server 又寫歷史、又寫 cache、又初始化:每次部署都要斷線(第 42 頁)090 · 062
- 每個 handler 各自訂閱 Redis:連線數會爆(第 43 頁)062 · 088
- 一台 Redis 每秒 10 萬次推送的假設、geohash 頻道的密度 → hot key(第 44 頁)029 · 182 · 064
- 位置歷史每秒 33 萬筆寫入要怎麼寫(第 50 頁)117
- 壞掉的 pub/sub 要「值班人員」手動換(第 46 頁)017
先說清楚:Triton 沒有講過 nearby friends 這個題目。下面每一頁的 🗣️ 是他在別的情境(chatroom、UNO 牌局、排行榜、Redis 講義)說的原話,🔭 是我們把那些原則套到這一章。而且他的範例規模本來就小:🗣️ 062「今天的設計不是用來面對上百萬在線用戶的」;🗣️ 078「警告:現實 chatroom會用MQTT機制,這篇單純教學MQ,請勿真的實作」。
延伸基礎 · 複習第 11 階 · Signal第 12 章講過懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
朋友的位置,是門鈴還是包裹?
① 先想像
門鈴響一下,沒聽到就算了,等下次再響;包裹不能丟,沒收到要重送。
你猜猜看:你過隧道 2 分鐘,小美的位置在這期間更新了 4 次。出隧道時要把這 4 次都補給你嗎?
你要的是她「現在」在哪。舊的 4 筆早就過時,補了只會讓地圖亂跳。
③ 這叫做 Signal、Message(複習)
④ 跟這章的關係
Triton:Redis Pub/Sub 適合傳 Signal(第 41 頁)。原書的需求「偶爾遺失可以接受」,剛好就是 Signal。
② 動手玩:分分看,門鈴還是包裹?(點卡片看答案)
Triton 同意 · 動手玩078 MQ 淺談 · Signal vs Message
✅ 同意原書 朋友的位置是 Signal:斷線時漏掉的,不用補
先猜:原書這樣做會出什麼事?原書選 Redis Pub/Sub:不存訊息,斷線期間的更新就漏掉了。Triton 會怎麼說?
078 把 Redis Pub/Sub 定位成「可以用在 Signal 的傳遞」。原書的需求本來就寫「偶爾遺失可以接受」。按 → 看原文。
「Signal – 要高度即時性 – 丟失沒太大差 Message – 可以排隊一個一個工作慢慢來~ – 絕對不能丟失」🗣️ Triton 本人說 078-mq-intro.pdf.md · 第 8 頁
「Redis的 PubSub 簡單而言:把 persistence刪掉的 MQ – 東西只傳一次,不管你是否有工作完成 – Redis連線斷掉期間的東西, Redis不會替你先保留 – 可以用在 Signal的傳遞」🗣️ Triton 本人說 078 · 第 10 頁
🗣️ 真正的 MQ「會把收到的Message先存到HDD,然後才回應成功」「會等待收件者回傳「工作完成」,才真的把訊息刪掉」;「Message一定用MQ Server來傳, Signal有很多手段的~」078 · 第 7、9 頁
🔭 放回這章
原書的需求「occasional data point loss is acceptable」就是 Signal 的定義。斷線期間漏掉的位置不需要補:30 秒後就有新的;重連時的 WebSocket initialization 從 location cache 讀一次最新位置,角色等於 078 聊天室裡的「GET 補回斷線期間留言」。如果硬用會存硬碟、要 ack 的 MQ,每秒 33 萬則發佈、1,400 萬份投遞都要先寫磁碟、等 ack,重連時還會倒出一串已經過時的位置。
Triton 不同意(推論)090 RESTful 範例 · 062 · 動手玩
原書的 WebSocket server 做太多事:改一行邏輯,1,000 萬人斷線
先猜:原書這樣做會出什麼事?原書的 WebSocket server 裡有寫歷史的程式。改一行,會怎樣?
程式在 WebSocket server 裡,換版就要重啟;連線接在它身上,重啟就斷。下面按「部署」看看。
「如果Websocket只用來接收 server push,那麼websocket可以非常簡單 – 單純簡單用戶身份驗證後, listen RabbitMQ特定 channel,把收到的東西全部 relay給用戶 就好 – 幾乎沒有Application Logic,所以極少改動」🗣️ Triton 本人說 090-restful-demo.pdf.md · 第 10 頁
「如果WebSocket有Application Logic – 那麼,你就會因為App Logic Change / Bug Fix 而需要做production deployment – 在deployment時,你要:等待這個Server全部的Websocket自然中斷?把用戶的Websocket強行中斷,叫他們連到新的AS 以上二者都不是好主意」🗣️ Triton 本人說 090 · 第 10 頁
🗣️「WebSocket單純用來接收其他玩家的改動 要出牌是用傳統的 RESTful API AS是 Stateless,不同的用戶的Websocket會散落在不同的機器上」090 · 第 12 頁;「page load時拿「過去72小時價格」,然後以websocket接收「最新報價」去append到「過去72小時價格」後面」146
🔭 依 Triton 原則推論
原書第 22 頁的 draining,正是 090 說「都不是好主意」的第一種。照 090 的切法:位置回報改成 POST 到 stateless API(寫 cache、寫歷史、publish),初始化改成 GET 附近朋友;WebSocket 只做驗證、訂閱朋友頻道、算距離、relay。代價:每秒 33 萬個 HTTP request 比 WebSocket frame 貴一些;距離過濾仍在 WebSocket,但它很小、很少改。
Triton 補充(推論)062「Message Queue」 · 088 connection anti-pattern · 動手算
每個 handler 各自訂閱 Redis?一台 WS server 共用一條就好
先猜:原書沒說連線怎麼開,會出什麼事?1,000 萬個 handler,每個都自己開連線到它朋友頻道所在的 pub/sub server。Redis 那邊總共有幾條連線?
每個 handler 的 400 個朋友頻道散在上百台 pub/sub 上,1,000 萬 × 約 130 台 ≈ 十幾億條。表格第一列就是這個數字。
「不管 App. Server 上有多少個 websocket 連線 都只會共用一個 MQ connection – 所以,你很可能需要 implement message dispatcher」🗣️ Triton 本人說 062-im-system design.pdf.md · 第 20 頁
「Anti pattern: no connection pool 沒有 connection pool,就代表你每一個 operation都要重建 TCP/IP conn – latency大增 最要命的是:這會嚴重浪費掉 redis server的 resource」🗣️ Triton 本人說 088-redis-intro.pdf.md · 第 12 頁
🔭 依 Triton 原則推論
原書寫「每個活躍朋友有一個專屬的 WebSocket connection handler 訂閱頻道」,沒說 Redis 連線怎麼開。照 062:每台 WebSocket server 對每台 pub/sub server 只開一條訂閱連線,收到後由 dispatcher 分給本機的 handler。算完會發現:它省下的是連線數(幾千倍),不是推送數:朋友隨機散在上千台 WS server,同一台很少有兩個人訂同一個頻道。
Triton 補充087 · 029 · 182 · 064 · Redis 單執行緒與 hot key · 動手玩
一個頻道只住在一台 Redis:5,000 個朋友不可怕,演唱會才可怕
先猜:原書的陌生人頻道會出什麼事?演唱會散場,2 萬人在同一個 geohash 格子,每人都發佈、也都訂閱這一格。推送量會?
每個人的一次發佈,要推給格子裡所有人:人數 × 人數。而且這個頻道只住在一台 Redis。上面切到「演唱會」看看。
「在 redis cluster,一份資料只存放在一個 node上 每一個 node都是 single thread的 … 容易發生 hotspot,沒法以增加硬體手段解決」🗣️ Triton 本人說 087-redis-2019.pdf.md · 第 8 頁
「我們的實戰經驗,單台的 redis 大約能支持 C10K。 (docker、簡單的 operation)」「如果這份資料有 C100K 的流量,存了那份資料的 redis 必檔。」📝 上課筆記 029-Redis.md(無署名的 Redis 課堂筆記)
「因為sorted set只有一個,即使建立了redis-cluster也只會存到其中一台redis上 … 像是新年倒數便一起開罐罐狂歡,瞬間有超高流量進了單一台redis。」🗣️ Triton 本人說 182 · 即時排名
🔭 依 Triton 原則推論
✅ 原書說 CPU 是瓶頸、要分很多台,和 087 一致;whale 也確實不是熱點。但 geohash 頻道是「開罐罐派對」:格子裡的人都發佈也都訂閱同一個頻道,推送量是人數的平方,又只能住在一台。照 064「了解 N(像是 QPS / user count / data size)」,先估最擠的格子有幾人。
Triton 同意087 · 088 · 017 · TTL、批次讀取、stateful 與 HA
✅ 同意原書 最新位置是「沒了也死不了人」的 hot data
先猜:原書這樣做會出什麼事?location cache 的 Redis 掛了,1,000 萬人的最新位置全沒了。要緊嗎?
原書說換一台空的、讓新的更新把它填滿。Triton 怎麼定位這種資料?按 → 看原文。
「正常人使用 Redis…… – 用作 caching,資料同時存放於主資料庫 – 儲存沒了也死不了人的 Hot Data」🗣️ Triton 本人說 087 · 第 6 頁
🔭 location cache 是第二種:它沒有背後的主資料庫,掛了就換空的、等 30 秒填滿。原書寫「acceptable tradeoff」,和 087 的定位一致。
「Anti pattern: cache without TTL … 問題 2:你還記得 redis是 single thread的嗎?」🗣️ Triton 本人說 088 · 第 11 頁
🔭 原書的 TTL 不只是衛生習慣,它就是功能:TTL = 10 分鐘不活躍逾時(第 20 頁)。
「如果有 1000筆ActivityHistory,先掃瞄一次拿出全部的UserID – 以 redis MGET,一次過拿回 1000個User.displayName」🗣️ Triton 本人說 088 · 第 13 頁
🔭 初始化的「批次 request」就是這招。但 location cache 依 user ID shard,087 也提醒「不同的 KeyValue會放到不同的 redis機器」:400 個朋友要依 shard 分組、各送一個 MGET 平行跑。
「stateless component算是很簡單的,就單純有N個相同的node就好」「stateful component是指像:postgresql database / kafka / rabbitMQ 這些會存放application state的component」「而redis嘛:如果單純用作caching的,那嚴格定義上算是stateless 不過,實務上當成stateful會比較安全」🗣️ Triton 本人說 017-High Availability stateful component vs stateless component.md
✅ 原書把 pub/sub cluster 當 stateful、不每天擴縮(第 30 頁),正是這個分法:訊息是 stateless,訂閱者清單是 state。
Triton 情境差異017 · HA 的定義
壞了一台要「值班人員」去換,還不算 HA
先猜:原書這樣做會出什麼事?pub/sub server 半夜 3 點掛了。原書的流程是監控通知值班人員,人去改 hash ring。這樣算 HA 嗎?
Triton 對 HA 的定義在右邊。按 → 揭曉。
📖 原書 第 31 頁的流程
- pub/sub server 掛掉,監控軟體通知值班人員
- 值班人員更新 service discovery 裡的 hash ring key
- WebSocket servers 通知 handlers 到新 server 重新訂閱
白話:HA(high availability)=一台壞了,系統自己撐得住、很快恢復。
🔭 情境差異 「值班人員」不是 HA
「如果single component掛掉,是不需要人類即時行動。」「有HA只代表有single component掛了後系統能自動短時間內回復。(一般來說「短時間」=數分鐘內)」🗣️ 017
原書第 31 頁是「監控通知值班人員,人去改 hash ring」。照 017,半夜這一台掛了、要等人起床,就還不算 HA;換 standby 這一步應該是自動的 script,或用別人做好的 managed 方案(017:「請使用像AWS RDS multi-AZ這些別人建好的方案」)。
Triton 補充087 · 029 · 090 · consistent hashing 與 Redis 內建
hash ring 自己存在 etcd?先看 Redis 內建了什麼
先猜:原書這樣做會出什麼事?原書自己在 etcd 存一份 hash ring、自己算 hash。Triton 對「自己算 hash 來分配」會怎麼說?
原書其實已經用 consistent hashing(第 28 頁複習)。Triton 會再問:能不能讓 Redis 自己做?按 → 看原文。
「別使用mod( md5(cacheKey), n )來決定某一 keyValue 位置 … 用這方法,當你系統繁忙要加開 redis時, n的改動會讓你的caching全滅 請學習 consistent hash – 其實 redis cluster內建了」🗣️ Triton 本人說 087 · 第 15 頁
✅ 原書用 consistent hashing,加兩台只搬約四分之一的頻道(第 30 頁的對照組:mod N 會搬三分之二)。029 的課堂版多一句:「也就是說,不要自己算 hash。」029
🗣️ 同一招 Triton 用在 load balancer:「LB層分派 Request的手段不是 random,而是基於 gameId的 Consistent hashing – 同一 gameId的 Request,就會被丟到同一台 AS上 – Consistent hashing不用把歷史存起來,不吃 Memory的 – 即使 AS 當掉, Request 自動丟到別的 AS上」090 · 第 18 頁
📅 2026 補充 Redis 7 的 sharded Pub/Sub
傳統 Redis Cluster 的 PUBLISH 會廣播到 cluster 的每一個 node,所以原書只能自己在 etcd 存 ring、自己算 hash。Redis 7.0(2022)加入 SSUBSCRIBE/SPUBLISH:頻道像 key 一樣依 hash slot 放在某個 shard,cluster 自己處理分配與 failover。
Triton 補充073 · 101 · 039 · 049 · 「少一個模組」與 Erlang
要維運三組東西,還是兩組?Erlang 又怎麼看?
先猜:原書這樣做會出什麼事?原書的 Redis 版要維運 WebSocket servers、上百台 pub/sub、etcd 三組東西;Erlang 版只有一組。照 Triton 的原則會怎麼選?
073 的「越少模組越好」有兩半:要管的東西少,團隊要學的技術也少。按 → 看原文。
「越少模組,便代表 – 你需要監控和管理的模組便越少 – 代表你的團隊需要掌握的語言/技術便越少」🗣️ Triton 本人說 073-lesson3.pdf.md · 第 8 頁
「其實C10K的架構,真的只是Redis + Application Server(你喜歡什麼語言也行)+ RabbitMQ + RDBMS(不是MS的就好)」🗣️ Triton 本人說 101
🗣️ Triton 也提過 actor model:「把這種worker pool再延伸出去,就是Java Akka / Erlang他們談到的actor model(自己google啦) 在高concurrency和高robustness要求的系統很常用的手法。」039;「channel 機制是 concurrency 的核心 – Akka, Erlang 的 Actor Model也是相以的」049
🔭 依 Triton 原則推論
原書的 Redis 版要維運三組東西:WebSocket servers、上百台 pub/sub、etcd/Zookeeper。073 會先問「能不能少一個」:用 Redis 內建的 cluster 分配,etcd 這組就省了。Erlang 版元件最少,但它踩到 073 的另一半:「團隊需要掌握的語言/技術」。原書自己的結論(有 Erlang 專長才選)和這條原則一致;Triton 沒有直接評論過 Erlang 適不適合這題。
延伸基礎第 12 階 · batch懂的人可以跳過
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
郵差每封信都跑一趟,還是收滿一袋再去?
① 先想像
每秒有 300 封信寄到。郵差可以每封都跑一趟郵局,也可以收 5 秒、裝一袋再去。
你猜猜看:每秒 300 封,收滿 5 秒才送一趟。一趟帶幾封?
300 × 5 = 1,500。跑的趟數從每秒 300 趟變成每 5 秒 1 趟;代價是路上出事時,這一袋 1,500 封一起不見。
③ 這叫做 batch、flush
batch(批次):湊一批,一起處理。flush:把湊好的那一批,一次寫出去。
④ 跟這章的關係
Triton 117:位置歷史可以先在 server 的記憶體湊一批再寫(第 50 頁)。原書初始化時一次拿 400 個朋友的位置(第 23 頁),也是批次。
② 動手玩:每秒 300 封,多久送一趟?
Triton 補充(推論)117 喵看 Data 的思維 · 位置歷史
每秒 33 萬筆位置歷史:可以掉一點,就先在記憶體裡湊一批
先猜:原書這樣做會出什麼事?位置歷史每秒 33 萬筆、偶爾掉一點沒關係。原書每次更新就寫一次資料庫。Triton 會建議?
117:不需要 consistency 的東西別用 RDBMS;可以掉一點的,先 buffer 在記憶體再 flush。按 → 看原文。
🗣️ Triton 本人說 談 data 先問三件事:Consistency「到底這份data是否錯一點也沒所謂的?」、Durability「你這份資料打算用多久?」、Usage「這份資料的Read freq和Write freq是多少?」117
「不需要Consistency的東西就別用RDBMS來存啦。 RDBMS為了Strong Consistency犧牲了很很很多的效能。 (當然,如果你的系統流量是 100 RPS以下的,你所有東西全用postgresql也沒什麼差)」🗣️ Triton 本人說 117-喵看Data 的思維.md
「把要寫到UserStatistics的改動都buffer在Application Server的local memory,再用background thread把改動一點一點flush到DB。 (這方案如果AS斷電會有data loss風險。不過嘛UserStatistics不見了一點點是死不了人的)」「(沒10K RPS前別做這種事)」🗣️ Triton 本人說 117
🗣️「再三警告:流量不夠大請勿用上noSQL」117
🔭 放回這章
位置歷史符合 117 的三個問題:錯一點沒關係(原書:偶爾遺失可接受)、要留給機器學習、寫入極高且只 append。所以原書選 Cassandra 和 117 同方向;334K 遠超過「10K RPS」,也不是「流量不夠大」。差別在寫法:原書第 3 步每次更新就寫一次 DB;照 117,先在 server 記憶體裡湊一批再 flush,代價是那台掛掉時丟掉最後幾秒。原書說歷史和這個功能「沒有直接關係」,它其實也可以完全離開即時路徑(例如經 MQ 交給 worker 批次寫入)。
到這裡你已經會了小結 4 / 4
- 位置回報
- 半徑
- fan-out
- WebSocket
- TTL
- pub/sub
- shard
- consistent hashing
- hotspot
- geohash
- Signal
- batch
到這裡你已經會了:Triton 怎麼看這一章
- 朋友的位置是 Signal:可以丟、不用補,Redis Pub/Sub 正好。這點 Triton 同意原書。
- 照 Triton 的原則:WebSocket 只負責推,寫入走 stateless REST;每台 WebSocket server 對 Redis 共用一條連線。
- 真正的熱點在人擠的 geohash 格子;位置歷史可以 batch 寫入,丟最後幾秒沒關係。
12 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
朋友的位置是門鈴:響一次就好,漏了 30 秒後會再響;
別把門鈴當包裹存起來,也別讓按門鈴的機器天天重開。
原書對的地方
- 偶爾遺失可接受 → Redis Pub/Sub(Signal)
- 最新位置只放 Redis、TTL = 不活躍逾時
- 初始化批次讀 cache
- CPU 是瓶頸;pub/sub cluster 當 stateful
- consistent hashing,換一台只搬一台的頻道
情境差異
- WebSocket server 裡有歷史、cache、初始化邏輯 → 每次部署都斷線
- 每個 handler 各自連 Redis → 連線數爆炸
- geohash 頻道在人擠的地方是 hot key
- 「值班人員」換 server 還不算 HA
照 Triton 原則的做法
- 寫入走 stateless REST,WebSocket 只推
- 每台 WS server 一條訂閱連線 + dispatcher
- 先估最擠的格子有幾人,再決定推還是查
- 位置歷史湊一批再寫;能用內建的 cluster 就別自建 ring
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)與原書對照
Triton 本人的講義 / 文章
- 078-mq-intro.pdf.md — Signal vs Message、正常 MQ 先寫 HDD 才回應、Redis PubSub = 刪掉 persistence 的 MQ、斷線期間不保留、可用在 Signal;MQTT 警告
- 090-restful-demo.pdf.md — WebSocket 只接收 push、App logic 會逼你部署、「以上二者都不是好主意」、出牌走 RESTful、LB 依 gameId consistent hashing
- 062-im-system design.pdf.md — 共用一個 MQ connection + message dispatcher;不是給上百萬在線用戶的設計
- 087-redis-2019.pdf.md — 一份資料只在一個 node、single thread、hotspot 沒法加硬體解決;Hot Data 沒了死不了人;consistent hash(cluster 內建);不同 key 在不同機器
- 088-redis-intro.pdf.md — cache without TTL、no connection pool、MGET 批次讀取
- 029-Redis.md(課堂內容)— 單台 Redis 約 C10K、C100K 的資料必死、不要自己算 hash
- 182 — 單一 sorted set 只在一台、開罐罐派對;064 — 了解 N
- 017 — stateless vs stateful、Redis 當 stateful、HA 不需人類即時行動、用別人做好的方案
- 117 — 不需 consistency 別用 RDBMS、local buffer 再 flush、10K RPS、流量不夠大別用 noSQL;146 — 先 GET 再用 WebSocket append
- 073 — 越少模組越好;101 — C10K 架構;039、049 — Akka / Erlang actor model
沒有引用:179(作者不明,含 NAT idle timeout 的說法);187–195(AI 生成);092、095(Roy 的專案報告,雖然提到 Pub/Sub)。
原書前後不一致的地方
334K × 400 × 10% 精確是 1,336 萬,原書寫 1,400 萬(27);Redis 推送對象是「在線」朋友,距離在推完才算,原書卻用「在線且附近」的 10%(17);Figure 7、9、10、11 的 alt 與內文不符,已在圖說註明;Figure 12 alt 的四個 geohash 不構成 2×2。
原書對照
Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.2。開場與 Figure 1(第 4 頁)、Step 1 需求(7)、估算(8)、Figure 2–3 與後端責任(10)、Proposed design、LB、API、WebSocket 與 Figure 4–5(13)、location cache、user DB、history DB、pub/sub 與 Figure 6(16)、Periodic location update 與 Figure 7(17)、Figure 8(18)、API design(19)、Data model 與 Table 1(20)、API/WebSocket servers 擴展(22)、Client initialization(23)、User DB 與 location cache 擴展(25)、Redis pub/sub server(26)、記憶體與 CPU 估算(27)、分散式 cluster、service discovery 與 Figure 9–10(29)、Scaling considerations(30)、Operational considerations 與 Figure 11(31)、Adding/removing friends、Users with many friends(33)、Nearby random person 與 Figure 12–14(35)、Erlang(36)、Wrap up 與心智圖(37)。15 張圖都依原書圖說與 alt 重繪,不是原圖;Figure 1 是截圖,改畫線框。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 12 階:位置回報(5)、半徑(6)、fan-out(9)、WebSocket(12,複習第 12 章)、TTL(14)、pub/sub(15)、shard(24,複習第 1 章)、consistent hashing(28,複習第 5 章)、hotspot(32,複習第 4 章)、geohash(34)、Signal(40,複習第 12 章)、batch(49);小結(11、21、38、51);名詞小卡(53)。延伸基礎頁的數字是示意。