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)。點地圖可以移動你自己。

0:00模擬時間(1 秒 = 1 分鐘)0附近的朋友0每分鐘收到的更新0平均位置誤差

學習地圖本章的概念階梯

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

  1. 1位置回報每 30 秒報一次
  2. 2半徑5 英里內才算
  3. 3fan-out一則轉給很多人
  4. 4WebSocket不掛斷的對講機
  5. 5TTL會自己撕掉的便利貼
  6. 6pub/sub每人一台小電台
  7. 7shard白板分成好幾塊
  8. 8consistent hashing圓形大樓找教室
  9. 9hotspot擠爆同一支電話
  10. 10geohash地圖格子編號
  11. 11Signal門鈴不是包裹
  12. 12batch收滿一袋再送

第 1–3 階 · 位置怎麼送、多近算附近

要回答:一次報位置,系統要轉幾份?

第 4–6 階 · 原書的三個零件

要回答:連線、最新位置、轉送各用什麼?

第 7–10 階 · 規模變大

要回答:上百台機器怎麼分工、哪裡會擠爆?

第 11–12 階 · Triton 的看法

要回答:哪些可以丟、哪些要湊一批?

全程只用一個情境:演唱會散場找朋友(虛構)

手機報一次位置 = location update「附近」那個圓 = radius不掛斷的對講機 = WebSocket集合點白板上的便利貼 = location cache每人一台小電台 = Redis pub/sub

每爬 3–4 階,有一頁「到這裡你已經會了」。前幾章講過的詞(WebSocket、shard、hotspot…)只複習一頁,並附上原本那一章的連結。

原書開場Figure 1 · 和 Proximity Service 差在哪

附近的朋友:清單上有距離,也有「多久前更新」

這一步要解決的問題找朋友和找餐廳差在哪?為什麼要另開一章?

📖 原書 為「附近的朋友」這個新功能設計可擴展的後端。使用者選擇加入(opt-in)並授權位置後,App 顯示地理位置接近的朋友清單。真實例子是 Facebook App 的同名功能(原書參考 [1] TechCrunch 2014 年的報導)。

📖 原書 為什麼要另開一章?

看起來像上一章的 proximity service,但有一個關鍵差異:

Proximity serviceNearby friends
要找的東西商家朋友
位置靜態,地址不會變動態,使用者位置經常改變

白話:opt-in=自己按「我要用」才開;後端=手機看不到、在機房裡做事的那一端。

文組翻譯:找餐廳像查電話簿,翻一次就好;找朋友像看即時轉播,要一直有人告訴你最新位置。所以這章的主角不是「索引」,而是「怎麼把更新送出去」。

📖 原書 Figure 1Facebook's nearby friends(原圖是 App 截圖,這裡依 alt 重繪成線框,不畫商標與頭像)

延伸基礎第 1 階 · 位置回報懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

散場了,你怎麼讓朋友知道你在哪?

① 先想像

你在群組裡說「我在 B 出口」。走了幾步,過 30 秒再報一次。人走路很慢,30 秒只差幾十步。

你猜猜看:1,000 人每 30 秒各報一次位置,伺服器每秒收到幾則?

③ 這叫做 location update、經緯度

location update:手機定期送出「我現在在哪」。經緯度(latitude/longitude):地球上的座標,像棋盤的第幾行、第幾列。

④ 跟這章的關係

原書:1,000 萬人同時在線、每 30 秒報一次,每秒約 33 萬則(第 8 頁)。

② 動手玩:多少人、多久報一次


      
33伺服器每秒收到幾則47 公尺兩次回報之間你走了多遠

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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

多近才算「附近」?以你為中心畫一個圓

① 先想像

你說:「5 公里內的朋友,一起去吃宵夜。」要先知道每個朋友離你多遠。

你猜猜看:小美在你東邊 3 公里、北邊 4 公里。直線距離幾公里?

③ 這叫做 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=每天有幾個人用(第 2 章);同時在線=同一秒掛在線上的人;QPS=每秒幾則(第 2 章)。

📖 原書Calculate QPS
DAU100 million
Concurrent users10% × 100 million = 10 million
回報頻率每 30 秒一次
Location update QPS10 million ÷ 30 = ~334,000

