Cruxly › System design › Design Exercises

Collaborative Document Editing

two people typing in the same paragraph, and both edits must survive

Prompt: design the sync engine behind a collaborative document editor — like Google Docs. Multiple users edit the same document simultaneously, and every user's edits must eventually be visible to everyone, without either user's keystrokes being silently lost or the document ending up corrupted.

40 minutes first. This is deliberately the hard problem that the file-sync exercise elsewhere in this track explicitly declined to solve — here, it's the whole point.

Applying the four moves: Scope — concurrent edits to one document, every edit eventually visible to everyone, nothing lost, no corruption; comments and permissions out. Estimate — concurrent editors per document and edit frequency per editor, which together tell you how often conflicts actually occur and how small each operation is. Sketch — clients send small operations, a document service sequences and broadcasts them, and every client applies them locally. Deep dive — two people typing at the same position at the same moment: last-write-wins silently loses keystrokes, so the design needs operational transformation or CRDTs, and the deep dive is about which one and why.

Why last-write-wins and 'keep both copies' both fail here

Scope. In scope: concurrent plain-text editing, automatic conflict-free merging, eventual consistency across clients, basic presence (seeing where others are typing). Out of scope: rich formatting merge semantics (bold/italic ranges overlapping edits — a real extension of the same problem, name it as such), access control, offline editing beyond a short disconnect.

Two users, same document, same moment: user X inserts "quick " at position 4 of "The fox jumps," while user Y simultaneously inserts "brown " at position 4 of their own copy of the same original text. Both edits are made against the same base state, at the same position, and both must survive — neither user's keystrokes should vanish, and both users should converge on the same final text.

Every option this track uses elsewhere for merge conflicts fails here. Last-write-wins would silently discard one user's insertion — unacceptable for live typing, where a user watches their own keystrokes appear and then vanish is a visibly broken product, not a rare edge case. "Keep both as a conflicted copy," the file-sync exercise's honest answer for opaque blobs, is equally unacceptable here — a document editor showing users two divergent copies to manually reconcile defeats the entire premise of simultaneous editing. This position — that the standard "detect and defer to the user" answer is actually wrong for this specific problem — is worth stating explicitly, because it demonstrates the difference is understood, not just pattern-matched from a similar-sounding exercise.

Two real answers: Operational Transformation and CRDTs

Operational transform adjusts a concurrent operation's position to account for another operation it didn't know about — the transform, not the raw operation, is what gets applied.

Operational Transformation (OT) — the approach Google Docs actually uses — represents every edit as an operation (insert "X" at position P, delete N characters at position P). When two operations arrive concurrently against the same base state, the server (or, in peer-to-peer designs, each peer) transforms the second operation against the first: if X's insertion at position 4 already happened, Y's "insert at position 4" operation gets its position shifted forward by the length of X's insertion, so Y's edit lands after X's rather than overwriting it. This requires a central server to establish a single serialization order (which operation is "first") — OT's correctness proofs depend on every client applying transformed operations in a consistent order, which is much simpler to guarantee with one authoritative sequencer than in a fully peer-to-peer setup.

CRDTs (Conflict-free Replicated Data Types) take a different approach: represent the document as a data structure specifically designed so that any two replicas' concurrent operations merge automatically into the same result, regardless of the order they're applied in or received — no central sequencer required. A common text CRDT gives every character a unique, stable identifier derived from its position between its neighbors at insertion time (rather than a raw numeric index, which shifts as the document changes); merging two replicas' character sequences is then a matter of the two sequences already having independently well-defined tie-breaking rules for how identifiers order relative to each other.

The real tradeoff: OT is proven and simpler for a client-server design with one obvious sequencer (a document naturally has one server); CRDTs are the better fit for peer-to-peer or offline-first designs where there may be no single server to sequence through, but they typically carry more per-character metadata overhead. Google Docs' server-centric architecture made OT the natural choice; a local-first, sync-when-connected app (like some newer note-taking tools) more often reaches for CRDTs specifically because there's no server in the loop to serialize through.

The rest of the system: presence, persistence, and reconnection

Presence (showing where other users' cursors are) is a separate, much simpler real-time broadcast — each client's cursor position is pushed to a lightweight pub/sub channel scoped to the document, with no durability requirement at all (a missed cursor-position update just means a slightly stale cursor indicator for one moment, not a correctness bug), which is worth explicitly distinguishing from the edit-merging problem so the harder problem doesn't get conflated with the easy one.

Persistence: periodically snapshot the merged document state, rather than replaying the full operation history from the beginning of the document's life on every load — the operation log is authoritative for recent history and for resolving concurrent edits, but a document open for a year accumulates an operation history far larger than the document itself, so snapshotting plus "replay only operations since the last snapshot" keeps load time bounded.

A client reconnecting after a disconnect needs to catch up on every operation it missed, applied (and transformed, for OT) in the correct order — this is the same "give me everything since marker X" pattern used for device sync in the file-storage exercise elsewhere in this track, here applied to a stream of edit operations instead of file chunks.

Failure modes and the honest edges

A client's local edit is applied optimistically before server confirmation — the user sees their own keystroke instantly, not after a round-trip — and if the server later transforms it against operations the client hadn't yet seen, the client must be able to reconcile its local optimistic state with the server's authoritative transformed result without a visible jump or flicker. This local-optimistic-then-reconcile pattern is the same idea as any optimistic-UI design, applied to character-level edits instead of, say, a "like" button.

OT's correctness depends on the transform functions themselves being provably correct for every pair of concurrent operation types — a subtle bug in one transform function (insert-against-delete, delete-against- delete) can silently corrupt documents in a way that's extremely hard to reproduce, because it only manifests under specific concurrent-timing conditions. This is a genuine reason some newer systems prefer CRDTs, whose merge correctness follows from the data structure's mathematical properties rather than from a hand-written transform function being right for every input pair.

Very long-lived documents with thousands of collaborators over years accumulate CRDT metadata (a stable ID per character, forever) that can grow to dwarf the actual text — a real, acknowledged limitation worth naming rather than presenting CRDTs as a free lunch relative to OT's central-sequencer constraint.

How to say it in the interview

"The file-sync exercise punts on this exact scenario by keeping both conflicting copies and asking the user to merge — here that's not acceptable, so the entire design is about a data structure that lets concurrent edits merge automatically and unambiguously, which is what operational transform and CRDTs are each, in different ways, built to do."

Checklist

Explained why last-write-wins and 'keep both copies' both fail specifically for live concurrent typing
Named this as the exact case the file-sync exercise explicitly declined to solve, and explained why it can't be declined here
Described OT as transforming a concurrent operation's position against one already applied, not discarding either
Named that OT depends on a single authoritative sequencer to establish operation order
Described a text CRDT's core idea — stable per-character identifiers, not raw shifting indices
Stated the real OT-versus-CRDT tradeoff as sequencer availability, not one being unconditionally better
Separated cursor presence from edit merging as a much simpler, non-durable broadcast problem
Used periodic snapshotting so document load time doesn't grow unbounded with operation history
Applied optimistic local edits with server-reconciliation, rather than waiting for round-trip confirmation
Named CRDT metadata growth on very long-lived, high-collaborator documents as a genuine unresolved cost

Practice this interactively