Design Collaborative Document Editing

The night before the college fest, the organising team's plan lives in a document file that hops around a WhatsApp group: plan_final.docx, plan_final_v2.docx, plan_final_ravi.docx. At 10 pm two copies disagree. One tells volunteers to meet at 5, the other at 6, and Meera's whole stage schedule exists only in a copy nobody else opened. A shared document ends this. All twelve volunteers type into one plan at the same time, see each other's cursors, and every screen ends up showing the same text. Making that hold when two people type in the same spot at the same moment is what this chapter designs.

The product: a collaborative document editor. Several people edit one document at once and see each other's changes and cursors live. Plan for about 10 million daily users. The fest team's plan, document d_91, edited by Asha on a laptop and Ravi on a phone, is the example we follow throughout.

The fest plan shows the whole product in miniature. Collaborative editing means many people changing one shared document at the same time, with every copy ending up identical. Sending keystrokes around is the easy part. The hard part is deciding what the document should say when two people change the same spot at once. Here is what the fest team, and 10 million people like them, need.

Two rows shape everything that follows: every copy must end up identical, and an acknowledged edit, one the server has confirmed as saved, must never be lost. The first rules out simply keeping the last save; the second decides when the server may say "saved".

Before choosing machines, find out how much editing there really is, and how it spreads across documents. Assume 10 million daily users. At the evening peak about 10% of them have a document open: 1 million live connections, most of them reading or thinking rather than typing.

The total is large, but each document is small. Four edits a second is nothing for one process, so every busy document can have a single owner that puts its edits in order. Scale comes from spreading 100,000 busy documents across many servers, not from splitting one document.

Why 20,000 connections and not the 100,000 mostly idle sockets a chat server holds (the group chat chapter)? These connections are busy with keystrokes and cursor moves, and the server also holds documents in memory and transforms edits. As for latency, the 200 ms target splits into up to 100 ms waiting for a batch, 20 to 50 ms from Asha to the server, a few milliseconds for the log write, and 20 to 50 ms on to Ravi.

Those numbers say each edit must be small and must go to the one server that orders its document. Opening a document is an ordinary HTTP call. Live editing uses a WebSocket, a long-lived two-way connection (the group chat chapter covers how servers hold many of them), because both sides push small messages at any moment.

GET /v1/docs/d_91
200 OK   { "doc_id": "d_91", "version": 1840, "text": "Meet at 5 ..." }

WS /v1/docs/d_91/live
client → server  { "type": "op", "base": 1840, "seq": 17, "op": { "insert": " pm", "at": 9 } }
server → client  { "type": "ack", "seq": 17, "version": 1841 }
server → client  { "type": "op", "version": 1842, "author": "u_7", "op": { "delete": 4, "at": 120 } }
server → client  { "type": "presence", "user": "u_7", "cursor": 120 }

GET  /v1/docs/d_91/history?before=1800
POST /v1/docs/d_91/restore   { "version": 1500 }

`base` is the version the edit was made on; `seq` lets the client match each ack to its own edit.

• Edits are operations, not whole documents. "Insert ' pm' at position 9" is a few bytes; sending the 30 KB plan on every keystroke would multiply the traffic about 300 times.
• Every acknowledged edit gets the next version number, assigned by the server: 1841, 1842, and so on. The version is how both sides know what an edit was based on.
• Restore is a new edit, not a rewrite of history. It replaces the text with the old version's text as the next version, so every copy moves forward together.

Those version numbers need a durable home. Two kinds of data matter. An append-only edit log is the source of truth: every acknowledged operation, in order. Snapshots are copies of the whole text at some version, so nobody replays a year of edits to open the plan.

Partition everything by doc_id (the databases chapter covers partitioning). All of one document's operations then live together, ordered by version, so opening one is a single blob read for the latest snapshot plus a single range read for the operations after it. The primary key (doc_id, version) does a second job. Every append is an insert-if-absent, which relational databases and many key-value stores support, so two writers can never both store version 1841. The high-level design uses that to stop a stale owner.

