Google Docs 協作編輯 (Design Google Docs)

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

開場後先問清楚邊界，別急著畫架構（弱候選人最常見死因就是沒釐清就開始畫）。建議問題：

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

• 功能性需求 (FR)

  • 使用者可 建立文件（CRUD）。
  • 多位使用者可 同時線上編輯同一份文件（collaborative editing）。
  • 修改 即時同步 給其他正在編輯的協作者（real-time updates）。
  • 即時看到其他協作者的 游標位置 / presence。

• 非功能性需求 (NFR)

  • 最終一致性：所有使用者最終看到的內容必須一致。
  • 單文件併發上限 ≤ 100 人。
  • 低延遲更新：每按鍵 ~50–100ms。
  • 規模：數十億文件、數百萬同時在線使用者。

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

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

估算的目的不是算到精確，而是 驅動 connection 擴展 / 儲存 / compaction 決策（估算 → 選型的 hand-off）。回連 02-Distributed-Systems/05-Numbers-to-Know。

連線數（WebSocket fan-out 的主壓力）

數百萬同時在線使用者 ≈ 1,000,000+ 並發 WebSocket 連線
單台 server 約可撐 萬級長連線（受 fd / 記憶體 / CPU 限制）
→ 需 數十~數百台 Document Service 才能承載 → 必須水平擴展 + 路由

儲存（op store / 文件本體）

數十億（1B+）份文件
若每份壓縮後 ≈ 100KB → 1B × 100KB ≈ 100 TB（採 OT、做 compaction 後的量級）
若不做 compaction：單份文件 1000 次編輯 × 1KB/snapshot ≈ 1GB → 全量爆炸

單文件 op 累積（compaction 觸發點）

熱門文件可累積 數百萬 ops
若新 client 進入要重播全部 ops → 載入延遲與頻寬不可接受
→ 必須定期 snapshot + compaction，新 client 只收 snapshot + tail ops

下表連線數 / 儲存量皆為 推導值（由「同時在線數」與「文件數 × 每份大小」算出，來源僅給出數十億文件 / 數百萬在線 / ≤100 人/文件 / 50–100ms 等輸入）。

4. 用到的積木 / Building Blocks Used

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

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

由 FR 驅動：建立走一般 REST，編輯走 WebSocket 事件（理據：每按鍵需雙向低延遲，見 01-Networking/05-Realtime-Protocols）。

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

兩類資料，命運完全不同：op（要持久、要定序） vs 游標（ephemeral、純記憶體）。

Documents（metadata，CRUD）
--------------------------------------------------
doc_id     UUID  PK
title      VARCHAR
owner_id   BIGINT
created_at TIMESTAMP

Operations / Operation Store（高寫入，定序 append）
--------------------------------------------------
doc_id     partition key   ← 同文件的 ops 聚在同一分片
ts (seq)   sort key        ← server 指派的 server_seq，保證總序
op_type    insert / delete
payload    position + content / range
--------------------------------------------------
採 Cassandra / 寬列：針對 high write throughput 最佳化
按 doc_id 分片 → 數十億文件可水平擴展

Snapshot（compaction 產物，存 blob / cold storage）
--------------------------------------------------
doc_id, snapshot@seq, blob_location   ← 新 client 從這裡載入再補 tail ops

Cursor / Presence（不入 DB）
--------------------------------------------------
只存 doc server 記憶體：{ user_id → cursor_position }，離線即移除

儲存選型：

→ 積木：op store 寬列模型見 06-Database-Tech/03-DynamoDB、分片見 05-Database-Advanced/02-Sharding；snapshot 走 07-Caching-Storage/02-Blob-Storage。

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

把前面的積木串成端到端流程。先看核心 flow，再看 scaled 架構。

(A) 連線 / 開始編輯 flow

Client
  │  GET v1/docs/:doc_id  （想開始編輯）
  ▼
API Gateway ──查 ownership（本地用 hash(doc_id, healthy_nodes) 算 owner）
  │  回傳對應 Document Service 的 socket server 位址
  ▼
Client ──建立 WebSocket──► Document Service (該文件的 owner server)
  │  owner 從 operation store 載入 snapshot + tail ops
  ▼
先把 snapshot + ops push 給 client → client 重建當前文件狀態，可開始編輯