動手算:刷新間隔換成多少才合理?

333,333

location update QPS

原書寫 ~334,000(無條件進位)。這個數字後面會一直出現:location cache 要扛它、Redis Pub/Sub 要把它乘上朋友數。

延伸基礎第 3 階 · fan-out懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

你報一次位置,系統要轉給幾個人?

① 先想像

你有 400 個朋友,此刻在線上的有 40 個。你每報一次,系統就要把它複製 40 份,一份一份送出去。

你猜猜看:你每 30 秒報一次,有 40 個在線朋友。一分鐘內系統要送出幾份?

③ 這叫做 fan-out

fan-out(扇出):一則進來,複製成很多份送出去,像扇子打開。

④ 跟這章的關係

原書:每秒 33 萬則 × 每則約 40 份 ≈ 每秒 1,400 萬次轉送(下一頁)。「乘上朋友數」整章都會出現。

② 動手玩:一則進來,幾份出去

0進來幾則0送出幾份80每分鐘送出(每 30 秒報一次)

原書 Step 2High-level design · Figure 2、3

朋友之間直接連線?不切實際;改成共用的後端

這一步要解決的問題一則位置更新,要怎麼送到所有朋友手上?

📖 原書 Figure 2Peer-to-peer:七支手機互相直連的 mesh(依原書內容重繪;連線位置為示意)

📖 原書 原書這章先講高階設計,再講 API 和資料模型:因為要把位置推給所有朋友,client 和 server 之間不會是單純的 HTTP,不先懂架構就說不清 API 長怎樣。

📖 原書 概念上是高效率的訊息傳遞。理論上可以純 peer-to-peer:每人和附近每個在線朋友維持一條持久連線(Figure 2)。但手機連線不穩、耗電預算很緊,不實際;不過這個想法點出了方向。

📖 原書 Figure 3 後端的責任

  1. 接收所有活躍使用者的位置更新
  2. 每次更新,找出所有應該收到它的活躍朋友,轉送到他們的裝置
  3. 兩人距離超過門檻,就不轉送

📖 原書 聽起來簡單,難在規模:每秒 334K 次更新 × 400 個朋友 × 約 10% 在線且在附近 = 每秒轉送 1,400 萬次。所以原書先畫一個小規模的設計,再到 deep dive 擴展。

白話:peer-to-peer=手機之間直接連,不經過伺服器;持久連線=接通後一直不掛斷;deep dive=深入細節那一段。

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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

到這裡你已經會了:位置怎麼送、多近算附近

下一階要解決的問題

手機和伺服器之間要用什麼線連著,伺服器才能隨時把朋友的新位置「推」過來?

延伸基礎 · 複習第 4 階 · WebSocket第 12 章講過懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

一直打電話問,還是對講機一直開著?

① 先想像

你想知道小美在哪。可以每 5 秒打一次電話問她;也可以兩人的對講機一直開著,她一動就說。

你猜猜看:小美每 30 秒才換一次位置。你每 5 秒打電話問,5 分鐘內有幾通是白問?

④ 跟這章的關係

原書:位置更新全走 WebSocket;WebSocket server 是 stateful,要拿掉一台得先「排空」(第 13、22 頁)。

② 動手玩:5 分鐘內,你的手機做了什麼

60你打出去的電話10真的拿到新位置50白問

原書 Step 2Proposed design · Figure 4、5

兩條路:WebSocket 管位置,RESTful API 管其他

這一步要解決的問題「位置更新」和「加朋友」這兩種事,要不要走同一條路?

📖 原書 Figure 4High-level design(依原書內容重繪)