Permissions are checked on connect and on change. The owner checks the user's role when the WebSocket opens and rejects edits from viewers. When someone's access is removed, the owner closes their connection at once instead of waiting for a reconnect.

With operations, versions and a log in place, the question is who puts each document's edits in order. The answer is one owner per document. The gateway routes every WebSocket for d_91 to the collaboration server that owns it. That server keeps the plan in memory, orders each incoming edit, writes it to the log, and only then acknowledges it and forwards it to the other editors.

The order is the lesson: log, then acknowledge, then forward. Ack before logging, and a crash leaves Asha believing a lost edit was saved. Forward before logging, and Ravi keeps an edit a new owner never heard of. Because the log holds every acknowledged edit, any server can rebuild the plan exactly.

• Finding the owner. The gateway hashes doc_id onto a ring of live collaboration servers, the consistent hashing idea from the key-value store chapter, so adding a server moves only a small share of documents.
• Loading and unloading. The first editor to open a document makes its owner read the latest snapshot and later operations into memory; a few idle minutes after the last editor leaves, the owner drops it.
• Exactly one owner. Each server holds a lease from a coordination service (the coordination chapter) and renews it every few seconds. A new owner's first append is a takeover record, an entry with no text change, in the next version slot. An old owner that was only paused then fails its next insert-if-absent and steps down: the version number plays the fencing token.

The owner puts edits in order, but order alone does not settle what the text should say. Edits name positions: "insert ' pm' at position 9" means after the ninth character. Think of directions that say "the ninth house on the street". If six new houses go up at the start of the street, the same house is now the fifteenth, and the old directions lead to the wrong door.

Say the plan's first line reads Meet at 5. At the same moment, Asha types Let's at the start and Ravi types pm at the end, position 9. Each app applies its own edit at once, called local echo, so typing never lags, then sends it to the other through the server.

The copies have diverged: the two now see different text and neither knows it. Ravi's position 9 was right for the text he saw, but Asha's copy had six more characters in front. His edit must be transformed to 9 + 6 = 15 before Asha applies it.

Operational transformation (OT) rewrites a late edit so that it means, on the current text, what it meant to its author. The owner decides the order: when an edit arrives with a base version older than the latest, the owner transforms it against every edit applied since that base, then logs and forwards the result.

Both sides transform. The owner transforms a late edit against everything logged since its base. Each app transforms incoming edits against its own unacked ones, and shifts those too: Ravi's waiting ' sharp' moved from 9 to 12 on his own screen. To keep this simple, an app has at most one batch in flight and buffers new keystrokes until the ack arrives.

The work is small. At about 4 edits a second per document and 100 to 200 ms for a round trip to the owner, an edit usually overlaps zero or one other, so it needs one transform or none, each a few comparisons. The single owner keeps it this simple: OT with no central order is hard to get right, and some published peer-to-peer designs were later shown to fail in rare cases.

The scene used one rule. Here is the full set for plain text, then one transform to do yourself. Each row says what happens to edit B when edit A, made on the same version, was applied first.

Check any rule with one test: applying A and then the transformed B must give the same text as applying B and then the transformed A. When both orders agree, every copy converges whichever edit it receives first.

def transform_insert(b, a, a_first):
    # b: an insert. a: applied first, made on the same version.
    if a.kind == "insert":
        if a.at < b.at or (a.at == b.at and a_first):
            return Insert(b.at + len(a.text), b.text)
        return b
    if a.at + a.n <= b.at:              # whole deleted range is before b
        return Insert(b.at - a.n, b.text)
    if a.at < b.at:                     # b sat inside the deleted range
        return Insert(a.at, b.text)
    return b                            # deleted range is after b

Four rows of the table as code. The owner and every app run the same function, which is why they agree.

