Messenger 即時通訊 (Design Messenger)

1. 釐清需求與範圍 (Clarify & Scope ~5 min)

開場後先框邊界，別急著畫 WebSocket 連線圖。即時通訊題最容易在「協定」「分片」「順序」三點翻車，先問清楚這三點要不要做：

2. 功能性與非功能性需求 (FR / NFR 與設計北極星)

• 功能性需求 (FR)
  • 使用者可 建立群聊（多位參與者，上限 100 人）。
  • 使用者可 收發訊息。
  • 使用者 離線期間 別人送的訊息，上線後 仍能收到。
• 不在範圍 (Out of Scope)：傳附件、視訊通話、線上狀態（presence）。
• 非功能性需求 (NFR)
  • 低延遲：在線使用者 < 500ms 收到訊息。
  • 耐久性（Durability）：送出的訊息 不可遺失。
  • 一致性（Consistency）：同一 chat 內所有人看到 完全一致的訊息順序。
  • 規模 / 高吞吐：支援 1 億使用者。

設計北極星（NFR 直接導出後續所有選型的判準）：

3. 容量估算 (Back-of-Envelope ~4 min)

估算的目的是 驅動連線分片與寫入選型（估算 → 選型的 hand-off）。回連 02-Distributed-Systems/05-Numbers-to-Know。

並發連線（最關鍵的維度——連線即狀態）

1 億使用者，假設高峰 ~10% 同時在線 → ~1,000 萬並發 WebSocket 連線
WhatsApp 經驗：單一 host 可承載 ~100–200 萬連線（來源給出此基準）
→ 連線數 ÷ 每台容量 = 10,000,000 ÷ 1,500,000 ≈ 7 台（僅承載連線）
→ 實務含備援 / 不均，需「數百台」量級（來源用語：可能數百台）

寫流量（訊息吞吐）

假設每位在線使用者每天送 ~40 則訊息（推導值，來源未給）
1 億 × 40 = 40 億則/day ÷ 86,400 s ≈ 46,000 訊息/sec（寫）
群聊放大：每則訊息要 fan-out 給聊天內成員 → 推送量 = 寫 × 平均群人數

儲存

40 億則/day × ~300 bytes/則 ≈ 1.2 TB/day（推導值）
→ 訊息是高寫吞吐 + 持續增長 → NoSQL（DynamoDB）+ 分區，而非單機關聯式

下表並發連線基準（100–200 萬/台）來自來源；訊息量、儲存量為 推導值（由「使用者數 × 每人次數」「筆數 × 每筆大小」算出）。

4. 用到的積木 / Building Blocks Used

架構即目錄：先給導覽圖，再展開。下表每個決策都對映一個既有 concept note（無 alias 連結）；本表即「本案例練到哪些積木」的單一事實來源（single source of truth）。

5. API 設計 (API Design ~3 min)

因為用 WebSocket（雙向），API 不必遵循 REST 慣例——訊息是雙向的「message」而非 request/response 資源（理據見 01-Networking/05-Realtime-Protocols）。為簡化用 JSON 表示。

6. 資料模型與儲存選型 (Data Model & Storage Choice ~4 min)

三張核心表，全部圍繞「以 chat 為單位高效查詢」設計（故獨立成段）。

Chat
--------------------------------------------------
chat_id   STRING  PK              ← 唯一聊天識別碼
name      STRING  群聊顯示名稱
created_at TIMESTAMP
--------------------------------------------------

Membership                         ← 查「某 chat 有哪些人」的核心表
--------------------------------------------------
chat_id   STRING  Partition Key    ← 同一 chat 的成員聚在同一分區
user_id   STRING  Sort Key         ← (chat_id, user_id) 唯一
last_read_message_id  BIGINT       ← 已讀指標，離線補收 / 已讀回執靠它
--------------------------------------------------
   → 以 chat_id 為 partition key 可一次撈出整個 chat 的全部參與者

Message
--------------------------------------------------
chat_id    STRING  Partition Key   ← 同一 chat 訊息聚在一起、依序查詢
message_id BIGINT  Sort Key        ← monotonic increasing（時間序 + 唯一）
sender_id  STRING
body       STRING
created_at TIMESTAMP
--------------------------------------------------
   → 離線補收 = 查 message_id > last_read_message_id 的所有訊息

儲存選型：

→ 積木：NoSQL 高寫吞吐見 06-Database-Tech/03-DynamoDB；建群多筆原子寫見 05-Database-Advanced/01-Transactions；以 chat_id 分片見 05-Database-Advanced/02-Sharding。

7. 高階架構 (High-Level Design ~6 min)

把積木串成端到端。先看「建群」與「在線/離線兩條傳遞 flow」（簡化假設：所有人連同一台 server、用 local hash map user_id → WebSocket connection；億級分片留 §8）。