📖 原書 先畫一個較小規模、能滿足功能需求的設計(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懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

集合點白板上的便利貼,10 分鐘沒換就撕掉

① 先想像

散場後大家在集合點白板貼便利貼:「小明 · B 出口 · 21:30」。規定:10 分鐘沒貼新的,就撕掉。

你猜猜看:小明 21:30 貼完最後一張就沒電關機。21:35 白板上還有他嗎?21:41 呢?

③ 這叫做 cache、TTL

cache:放手邊的小抄,拿得快(第 1 章)。TTL(time to live):小抄的保存期限,時間到自動消失。

④ 跟這章的關係

原書:location cache 每人一筆最新位置、TTL 10 分鐘,每次回報就刷新。TTL 到了,就是「不活躍就不顯示」(第 20 頁)。

② 動手玩:點名字讓他關機,再按「過 1 分鐘」

21:30現在時間

延伸基礎第 6 階 · pub/sub懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

每人一台小電台,朋友把收音機調過來

① 先想像

每個人有一台只播自己位置的小電台。想知道小美在哪,就把收音機調到「小美台」。

你猜猜看:你的電台有 2 個朋友在聽,其中阿傑關機了。你播一次位置,阿傑開機後聽得到這一次嗎?

③ 這叫做 pub/sub、channel

pub/sub:publish(播出)+ subscribe(訂閱)。channel:頻道,這章是一人一個。

④ 跟這章的關係

原書:每人一個 Redis pub/sub 頻道,朋友那邊的 handler 訂閱它(下一頁 Figure 6)。Redis 就是放在記憶體裡的共用白板(第 4 章)。

② 動手玩:誰在聽你的電台?

0你播了幾次0送到幾份0關機錯過

原書 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=不是傳統表格的那一類資料庫;訊息匯流排=大家把訊息丟上去、由它轉送的公共管道。

📖 原書 Figure 6Redis Pub/Sub(依原書內容重繪)

一個頻道可以有很多訂閱者:User 2 的頻道有兩個訂閱者。

文組翻譯:每個人有一台自己的「廣播電台」,只播自己的位置。朋友把收音機調到你的頻率;你一開口,所有正在聽的朋友同時聽到。沒人在聽的時候,你講的話就散在空氣裡。

原書 Step 2Periodic location update · Figure 7

一次位置更新,從手機到朋友的手機要走 8 步

這一步要解決的問題把前面的零件串起來:一次更新到底經過哪幾站?按「下一步」一站一站看。

📖 原書 Figure 7Periodic location update(依原書內容重繪;alt 的編號和元件對不太上,這裡依內文步驟 1–7 標號,第 8 步原書也沒畫)
  1. 手機把位置更新送到 load balancer
  2. LB 把它轉給這個 client 在 WebSocket server 上的持久連線
  3. WebSocket server 把位置存進 location history database
  4. 更新 location cache 裡的新位置並刷新 TTL;同時存在這個使用者的 connection handler 變數裡,給之後算距離用
  5. 發佈到 Redis pub/sub 裡這個使用者的頻道。步驟 3–5 可以平行執行
  6. Redis pub/sub 把更新廣播給所有訂閱者(WebSocket connection handlers),也就是這個人所有在線的朋友
  7. handler 所在的 WebSocket server 計算距離:發送者的位置在訊息裡,訂閱者的位置在 handler 的變數裡
  8. (圖上沒畫)距離沒超過半徑,就把新位置和最後更新時間送給訂閱者的 client;否則丟掉

原書 Step 2具體例子 · Figure 8

User 1 動了:User 2、3、4 的 handler 各自算一次距離

這一步要解決的問題換成具體的人:誰會收到、誰被丟掉?

📖 原書 Figure 8Send location update to friends(依原書內容重繪;✓/✗ 的距離結果是示意)

📖 原書 假設

  • User 1 的朋友:User 2、3、4
  • User 5 的朋友:User 4、6
  1. User 1 位置改變,更新送到握著 User 1 連線的 WebSocket server
  2. 位置發佈到 Redis pub/sub 裡 User 1 的頻道
  3. Redis pub/sub 廣播給所有訂閱者,這裡是 WebSocket connection handlers(User 1 的朋友們)
  4. 發送者(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 APIRequestResponse / 送出的資料
1Periodic location updateclient 送 latitude、longitude、timestamp無
2Client receives location updates—朋友的位置資料和時間戳
3WebSocket initializationclient 送 latitude、longitude、timestampclient 收到朋友們的位置資料
4Subscribe to a new friendWebSocket server 送 friend ID朋友最新的 latitude、longitude、timestamp
5Unsubscribe a friendWebSocket 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 到了就消失

這一步要解決的問題最新位置要存成什麼樣子?歷史位置又放哪?

📖 原書 Table 1Location cache
keyvalue
user_id{latitude, longitude, timestamp}

📖 原書 存所有開啟這個功能的活躍使用者的最新位置,用 Redis。

📖 原書 為什麼不用資料庫存位置?

  • 這個功能只在乎現在的位置,每人只要存一筆
  • Redis 讀寫超快,而且支援 TTL,用來自動清掉不再活躍的人
  • 現在位置不需要持久保存。Redis 掛了就換一台空的,讓新的更新把它填滿;活躍使用者可能錯過朋友一兩個週期的更新,可以接受的取捨(deep dive 再談怎麼減少影響)
TTL 模擬(10 分鐘)點一列讓那個人關掉 / 打開 App
0:00模擬時間(1 秒 = 30 秒)

📖 原書 Location history database

user_idlatitudelongitudetimestamp

要能扛大量寫入、可以水平擴展:Cassandra 是好選擇。也可以用關聯式資料庫,但歷史資料放不進一台,要 shard;最基本是依 user ID 分片,負載平均、維運也簡單。

白話:Cassandra=擅長大量寫入、可以一直加機器的資料庫;shard/分片=依 user ID 分到好幾台(第 24 頁複習)。

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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

到這裡你已經會了:原書的三個零件

下一階要解決的問題

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,移除節點要小心:

  1. 在 load balancer 把節點標成 “draining”,新的 WebSocket 連線不再導過去
  2. 等現有連線全部關閉(或等一段合理的長時間)
  3. 再移除這台 server

📖 原書 在 WebSocket server 上發佈新版本也要同樣小心。有效地自動擴展 stateful server 是好的 load balancer 的工作,多數雲端 LB 都做得很好。

白話:draining=「這台不再接新連線」,等舊的自己走;發佈新版本=把新程式換上去,要重啟。

原書 Step 3Client initialization

連上 WebSocket 的那一刻,handler 要做 7 件事

這一步要解決的問題剛打開 App、什麼都還沒收到,畫面上的朋友從哪來?

📖 原書 手機啟動時和某一台 WebSocket server 建立持久連線。每條連線都跑很久;多數現代語言都能用很小的記憶體維持大量長連線。連線初始化時 client 送出初始位置,server 在 connection handler 裡:

  1. 更新 location cache 裡這個人的位置
  2. 把位置存在 handler 的變數裡,給之後計算用
  3. 從 user database 載入這個人所有的朋友
  4. 對 location cache 發一個批次 request 拿所有朋友的位置。TTL 等於不活躍逾時,不活躍的朋友不會在 cache 裡
  5. 對 cache 回傳的每個位置算距離;在半徑內,就把朋友的 profile、位置、最後更新時間從 WebSocket 回給 client
  6. 訂閱每個朋友在 Redis pub/sub 的頻道。建頻道很便宜,所以活躍和不活躍的朋友都訂閱;不活躍的只佔一點記憶體,不吃 CPU 和 I/O(他們不發佈)
  7. 把自己現在的位置發佈到自己的頻道

白話:批次 request=一次問 400 個朋友,不是問 400 次;profile=名字、大頭貼這些個人資料。

延伸基礎 · 複習第 7 階 · shard第 1 章講過懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

一塊白板貼不下:依會員編號分成四塊

① 先想像

1,000 萬張便利貼,一塊白板貼不下,一個人也寫不完。改成四塊白板,看會員編號除以 4 的餘數決定貼哪一塊。

你猜猜看:會員編號 1,002 的便利貼貼在第幾塊?(從第 0 塊算起,看除以 4 的餘數)

④ 跟這章的關係

原書: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=公司裡別的團隊開的窗口。

~1 GB10M × 100 bytes83K每個 shard 每秒寫入

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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

加開一台機器,要搬多少個頻道?

① 先想像

頻道用「除以 4 的餘數」分給 4 台機器。人變多,加成 5 台,改成「除以 5」。

你猜猜看:「除以 4」改成「除以 5」,大概多少頻道要換機器?

④ 跟這章的關係

原書:上百台 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,每個頻道要去哪一台找?

📖 原書 Figure 9Consistent hashing(依原書內容重繪;alt 描述的圓圈數彼此矛盾,這裡依內文畫成 4 台 server 加 3 個落在 p_1 區段的頻道)

📖 原書 頻道彼此獨立,依發佈者的 user ID shard 到多台 server 相對容易。但幾百台 server 一定會不時當機,要說清楚怎麼做才好維運。於是加入 service discovery(最常見的是 etcd [4] 和 Zookeeper [5])。只需要兩個基本功能:

  1. 在 service discovery 裡存一份 server 清單,有簡單的 UI 或 API 可以更新。本質上它是存設定的小 KV store:
    Key:   /config/pub_sub_ring
    Value: ["p_1", "p_2", "p_3", "p_4"]
  2. 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 應該會有一波尖峰。

0%頻道換了 server0全站要重新訂閱(1 億頻道 × 40)

原書 Step 3Operational considerations · Figure 11

換掉一台壞掉的 server,風險低得多

這一步要解決的問題一台 pub/sub 壞掉了,怎麼換掉又不驚動全部人?

📖 原書 Figure 11Replace pub/sub server(依原書內容重繪;alt 說成「加入新節點」,依內文這是把 p_1 換成 p_1_new,ring 大小不變)

📖 原書 替換一台既有的 pub/sub server,不會讓大量頻道搬家,只有被替換那台上的頻道要處理。這很好,因為 server 一定會當機、要定期替換。

  1. pub/sub server 掛掉時,監控軟體通知值班人員(怎麼監控超出本章範圍)
  2. 值班人員更新 service discovery 裡的 hash ring key,把死掉的節點換成一台新的 standby
  3. WebSocket servers 收到通知,再通知各自的 connection handlers 到新 server 重新訂閱
  4. 每個 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 章講過懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

一個頻道只住一台:太多人聽同一台會怎樣?

① 先想像

四支總機各管一部分電台。大部分人只有幾十個朋友在聽;某位大明星的電台,卻有 100 萬人在聽。

你猜猜看:大明星每 30 秒播一次,100 萬人在聽。他那支總機每秒要送幾份?

④ 跟這章的關係

原書:朋友上限 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=朋友特別多的大戶。

500每次更新要推幾份16.7這個頻道每秒推送5平均每台 WS server 分到(共 100 台)

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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. 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 當頻道

這一步要解決的問題加分題:想看到附近的陌生人,頻道要怎麼切?

📖 原書 Figure 12Redis pub/sub channels(依原書內容重繪;原圖底圖是 OpenStreetMap 街道,這裡畫成示意街區。alt 列的四個 geohash 照抄,但依編碼 9q8znf 和 9q8zn3 並不構成 2×2)

📖 原書 可以當成 extra credit,不在原本的功能需求裡:如果面試官想顯示選擇分享位置的隨機陌生人呢?

📖 原書 沿用現有設計:加一組依 geohash 劃分的 pub/sub 頻道(geohash 見 Proximity Service 那章)。Figure 12 把一個區域分成四個 geohash 格子,每格一個頻道;格子裡的每個人都訂閱同一個頻道。

  1. 以 9q8znd 為例(Figure 13):User 2 更新位置時,handler 算出他的 geohash ID,把位置送到那個 geohash 的頻道
  2. 附近訂閱這個頻道的人(不包括發送者)都收到位置更新

📖 原書 靠近格子邊界的人怎麼辦?每個 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

原書的收尾:把一個人的位置,有效率地送給他的朋友

這一步要解決的問題回頭看一遍:這章到底解決了什麼?

📖 原書 Chapter Summary本章心智圖(依原書內容重繪;alt 把非功能需求只寫了 low latency,這裡照 alt)

📖 原書 核心元件:

  • WebSocket:client 和 server 之間的即時通訊
  • Redis:位置資料的快速讀寫
  • Redis pub/sub:路由層,把一個人的位置更新導向所有在線的朋友

📖 原書 先在較小規模提出高階設計,再討論規模變大時的挑戰,探討了怎麼擴展:RESTful API servers、WebSocket servers、資料層、Redis pub/sub servers,以及 Redis pub/sub 的替代方案。

📖 原書 最後討論了朋友很多的使用者可能造成的瓶頸,並提出「附近隨機陌生人」的設計。

原書最後一句:恭喜你讀到這裡,給自己拍拍肩膀。

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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

到這裡你已經會了:規模變大之後

下一階要解決的問題

原書的部分講完了。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 章講過懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

朋友的位置,是門鈴還是包裹?

① 先想像

門鈴響一下,沒聽到就算了,等下次再響;包裹不能丟,沒收到要重送。

你猜猜看:你過隧道 2 分鐘,小美的位置在這期間更新了 4 次。出隧道時要把這 4 次都補給你嗎?

④ 跟這章的關係

Triton:Redis Pub/Sub 適合傳 Signal(第 41 頁)。原書的需求「偶爾遺失可以接受」,剛好就是 Signal。

② 動手玩:分分看,門鈴還是包裹?(點卡片看答案)

Triton 同意 · 動手玩078 MQ 淺談 · Signal vs Message

✅ 同意原書 朋友的位置是 Signal:斷線時漏掉的,不用補

4斷線期間的更新1重連後收到幾則0其中已過時

先猜:原書這樣做會出什麼事?原書選 Redis Pub/Sub:不存訊息,斷線期間的更新就漏掉了。Triton 會怎麼說?

「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—重連時的初始化(MGET+SUBSCRIBE)

「如果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 那邊總共有幾條連線?

「不管 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 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 萬人的最新位置全沒了。要緊嗎?

「正常人使用 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 嗎?

📖 原書 第 31 頁的流程

  1. pub/sub server 掛掉,監控軟體通知值班人員
  2. 值班人員更新 service discovery 裡的 hash ring key
  3. 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 來分配」會怎麼說?

「別使用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 的原則會怎麼選?

「越少模組,便代表 – 你需要監控和管理的模組便越少 – 代表你的團隊需要掌握的語言/技術便越少」🗣️ 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懂的人可以跳過

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

郵差每封信都跑一趟,還是收滿一袋再去?

① 先想像

每秒有 300 封信寄到。郵差可以每封都跑一趟郵局,也可以收 5 秒、裝一袋再去。

你猜猜看:每秒 300 封,收滿 5 秒才送一趟。一趟帶幾封?

③ 這叫做 batch、flush

batch(批次):湊一批,一起處理。flush:把湊好的那一批,一次寫出去。

④ 跟這章的關係

Triton 117:位置歷史可以先在 server 的記憶體湊一批再寫(第 50 頁)。原書初始化時一次拿 400 個朋友的位置(第 23 頁),也是批次。

② 動手玩:每秒 300 封,多久送一趟?

12每分鐘跑幾趟1,500一趟帶幾封1,500路上出事最多丟幾封

Triton 補充(推論)117 喵看 Data 的思維 · 位置歷史

每秒 33 萬筆位置歷史:可以掉一點,就先在記憶體裡湊一批

先猜:原書這樣做會出什麼事?位置歷史每秒 33 萬筆、偶爾掉一點沒關係。原書每次更新就寫一次資料庫。Triton 會建議?

🗣️ 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

  1. 位置回報
  2. 半徑
  3. fan-out
  4. WebSocket
  5. TTL
  6. pub/sub
  7. shard
  8. consistent hashing
  9. hotspot
  10. geohash
  11. Signal
  12. batch

到這裡你已經會了:Triton 怎麼看這一章

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

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

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

location update手機定期送出「我現在在哪」
經緯度地球上的座標(latitude/longitude)
timestamp這筆位置是幾點幾分記的
QPS每秒進來幾則
DAU每天有幾個人用
concurrent users同一時間在線上的人
radius「附近」那個圓的半徑,原書 5 英里
直線距離兩點之間拉直線量,不管路怎麼繞
fan-out一則進來,複製成很多份送出去
peer-to-peer手機之間直接連,不經過伺服器
latency等多久才收到
eventual consistency各副本先各記各的,過幾秒再一致

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

引述來源(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)。延伸基礎頁的數字是示意。

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