在這一章中，我們將探討聊天系統（chat system）的設計。幾乎每個人都在使用聊天 App。圖 1 顯示了市場上一些最受歡迎的 App。

聊天 App 對不同的人來說會執行不同的功能。確定明確的需求極為重要。例如，當面試官心中想的是一對一聊天時，你不會想設計一個專注於群組聊天的系統。釐清功能需求十分重要。

Step 1 - Understand the problem and establish design scope#

對於要設計什麼類型的聊天 App 達成共識至關重要。市面上有多種類型：

• 一對一聊天 App，例如 Facebook Messenger、WeChat、WhatsApp
• 辦公室群組聊天 App，例如 Slack
• 遊戲聊天 App，例如 Discord，專注於大型群組互動與低延遲語音聊天

第一組釐清問題應該要明確界定，當面試官請你設計一個聊天系統時，她心中具體想的是什麼。至少要先弄清楚你應該專注於一對一聊天還是群組聊天 App。你可以詢問的一些問題如下：

應徵者：我們要設計什麼樣的聊天 App？一對一還是群組？

面試官：兩者都要支援。

應徵者：這是行動 App 嗎？還是 Web App？或兩者都是？

面試官：兩者都是。

應徵者：這個 App 的規模有多大？是新創 App 還是大規模的？

面試官：應該要支援 5,000 萬的日活躍使用者（DAU）。

應徵者：對於群組聊天，群組成員上限是多少？

面試官：最多 100 人。

應徵者：聊天 App 哪些功能很重要？是否支援附件？

面試官：一對一聊天、群組聊天、線上指示器。系統只支援文字訊息。

應徵者：訊息有大小限制嗎？

面試官：有，文字長度應少於 100,000 個字元。

應徵者：是否需要端對端加密（end-to-end encryption）？

面試官：目前不需要，但如果時間允許我們可以討論。

應徵者：我們應該保存聊天紀錄多久？

面試官：永久保存。

在本章中，我們專注於設計一個類似 Facebook Messenger 的聊天 App，重點放在以下功能：

• 低傳遞延遲的一對一聊天
• 小型群組聊天（最多 100 人）
• 線上狀態（online presence）
• 多裝置支援，同一個帳號可以同時登入多台裝置
• 推播通知（push notifications）

對於設計規模達成共識也很重要。我們將設計一個支援 5,000 萬 DAU 的系統。

Step 2 - Propose high-level design and get buy-in#

要發展出高品質的設計，我們應對 client 與 server 如何通訊有基本的了解。在聊天系統中，client 可以是行動應用程式或 Web 應用程式。Client 之間並不直接通訊，而是每個 client 都連線到一個聊天服務（chat service），由它支援上述所有功能。

讓我們專注在基本操作。聊天服務必須支援以下功能：

• 接收來自其他 client 的訊息
• 為每則訊息找到正確的接收者，並將訊息轉送給接收者
• 如果接收者不在線上，將訊息暫存在伺服器上，直到她上線為止

圖 2 顯示了 client（傳送者與接收者）與聊天服務之間的關係。

當 client 想要開始聊天時，它會使用一種或多種網路協定連線到聊天服務。對於聊天服務來說，網路協定的選擇非常重要。讓我們和面試官討論一下。

對大多數 client/server 應用程式來說，請求都是由 client 發起的。對於聊天應用程式的傳送端來說也是如此。在圖 2 中，當傳送者透過聊天服務向接收者傳送訊息時，它使用了歷經考驗的 HTTP 協定，這是最常見的 web 協定。在此情境下，client 與聊天服務開啟一個 HTTP 連線並傳送訊息，告知服務將訊息傳送給接收者。Keep-alive 對此很有效率，因為 keep-alive header 允許 client 與聊天服務維持持久連線（persistent connection）。它也減少了 TCP handshake 的次數。HTTP 在傳送端是一個不錯的選擇，許多受歡迎的聊天應用程式（例如 Facebook [1]）一開始都使用 HTTP 來傳送訊息。

然而，接收端就比較複雜一些。由於 HTTP 是由 client 發起的，要從伺服器主動傳送訊息並不容易。多年來，人們使用了許多技術來模擬伺服器端發起的連線：polling、long polling 與 WebSocket。這些都是在系統設計面試中廣泛使用的重要技術，所以讓我們逐一檢視。

Polling#

