Design a Collaborative Editor

Three people have the same document open. Ana fixes a typo while Ben adds a sentence above it and Chen watches both cursors move. Each types into their own copy with no delay, and a moment later every copy shows the same text. Nobody presses Save and no edit is lost.

Interviewers ask this because the boxes are simple and the core problem is not: two edits made at the same moment against the same text must merge into one result, on every screen, whatever order the network delivers them in. The steps follow A Framework for Any Design; try each "Your turn" box before you read on.

#Clarify the problem

• Functional: open a document; type and see your change instantly; see other people's changes and cursors live; keep working offline and sync on reconnect; browse version history.
• Non-functional: all copies converge; remote edits appear within about 200 ms in one region; an acknowledged edit is never lost; up to 100 editors per document; a document opens in under a second.
• Out of scope: comments, search, sharing screens, rich-text layout.

#Estimate the scale

Editors do not send a message per keystroke. The client batches the last 100 ms or so of typing into one operation, such as "insert the at position 4". Assume an open document sends one operation every 2 seconds on average, counting pauses.

• Daily volume: with a document open about an hour a day, 3,600 ÷ 2 ≈ 2,000 operations per user, so 20 million users × 2,000 = 40 billion, an average of 40 × 10⁹ ÷ 86,400 ≈ 460,000 a second. The peak of 1 million is about twice that.
• Fan-out: with 2 editors per open document, there are 1 million open documents. Each operation is acknowledged to its author and sent to one other person: 2 million outgoing messages a second.
• Connections: 2 million WebSockets. At an assumed 50,000 per server (load test it), 40 servers.
• Snapshots: assume 1 billion documents of about 50 KB: 50 TB for the latest copy of each.

#Define the API

GET /docs/{id}
  200 { "rev": 1042, "content": "...", "title": "Q3 plan" }
  403 Forbidden    no access     404 Not Found
 
WSS /docs/{id}/live?since=1042
  client -> server
    { "type": "op", "base_rev": 1042, "client": "c7", "seq": 17,
      "ops": [ { "insert": "the ", "at": 4 } ] }
    { "type": "cursor", "rev": 1043, "at": 88 }
  server -> client
    { "type": "ack", "seq": 17, "rev": 1043 }
    { "type": "op", "rev": 1044, "author": "ben", "ops": [...] }
    { "type": "cursors", "users": [ { "user": "ben", "rev": 1044, "at": 12 } ] }
    { "type": "reload" }   since is older than the kept log; fetch a snapshot

The decision worth arguing: each client keeps at most one operation in flight. Until seq 17 is acknowledged, new typing is buffered and sent as one operation after the ack. The server then only adjusts an incoming operation against what was committed since its base_rev. The pair (client, seq) makes a resend harmless: the server remembers the last seq applied per client and drops duplicates.

#Model the data

documents                         -- metadata, relational
  doc_id        BIGINT PRIMARY KEY
  owner_id      BIGINT
  title         VARCHAR(200)
  snapshot_rev  BIGINT            -- newest snapshot
  updated_at    TIMESTAMP
 
doc_ops                           -- about 100 B a row
  doc_id        BIGINT
  rev           BIGINT            -- 1, 2, 3 ... per document, no gaps
  author_id     BIGINT
  client_id     VARCHAR(16)
  client_seq    INT
  op            BYTES             -- the transformed operation
  created_at    TIMESTAMP
  PRIMARY KEY (doc_id, rev)
 
snapshots  -- blob store, key "docs/{doc_id}/{rev}", about 50 KB

Access patterns: append the next revision of document 42, read its operations after revision 1000, fetch its newest snapshot. All stay inside one document, so partition everything by doc_id.

For doc_ops, use a store with one leader per shard and a unique primary key, such as a sharded relational database. "Insert revision 1043" then fails cheaply if 1043 exists, which the deep dives use to stop two servers writing the same revision. At 1 million inserts a second and an assumed 20,000 per shard, that is 50 shards, each with a synchronous replica so an acknowledged operation survives losing the leader. A leaderless store fits the range reads too, but there "insert if absent" costs a consensus round on every operation. Snapshots are write-once blobs, so they go to blob storage.

#High-level design

Every operation on a document must be put in one order, and the cheapest place to do that is the memory of one process. So each open document has exactly one owner: a document server holding its text, recent operations and the people in it.

#Deep dives

#Merging concurrent edits: OT or CRDT

The document is dog. Ana adds s at the end: insert at 3. At the same moment Ben adds my at the start: insert at 0. If each side applies the other's operation as sent, Ana gets my dogs, but Ben applies "insert s at 3" to my dog and gets my sdog. The copies have diverged.

Operational transformation (OT) fixes the position before applying. For two inserts: if the other insert landed before yours, shift yours right by its length; at the same position, the one the server committed first goes left. Deletes need matching rules (overlapping deletes shrink each other), and that is where implementations get subtle.