(A) 建群 flow（createChat）

Client ──WebSocket── Chat Server
   │  createChat { participants, name }
   ▼
Chat Server （同一 DB transaction 內）
   │ 1. INSERT Chat(chat_id, name)
   │ 2. 為每位 participant INSERT Membership(chat_id, user_id, last_read=0)
   ▼
回傳 { chatId }

(B) 在線傳遞 flow（recipient online）

Sender ──sendMessage{chatId, message}──► Chat Server
                                            │ 1. 寫入 Message table
                                            │    （message_id = monotonic increasing）
                                            │ 2. 查 Membership(chat_id) 取得所有參與者
                                            │ 3. 回 SUCCESS/FAILURE 給 sender
                                            │ 4. 逐一查每位參與者的 WebSocket connection
                                            ▼  並 push newMessage
                              在線接收者 ◄── newMessage{messageId, ...}
                                            │ 5. Client 回 ack{messageId}
                                            ▼
                              Chat Server 更新 Membership.last_read_message_id

(C) 離線傳遞 flow（recipient offline — store & forward）

接收者離線時：訊息已落在 Message table（durability 已達成）
        │
   接收者上線、重連 WebSocket
        ▼
   1. 查 Membership 取該 user 的 last_read_message_id
   2. 查 Message: message_id > last_read_message_id 的所有訊息
   3. push 給接收者
   4. Client 回 ack → 更新 last_read_message_id

(D) Scaled 架構（端到端 — 億級的 pub/sub by chat，詳見 §8）

   Sender Client ─┐
                  │ WebSocket
                  ▼
            ┌──────────────┐    Subscribe(chat_id)   ┌────────────────────────┐
            │  Gateway (stateless) ──────────────────►│  Pub/Sub Server (owner) │
            │  維護本地 WS 連線    │                   │  by shard = hash(chat_id)%S │
            └───────┬──────┘                          │  subscribers[chat_id] =  │
                    │ sender→gateway→pub/sub          │     [subscribing_gateways]│
                    ▼                                  │  指派 monotonic message_id│
        ┌────────────────────────┐                    └───────────┬────────────┘
        │ Service Discovery       │◄── heartbeat /                 │ fan-out 給 M 個
        │ (Zookeeper/Consul, Raft)│    shard ownership             ▼  subscribing gateways
        │ shard_id → pub/sub host │                    ┌────────────────────────┐
        └────────────────────────┘                    │ 其他 Gateways → Receiver │
                                                       └────────────────────────┘
        ┌─────────────────────────────────────────────────────────────────────┐
        │  DynamoDB:  Chat / Membership(chat_id PK) / Message(chat_id PK, msg_id SK)│
        └─────────────────────────────────────────────────────────────────────┘

關鍵 hand-off：gateway（stateless，持 WS 連線）→ pub/sub owner（by chat_id，順序權威 + fan-out）→ 其他 subscribing gateways → 接收者；service discovery 維護 shard_id → pub/sub host，gateway 本地快取。

8. 深入探討 (Deep Dives ~8 min)

8.1 協定選型：為何不能 polling，要 WebSocket

問題：即時通訊要 server 主動推送，但標準 HTTP 是 request-response、回完即關閉，不適合 server push。
為何是瓶頸：讓每個 client 每幾毫秒 poll 一次，基礎設施會被海量空回應壓垮。

選擇與理由：選 WebSocket。高頻雙向、低延遲、傳輸效率高（< 500ms 需求 polling 達不到）。代價是 連線即狀態 + 連線管理複雜——這正是 §8.2 的起點。
→ 積木：01-Networking/05-Realtime-Protocols、10-Design-Patterns/05-Real-time-Updates、01-Networking/03-HTTP-and-HTTPS

8.2 億級在線：user_id 分片 vs chat_id 分片（招牌取捨）

問題：需數百台 server（單台僅 100–200 萬連線）。發送者與接收者連到不同 host 時，如何定位接收者所在 host 以即時推送？

方案 A：以 user_id 為核心的 consistent hashing
每台 server 負責一段 user_id key space，連線平均分散；用 集中式強一致 service discovery（Zookeeper/Consul，Raft/Zab 共識） 維護 user_id → node，各節點本地快取。1-1 聊天理論可行，但規模一大就難維護：

1. 每則訊息要對 N 個接收者各發一次 RPC；大群聊每則可能數百~上千 RPC。
2. scale up/down 時除了 socket，還要重新分配 user_id 的 ownership，極難。
3. 最根本：以 user 分片，同一 chat 散在多個 owner（A 的訊息在 server 1、B 的在 server 2），幾乎無法強制單一訊息順序。

方案 B：以 chat_id 為核心的 pub/sub（解耦 socket 與 chat ownership）