如圖 3 所示，polling 是一種 client 定期詢問伺服器是否有可用訊息的技術。根據 polling 頻率，polling 可能成本高昂。它可能消耗寶貴的伺服器資源去回答一個大多數時候答案都是「沒有」的問題。

Long polling#

由於 polling 可能效率不彰，下一步演進就是 long polling（圖 4）。

在 long polling 中，client 會持續保持連線開啟，直到真的有新訊息可用，或達到逾時門檻為止。一旦 client 收到新訊息，它會立即向伺服器發出另一個請求，重新開始這個流程。Long polling 有一些缺點：

• 傳送者與接收者可能沒有連線到同一個聊天伺服器。基於 HTTP 的伺服器通常是無狀態（stateless）的。如果你使用 round robin 進行負載平衡，接收訊息的伺服器可能與接收訊息的 client 沒有 long polling 連線。
• 伺服器無法很好地判斷 client 是否已斷線。
• 它效率不彰。如果使用者並不常聊天，long polling 在逾時後仍會定期建立連線。

WebSocket#

WebSocket 是從伺服器向 client 傳送非同步更新最常見的解決方案。圖 5 顯示了它的運作方式。

WebSocket 連線是由 client 發起的。它是雙向且持久的。它一開始是 HTTP 連線，可透過某種定義良好的 handshake「升級」為 WebSocket 連線。透過這個持久連線，伺服器可以向 client 傳送更新。

即使有防火牆存在，WebSocket 連線通常也能正常運作，因為它們使用 port 80 或 443，這也是 HTTP/HTTPS 連線使用的 port。

我們先前提到，在傳送端使用 HTTP 是不錯的協定，但既然 WebSocket 是雙向的，也就沒有強烈的技術理由不在傳送端使用它。圖 6 顯示了 WebSocket（ws）如何同時用於傳送端與接收端。

藉由在傳送與接收端都使用 WebSocket，可以簡化設計，並讓 client 與 server 兩端的實作更直接。

由於 WebSocket 連線是持久的，伺服器端有效的連線管理至關重要。

High-level design#

剛才我們提到 WebSocket 因其雙向通訊能力被選為 client 與 server 之間的主要通訊協定，但要注意的是，其他所有東西不一定要使用 WebSocket。事實上，聊天應用程式的大多數功能（註冊、登入、使用者資料等）都可以使用傳統的 HTTP request/response 方式。讓我們深入一點，看看系統的高階元件。

如圖 7 所示，聊天系統被拆解為三大類：

• 無狀態服務（stateless services）
• 有狀態服務（stateful services）
• 第三方整合（third-party integration）

Stateless Services#

無狀態服務是傳統面向公眾的 request/response 服務，用來管理登入、註冊、使用者資料等。這些是許多網站與 App 的常見功能。

無狀態服務位於 load balancer 之後，load balancer 的工作是根據請求路徑將請求路由到正確的服務。這些服務可以是單體式（monolithic）或個別微服務（microservices）。我們不需要自己建構許多這類無狀態服務，因為市場上有很多可以輕鬆整合的服務。我們將在 deep dive 中更深入討論的一個服務是服務發現（service discovery）。它的主要工作是給 client 一份聊天伺服器的 DNS host name 清單，讓 client 可以連線。

Stateful Service#

唯一的有狀態服務是聊天服務。這個服務之所以有狀態，是因為每個 client 都與一台聊天伺服器維持持久的網路連線。在這個服務中，只要伺服器仍然可用，client 通常不會切換到另一台聊天伺服器。服務發現會與聊天服務密切協調，以避免伺服器超載。我們會在 deep dive 中詳細說明。

Third-party integration#

對於聊天 App 來說，推播通知是最重要的第三方整合。它是一種在新訊息送達時通知使用者的方式，即使 App 沒在執行。推播通知的正確整合至關重要。請參考「Design a notification system」章節以了解更多資訊。

Scalability#

在小規模上，上述所有服務都可以放進一台伺服器。即使是我們設計的這個規模，理論上也可以將所有使用者連線都放進一台現代雲端伺服器。一台伺服器能處理的並行連線數很可能就是限制因素。在我們的情境中，假設並行 100 萬使用者，每個使用者連線在伺服器上需要 10K 記憶體（這是非常粗略的數字，且高度取決於語言選擇），那麼一台機器只需要約 10GB 的記憶體就能容納所有連線。

