Design Collaborative Editing Like Google Docs

This is lesson 3 of System Design Case Studies, Part 2. Lesson 2 kept two copies of a file when two devices edited at once. A document editor cannot do that. It must merge, character by character, while people type. The real-time connection part is covered in Real-Time Apps: Polling, WebSockets and SSE.

Words used in this lesson

• Concurrent operations are two changes made by two people who had not yet seen each other's change.
• Convergence means that after all changes reach everyone, every copy of the document is identical.
• Operation (op) is one small change, such as "insert a at position 5" or "delete the character at position 3".
• OT (operational transformation) rewrites an incoming operation so that it has the intended effect on a document that has already changed. The function that does it is called transform.
• CRDT (conflict-free replicated data type) is a data type designed so that replicas can apply changes in any order and still end up equal.
• Tombstone is a marker kept in place of a deleted item. The item is hidden, not removed, so later operations that refer to it still make sense.
• LWW register (last-writer-wins register) is a single value with a timestamp; the newest write replaces the older ones. It is the simplest CRDT.
• Presence is who is in the document now. Cursor is where each person's caret or selection is.
• Op log is the ordered list of all operations. Snapshot is the full document at one point in the log.
• Causal order means an operation is applied only after the operations it depends on (for example, you cannot insert "after character X" before X exists).

1. Requirements

Functional

• Many people edit one document at once. They see each other's changes within about 100 to 200 ms (assume).
• Everyone ends up with the same text (convergence), and nobody's typing is lost.
• Show who is present and where their cursors and selections are.
• Edit offline and merge when back online.
• Undo your own changes, and see version history (restore an older version).
• Rich text (bold, headings, lists) is needed in a real product. We design the plain text core and explain how it extends.

Non-functional

• Low latency for the typist: your own keystrokes must appear at once, with no wait for the server. This is called local-first editing: apply locally, send later.
• Correctness over speed: a document that shows different text to different people is the worst failure.
• Scale: assume most documents have 1 to 3 editors and a rare few have 100 or more.
• Durable: no acknowledged edit is lost.
• Access control per document (view, comment, edit).

2. Back-of-envelope numbers

Assumptions throughout. Method: Back-of-the-Envelope Estimation.

Open sessions        : 5,000,000 people with a document open at once (assume)Typing at a moment   : 10% -> 500,000 active typistsMessages             : the client batches keystrokes, 2 messages/s per typist                       500,000 * 2 = 1,000,000 messages/s into the systemFan-out              : assume an average of 2.5 open sessions per document -> each message goes to 1.5 others                       1,000,000 * 1.5 = 1,500,000 messages/s outMessage size         : ~100 bytes (op + metadata)Bandwidth            : in 100 MB/s, out 150 MB/s  -> fine across a fleetDocument size        : 10,000 words * ~6 characters = ~60 KB of textOp log for one doc   : suppose 500,000 operations over its life * 50 B = 25 MB   (400x bigger than the text)Replay cost          : at an assumed 1,000,000 simple ops/s, replaying 500,000 ops = 0.5 s  with a snapshot every 1,000 ops, opening a doc = load snapshot + replay <= 1,000 ops = ~1 ms of replayDocs per server      : if one server owns each active document and can run ~5,000 active docs (assume)                       500,000 active typists / 2 per doc = 250,000 active docs -> ~50 servers + spares

Two things to notice. The log is far bigger than the text, so we need snapshots and compaction. And the load is spread by document: a document is small and its editors are few, so one server per document (sticky) is possible. That makes ordering simple, and it is the choice behind most OT systems.

3. API

Editing is a WebSocket conversation, not a REST call per key.

