System design deep dive · HLD
Design Google Docs: a real-time collaborative document editor.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for a concurrent edit and an offline reconnect, and an entity-relationship diagram for the document/operation/revision model - built around the one algorithm that makes concurrent editing actually converge: operational transformation.
1. Clarify requirements before drawing any box
A strong system design answer starts by pinning down scope out loud. For a collaborative editor, the hard part is never rendering text - it's guaranteeing that N people typing in the same paragraph at the same instant all end up looking at the exact same document, with nobody's keystroke ever silently disappearing.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers decide the shape of everything downstream: whether operations can be transformed on a single in-memory sequencer per document, how much the operation log has to sustain in writes per second, and why cursor updates cannot go through the same durable path as text edits.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Documents stored | ~1 billion documents | ~50KB average content + compacted op history per doc |
| Concurrent editing sessions | ~5 million documents actively edited at peak, globally | Typically 1-10 editors/doc, occasional spikes to 50+ on a viral shared doc |
| Operation rate | Keystroke-derived op every ~200-500ms while actively typing; ~10% of sessions typing at any instant | ~500K sessions typing → roughly 500K-1M small ops/sec system-wide, fanned out to collaborators |
| Bandwidth profile | Each op is tens of bytes; average 5-10 collaborators per active doc | Bandwidth is dominated by open WebSocket connection count, not op payload size |
| Storage | 1B docs × ~50KB (content + compacted op log) | ≈50TB of live document data, plus a much larger append-only raw op log before compaction |
3. High-level design (HLD)
The HLD names the major components and the one-directional data flow between them, without committing yet to specific infrastructure, regions, or shard counts - that level of detail belongs in the architecture diagram in the next section.
What each box owns
Client editor
Applies every local keystroke immediately (optimistic UI - the user never waits on the network to see their own character appear), buffers the resulting operation, and sends it to the server tagged with the revision it was based on. It reconciles its buffer whenever the server sends back transformed operations from other collaborators.
Collaboration / session server
Holds the authoritative, in-memory OT state for one document while it's being actively edited: the current revision number and the transform logic that reorders and adjusts concurrent operations so every client converges. This is the one piece of state that must never be split across two instances at once - see the sharding decision in the architecture section.
Operation log store
An append-only log of every accepted operation, in server-assigned order. It is the actual source of truth - if a collaboration server crashes, everything it knew can be rebuilt by replaying this log, which is exactly why durability lives here and nowhere else.
Snapshot store
Periodic compacted copies of the full document at a given revision, so recovery and revision-history restore don't require replaying the operation log from operation 1 for a document that's been edited for two years.
Presence / cursor broadcast service
Fans out cursor position and selection range to collaborators on a completely separate, non-durable path. It deliberately does not go through the operation log - losing one cursor update is invisible to the user; losing a text edit is not.
Design decision: Operational Transformation, not CRDTs
Because a collaboration server is already sitting in the loop for every document (for auth, sharing permissions, and connection routing), the design picks Operational Transformation over Conflict-free Replicated Data Types. OT needs a central authority to hold canonical operation order and transform concurrent ops against each other - which this system already has, for unrelated reasons. CRDTs exist specifically to remove that central authority and allow peer-to-peer merge, which is a capability this design doesn't need and would only pay for.
| Property | Operational Transformation | CRDT |
|---|---|---|
| Requires a central server | Yes - the collaboration server holds canonical order and transforms ops against it | No - designed for full peer-to-peer merge without one |
| Per-character metadata overhead | Low - operations reference plain positions in the current text | Higher - many CRDT text schemes need a tombstone or unique id per character to merge deterministically |
| Storage model | Simple: a plain string/rope plus an ordered op log | Grows with edit history unless aggressively garbage-collected |
| Fits client-server architecture | Naturally - server is already required for sharing/auth | Its decentralization benefit is unused when a server is mandatory anyway |
4. Detailed architecture diagram
The architecture diagram takes every HLD box and answers "how is this actually deployed?" - sharding key, region topology, and failover behavior, which is what an interviewer is checking for once they've accepted the high-level shape.
| Decision | Choice | Reasoning |
|---|---|---|
| Routing / sharding key | Consistent hashing on document_id, sticky assignment | All edits for one doc funnel through a single authoritative OT sequencer at a time, avoiding distributed-transform complexity entirely. |
| Failover | Rehydrate from last snapshot + replay operation log tail | Bounds recovery time - a document edited for two years still recovers in seconds, not by replaying from operation 1. |
| Cross-region routing | Gateway forwards to the doc's home shard even if it's in another region | One extra network hop is an acceptable cost for guaranteeing a single global order of operations per document. |
| Snapshot cadence | Every N operations or T seconds, whichever comes first | Keeps the operation log tail short enough that failover replay stays fast even for a hot, long-lived document. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether you actually understand call order - specifically, what gets transformed against what, and in which order operations get appended to the log so every replica derives the same result.
5.1 Two users editing the same paragraph concurrently
Step 6 happens entirely inside the collaboration server and touches no network - it is the classic OT transform: because opB arrived second but was written against the same base revision as opA, its position has to be shifted from 12 to 13 to account for the three characters opA already inserted. Steps 5 and 9 are drawn as dashed, non-blocking broadcasts, the same pattern used for fire-and-forget work elsewhere in this series - the acking client never waits on the broadcast to other collaborators, only on its own ack.
5.2 Client reconnect after a brief offline period
Step 5 is the reconnect equivalent of step 6 in the concurrent-edit diagram above - the client's buffered edits were written against revision 40, which is now stale, so they get transformed against everything that happened while the client was gone before being appended. Step 8 replaces the client's entire local optimistic buffer rather than trying to merge it in place, which is simpler and safe precisely because the server has already done the one transform that matters. The collaboration server also broadcasts the newly appended rebasedOps to every other connected collaborator using the same dashed, fire-and-forget path shown in the concurrent-edit sequence above.
6. Entity-relationship (ER) diagram and schema
The data model has to answer three questions: what is the single source of truth for what happened (the operations log), how does replay stay bounded (revisions), and how is access plus live presence tracked without writing presence updates into the durable log.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Relational (Postgres), for documents / revisions / collaborators | You need strong FK joins for permission checks ("can this user edit this doc?") and ACID metadata updates. | Not built for the sustained high single-table insert rate that the operations table needs at peak. |
| Wide-column / log-oriented (Bigtable/Cassandra), for operations | Append-only writes at up to ~1M ops/sec system-wide, keyed by (document_id, revision_number) for fast sequential range scans during replay. | No cross-table joins or transactions - the application layer fetches documents/collaborators separately. |
7. Deep dives interviewers actually probe
OT vs CRDT in more depth - what "correct" actually requires
An OT transform function isn't just "adjust the position" - it has to satisfy TP1 (transforming two concurrent ops against each other and applying them in either order must yield the same result) and, for the general case where a server may need to transform an op against a sequence of ops applied in different orders on different replicas, TP2 (transforming against a composed sequence must be equivalent regardless of how that sequence was itself built). Getting TP1/TP2 wrong is the classic source of the historical "OT bugs" that make people distrust hand-rolled implementations - it needs either a proven transform function per operation type or an already-battle-tested library. CRDTs sidestep this by making merge commutative and associative by construction (no bespoke transform proof needed), at the cost of the metadata overhead already covered in the trade-off table above.
How does undo/redo work when other people are editing concurrently?
A naive local undo stack (pop the last local op and apply its inverse) breaks the moment someone else has edited in between - the position the undo targets may no longer mean what it meant when the op was pushed. The fix is that undo is itself just another operation: the client requests "invert my op at revision R," and the server transforms that inverse operation against everything that has happened since revision R, the same transform machinery used for every other concurrent op, before appending and broadcasting it. Undo is never a special, un-transformed code path.
Why snapshot-plus-delta instead of full copies or infinite replay?
Storing a full document copy at every revision is wasteful - most revisions differ from their predecessor by a handful of characters, so storage cost scales with revision count times document size instead of with the actual amount of change. Storing only operations and replaying from operation 1 for a document edited daily for three years makes recovery time unbounded and growing forever. Snapshot-plus-delta bounds recovery to "load the nearest snapshot, replay however many operations happened since" - a cost that stays flat regardless of the document's total lifetime.
Why is presence/cursor broadcast treated as ephemeral, best-effort pub/sub?
Cursor position updates happen far more often than text edits (every mouse move or arrow key), and losing one is invisible - the next update a few hundred milliseconds later simply supersedes it. Routing that volume through the durable operation log would multiply write load on the one component that must never lose data, for a feature where data loss is harmless. So presence lives in Redis pub/sub: fast, unordered, and never retried, which is exactly the risk profile it needs.
What happens if the collaboration server holding a hot document crashes mid-session?
The consistent-hash router detects the failure and assigns the document's shard to a healthy instance, which rehydrates by loading the nearest snapshot and replaying the operation log tail since that snapshot's revision. Connected clients, meanwhile, must detect the gap themselves: each client tracks the last revision number it saw, and if the reconnected server's current revision doesn't match what the client expects, the client requests a replay of the missing range rather than assuming its local state is still valid - the same reconciliation path used for the offline-reconnect flow in section 5.2.
What happens when one document spikes to 50+ simultaneous editors?
Because every op for a document is serialized through one authoritative collaboration server, the transform cost scales with the rate of incoming ops, not with the number of viewers - CPU stays manageable. What does scale with N is broadcast fanout, which is why presence and broadcast are handled by a separate pub/sub tier that can be scaled independently of the OT sequencer itself, and why that hot document's snapshot cadence is tightened dynamically so a failover under heavy load still recovers fast.
Post a Comment
Add