OT repairs positions after the fact. A CRDT (conflict-free replicated data type) avoids positions altogether. Instead of "the ninth house on the street", every house gets a permanent number painted on its gate, so new houses never change anyone's address.

In a text CRDT every character gets a permanent unique id: here, the device that typed it plus that device's counter. An insert says "put ' pm' after character a9", not "at position 9". This is the plan's line as a CRDT holds it:

id     a1  a2  a3  a4  a5  a6  a7  a8  a9
char   M   e   e   t   _   a   t   _   5

a is Asha's laptop and 1 to 9 its counter; _ marks a space.

Now Asha types ' pm' and Ravi types ' sharp', both after a9, at the same moment. Each new character is anchored to the one before it, so each word is a chain hanging off a9. A device's counter always moves past the highest it has seen, so Asha's chain starts at id a10 and Ravi's at r10. Every copy orders two chains on one anchor by a fixed rule: higher counter nearer the anchor, and on a tie, the higher device name. r10 beats a10, so every copy reads Meet at 5 sharp pm, whichever edit arrives first, with no server deciding.

Deletes do not remove a character; they mark it deleted, a tombstone, because a slower edit may still be anchored to it. If Ravi deletes the 5 while Asha's ' pm' is in flight, a9 stays as a tombstone and ' pm' still lands after it. An edit anchored to a character a copy has not received yet waits until that character arrives.

Meet at 5 sharp pm may not be what either person wanted, but OT's tie-break cannot read minds either: both approaches promise identical copies and leave wording to people. Many CRDT apps still use a server to relay and store edits; they just do not need it to decide the order. What does all this bookkeeping cost?

The permanent ids that free a CRDT from a central order are also its price. Count them for the fest plan, a 30 KB document. Three costs show up in practice.

• Metadata per character. Each character carries its own id and its anchor's id, roughly 8 to 16 bytes each: 16 to 32 bytes of bookkeeping for one byte of text. Stored naively, the 30 KB plan carries about 1 MB of ids, and several times that in memory.
• Tombstones that pile up. Every character ever typed stays. If the team typed 300 KB over a month of rewrites and kept 30 KB, the CRDT holds ten times the visible text.
• Clean-up needs everyone. A tombstone can be dropped only when every copy has seen the delete, since an older edit may still point at it. One phone that stays offline for a month blocks clean-up for that document.

Libraries cut the first cost sharply by storing a run of characters typed in one go as a single item with a range of ids, which brings the metadata for normal typing down to a small multiple of the text. They cannot remove the history: a heavily rewritten document stays large, and opening it means loading that state, not just the text.

Choose OT with an owner when a server is always in the path; choose a CRDT when copies must merge without one. The fest plan is edited in browsers and apps that are almost always online, so this design keeps OT and its small per-edit cost.

Whichever method orders the edits, the ordered result must survive crashes and answer "what did the plan say yesterday?". The edit log is the document's diary: every acknowledged operation is appended with its version number and never changed. Replaying it from version 1 rebuilds the plan exactly, but after months that could mean millions of operations, so the owner also writes snapshots, bookmarks that hold the whole text at one version.

• When to snapshot: every 500 operations, or after a few minutes of quiet, whichever comes first. The owner writes the full text to the blob store and records the version in snapshots.
• Opening a document: read the latest snapshot, then the operations after it, rarely more than about 500.
• Version history: group operations into sessions (a 30-minute gap starts a new one) and show each session's authors and time. An old version is the nearest snapshot before it, replayed forward.
• Compaction: after, say, 30 days, keep hourly or daily snapshots and drop the operations between them. Old history becomes coarser but cheap.

open d_91
  latest version      1840
  latest snapshot     1500   (30 KB file from the blob store)
  ops to replay       1501 to 1840   (340 ops, about 34 KB)
  time to apply       a few milliseconds in memory

Snapshots keep opening fast no matter how long a document has existed.

