Design a collaborative editor
Read firstDesign a chat system
Two people have the same document open. One types a character at position 4. At the same instant, the other deletes the word at position 2. Both edits are valid, both were made against the same version, and neither person did anything wrong.
There is no correct way to merge those two edits by sorting them or by timestamping them, because the second edit's position number stopped being true the moment the first one was applied. That is the whole question, and everything else here is plumbing around it.
Step 1: Understand the problem#
The scope question that matters is how strong the convergence guarantee has to be, and almost nobody asks it.
| You ask | They say | What it settles |
|---|---|---|
| How many people edit one document at once? | Usually two or three. Occasionally fifty in a meeting. | A server per document is affordable. Fifty editors on one document is a small fan out, which is a relief, because the hard part here is correctness and not scale. |
| Must every editor end up with an identical document? | Always, no exceptions. | The convergence requirement. Last write wins is off the table immediately, because two concurrent edits at different positions must both survive. |
| Does intent have to be preserved, or just the characters? | Intent. If I bold a word while you move it, the word stays bold and moves. | Operations described relative to the text rather than to positions in it. This is the answer that rules out the naive "send the whole document" design. |
| How fast does a keystroke have to appear locally? | Instantly. Nobody tolerates latency on their own typing. | Optimistic local application, with reconciliation afterwards. The client edits its own copy first and finds out later whether the server agreed. |
| Can someone edit offline? | Yes, and it must merge when they reconnect. | Operations have to compose after an arbitrary delay, not just a few hundred milliseconds. This makes the merge algorithm the centre of the design rather than an edge case. |
| Do we need history and undo? | Full version history, and undo that only undoes my own edits. | An append only operation log as the source of truth, with the document as a materialised view of it. Per user undo is much harder than it sounds and is worth flagging as such. |
What you are building, and what you cut#
- Several people editing one text document at once. Every editor converges to the same result, always.
- Local edits apply instantly. Reconciliation happens behind the cursor, never in front of it.
- Presence and cursors. Cheap, ephemeral, and the thing users notice first.
- History, and offline edits that merge on reconnect. The operation log gives you both.
- A keystroke is visible locally in under 16ms and to others in under 200ms.
- Every client converges to a byte identical document.
- A document survives any server restarting mid edit.
- Fifty concurrent editors on one document without degradation.
- Rich media, tables and embedded objects. Same machinery, much messier operations, and it triples the page.
- Access control and sharing. Real and orthogonal, and it belongs one layer up.
- Rendering and layout. That is a word processor, not a distributed system.
- Spreadsheet formula recalculation, which is a dependency graph problem hiding behind the same UI.
Back of the envelope#
Per document this is a trivial workload. 25 operations a second means one process can comfortably own a document and serialise every edit to it, which removes the entire distributed consensus problem. The scale challenge is 2,500,000 open connections, and connections are a known problem with known answers. The hard problem is that two of those 25 operations conflict.
The low per document rate tempts people into batching keystrokes to reduce traffic. Resist it, or at least be careful: batching changes what an operation means, and two batched operations conflict in ways two single character operations do not. Debounce the network send by a few tens of milliseconds if you must, but keep operations small and let the transform handle them. Cleverness in the merge algorithm is where bugs live forever.
Step 2: Propose the high level design#
The API#
{
"docId": "d_91",
"baseVersion": 41207,
"clientId": "c_7f",
"seq": 88,
"op": { "type": "insert", "pos": 4, "text": "h" }
}The data model#
| doc_id | uuid | PK | Partition key. One document is one log, read and written by one owner at a time. |
| version | bigint | PK | Clustering key, strictly increasing, assigned by the document owner. This ordering is the total order every client agrees on. |
| client_id | varchar(32) | UQ | With seq, makes an operation idempotent. A reconnecting client resends and the server recognises it. |
| op | json | insert, delete or format, with positions relative to the base version. Small, and it is never rewritten after being logged. | |
| base_version | bigint | What the client thought the document was. The gap between this and current version is exactly what has to be transformed against. | |
| author_id | bigint | IDX | For per user undo, and for showing who wrote what. |
The whole system on one whiteboard#
Walking Figure 1:
- An editor sends an operation tagged with the version it was written against. Locally it has already been applied, because nobody waits for a server to see their own keystroke.
- The gateway forwards it to the one server that currently owns this document. The coordinator is what makes "the one server" true, and it is the box that turns this from a consensus problem into an ordering problem.
- The document server transforms the operation against everything that has been applied since the client's base version. Usually that is nothing and the transform is a no op.
- It applies the result to the in memory document and assigns the next version number.
- It appends to the durable log, and only then acknowledges. Acknowledging before the append means a server crash can lose an edit the user watched appear.
- The transformed operation goes back through the gateway to everyone else on the document, and each client applies it, transforming against its own pending operations that the server has not seen yet.
Cursors and presence go around all of this. They are ephemeral, they are lost on disconnect without consequence, and putting them through the operation log would multiply your durable write rate by ten for data that is worthless in a second.
Two clients both send an insert based on version 41207. The server applies one and assigns 41208. What does it have to do to the second one before applying it, and what happens if it skips that step?
Step 3: Design deep dive#
Why positions lie#
Here is the conflict from the opening paragraph, in slow motion. Both clients start from
the string hello world at version 7.
This is operational transformation. One function, transform(opA, opB), that rewrites an
operation so it means the same thing after another operation has been applied. It is easy to describe and famously easy to get wrong. Insert against insert at the same
position needs a tiebreak. Delete against delete of the same character must not delete
twice. Every pair of operation types needs its own case, and missing one corrupts
documents months later.
Operational transformation with a single serialisation point needs one transform function against a linear history. Peer to peer OT, where any client can transform against any other, needs the transform to satisfy properties that are genuinely hard to prove and that several published algorithms got wrong for years. Assigning one owner per document is not laziness, it is what makes the correctness argument tractable, and it is exactly what Google Docs does.
The other answer, and when to pick it#
There is a second family of solutions that avoids transformation entirely by never using positions.
Pick operational transformation for a server based document editor and say why in one sentence: you already have a natural serialisation point, so you may as well use it and avoid paying tombstone overhead forever. Pick a CRDT when peers must merge without a server, which is the offline first and peer to peer case.
Then name the thing that makes the answer credible: garbage collecting tombstones in a CRDT requires knowing that every replica has seen a deletion, and if replicas can be offline indefinitely, you cannot know that. That is the practical reason CRDT documents grow, and it is a much better answer than "CRDTs use more memory".
Owning a document, and what happens when the owner dies#
One server per document is the assumption everything rests on, so it needs a real answer for failure.
The coordinator maintains a lease: server 12 owns document d_91 for the next thirty seconds, renewed continuously. Gateways route by asking the coordinator, and cache the answer for the lease duration. When server 12 dies, the lease expires, and only then may another server claim the document. The gap is deliberate: two servers assigning version numbers to one document is the one failure this design cannot tolerate, so it prefers a few seconds of unavailability to a moment of ambiguity.
Recovery is straightforward because the log is the truth. The new owner loads the most recent snapshot, replays operations after it, and announces the current version. Clients reconnect, send their pending operations again with the same client id and sequence number, and the server recognises anything it had already applied before it crashed.
"What if a client was offline for a week?" It reconnects with base version 41207 while the document is at 89000. Transforming its pending operations against 48,000 later ones is expensive and, worse, the result is often nonsense: the paragraph it was editing may no longer exist. The honest answer is that past some threshold you stop merging and start branching. Show the user their version as a suggestion or a copy, and let a human decide. Every editor that survives contact with real users has this escape hatch.
Break it#
Read every step as text
- 3 editors · Healthy. Fifteen operations a second on one document. The transform is almost always a no op because nothing arrived between the client reading and writing. This is the normal case and it is trivial.
- 50 editors · Degraded. A workshop. 250 operations a second in, and each one broadcast 49 times, so 12,000 messages a second out of one process. The transform queue is now genuinely doing work, because concurrent edits are constant rather than rare.
- paste 200 pages · Down. Someone pastes an enormous block. As one operation it is a multi megabyte message broadcast to fifty people. Split large insertions into bounded operations on the client, and rate limit per client, or one paste stalls everybody on the document.
- owner dies · Down. The document server crashes. Editing stops for this document until the lease expires and another server loads the snapshot and replays the tail. A few seconds of a frozen cursor, which users forgive, and no ambiguity about ordering, which they would not.
- repaired · Healthy. Clients reconnect and resend pending operations with the same client id and sequence, so anything applied before the crash is recognised rather than duplicated. Idempotent operations are what make the recovery boring, which is the highest praise a recovery path can get.
Notice that none of the failures above are about scale. A collaborative editor fails on correctness under concurrency and on one enormous operation, and both of those happen at five users just as readily as at fifty.
Trade-offs#
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| One server owns one document | A linear order for free, which makes the transform tractable and provably correct. | A few seconds of unavailability when that server dies, and a coordinator to run. | Any collaborative system with a server in the middle. The alternative is peer to peer OT, which is genuinely hard to get right. |
| Operational transformation over CRDT | No per character metadata and no tombstones, so a document edited for a decade stays small. | A transform function with a case per operation pair, and it must run somewhere central. | Server based editors. Choose a CRDT when peers must merge with no server, or when offline is the normal state rather than the exception. |
| Optimistic local application | Typing is instant, which is not negotiable in an editor. | The client holds pending operations and must transform incoming ones against them, so the algorithm lives on both sides. | Always for text input. The alternative is a keystroke that waits for a round trip, which no user tolerates. |
| Log as truth, snapshots as cache | History, undo and crash recovery all fall out of one decision. | Replay cost grows between snapshots, and the log grows forever unless compacted. | Any system where the sequence of changes is as interesting as the current state, which for documents it always is. |
Interview replay#
Checkpoint#
1. Why can concurrent edits not simply be ordered by timestamp and applied?
2. What does a CRDT trade away to avoid needing a central server?
3. Same design, but for a spreadsheet where cells contain formulas. What is the first new problem?
- 60 words a minute is about 5 operations a second per editor. Per document this is a trivial workload.
- One server owns one document. That is what makes the transform provably correct against a linear history.
- Append to the log before acknowledging. Reverse it and you lose edits the user watched appear.
- OT keeps documents small, CRDTs remove the server and pay in tombstones. Pick by whether you have a server.
A collaborative editor is a convergence problem wearing a UI. The core issue is that an operation says insert at position four, and the moment another edit lands before that point, position four means something different. So every operation carries the version it was written against, one server owns each document and assigns a linear order, and it transforms each incoming operation against everything applied since that base version before applying it. Clients apply their own keystrokes immediately and transform inbound operations against their own pending ones, because nobody accepts latency on their own typing. The log is the source of truth and the document is a materialised view of it, which gives history, undo and crash recovery from one decision, with snapshots as a cache. Single ownership is the key constraint: it makes the transform provably correct against a linear history, and I would rather pay a lease and a coordinator than attempt peer to peer transformation. The alternative family is CRDTs, which give every character an id so operations commute with no server, and pay for it in tombstones that cannot be collected while any replica might still be offline. For a server based editor I would take operational transformation.