Design a collaborative document editor

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.

The question

Clarifying questions

• 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.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real product.
• 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.

The arithmetic:

• 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

High-level design

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.

How a request flows

Type a character

1. Alice types a letter. Her editor shows it at once and sends the operation with the revision it was based on, say 41.
2. The gateway forwards it to the session server that owns this document.
3. The server transforms the operation against any accepted since revision 41, gives it revision 42 and appends it to the log.
4. It sends the accepted operation, with revision 42, back through the gateway to every editor of the document.
5. Alice's editor sees it acknowledged. Bob's editor applies it after adjusting it for any edits Bob has typed but not yet sent.

Open a document

1. Bob opens a document from his list.
2. The gateway asks the directory which session server owns it.
3. The directory answers: server 7. If the document was idle, a server is chosen and recorded.
4. The gateway joins Bob to the document's session on server 7.
5. If the document is not in memory, the server loads its latest snapshot, say at revision 4,000.
6. It replays the operations logged after that revision, at most about 500.
7. The server sends Bob the current text and revision number.
8. Bob sees the document and can start typing within a second or two.

Show a collaborator's cursor

1. Alice moves her cursor. The editor sends its position and selection, at most a few times a second.
2. The gateway passes it to the presence service, which keeps it in memory and does not log it.
3. The service returns the cursors of everyone else in the document.
4. Bob sees Alice's cursor in her colour. It expires on its own if she disconnects.

Deep dive: OT or CRDT: merging concurrent edits

Take the text 'cat'. 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.

Deep dive: a session server that orders each document's edits

Give each document one owner: a session server chosen by hashing the document ID, or recorded in the directory with a lease. 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.

Deep dive: persistence, snapshots and presence

Store the document as an append-only log of operations: the document ID, the revision, the operation, the author and the time. 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.

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.

Common follow-up questions

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.