Client -> Server  (WebSocket, after auth)  { "type": "join",  "docId": "d1", "lastRev": 41 }                # I have revision 41  { "type": "op",    "docId": "d1", "baseRev": 41, "ops": [ {t:"ins",pos:5,ch:"x"} ], "clientSeq": 17 }  { "type": "cursor","docId": "d1", "pos": 12, "selEnd": 18 }      # presence, not saved  { "type": "leave", "docId": "d1" }Server -> Client  { "type": "ack",   "clientSeq": 17, "rev": 42 }                  # your op got revision 42  { "type": "op",    "rev": 43, "from": "u9", "ops": [ ... ] }     # someone else's op, already transformed  { "type": "presence", "users": [ {"id":"u9","name":"Asha","color":"#e67e22","pos":3} ] }  { "type": "resync", "snapshotRev": 40, "snapshotUrl": "…" }      # you are too far behind: reloadREST (not real-time)  GET  /v1/docs/{id}              -> latest snapshot + ops after it  GET  /v1/docs/{id}/revisions    -> version history  POST /v1/docs/{id}/restore      { "rev": 30 }

4. Data model

documents   : doc_id, owner, title, acl, latest_rev, latest_snapshot_revop_log      : doc_id, rev (increasing), author, ops (compact bytes), created_at     PRIMARY KEY (doc_id, rev)snapshots   : doc_id, rev, content (blob), created_at           every ~1,000 ops or ~1 minute of activitypresence    : NOT stored in the database. Kept in memory on the doc's server (and in Redis if shared), thrown away on disconnect

The op log is append-only. It is the source of truth; the document is a function of the log. Because it is ordered by (doc_id, rev), it fits a wide-column store or a relational table sharded by doc_id (Sharding). Snapshots can sit in object storage.

5. High-level architecture

 Browser A (local copy)           Browser B (local copy)   | type -> apply at once          ^   | send op (WebSocket)            | receive transformed op   v                                | +--------------------------------------------------+ | Edge / WebSocket gateway  (sticky: docId -> same  | | collaboration server, chosen by consistent hash)  | +-------------------------+------------------------+                           |                           v              +------------------------------+              | Collaboration server (1 per  |              | active document)             |              |  - holds current text + rev  |              |  - transforms/orders ops     |   presence in memory              |  - broadcasts to all clients |              +-----+-----------------+------+                    | append op       | every ~1,000 ops                    v                 v              +-----------+     +-------------+              | Op log DB |     | Snapshot    |              | (doc,rev) |     | store (S3)  |              +-----------+     +-------------+                    ^                    | open a doc: latest snapshot + log after it              +-----+-----------+              | Doc service     |  (REST: open, history, restore, permissions)              +-----------------+

The collaboration server for a document is the single sequencer: it takes operations, gives each a revision number, and sends them out in that order. If it dies, another server loads the last snapshot and the log and takes over, and clients reconnect and tell it the last revision they have.

6. Deep dives

6.1 Why simple approaches fail

Lock the document. Only one person can type. Not acceptable.

Send the whole document each time, last one wins. Two people typing at once overwrite each other. Not acceptable.

Send operations by position without care. This is the interesting case. Start with cat. User 1 inserts A at position 0. User 2, at the same moment, deletes the character at position 2 (t). If each user applies the other's operation as it arrives, with no change:

without transform (naive): user 1 ends with Act, user 2 ends with Aca

User 1 has Acat, then "delete position 2" removes a, giving Act. User 2 has ca, then "insert A at 0" gives Aca. The two screens differ: divergence. The positions in the operation were right for the document the author saw, not for the document after another change. There are two families of fixes.

6.2 Operational transformation (OT)

OT keeps positions but rewrites each operation against the operations that were applied before it. transform(a, b) answers: "a was made when the document looked like X; b has already been applied; what should a be now?" For the example: user 2's delete at position 2 was made on cat. After A was inserted at position 0, the t is at position 3, so the delete becomes "delete at 3".

My transform for one-character inserts and deletes:

