Design Google Docs (Real-Time Collaborative Editing)

Collaborative Undo/Redo

Maintain a per-user undo stack that records that user's intent rather than a copy of the entire document. Undo creates a new inverse operation against the current document state, so it does not erase edits made by other users. Permission checks still apply to the generated operation.

1. User A inserts "X" → append operation to A's undo stack
2. User B edits the same document → document state advances
3. User A presses Undo → create an inverse operation for A's insert
4. OT: transform the inverse against intervening operations before applying
5. CRDT: emit a new operation that reverts A's prior mutation while preserving later edits from others
6. Persist the undo operation in the normal operation log so version history remains durable
7. Redo emits another forward operation. Never restore an old snapshot wholesale

Offline Editing & Sync

1. User goes offline → all edits stored in IndexedDB/SQLite
2. Local CRDT state diverges from the server
3. User comes back online:
   a. Client sends all buffered ops to the server
   b. Server sends missing operations using the client's last seen sequence or causal state
   c. CRDT merge: both sides apply all missing operations, ensuring convergence under the CRDT's merge assumptions
   d. No manual conflict resolution is needed for ordinary text edits

Version History & Snapshotting

• Snapshot every 100 ops or every 30 seconds
• Operation log kept for 90 days for the stated compliance requirement. The 500 TB capacity estimate covers 30 days of version history
• To view version at time T: find latest snapshot before T, replay ops to T
• Delta compression between adjacent snapshots (~90% reduction)

Real-Time Presence at Scale

Problem: 200 users in a doc, each sending cursor updates at 10/sec
Raw inbound updates: 200 × 10 = 2K cursor updates/sec
Naive fanout: 2K × 199 other editors ≈ 398K outbound deliveries/sec
Solution:
- Cursor throttling (client-side): limit each user to one update per 100ms
- Cursor batching (server-side): aggregate all 200 positions, broadcast every 100ms
- Batched fanout: 10 batches/sec × 199 recipients = 1,990 outbound batch messages/sec
- Message count reduction: roughly 200x compared with naive per-update fanout

Interview Walkthrough

• 25-minute cut

  Skip arch50/arch75 depth unless staff.

  • One collaboration server per active document (6 min)
  • WebSocket for operations, with OT or CRDT for merging (7 min)
  • Local keystroke instant. Remote op < 200ms (6 min)
  • Version history via operation log compaction (6 min)
• Lead with the OT vs CRDT decision as the defining architectural fork. Explain the trade-off using offline requirements, metadata cost, and coordination complexity.
• Explain how concurrent edits converge: OT transforms ops against each other on a central server, CRDT merges ops commutatively without coordination.
• Use WebSocket for real-time operation delivery. Batch cursor and presence updates to avoid roughly 398K outbound cursor deliveries per second when 200 users each send updates at 10/sec.
• Persist an append-only op log plus periodic snapshots, replaying ops from the latest snapshot for version history and crash recovery, integrating patterns from Event Sourcing and CQRS.
• Address offline editing by buffering operations locally and synchronizing on reconnect. Use CRDT causal merge when CRDT is selected, or OT rebasing when OT is selected.
• Frame consistency using CAP Theorem and Consistency Models. Explain that the design remains available during partial failures while convergence and durable writes are preserved under the stated failure model.
• Mention tombstone compaction for CRDT storage growth (~30% overhead after heavy editing).
• Common pitfall: last-write-wins timestamps, where two users typing simultaneously will silently lose one user's edits.