Undo is per person. Undo should take back your own last edit, not whatever anyone typed last. The app keeps a stack of the user's own operations; undo builds the inverse (a delete for an insert), transforms it past every edit made since, and sends it as a new edit. Restore works the same way, so history only moves forward.

Two kinds of data are left: the kind that is useless a minute later, and the kind that arrives hours late. Presence (who is here) and cursors (where they are) change many times a second, so they live only in the owner's memory and never touch the log. The owner forwards cursor moves a few times a second at most and drops a user whose connection misses heartbeats for about 30 seconds.

Cursors shift the same way edits do. If Ravi's cursor is at position 40 and Asha inserts 10 characters at position 5, Ravi's cursor must move to 50 on everyone's screen. The same transform rules apply.

Offline edits. When the connection drops, the app keeps working: it applies edits locally and queues them in the device's storage with the last version it saw. Say Ravi edits the plan on a two-hour train ride with no signal and returns with 500 queued operations while the plan moved on by 2,000. On reconnect the owner transforms his queue against those 2,000, and his app transforms the 2,000 against his queue: about a million rule checks, well under a second of CPU.

• The real cost is meaning. The merge converges, but where both sides rewrote the same paragraph the text may read oddly. Show the user what changed while they were away.
• Lost access. If the user's edit right was removed meanwhile, the owner rejects the queue. Offer to save their text as a new document rather than throwing it away.
• Repeats. A reconnecting app may resend an edit the owner already stored. Each edit carries a client id and sequence number, so the owner recognises repeats, skips them and acks them again.

Everything so far assumed machines stay up. Most failures here pause editing for a few seconds; the promise to keep through all of them is that no acknowledged edit is lost.

The region row is the one place the promise bends. Copying to another region before every ack would add a cross-region round trip, about 30 ms even from Mumbai to Delhi, and let a slow standby slow every editor, so most designs accept losing the last second or two in a rare whole-region loss. The viewer row matters on fest day, when the schedule is projected around campus and 5,000 phones follow it while 3 organisers edit. Editors need the owner to order their edits; viewers only need the ordered stream. The owner publishes each version to a topic (the pub-sub chapter), a fan-out tier pushes it to viewers, and the owner keeps 3 sockets, not 5,003.

Each choice above buys something and costs something. Here they are side by side, with the one that remote editors feel explained below.

Editors far away. A New York editor on a plan owned in Mumbai still sees their own letters at once, thanks to local echo; only the ack takes about 200 ms, and the app simply sends bigger batches meanwhile. Others' edits reach them within about 250 ms. Do not give each region its own owner: two owners mean two orders of the same edits, which needs consensus between regions or a CRDT. If the team moves for weeks, hand ownership to a nearer region at a version boundary.

The replicated edit log dominates the bill: about 400,000 writes a second at peak, each kept in three copies, takes far more machines than the 50 or so collaboration servers. Compacting old operations after 30 days keeps its storage in check.

Optional: the fest plan has headings, bold times and lists, and supporting them changes the transform function but not the architecture. Store the document as a tree: blocks such as paragraphs, headings, list items and tables, each holding runs of text with marks such as bold or a link.

The owner still orders every edit, so nothing in the design above changes; only the transform function grows. Five operation types make 25 ordered pairs, each with its own cases. Marks add a question plain text never had: is a letter typed right after a bold word bold too? Many editors say yes for bold and no for links.

CRDT versions use the same trick as before: a mark is anchored to the ids of its first and last characters, so a bold range keeps covering the right words while others type inside it.

A 45-minute round leaves about 40 minutes of design after introductions. Here is this product on that clock.

Pick the deep dive from the question. Two people in one spot: OT and the tie-break. Editing on a train with no signal: offline merging, and CRDTs if offline is the main use. Last Tuesday's version, or what survives a crash: the edit log and snapshots.

Interviewers often change one thing and watch how you adapt. Try each before opening the answer.