function transform(a: Op, b: Op): Op | null {   // rewrite a so it still means the same after b  if (a.t === "ins" && b.t === "ins") {    if (a.pos < b.pos || (a.pos === b.pos && a.site < b.site)) return a; // tie at same spot: lower site id goes first    return { ...a, pos: a.pos + 1 };  }  if (a.t === "ins" && b.t === "del") return b.pos < a.pos ? { ...a, pos: a.pos - 1 } : a;  if (a.t === "del" && b.t === "ins") return b.pos <= a.pos ? { ...a, pos: a.pos + 1 } : a;  // del vs del  if (b.pos < a.pos) return { ...a, pos: a.pos - 1 };  if (b.pos === a.pos) return null;     // both deleted the same character: nothing left to do  return a;}

Two details to see. When both insert at the same position we need a tie-break (here the lower site id goes first), otherwise the two sides would pick different orders. And two deletes of the same character become a no-op.

The example result:

user 1 applies a then transformed b : Acauser 2 applies b then transformed a : Acawithout transform (naive): Act vs Aca

Both users reach Aca: A was inserted at the start, and the t was deleted. This rule has a name, TP1 (transformation property 1): applying a then transform(b, a) must give the same document as applying b then transform(a, b). I tested it on 100,000 random pairs of operations on random small documents:

TP1 random test: 100000 pairs, 0 diverged

This test covers two operations from one starting point. With many users and a central server, the server puts all operations in one order and transforms each new operation against the ones accepted since the revision the client based it on:

const history: (Op | null)[] = []; let doc = "hello";function receive(op: Op, baseRev: number) {  let cur: Op | null = op;  for (const h of history.slice(baseRev)) { if (!cur) break; if (h) cur = transform(cur, h); }  if (cur) { doc = apply(doc, cur); history.push(cur); } else history.push(null); // op became a no-op}

Three clients, all starting from hello at revision 0, all sending at once:

  server got {"t":"ins","pos":5,"ch":"!","site":1} (base 0) -> doc "hello!"  server got {"t":"ins","pos":0,"ch":">","site":2} (base 0) -> doc ">hello!"  server got {"t":"del","pos":1,"site":3} (base 0) -> doc ">hllo!"final: >hllo!

The third client deleted the e (position 1 in hello). After the > was inserted at the start, the e was at position 2, and the server's transform changed the delete to match. The e was removed, not the h. In a real system each client also keeps its own sent-but-not-acknowledged operations and transforms incoming operations against them. I did not build that client half; I tested the pair rule and the server rule only.

The cost of OT. With a central server, OT with one-step transforms is manageable, which is why a "one server per document" design suits it. Without a central server (peer-to-peer), you need a stronger property (called TP2) that is famously hard to get right, and many published algorithms were later found to be wrong (from general knowledge, not re-read). Rich text multiplies the number of operation pairs to transform (insert text, delete, format, insert image, ...), and each pair needs correct code.

6.3 CRDTs

A CRDT takes the opposite route: instead of fixing positions after the fact, make operations that do not depend on positions. In a sequence CRDT every character gets a unique, permanent id, and an insert says "put this character right after the character with id X", never "at position 5". Ids do not change when other text moves.

My version follows the RGA idea (replicated growable array). The id is (counter, site). Characters inserted after the same parent are ordered with the newest first, which is a rule every replica applies the same way. A delete just sets a tombstone flag.

integrate(m: Msg) {  this.clock = Math.max(this.clock, m.id.c);              // a Lamport clock: always above anything seen  if (m.t === "del") { this.nodes.get(key(m.id))!.dead = true; return; }   // tombstone  const n = { id: m.id, ch: m.ch, dead: false };  this.nodes.set(key(m.id), n);  const list = this.kids.get(key(m.after)) ?? [];          // children of the "after" character  let i = 0; while (i < list.length && newer(list[i].id, n.id)) i++;   // newest sibling first  list.splice(i, 0, n); this.kids.set(key(m.after), list);}// The visible text is a depth-first walk: each character, then its children, skipping tombstones.

Same spot, same time. Two replicas both type after c: one types a, the other o.

A: coa B: coa

Both show coa. The two inserts have the same parent, so they are siblings. The higher id wins the earlier slot (o from site 2 beats a from site 1 when counters are equal), and every replica makes that same choice.

The convergence test: 3 replicas, 40 random inserts and deletes, messages held back and delivered in a shuffled order, with a rule that an operation waits until the character it points to has arrived (causal delivery). 300 random runs:

run 0 final text on all 3 replicas: ["icieig","icieig","icieig"]300 random runs, 0 diverged

The sequence-CRDT version needs no central server for correctness, and works for offline use and peer-to-peer. The costs:

• Metadata per character: an id for every character (my (counter, site) pair). Libraries compress this by merging runs of characters typed in a row. Yjs and Automerge both do heavy work on this.
• Tombstones grow: deleted characters are kept. They need garbage collection once every replica has seen the delete.
• Merge intent: a CRDT guarantees equal results, but not that the result is what both people meant. Two people fixing the same typo can both insert the fix and produce a doubled word.

The Yjs README describes Yjs as a CRDT implementation with support for shared editors, offline editing, version snapshots, undo/redo and shared cursors. Automerge's README describes CRDTs and a sync protocol for local-first apps. Both are good starting points if you build one instead of writing your own.

The simplest CRDT: the LWW register. For a single value (a title, a checkbox, a colour) keep (value, timestamp, site). On merge keep the entry with the higher timestamp; break ties by site id. This converges, but it throws away the other write, so it is right for settings and wrong for text.

6.4 OT or CRDT? How I would choose

My honest rule: for a product that is online most of the time and has a server anyway, either works, and a well-tested CRDT library is the safer start than writing a transform from scratch. For a local-first or peer-to-peer product, use a CRDT. In an interview, explain both, pick one, and say why.

6.5 Presence and cursors

Presence (who is here) and cursors (where they are) are not part of the document. They change many times a second, they are useless after the person leaves, and losing one does no harm. So:

• Send them on the same WebSocket as a separate message type, and do not write them to the op log.
• Keep them in memory on the collaboration server (use Redis if several servers share a document). When the connection closes, remove the person. A heartbeat every few seconds handles lost connections.
• Throttle: send a cursor update at most every 50 to 100 ms. Do not send one for every arrow-key press.
• A cursor position is a number, so it must move when text changes. If someone inserts text before your collaborator's cursor, their cursor must shift right. In OT you transform the cursor with each operation, in the same way as an operation. In a CRDT you store the cursor as "after character id X", which does not move by itself.

I ran the cursor shift. Bob's cursor is right before world (position 6). Three operations arrive:

Bob sees: "hello |world"{"t":"ins","pos":0,"ch":">"}       Bob sees: ">hello |world"{"t":"del","pos":1}                Bob sees: ">ello |world"{"t":"ins","pos":6,"ch":","}       Bob sees: ">ello ,|world"

function moveCursor(cursor: number, op: Op): number {  if (op.t === "ins") return op.pos <= cursor ? cursor + 1 : cursor;   // insert at or before the cursor pushes it right  return op.pos < cursor ? cursor - 1 : cursor;                        // delete before the cursor pulls it left}

The cursor stayed next to world through all three changes. The last line shows a choice: an insert exactly at the cursor position pushes the cursor to its right. That is a rule you pick and then apply the same way everywhere. Yjs's README lists shared cursors as a feature, and mentions an "awareness" mechanism for this kind of information (I did not read the details).

6.6 Offline edits

A client working offline keeps editing its local copy and stores its unsent operations (in IndexedDB, the browser's local database). On reconnect it sends join with the last revision it knew, plus its pending operations.

• With OT: the server must transform each of those operations against everything that happened since that revision. If the client was away for a day and 2,000 operations happened, that is 2,000 transforms per pending operation. It works, but it is slow and it is where subtle bugs show. Many products limit how long offline edits are accepted, or show the user a merge view.
• With a CRDT: send the operations or the updated state. They merge without change, because they never depended on the others' positions. This is the biggest practical argument for CRDTs.

Either way the user may see text appear around their edits after reconnect. Good UX shows a short "synced" note, and keeps the cursor stable using the cursor rule above.

6.7 Snapshots plus an operation log

The log is the truth, but replaying it from the start is slow, and it is large (25 MB for 60 KB of text, in my numbers). So:

1. Every N operations (say 1,000) or after some idle time, the collaboration server writes a snapshot: the full document at revision R.
2. To open a document: load the latest snapshot, then apply the log entries after R.
3. Version history is made from snapshots at chosen points (for example every few minutes of activity), and the log between them gives fine steps. Restoring version V is a new edit that sets the document to V's content, so history is never rewritten.
4. Compaction: old log entries before an old snapshot can be dropped or packed into bigger chunks after the retention time. Keep enough for undo and for clients that were offline.

A client that comes back after being away too long (its lastRev is older than what the log keeps) gets a resync: load the new snapshot and re-apply its own unsent changes with a merge (easy with a CRDT).

6.8 Undo

Undo must undo your last change, not the last change by anyone. With OT, you create the inverse of your own operation (delete what you inserted) and transform it against everything since. With a CRDT, undo is a new operation on the characters you created (tombstone them, or re-insert what you deleted). Libraries such as Yjs include an undo manager that tracks your own changes. I did not build undo.

6.9 Scale and routing

• Route all connections for a document to one collaboration server by hashing the doc id (consistent hashing), via a gateway that can look up or compute the owner.
• When a server is lost, the new owner loads the snapshot and log, and clients reconnect and send their last revision. Op acknowledgements tell clients which of their operations were saved, so they can resend the others.
• A very popular document (a webinar with 10,000 viewers) is mostly read: send viewers a read-only stream (a CDN or fan-out tier), and keep editors on the sequencer.
• Large documents can be split into sections (a spreadsheet by sheet, a doc by page), with one sequencer for each section.

7. Failure modes and trade-offs

Trade-offs to say aloud

• OT vs CRDT: central and compact vs decentralised and heavier.
• Local-first: instant typing, but the screen can change after the server's answer.
• Granularity: operation per keystroke is simple but chatty. Batching every 100 to 200 ms cuts the traffic with a small delay.
• Strong guarantees: you give up "lock the section" simplicity to allow free editing.

8. How to say it in an interview (60 seconds)

"Each client edits a local copy so typing is instant, and sends small operations over a WebSocket. The hard part is that concurrent operations carry positions that are stale by the time they arrive. There are two answers. With OT, a server per document gives every operation a revision number and rewrites it against the operations accepted since the client's base revision. In my test of the insert/delete rule, 100,000 random concurrent pairs all converged. With a CRDT, each character gets a unique id and an insert says 'after this id', so operations can arrive in any order; 300 random runs of three replicas with shuffled delivery all converged, at the price of metadata and tombstones. I would pick a CRDT library if offline editing matters, and OT if I already have a central server and a team that can test transforms. Presence and cursors go on the same socket but are not saved, and are throttled; cursors move with each operation. The server stores an append-only op log plus a snapshot every 1,000 operations, so opening a document is a snapshot and a short replay. One collaboration server owns each active document, found by consistent hashing; if it dies, another loads the snapshot and log and the clients resend what was not acknowledged."

Run it yourself

Three small files: ot.ts (transform, the TP1 test, the server run), crdt.ts (sequence CRDT and the random test) and cursor.ts. Run each with node file.ts on Node 22. They use no packages. The random numbers come from a fixed seed so the runs repeat.

Interview questions

Key takeaways

• Apply edits locally first, then merge. The difficulty is concurrent operations with stale positions.
• OT rewrites an operation against the ones accepted before it, using one server per document to set the order. My insert/delete rules converged on 100,000 random pairs.
• CRDTs give every character a permanent id so operations commute. 300 random runs with shuffled delivery converged. The price is metadata and tombstones.
• Presence and cursors are temporary, throttled, never written to the log, and must move with edits.
• Store an append-only op log plus snapshots, so opening a document is a short replay.
• Offline merging is easy for a CRDT and slow for OT. Choose by your product, and use a maintained library.

What's next

Lesson 4: Design a CDN. So far the data was written by users. Next is a system that serves the same bytes to millions of readers: how a content delivery network decides what to cache at the edge, where, and for how long.