transform(mine, theirs):  if theirs.at < mine.at: mine.at += len(theirs.text)  if theirs.at == mine.at and theirs was committed first:    mine.at += len(theirs.text)  return mine

The central server is what keeps OT manageable. Because it picks one order, the transform only has to guarantee that A then B-transformed gives the same text as B then A-transformed. Without a server, peers see operations in different orders and the transform must meet a much harder second condition, which several published peer-to-peer OT algorithms were later shown to break.

A CRDT (conflict-free replicated data type) avoids positions. Every character gets a permanent unique id, such as (ben, 1), and an insert says "after the character with id X". Ana's s goes after the id of g; Ben's m goes at the start. Ids never shift, so concurrent operations can be applied in either order, a repeated one changes nothing, and every copy ends at my dogs. Two inserts after the same character are ordered by comparing their ids. A deleted character stays as a hidden tombstone, because a later insert may point at it.

My pick is OT with a central server: the design needs one owner per document anyway, for order, presence and access checks, so OT's main cost is already paid. "Offline for days" or "no server in the middle" would flip it to a CRDT, with a server kept only to store and relay operations.

#One server per document

The gateways hash the document id onto a consistent-hash ring of document servers. Ring membership lives in a small strongly consistent store that every gateway caches and watches. With hash mod N, adding a 41st server would remap almost every document. With a ring, about 1/41 move: 1,000,000 ÷ 41 ≈ 24,000 documents, each reloaded from its snapshot.

Ownership can briefly overlap: a server paused by a long garbage-collection run may wake still believing it owns a document. A lease makes this rare: an owner stops serving when its lease lapses, before the store reassigns the document. The log as a fence makes it harmless. An owner only inserts the revision after the last one it has seen, and each revision can be written once, so two servers can never both commit 1045. The loser of that race re-reads the log, and steps down if the ring names another owner. A new owner learns each client's last seq from the logged operations, so resends stay harmless. Consensus and leader election explains why a lease alone is not enough.

#Storing operations and compacting them

The compactor writes a snapshot every 1,000 operations, so nobody replays a busy document from revision 1. Opening a document reads one 50 KB snapshot and at most 999 operations, about 150 KB. Keep fine-grained operations for 30 days (120 TB) for catch-up and recent history, then delete them. Do not keep every snapshot: that would be 40 million a day, 2 TB. Keep the newest, plus one per editing session for version history. A snapshot is a cache of the log, so a bad one is rebuilt from the previous snapshot and the operations.

#Cursors, reconnects and offline work

Cursors are not operations. Nobody needs their history and losing one is harmless, so they stay in the owner's memory and are never logged. A cursor is sent with its revision; when Ben inserts 3 characters before Ana's cursor, it shifts right by 3 with the same transform used for text. Cursor traffic is what hurts big documents: 100 editors sending their cursor 10 times a second to 99 others is 100 × 10 × 99 = 99,000 messages a second. Instead the owner sends each client one combined update every 500 ms: 100 × 2 = 200 messages a second.

Reconnecting reuses the edit path. The client keeps its last acknowledged revision and its unacknowledged operations, reconnects with since=1044, transforms its pending operations against what it receives, and resends them with their original (client, seq), so nothing is applied twice.

Offline editing is a long reconnect: the offline edits are sent as one operation with the old base_rev and transformed against everything since. If that revision is older than the 30-day log, the server answers reload; the client fetches a snapshot and does a three-way text merge, or saves its version as a copy.

#Bottlenecks and failures

At 10x (10 million operations a second), gateways and document servers scale by adding machines, and the ring moves a small share of documents each time. The log grows to about 500 shards. The real limit is one document, since one owner serves all its editors. At 100 editors, 100 × 0.5 = 50 operations a second sent to 99 others is about 5,000 messages a second: easy. A document read by 10,000 people needs a read-only stream for viewers through a separate fan-out tier.

#What a strong answer sounds like

#Follow-up questions

#How does undo work with several editors?

Undo only undoes your own edits. The client keeps the inverse of each of its operations, transforms it against everything committed since, and sends it as a new operation.

#How do you add formatting such as bold?

Add operations over ranges, such as "bold from 10 to 18". The same transform shifts the range ends when text is inserted or deleted before or inside them.

#Someone loses access while editing. What happens?

The metadata service tells the owner, which drops that user's socket and rejects their pending operations. Every operation passes through the owner, so there is one place to enforce it.

#How would you run this in several regions?

Each document's owner lives in one region. Distant editors still type with zero delay, but see others' edits one cross-region round trip later. If two regions must accept writes for one document, that is the case for a CRDT.

#How do you show last Tuesday's version?

Take the nearest snapshot before that time and, within 30 days, apply operations up to the chosen moment. Older versions are limited to the kept snapshots.