如果我們提出將所有東西放在一台伺服器的設計，這可能會在面試官心中亮起大紅燈。沒有技術人員會把這種規模的系統設計成單一伺服器。單一伺服器設計是個致命缺陷，原因有很多，其中最大的就是單點故障（single point of failure）。

不過，從單一伺服器設計開始是完全可以接受的，只要確保面試官知道這只是起點。把我們提到的所有內容綜合起來，圖 8 顯示了調整後的高階設計。

在圖 8 中，client 與聊天伺服器之間維持一個持久的 WebSocket 連線以進行即時訊息傳遞。

• 聊天伺服器負責訊息傳送/接收。
• **在線狀態伺服器（presence servers）**管理在線/離線狀態。
• API 伺服器處理一切，包括使用者登入、註冊、變更個人資料等。
• 通知伺服器傳送推播通知。
• 最後，key-value store 用來儲存聊天紀錄。當離線使用者上線時，她會看到她之前所有的聊天紀錄。

Storage#

到此為止，我們已經準備好伺服器、服務在運行，以及第三方整合也完成了。技術堆疊深處則是資料層。資料層通常需要花一些功夫才能做對。我們必須做的一個重要決定是，選擇正確的資料庫類型：關聯式資料庫還是 NoSQL 資料庫？為了做出明智的決定，我們會檢視資料類型與讀寫模式。

在典型的聊天系統中存在兩種資料。第一種是通用資料，例如使用者個人資料、設定、好友清單。這些資料儲存在強健且可靠的關聯式資料庫中。Replication 與 sharding 是滿足可用性與可擴展性需求的常見技術。

第二種是聊天系統獨有的：聊天紀錄資料。理解讀寫模式很重要。

• 聊天系統的資料量極為龐大。先前的研究 [2] 顯示 Facebook Messenger 與 WhatsApp 每天處理 600 億則訊息。
• 只有最近的聊天會被頻繁存取。使用者通常不會去找舊的聊天。
• 雖然在大多數情況下查看的是最近的聊天紀錄，但使用者可能會使用需要隨機存取資料的功能，例如搜尋、查看你被提及的訊息、跳到特定訊息等。這些情況應該由資料存取層支援。
• 對於一對一聊天 App 來說，讀寫比約為 1:1。

選擇能支援我們所有使用情境的正確儲存系統至關重要。我們建議使用 key-value store，原因如下：

• Key-value store 容易做水平擴展。
• Key-value store 提供非常低的資料存取延遲。
• 關聯式資料庫無法很好地處理長尾（long tail）[3] 資料。當索引變得很大時，隨機存取的成本很高。
• Key-value store 已被其他經過驗證的可靠聊天應用程式採用。例如，Facebook Messenger 與 Discord 都使用 key-value store。Facebook Messenger 使用 HBase [4]，而 Discord 使用 Cassandra [5]。

Data models#

剛才我們談到使用 key-value store 作為儲存層。最重要的資料是訊息資料，讓我們仔細看看。

Message table for 1 on 1 chat#

圖 9 顯示了一對一聊天的訊息表。Primary key 是 message_id，用來決定訊息順序。

我們不能依賴 created_at 來決定訊息順序，因為兩則訊息可能在同一時間被建立。

Message table for group chat#

圖 10 顯示了群組聊天的訊息表。複合 primary key 是 (channel_id, message_id)。Channel 與 group 在這裡代表相同的意思。channel_id 是 partition key，因為群組聊天中所有的查詢都在某個 channel 內進行。

Message ID#

如何產生 message_id 是一個值得探索的有趣議題。Message_id 肩負著確保訊息順序的責任。為了確認訊息的順序，message_id 必須滿足以下兩個條件：

• ID 必須是唯一的。
• ID 應可依時間排序，意即新的列要有比舊的列更高的 ID。

我們如何達成這兩項保證？可以考慮以下方法：

1. MySQL auto_increment：腦海中浮現的第一個想法是 MySQL 中的「auto_increment」關鍵字。然而，NoSQL 資料庫通常不提供此功能。
2. 全域序號產生器：使用像 Snowflake [6] 這樣的全域 64-bit 序號產生器。這在「Design a unique ID generator in a distributed system」章節中有討論。
3. 區域序號產生器：區域意指 ID 只在群組內是唯一的。區域 ID 行得通的原因是，在一對一 channel 或群組 channel 內維護訊息順序就已足夠。相較於全域 ID 實作，這種方法更容易實現。