(B) 並發編輯 flow（OT 核心）

User A ──SEND insert(...)──┐
User B ──SEND insert(...)──┤
                          ▼
            Document Service (single owner / 序列器)
              │ 1. 決定唯一順序（指派 server_seq）
              │ 2. 對後到的 edit 做 OT transform（依當下文件狀態）
              │ 3. append 到 operation store (Cassandra: doc_id|ts)
              ▼
            broadcast transformed op 給同文件其他 client
              │
              ▼
   其他 client 收到後，client 端也須再做一次 OT
   （server 順序 Ea→Eb，但 B 本地已套 Eb，故 B 需對 Ea 再 transform）
   → 所有人最終收斂到一致狀態（eventual consistency）

(C) Scaled 架構（端到端）

                         ┌─────────────────────────────┐
                         │  Service Registry (Zookeeper) │  ← 偵測節點上/下線
                         │  push online nodes+ring_config │     quorum 強一致
                         └───────────┬─────────────────┘
                                     │ (節點清單 / ring 配置)
   Client ──HTTP──► API Gateway ─────┤ 本地 hash(doc_id, healthy_nodes)→owner
                    （依 ownership 路由）│
                                     ▼
              ┌────────────────────────────────────────┐
              │  Document Service 叢集（多台，按文件分片） │
              │  每台負責一部分文件：序列器 + WebSocket fan-out│
              │  記憶體：游標 presence（離線即移除）        │
              └───────┬───────────────────────┬─────────┘
            (持久化 ops)│                       │(發佈 ops 給 viewer)
                       ▼                       ▼
        ┌──────────────────────┐     ┌──────────────────────────┐
        │ Operation Store        │     │ Durable Queue (Kafka)     │
        │ Cassandra: doc_id|ts   │     └───────────┬──────────────┘
        │ + Snapshot → Blob/Cold │                 │ (有序 / 可 replay)
        └──────────────────────┘                 ▼
                                       ┌──────────────────────────┐
                                       │ Viewer Cluster (SSE 單向)  │
                                       │ viewer-owner 消費並廣播    │
                                       └──────────────────────────┘

關鍵 hand-off：Gateway 用 consistent hashing 算 owner → client 連到正確的 doc server（升級 WebSocket）→ owner 序列 + OT + 持久化 → broadcast 給編輯者、並發佈到 Kafka 給 viewer cluster（SSE）。游標與主資料路徑解耦（純記憶體）。

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

8.1 並發編輯如何收斂一致：OT vs CRDT（招牌取捨）

問題：A、B 同時看到 "This is a doc"，A 在尾端插 "ument"、B 在尾端插 "!"。誰先到決定結果——若不處理，兩人最終看到不同內容。
為何是瓶頸：edits 是 contextual 的——一個 op 的正確性取決於 當下文件狀態與套用順序。若以「最新 snapshot 蓋一切」會直接遺失其他人的修改。

選擇與理由：採 A（OT + 中心化序列器）。因為 (1) 單文件併發上限 ≤ 100 人，中心化序列器完全 hold 得住；(2) 極低輸入延遲——WebSocket 直達單一 owner，排序 + transform 後立即回送，省去 CRDT 的多主同步開銷；(3) 決定性總序——變更建議、註解錨點、樣式套用都仰賴穩定順序。這就是本題的 core_tradeoff：用中心化 OT 換低延遲與總序，放棄離線 / P2P。
→ 積木：02-Distributed-Systems/02-CAP-Theorem（接受 eventual consistency）、10-Design-Patterns/05-Real-time-Updates

8.2 如何擴展到數百萬個 WebSocket 連線

問題：單台 server 無法同時持有數百萬連線。必須把 Document Service 水平擴展到多台，每台負責 一部分文件與使用者。三個子問題：(1) 怎麼把 user 均分到各 server？(2) 連線時怎麼確保被正確導向？(3) server 增減時怎麼最小化重路由？

連線流程：(1) Registry 把 online nodes + ring_config 推給 Gateway/servers，雙方 本地 用 hash(doc_id, healthy_nodes) 算 owner；(2) client 發 HTTP 到 Gateway，Gateway 依 ownership 導向對應 doc server；(3) 連線升級為 WebSocket；(4) owner 從 operation store 載入 snapshot + ops 先傳給 client，再讓他開始編輯。