shard_id = hash(chat_id) % S          （S = shard 數）
service registry:  shard_id → pub/sub server
pub/sub server 記憶體:  chat_id → [subscribing_gateways]
流程:  sender → gateway → pub/sub → subscribed gateways → receiver

• gateway 啟動時從 service discovery 載入 shard mapping 並本地快取、定期監聽更新。
• 使用者連上 gateway 並加入某 chat → gateway 向該 chat 的 owning pub/sub server 發 Subscribe(chat_id) → owner 把該 gateway 加入 subscribers[chat_id]。
• pub/sub server 用 heartbeat 向 service discovery 回報存活與 shard ownership。

選擇與理由：選 B（chat_id pub/sub）。它一次解決 fan-out 放大、gateway 無狀態擴展、以及最關鍵的訊息順序權威——這就是本題 core_tradeoff。
→ 積木：02-Distributed-Systems/04-Consistent-Hashing、09-Messaging-Coord/05-Zookeeper、09-Messaging-Coord/02-Queue、02-Distributed-Systems/03-Scalability

8.3 訊息亂序：為何用伺服器端 monotonic message_id

問題：同一 chat 兩人同時送訊息，如何確保所有人看到 一致順序？
為何是瓶頸：client 端時鐘有 clock skew，且 timestamp 不保證唯一（同毫秒多人送）——靠 client 時間排序必然亂。

解法：讓「接收並持久化訊息的 server」成為順序的 唯一真實來源。§8.2 的 pub/sub 正好提供此特性——同一 chat 全部路由到 同一 pub/sub owner，由它在處理時 指派 monotonic increasing 的 message_id 並持久化到 DB。

client 端收尾：若收到 late-arriving message（message_id 較小），client 在本地 重新排序 對話，確保呈現順序正確。
→ 積木：05-Database-Advanced/02-Sharding（chat 分片使單一 owner 可行）、06-Database-Tech/03-DynamoDB（message_id 當 sort key 天然有序）

8.4 不可遺失：持久化點與 ack 閉環

問題：訊息 durability——送出後不可丟。
做法：sendMessage 的 SUCCESS 語意是 已寫入 Message table（持久化點），而非「已送達」。送達靠 push newMessage；接收者收到回 ack → server 更新 last_read_message_id。離線者 的訊息早已在 Message table，上線後查 message_id > last_read_message_id 補收即可——store-and-forward 的真實來源是 DB，不是記憶體佇列。
→ 積木：12-Ops-and-Reliability/03-Reliable-Delivery

9. 擴展與瓶頸 (Scaling & Bottlenecks ~5 min)

主動找出系統會先在哪裂開並補強。

10. 取捨總表與收尾 (Trade-off Recap & Wrap-up ~2 min)

後續追問演練 (Interviewer Follow-ups — "What if…")

主動回想：白板重建 (Whiteboard from Scratch)

不看上文，照下面提示把整個設計重建一次。每格都該能 30 秒內口述。

• 0. Frame：一句話定位 + 宣告 35 min 配速 → __
• 1. Clarify：列 3 個必問問題（群聊人數？離線補收？順序一致？）→ __
• 2. FR / NFR：3 個 FR、4 個 NFR、一句話北極星 → __
• 3. 估算：並發連線 = ？ 單台容量 = ？ 結論（要幾台 / 用什麼 DB）= ？ → __
• 4. Building Blocks：默寫 ≥6 個決策→積木對映 → __
• 5. API：createChat / sendMessage / modifyChatParticipants / newMessage / ack → __
• 6. 資料模型：Chat / Membership(chat_id PK, user_id SK) / Message(chat_id PK, message_id SK) + last_read_message_id 用途 → __
• 7. 架構：建群 flow / 在線 flow / 離線 store-and-forward / scaled（gateway→pub-sub by chat→gateways）→ __
• 8. Deep Dives：polling vs WebSocket、user_id vs chat_id 分片、monotonic message_id 解亂序、durability+ack → __
• 9. Scaling：先在哪裂開（連線層）？consistent hashing / pub-sub / shard 重分配 / NoSQL → __
• 10. Recap：一句話招牌取捨 = ？ → __

常見陷阱 (Exam Traps for This Problem)

Related Notes

• 02-Distributed-Systems/05-Numbers-to-Know
• 02-Distributed-Systems/03-Scalability
• 02-Distributed-Systems/04-Consistent-Hashing
• 01-Networking/05-Realtime-Protocols
• 01-Networking/02-TCP-vs-UDP
• 01-Networking/03-HTTP-and-HTTPS
• 10-Design-Patterns/05-Real-time-Updates
• 09-Messaging-Coord/02-Queue
• 09-Messaging-Coord/05-Zookeeper
• 05-Database-Advanced/01-Transactions
• 05-Database-Advanced/02-Sharding
• 06-Database-Tech/03-DynamoDB
• 12-Ops-and-Reliability/03-Reliable-Delivery