Step 3 - Design deep dive#

在系統設計面試中，通常你會被期望深入探討高階設計中的某些元件。對於聊天系統來說，服務發現、訊息流以及在線/離線指示器都值得更深入的探索。

Service discovery#

服務發現的主要角色是根據地理位置、伺服器容量等條件，為 client 推薦最佳的聊天伺服器。Apache Zookeeper [7] 是一個受歡迎的開源服務發現解決方案。它會註冊所有可用的聊天伺服器，並根據預先定義的條件為 client 挑選最佳的聊天伺服器。

圖 11 顯示了服務發現（Zookeeper）如何運作。

1. 使用者 A 嘗試登入 App。
2. Load balancer 將登入請求送到 API 伺服器。
3. 後端驗證使用者身份後，服務發現為使用者 A 找到最佳的聊天伺服器。在此例中，server 2 被選中，伺服器資訊回傳給使用者 A。
4. 使用者 A 透過 WebSocket 連線到聊天 server 2。

Message flows#

了解聊天系統的端對端流程很有趣。在本節中，我們將探討一對一聊天流程、跨多裝置的訊息同步，以及群組聊天流程。

1 on 1 chat flow#

圖 12 解釋了當使用者 A 傳送訊息給使用者 B 時會發生什麼事。

1. 使用者 A 將聊天訊息傳送到聊天 server 1。
2. 聊天 server 1 從 ID 產生器取得一個 message ID。
3. 聊天 server 1 將訊息傳送到 message sync queue。
4. 訊息儲存在 key-value store 中。
5. 分兩種情況：
   • 5.a. 如果使用者 B 在線上，訊息會被轉發到使用者 B 連線的聊天 server 2。
   • 5.b. 如果使用者 B 不在線上，由推播通知（PN）伺服器傳送推播通知。
6. 聊天 server 2 將訊息轉發給使用者 B。使用者 B 與聊天 server 2 之間有一個持久的 WebSocket 連線。

Message synchronization across multiple devices#

許多使用者擁有多台裝置。我們會說明如何跨多台裝置同步訊息。圖 13 顯示了一個訊息同步的例子。

在圖 13 中，使用者 A 有兩台裝置：手機與筆電。當使用者 A 用手機登入聊天 App 時，它會與聊天 server 1 建立 WebSocket 連線。同樣地，筆電與聊天 server 1 之間也有一個連線。

每台裝置都維護一個叫 cur_max_message_id 的變數，用來追蹤該裝置上最新訊息的 ID。滿足以下兩個條件的訊息會被視為新訊息：

• 接收者 ID 等於目前登入的使用者 ID。
• Key-value store 中的 message ID 大於 cur_max_message_id。

由於每台裝置上都有不同的 cur_max_message_id，訊息同步變得很容易，每台裝置都可以從 KV store 取得新訊息。

Small group chat flow#

相較於一對一聊天，群組聊天的邏輯較為複雜。圖 12-14 與 12-15 解釋了該流程。

圖 14 解釋了當使用者 A 在群組聊天中傳送訊息時會發生什麼事。假設群組中有 3 位成員（使用者 A、使用者 B 與使用者 C）。首先，來自使用者 A 的訊息會被複製到每位群組成員的 message sync queue：一個給使用者 B，一個給使用者 C。你可以把 message sync queue 想像成接收者的收件匣。

這個設計選擇對小型群組聊天很好，因為：

• 它簡化了訊息同步流程，因為每個 client 只需要檢查自己的收件匣即可取得新訊息。
• 當群組人數較少時，在每位接收者的收件匣中儲存一份副本並不會太昂貴。

WeChat 採用類似的方法，並將群組限制為 500 位成員 [8]。然而，對於擁有大量使用者的群組，為每位成員儲存一份訊息副本是無法接受的。

在接收端，接收者可以從多個使用者接收訊息。每位接收者都有一個收件匣（message sync queue），其中包含來自不同傳送者的訊息。圖 15 說明了該設計。

Online presence#

線上狀態指示器是許多聊天應用程式中不可或缺的功能。通常你可以在使用者頭像或使用者名稱旁邊看到一個綠色圓點。本節說明背後發生的事情。

