案例:即時通訊
訊息要即時送到對方的每一台裝置、對方離線時改用推播、而且順序不能亂:長連線閘道、訊息儲存和上線狀態怎麼配合。
流程
即時通訊是圍繞著「連線」而不是「請求」設計的:每台在線的裝置都和一台閘道維持長連線,所以系統必須知道誰連在哪一台。訊息只寫一次、拿到流水號,投遞在之後非同步進行。選一個流程一步步看;點方塊可以進到那個元件的主題。
亮起來的是這一步執行的程式碼
type Device = { device: string; gateway: string };type Message = { conv: string; seq: number; from: string; text: string }; class Messenger { private sessions = new Map<string, Device[]>(); // user -> connected devices private seqs = new Map<string, number>(); // conversation -> last seq private log = new Map<string, Message[]>(); // conversation -> messages delivered: Array<[string, string, number]> = []; // [gateway, device, seq] pushed: Array<[string, number]> = []; // [user, seq] connect(user: string, device: string, gateway: string): void { const list = this.sessions.get(user) ?? []; list.push({ device, gateway }); this.sessions.set(user, list); } disconnect(user: string, device: string): void { const list = (this.sessions.get(user) ?? []).filter((d) => d.device !== device); this.sessions.set(user, list); } send(from: string, conv: string, members: string[], text: string): Message { const seq = (this.seqs.get(conv) ?? 0) + 1; this.seqs.set(conv, seq); const message = { conv, seq, from, text }; const log = this.log.get(conv) ?? []; log.push(message); this.log.set(conv, log); for (const user of members) { if (user === from) continue; const devices = this.sessions.get(user) ?? []; if (devices.length === 0) { this.pushed.push([user, seq]); continue; } for (const d of devices) { this.delivered.push([d.gateway, d.device, seq]); } } return message; } sync(conv: string, afterSeq: number): Message[] { return (this.log.get(conv) ?? []).filter((m) => m.seq > afterSeq); }}① 順序:手機時間 vs 流水號
3.00 s
依手機時間排序
- A#1
- B#3
- A#2
- B#5
- A#4
- B#8
- A#6
- A#7
- B#10
- A#9
依伺服器流水號排序
- A#1
- A#2
- B#3
- A#4
- B#5
- A#6
- A#7
- B#8
- A#9
- B#10
排錯位置:回覆跑到問題前面
依手機時間:排錯的回覆
14.2%
依流水號:排錯的回覆
0.0%
400 段對話、3,600 則回覆中,依各自手機的時間排序時,有 511 則排到它所回覆的訊息前面。回覆一定是在問題送到之後才打的,伺服器收到的順序就是真正的順序,依此發的流水號永遠不會排錯。手機時鐘誤差小於回覆所需的時間(這裡是 0.3–4 秒)時很少出錯,但被手動調過時間的手機可能差上好幾分鐘。
② 一則群組訊息的成本
200
70%
50
寫進儲存
1 次
推到在線裝置
195.6
發出推播通知
59.4
碰到的閘道
49.1 / 50
不管群組多大,訊息都只存一次;但投遞是每個成員各做一次:查 199 次登記表、沿長連線推 195.6 次(在線成員有 40% 還開著第二台裝置)、發 59.4 則推播。連線是隨機分散到各台閘道的,所以大群組會碰到 50 台中的 49.1 台。
模型假設與範圍
- 這是可重現的教學模型;延遲、容量、故障率與工作負載是設定或樣本,不能直接當作正式系統的效能承諾。
- 依對話排序、離線儲存與推送的簡化模型;沒有端對端加密、裝置金鑰管理與完整多區域傳送協定。
什麼時候用
- 任何「伺服器要主動把東西送到使用者面前」的系統:聊天、協作編輯、即時通知、多人遊戲大廳。
- 需要順序正確、不漏不重的時候:用伺服器發的流水號,而不是手機上的時間。
- 一個人有多台裝置要同步同一份狀態時:用「對話+最後看到的流水號」來同步,而不是推送一次就算送達。
和其他主題的關係
- 延伸閱讀
- 案例:動態牆
時間與空間複雜度(Big O)
| 操作 | 平均 | 最差 |
|---|---|---|
| 寫入一則訊息 對話所在的分片上加一筆、流水號加一,與群組大小無關 | O(1) | O(1) |
| 查一個人連在哪 d 是這個人的裝置數 | O(1) | O(d) |
| 投遞給 n 人的群組 | O(n) | O(n·d) |
| 重新上線同步 m 是錯過的訊息數;靠 (對話, 流水號) 的索引直接跳到該處(程式裡用過濾示意) | O(m) | O(m) |
空間:O(M + C),M 則訊息,加上登記表裡 C 條在線連線
Big O 實測:n 變大時步數怎麼長
數的是:每則訊息的工作量(n 是群組人數)
| Big O | n = 10 | n = 100 | n = 1,000 | n = 10,000 | 成長倍數:實測(理論) | |
|---|---|---|---|---|---|---|
| 寫進訊息儲存 | O(1) | 1 | 1 | 1 | 1 | ×1.0 (×1.0) |
| 查登記表 | O(n) | 9 | 99 | 999 | 9,999 | ×1,111 (×1,000) |
| 推到裝置+推播 | O(n) | 11.4 | 128 | 1,273 | 12,804 | ×1,123 (×1,000) |
存一次、送 n 次:這就是為什麼訊息存在對話底下,而不是複製到每個人的收件匣。
和其他做法比
| 寫進儲存 | 查登記表 | 推到裝置 | 推播通知 | 碰到的閘道 | |
|---|---|---|---|---|---|
| 2 人的對話 | 1 | 1 | 0.9 | 0.3 | 0.9 / 50 |
| 20 人的對話 | 1 | 19 | 20.3 | 4.8 | 16.4 / 50 |
| 200 人的對話 | 1 | 199 | 195.6 | 59.4 | 49.1 / 50 |
| 2,000 人的對話 | 1 | 1,999 | 1,950 | 609.1 | 50 / 50 |
每則訊息平均(20 個群組):70% 成員在線、在線者 40% 有第二台裝置、50 台閘道。儲存永遠只寫一次,其他每一欄都隨人數線性成長,直到所有閘道都被碰到。
| 依手機時間排錯 | 依流水號排錯 | |
|---|---|---|
| 時鐘誤差 ±0 秒 | 0.0% | 0.0% |
| 時鐘誤差 ±0.5 秒 | 0.5% | 0.0% |
| 時鐘誤差 ±1 秒 | 2.8% | 0.0% |
| 時鐘誤差 ±3 秒 | 14.2% | 0.0% |
| 時鐘誤差 ±10 秒 | 26.7% | 0.0% |
每一列是同樣的 400 段兩人對話、共 3,600 則回覆,只差在兩支手機的時鐘誤差。
真實世界裡的它
- WhatsApp 用 Erlang 讓單台伺服器撐住上百萬條連線;LINE、Messenger、Slack 都是「長連線閘道+訊息儲存+推播」的組合。
- Discord 把訊息存在依頻道分片的寬欄資料庫(先用 Cassandra,後來換成 ScyllaDB)。
- 推播一定經過 Apple 的 APNs(Apple Push Notification service)或 Google 的 FCM(Firebase Cloud Messaging):App 在背景時,只有它們叫得醒手機。
取捨與陷阱
- 用手機時間排序會亂:時鐘可能差上好幾秒甚至幾分鐘,回覆會排到問題前面(上面的模擬量得出來)。
- 推播不保證送達:可能被系統合併、延遲或丟掉,訊息本身要靠同步補齊。
- 閘道是有狀態的:重新部署一台閘道會斷掉上面所有連線,要讓用戶端隨機等一下再重連,否則全部同時湧回來。
- 大群組的扇出隨人數線性成長;幾千人的群組要改成「只通知、讓 App 自己來拉」,或限制群組大小。