選擇與理由：為什麼一定要把同一文件釘在同一台——因為 OT 要求單一序列器；consistent hashing 正好保證 同 doc_id 永遠映到同一 owner，又能在擴縮容時把重路由壓到最低。Registry 背後用 quorum consensus 確保節點視圖強一致，避免兩台同時自認某文件 owner（雙序列器 = 一致性災難）。
→ 積木：02-Distributed-Systems/04-Consistent-Hashing、09-Messaging-Coord/05-Zookeeper、11-Infrastructure/01-API-Gateway

8.3 如何控制儲存成本（snapshot / compaction）

問題：數十億文件、單文件可累積 數百萬 ops。即使選 OT 已比 CRDT 省一個數量級（100KB/文件 → 100TB 總量），仍有兩個痛點：(1) 總量大；(2) 新加入的 client 必須接收並重播所有 ops，效能與體驗都不可接受。

選擇與理由：採 hybrid——online server 對小批次做輕量 compaction（即時降低 tail 長度），offline worker 定期做 durable snapshot 並 GC（控制總量、把舊 ops 沉到 cold storage）。這同時解決「總儲存」與「新 client 載入延遲」兩個問題。
→ 積木：snapshot 沉冷見 07-Caching-Storage/02-Blob-Storage、寫入分片見 05-Database-Advanced/02-Sharding

8.4 游標 presence 與 viewer mode

問題 A（游標）：協作者游標要即時顯示，但 (1) 只有「當下」位置重要；(2) 離線後不需回報；(3) latency 要極低。
選擇：純記憶體 ephemeral state——在線時每 100ms 把游標位置回報給 WebSocket server，server broadcast 給其他人；使用者離線時 直接從記憶體移除。完全不入 DB（持久化純屬浪費）。

問題 B（viewer mode）：唯讀使用者 不上傳 edits，但仍需即時接收更新。若把 viewer 也塞進 edit owner，會與編輯者爭搶資源、且擴展受限。

viewer 重連：client 提供最後看到的 resume_seq，server 回 + ops(S+1…head)；若 gap 過大，直接回 snapshot@head + 一小段 tail ops。概念上 viewer 感覺像「只有一位作者在對他們廣播」。
→ 積木：09-Messaging-Coord/03-Kafka、12-Ops-and-Reliability/03-Reliable-Delivery、01-Networking/05-Realtime-Protocols

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

主動找出系統會先在哪裂開並補強（訓練 drive 而非被動回答）。

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：4 個 FR、4 個 NFR、一句話北極星 → __
• 3. 估算：並發連線 = ？ 總儲存 = ？ 兩個導出結論（路由 / compaction）= ？ → __
• 4. Building Blocks：默寫 ≥6 個決策→積木對映 → __
• 5. API：建立走 REST、編輯走 WebSocket（insert/delete/updateCursor）→ __
• 6. 資料模型：op store（doc_id|ts, Cassandra）/ snapshot（blob）/ 游標（記憶體）→ __
• 7. 架構：連線 flow（Gateway→hash→owner→WS）/ 編輯 flow（序列器+OT+廣播）/ scaled 圖 → __
• 8. Deep Dives：OT vs CRDT（招牌）、consistent hashing 路由、snapshot/compaction、viewer（Kafka+SSE）→ __
• 9. Scaling：先在哪裂開？連線層 / handoff / compaction / viewer cluster → __
• 10. Recap：一句話招牌取捨 = ？ → __

常見陷阱 (Exam Traps for This Problem)

Related Notes

• 02-Distributed-Systems/05-Numbers-to-Know
• 02-Distributed-Systems/02-CAP-Theorem
• 02-Distributed-Systems/04-Consistent-Hashing
• 01-Networking/05-Realtime-Protocols
• 10-Design-Patterns/05-Real-time-Updates
• 10-Design-Patterns/02-Scaling-Writes
• 09-Messaging-Coord/05-Zookeeper
• 09-Messaging-Coord/03-Kafka
• 11-Infrastructure/01-API-Gateway
• 06-Database-Tech/03-DynamoDB
• 05-Database-Advanced/02-Sharding
• 07-Caching-Storage/02-Blob-Storage
• 12-Ops-and-Reliability/03-Reliable-Delivery