在高階設計中，在線狀態伺服器負責管理在線狀態，並透過 WebSocket 與 client 通訊。有幾種流程會觸發在線狀態變更，讓我們逐一檢視。

User login#

使用者登入流程在「Service Discovery」章節中已說明。在 client 與即時服務之間建立 WebSocket 連線後，使用者 A 的在線狀態與 last_active_at 時間戳記會儲存在 KV store。線上狀態指示器會在她登入後顯示使用者在線。

User logout#

當使用者登出時，會經過如圖 17 所示的使用者登出流程。在線狀態在 KV store 中變更為離線。線上狀態指示器顯示使用者離線。

User disconnection#

我們都希望我們的網路連線是穩定且可靠的，但實際上並非總是如此；因此我們必須在設計中處理這個問題。當使用者斷開網路時，client 與 server 之間的持久連線會中斷。

處理使用者斷線的天真做法是將使用者標記為離線，並在重新連線時將狀態變更為在線。然而，這種做法有一個重大缺陷。使用者在短時間內頻繁斷線與重新連線是很常見的。例如，當使用者經過隧道時，網路連線可能會時開時關。在每次斷線/重連時更新在線狀態會讓在線狀態指示器變動太頻繁，導致很差的使用者體驗。

我們引入心跳（heartbeat）機制來解決這個問題。在線的 client 會定期向在線狀態伺服器傳送 heartbeat 事件。如果在線狀態伺服器在某個時間內（例如 x 秒）收到來自 client 的 heartbeat 事件，使用者就被視為在線；否則就是離線。

在圖 18 中，client 每 5 秒向 server 傳送一個 heartbeat 事件。在傳送 3 個 heartbeat 事件後，client 斷線且在 x = 30 秒內未重新連線（這個數字是任意選的，用來示範邏輯）。在線狀態變更為離線。

Online status fanout#

使用者 A 的好友是如何知道狀態變更的？圖 19 解釋了它的運作方式。在線狀態伺服器使用發布-訂閱模型（publish-subscribe model），其中每對好友都維護一個 channel。當使用者 A 的在線狀態變更時，它會將事件發布到三個 channel：channel A-B、A-C 與 A-D。這三個 channel 分別由使用者 B、C 與 D 訂閱。因此，好友可以很容易地取得在線狀態更新。Client 與 server 之間的通訊是透過即時 WebSocket 進行的。

上述設計對小型使用者群組很有效。例如，WeChat 採用類似的方法，因為其使用者群組上限為 500。

對於較大的群組，告知所有成員在線狀態既昂貴又耗時。假設一個群組有 100,000 位成員，每次狀態變更會產生 100,000 個事件。為了解決這個效能瓶頸，一個可能的解決方案是只在使用者進入群組或手動重新整理好友清單時才抓取在線狀態。

Step 4 - Wrap up#

在本章中，我們呈現了一個同時支援一對一聊天與小型群組聊天的聊天系統架構。WebSocket 用於 client 與 server 之間的即時通訊。聊天系統包含以下元件：

• 聊天伺服器：用於即時訊息
• 在線狀態伺服器：用於管理在線狀態
• 推播通知伺服器：用於傳送推播通知
• key-value store：用於聊天紀錄持久化
• API 伺服器：用於其他功能

如果你在面試結束時還有額外的時間，以下是其他可以討論的要點：

• 擴展媒體檔案支援：擴展聊天 App 以支援照片與影片等媒體檔案。媒體檔案的大小遠大於文字。壓縮、雲端儲存與縮圖都是有趣的話題。
• 端對端加密：WhatsApp 支援訊息的端對端加密。只有傳送者與接收者能讀取訊息。有興趣的讀者可以參考參考資料中的文章 [9]。
• Client 端快取：在 client 端快取訊息能有效減少 client 與 server 之間的資料傳輸。
• 改善載入時間：Slack 建立了一個地理分散的網路來快取使用者資料、channel 等，以獲得更佳的載入時間 [10]。
• 錯誤處理：
  • 聊天伺服器錯誤。聊天伺服器上可能有數十萬甚至更多的持久連線。如果聊天伺服器離線，服務發現（Zookeeper）會為 client 提供新的聊天伺服器以建立新的連線。
  • 訊息重送機制。重試與佇列是重送訊息的常見技術。

恭喜你走到這裡！現在給自己一個鼓勵。做得好！