System design interview
Design a collaborative document editor
OT versus CRDT, session servers, op logs, snapshots and cursors.
Press Play to follow a request through the design, or step through it.
- Client and edge
- Service
- Data store
- Cache and queue
- Alice types a letter. Her editor shows it at once and sends the operation with the revision it was based on, say 41.
- The gateway forwards it to the session server that owns this document.
- The server transforms the operation against any accepted since revision 41, gives it revision 42 and appends it to the log.
- It sends the accepted operation, with revision 42, back through the gateway to every editor of the document.
- Alice's editor sees it acknowledged. Bob's editor applies it after adjusting it for any edits Bob has typed but not yet sent.
- Editor
- Gateway: WebSocket connections
- Document directory: document → server
- Session server: orders edits
- Presence service: cursors, not stored
- Snapshot store: full copies
- Op log: append-only edits
On this page
In 2 minutes
I would give each document one owner: a session server chosen through a directory, with a lease. Editors connect over WebSockets through a gateway that forwards their edits to the owner. The client applies its own edits at once and sends one pending operation at a time, tagged with the revision it was based on.
The server transforms the operation against anything accepted since that revision, which is operational transformation, assigns the next revision number, appends it to an op log, and broadcasts it to the other editors. Because one server orders each document, there is no consensus protocol per keystroke, and the system scales by adding servers: about 167 for a million editors in our estimate. A CRDT is the alternative, and it is better for long offline editing, at the cost of per-character metadata.
For persistence, I keep the log as the source of truth and write a snapshot every 500 operations, so opening a document replays at most 500 operations. If the owner fails, another loads the snapshot and replays the log, and clients resend unacknowledged edits, which are deduplicated by client ID and sequence. Cursors travel separately and are never stored.
Step 1 of 6: Clarify the scope
Interviewer asks
Design an editor where several people type in the same document at the same time. Everyone should see the same text in the end, edits should appear within a fraction of a second, and no one's typing should be lost.
Questions to ask first
Ask these before you draw anything. Under each one is why its answer changes the design.
- How many people edit one document at once, at the most?
A handful of editors is easy. Hundreds of simultaneous editors change how broadcasts and ordering must work.
- Is plain text enough, or do we need rich text, tables and comments?
Richer content means richer operations and harder rules for merging concurrent changes.
- Must people be able to edit offline and merge later?
Offline editing is where CRDTs shine. If it is not required, a central server can simplify the design.
- Do we need version history and undo?
History means keeping the operations, or snapshots of the text, and not only the latest state.
- Should other people's cursors and selections be visible?
Cursors are frequent, short-lived and need to follow the text as it changes, so they are a separate stream.
Requirements
Functional
- Several people edit one document at the same time, and all copies converge to the same text.
- Show each person's own edits instantly, before the server has replied.
- Show collaborators' cursors and selections.
- Save every change, and let people open any document and see its history.
Non-functional
- A collaborator's edit appears within 200 ms at p95 in the same region.
- No acknowledged edit is ever lost, even if a server crashes.
- Opening a document takes under 2 seconds, however long its history.
- Handles 500,000 operations a second at peak.
Step 2 of 6: Size it
Each document is a small, independent world. That lets one server own it and order all its edits cheaply, so the whole problem scales by adding servers. The difficulty is in the merge rule, not in the volume.
Assumed for the exercise, not facts about a real system:
- 1 million people are editing at the busiest time, on documents with 3 editors each on average. Each sends 0.5 operations a second, because typing is batched.
- One session server can hold 2,000 active documents at about 100 KB each. An operation takes about 50 bytes.
- A snapshot is saved every 500 operations.
- Operations per second
- 1M editors × 0.5
- 500,000/s
- Messages sent out per second
- 500,000 ops × 3 recipients (two collaborators plus the sender's acknowledgement)
- ≈ 1.5 million/s through the gateways
- Documents open at once
- 1M editors ÷ 3 per document
- ≈ 333,000 documents
- Session servers
- 333,000 ÷ 2,000 documents per server
- ≈ 167 servers, using about 200 MB of memory each for documents
- Operation log growth at the peak rate
- 500,000 × 50 bytes
- 25 MB/s, so the log is partitioned by document
- Work to open a document
- A snapshot every 500 operations means at most 500 operations to replay
- A fast open, even for a document with a million edits
Step 3 of 6: Sketch the path of one request
Step through the diagram at the top of the page to watch a request move through these parts.
Each person's Editor keeps a live connection to a Gateway. The gateway asks the Document directory which Session server owns the document, and forwards the person's edits there. Every document has exactly one owner at a time, so all its edits meet in one place.
The session server holds the document in memory. It puts each incoming operation in order, transforms it if the sender had not yet seen the latest edits, gives it the next revision number and appends it to the Op log. It then broadcasts it to every editor of the document.
From time to time the server saves a full copy in the Snapshot store. To open a document, load the latest snapshot and replay the few operations after it. Cursors travel separately through the Presence service. They are frequent and short-lived, so they are never stored.
Other paths through the system
Open a document
- Bob opens a document from his list.
- The gateway asks the directory which session server owns it.
- The directory answers: server 7. If the document was idle, a server is chosen and recorded.
- The gateway joins Bob to the document's session on server 7.
- If the document is not in memory, the server loads its latest snapshot, say at revision 4,000.
- It replays the operations logged after that revision, at most about 500.
- The server sends Bob the current text and revision number.
- Bob sees the document and can start typing within a second or two.
Show a collaborator's cursor
- Alice moves her cursor. The editor sends its position and selection, at most a few times a second.
- The gateway passes it to the presence service, which keeps it in memory and does not log it.
- The service returns the cursors of everyone else in the document.
- Bob sees Alice's cursor in her colour. It expires on its own if she disconnects.
Step 4 of 6: Go deep on the hard part
OT or CRDT: merging concurrent edits
Interviewer asks
Alice and Bob edit at the same moment. How do both end up with the same text?
Take the text 'cat'.
Read moreShow less: OT or CRDT: merging concurrent edits
Alice inserts 's' at position 3. At the same moment, Bob inserts 'h' at position 0. Each applies their own edit at once, so they now see 'cats' and 'hcat'. If each simply applied the other's edit, Alice would insert 'h' at 0, giving 'hcats', but Bob would insert 's' at position 3, giving 'hcast'. The texts have diverged. Something must adjust the edits.
Operational transformation (OT). Edits are position-based operations. The server accepts Alice's first, then transforms Bob's against it: Alice's insertion at 3 does not affect an insertion at 0, so Bob's stays. Alice's editor does the reverse transformation when Bob's arrives: his insertion at 0 comes before her position 3, so her 's' moves to position 4. Both reach 'hcats'. OT needs a rule for every pair of operation types, and getting those rules right is hard, but the data stays compact. It normally relies on a central server to order operations.
CRDTs (conflict-free replicated data types). Give every character a unique ID, and place each one relative to its neighbours' IDs, not by index. Edits then commute: applying them in any order gives the same result. No central ordering is needed, so CRDTs suit offline editing and peer-to-peer. The costs are metadata for each character, and deleted characters often remain as markers (tombstones) until a cleanup step removes them.
Which one? We have a server per document anyway for access control and saving, so OT fits well and keeps documents small. If offline editing for hours or days is a core need, a CRDT is the stronger fit. Say the trade-off aloud and pick one.
For rich text, operations carry formatting as well: keep this many characters, insert this text, delete that many, or change this attribute. The transform rules grow, but the idea is the same.
A session server that orders each document's edits
Interviewer asks
How do you give every edit a single, agreed order without a slow distributed protocol?
Give each document one owner: a session server chosen by hashing the document ID, or recorded in the directory with a lease.
Read moreShow less: A session server that orders each document's edits
All editors of that document connect, via gateways, to the same owner. It keeps the document in memory, with its current revision number and a short list of recent operations.
Having one owner means ordering is trivial. When an operation arrives, the server compares its base revision with the current one, transforms it against the operations accepted in between, assigns the next revision, applies it, appends it to the log, and broadcasts it. No consensus protocol runs per keystroke. Documents are independent, so adding servers adds capacity.
The clients cooperate. Each client sends one operation at a time and waits for the acknowledgement before sending the next, combining anything typed in the meantime into a single pending operation. Then the server only ever transforms against operations it has accepted, which keeps the rules manageable. The client applies its own edits locally at once, so typing never waits on the network.
Failure. If the owner dies, its lease expires and another server takes over. It loads the snapshot, replays the log, and clients reconnect and resend anything unacknowledged. Each operation carries a client ID and a sequence number, so a resend that was already accepted is recognised and dropped. An edit is acknowledged only after it is durably in the log. Group several appends per millisecond into one write to keep that cheap.
Very popular documents are the exception. If a thousand people open one document, broadcasting to all of them is costly. Cap the number of active editors, say at a hundred, and serve the rest as read-only viewers, who can receive updates in batches from a fan-out layer.
Persistence, snapshots and presence
Interviewer asks
How do you store a document's history, open it quickly, and show cursors?
Store the document as an append-only log of operations: the document ID, the revision, the operation, the author and the time.
Read moreShow less: Persistence, snapshots and presence
The log is the truth. It gives you version history, an audit trail and crash recovery from one structure.
Replaying a log of a million edits to open a document would be slow, so save snapshots. Every 500 operations, or after a period of quiet, write the full document and its revision to the snapshot store. To open a document, load the newest snapshot and replay the operations after it, at most about 500. Named versions and 'see what changed yesterday' are built from older snapshots plus the log between them. Old operations past the retention period can be compacted away.
Presence is a different kind of data: frequent, small, and useless a few seconds later. Do not put it in the log. Keep each person's cursor and selection in memory with a short expiry, and broadcast it to the others in the document. Throttle it to a few updates per second.
Cursors must also follow the text. If Alice's cursor is at position 10 and Bob inserts five characters before it, her cursor belongs at 15. Treat a cursor position as something that is transformed by each incoming operation, the same way an insertion position is. Comments anchored to a range work the same way.
Check permissions when a client joins and when it sends edits. A person with view-only access can receive operations but is never allowed to submit them.
Step 5 of 6: Name the trade-offs
Merge strategy
OT with a central session server over A CRDT with no central ordering
Documents stay compact and ordering is simple. The cost is transform rules that are hard to get right, and weaker support for long offline editing.
Ordering
One owner server per document over Replicated servers agreeing by consensus
Ordering costs a memory lookup, not a network round of agreement. The cost is a failover step, in which another server loads the document and clients resend.
Storage
An op log plus periodic snapshots over Store only the latest text
We get history, recovery and fast opening. The cost is more storage and a snapshot job.
Cursors
A separate in-memory presence stream over Send cursors as ordinary operations in the log
The log stays small and cursors can be dropped freely. The cost is a second channel to run.
Step 6 of 6: Say what breaks next
Questions an interviewer asks once the design is on the board. Answer each one out loud first.
- How would you support offline editing?
With OT, the client queues its edits and on reconnect rebases them against everything the server accepted meanwhile. That works for short gaps but gets slow and fragile for long ones. A CRDT handles long offline periods better, which is why it is the usual choice when offline is a core need.
- How does undo work when others are editing?
Undo is per person, not global. The editor creates the inverse of that person's last operation and transforms it against everything accepted since, then submits it as a new operation. Other people's text is untouched.
- How do you handle a huge document?
Keep the text in a tree-like structure so inserting in the middle is cheap, and send the client only the part near its viewport at first. Operations stay small, whatever the size of the document. Opening does not depend on size because of snapshots.
- What if two people edit the same word at the same moment?
Both edits are kept. The transform rules decide a consistent order, for example by comparing client IDs when two insertions land at the same spot. The result may be mixed text, but it is the same for everyone, and each person can fix it.