跳到主要內容

系統設計

把資料結構放大到好幾台機器

主題 · 案例:即時通訊

案例:即時通訊

訊息要即時送到對方的每一台裝置、對方離線時改用推播、而且順序不能亂:長連線閘道、訊息儲存和上線狀態怎麼配合。

流程

即時通訊是圍繞著「連線」而不是「請求」設計的:每台在線的裝置都和一台閘道維持長連線,所以系統必須知道誰連在哪一台。訊息只寫一次、拿到流水號,投遞在之後非同步進行。選一個流程一步步看;點方塊可以進到那個元件的主題。

亮起來的是這一步執行的程式碼
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
依手機時間排序
  1. A#1
  2. B#3
  3. A#2
  4. B#5
  5. A#4
  6. B#8
  7. A#6
  8. A#7
  9. B#10
  10. A#9
依伺服器流水號排序
  1. A#1
  2. A#2
  3. B#3
  4. A#4
  5. B#5
  6. A#6
  7. A#7
  8. B#8
  9. A#9
  10. 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 On = 10n = 100n = 1,000n = 10,000成長倍數:實測(理論)
寫進訊息儲存O(1)1111×1.0 (×1.0)
查登記表O(n)9999999,999×1,111 (×1,000)
推到裝置+推播O(n)11.41281,27312,804×1,123 (×1,000)

存一次、送 n 次:這就是為什麼訊息存在對話底下,而不是複製到每個人的收件匣。

和其他做法比

寫進儲存查登記表推到裝置推播通知碰到的閘道
2 人的對話110.90.30.9 / 50
20 人的對話11920.34.816.4 / 50
200 人的對話1199195.659.449.1 / 50
2,000 人的對話11,9991,950609.150 / 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 自己來拉」,或限制群組大小。