Google Docs (Collaborative Real-Time Editor)

Sharpened prompt. Design a collaborative document editor where 50 people can type simultaneously in one document with sub-100ms echo, every client converges to byte-identical state, an editor who was offline for a week merges cleanly, undo reverts my last edit and nobody else's, and a five-year-old document with 40 million keystrokes still opens in under a second.

Convergence is the famous part, but it is a solved problem you can pick off a shelf. The parts that actually separate candidates are selective undo, history compaction, and what happens to a document that has been edited offline for a month.

1. Problem framing

Functional requirements

• Concurrent rich-text editing with real-time cursors and selections.
• Convergence: all clients end in identical state regardless of message order.
• Intention preservation: if I bold a word while you delete a different one, both survive.
• Undo/redo scoped to the local user.
• Version history, named revisions, and restore.
• Offline editing with automatic merge.

Non-functional requirements

Property	Target	Consequence
Local echo	0ms (optimistic)	Client applies its own edit immediately, never waits for the server
Remote propagation	P99 < 100ms	Persistent connections, regional edge servers
Convergence	Guaranteed, not best-effort	The algorithm must be provably convergent, not heuristically
Document open	< 1s for a 500-page doc	Snapshot + tail of ops, never full history replay
Concurrent editors	50 real-time, 100 viewers	One authoritative room per document

Back-of-the-envelope

Ops:        50 editors × 5 keystrokes/sec = 250 ops/sec/document
Fan-out:    250 ops/s × 50 clients = 12,500 messages/sec for ONE hot document
Doc size:   500 pages ≈ 1M characters
History:    5 years × 40M ops × 60 B = 2.4 GB of raw ops for one document
            -> replaying that on open is impossible. Snapshots are mandatory.
Scale:      10M concurrent documents × 3 editors avg = 30M connections

The 2.4 GB figure is the one that forces the design: history must be compacted, and open must be O(snapshot + tail), never O(history).

2. High-level architecture

The single most important box is one actor per document. All operations for a document funnel into one single-threaded mailbox, which makes transformation ordering trivially correct — no locks, no distributed consensus per keystroke. Everything else is plumbing around that decision.

3. Component inventory

Component	Concrete choice	Why this one
Concurrency algorithm	OT (ShareDB / server-authoritative) or CRDT (Yjs, Automerge)	See 5.1 — this is the design decision
Room runtime	Akka/Pekko actors, Elixir processes, or Cloudflare Durable Objects	Serialised per-document execution with cheap per-entity isolation
Transport	WebSocket, binary frames	Ops are tiny and frequent; JSON over HTTP wastes both bytes and syscalls
Op log	Bigtable / Spanner, key (doc_id, revision)	Append-only, ordered range scans, and a strict revision counter
Snapshots	Protobuf blobs in object storage	Immutable, cacheable, cheap
Presence	In-memory in the room actor, never persisted	Cursor positions are worthless a second later
Offline merge	Dedicated service	A week-old divergence is a batch problem, not a real-time one

4. The toughest parts

4.1 Concurrent edits at the same offset: OT vs CRDT

Why it's hard. Two clients act on the same document state. A inserts "X" at position 5; B deletes the character at position 3. When A's operation arrives at B, position 5 no longer means what A meant — B's delete shifted everything after position 3 left by one. Applying operations verbatim produces divergent documents, and divergence in a text editor is unrecoverable: two people are now editing different documents that both claim to be the same file.

Solution A — Operational Transformation. Transform each incoming operation against every concurrent operation it did not see.

// The core of OT: rewrite op1 so it can apply after op2, preserving both intentions.
function transform(op1, op2) {
  if (op1.type === 'insert' && op2.type === 'insert') {
    if (op1.pos < op2.pos) return op1;
    if (op1.pos > op2.pos) return {...op1, pos: op1.pos + op2.text.length};
    // Same position: break the tie deterministically by site id, or both
    // clients resolve it differently and diverge forever.
    return op1.siteId < op2.siteId ? op1 : {...op1, pos: op1.pos + op2.text.length};
  }
  if (op1.type === 'insert' && op2.type === 'delete') {
    if (op1.pos <= op2.pos) return op1;
    return {...op1, pos: op1.pos - Math.min(op1.pos - op2.pos, op2.len)};
  }
  // ... delete/insert and delete/delete, including partial overlap
}

OT needs a central server to impose a total order (the transformation functions must satisfy convergence properties that are notoriously hard to prove for peer-to-peer topologies — several published OT algorithms were later found incorrect). Google Docs, Etherpad, and ShareDB are OT. The upside: the document representation is just a string, so memory is small and the wire format is compact.

Solution B — CRDTs. Give every inserted character a globally unique, densely ordered identifier, so positions never need translating. Concurrent operations commute by construction and converge with no server.

// Sequence CRDT (RGA/Fugue family): identity, not index.
type CharId = { site: string; counter: number };
interface Char { id: CharId; value: string; originLeft: CharId | null; deleted: boolean; }

// Insert references its neighbour's IDENTITY, so it stays correct no matter what
// else was inserted or deleted concurrently.
function insert(doc: Char[], after: CharId | null, ch: string, site: string): Char { ... }

// Delete is a tombstone: the character stays, flagged. Removing it outright would
// invalidate every concurrent operation that references it as a neighbour.
function remove(doc: Char[], id: CharId): void { find(doc, id).deleted = true; }

Yjs and Automerge are the mature implementations, and Yjs in particular is fast enough for production text editing.

The comparison to give:

	OT	CRDT
Needs a central server	Yes (for total order)	No (converges peer-to-peer)
Memory overhead	~1× document size	2–10× (IDs + tombstones)
Offline for a week	Painful: transform against thousands of ops	Natural: just merge
Implementation risk	High — subtle, easy to get wrong	Use a library; don't write your own
Rich text / formatting	Well-trodden	Improving, historically weaker

The answer to actually give: "For a Google Docs clone today I'd use a CRDT — Yjs — because offline support and reconnection are first-class rather than a special case, and because I trust a well-tested library more than a hand-rolled transformation matrix. The costs are memory overhead from tombstones and a larger wire format, both of which are addressable with garbage collection and compaction. Google itself uses OT for historical reasons and because their server is authoritative anyway."

Having a clear recommendation and the reason the other choice exists is what the question is testing.

4.2 Undo that reverts my edit and nobody else's

Why it's hard. In a single-user editor, undo pops a stack. In a collaborative editor, "undo my last operation" is a selective undo of an operation buried in the middle of the shared history, with other people's edits layered on top. Naively inverting it is wrong in ways that produce data loss:

1. Alice types "Hello world"
2. Bob deletes "world"        (doc: "Hello ")
3. Alice presses Ctrl+Z       -> she wants to undo step 1
   Inverting step 1 verbatim = "delete 11 characters from position 0"
   But only 6 characters remain. The operation is not applicable, and forcing
   it corrupts the document or deletes Bob's later work.

Solution — model undo as a new compensating operation, computed against current state.

// The undo stack holds operation IDs, not raw inverses. The inverse is derived
// at undo time, transformed past everything that happened since.
class UndoManager {
  private stack: OpId[] = [];

  undo(doc: Doc, site: string) {
    const id = this.stack.pop();
    if (!id) return;
    const original = doc.log.get(id);
    // 1. Build the naive inverse (insert <-> delete).
    let inv = invert(original);
    // 2. Transform it past every op that arrived after the original.
    for (const later of doc.log.since(id)) {
      inv = transform(inv, later);
      if (inv.isNoop()) return;   // someone already deleted what we'd undo
    }
    // 3. Apply as a NEW operation with a new id. History is append-only.
    doc.apply({...inv, undoes: id, site});
  }
}

In a CRDT this is cleaner because identities are stable: undoing an insert means tombstoning exactly those character IDs, and undoing a delete means clearing exactly those tombstones. No transformation is required at all — which is a concrete, practical argument for CRDTs that goes beyond "they converge nicely."

Two semantics to get right and to mention:

• Undo is per-user. Each client keeps its own stack of its own operation IDs. Bob pressing undo must never revert Alice's work — that is the single most common bug in homegrown collaborative editors.
• Redo after concurrent edits. If Alice undoes, then Bob types into the affected region, Alice's redo must apply relative to the current state, which means the same transform-forward treatment. Some editors simply clear the redo stack when a remote op touches the affected range; that is a defensible product decision, and saying "I'd choose the simpler semantics here and document it" is a fine answer.

4.3 Forty million operations and a one-second open

Why it's hard. A document's history is its source of truth, but replaying 40M operations client-side takes minutes. CRDTs make it worse: tombstones are never removed, so a document that has had 10M characters typed and deleted still carries 10M tombstones. Memory and load time grow with total historical activity, not current size.

Solution — snapshot, compact, and tier.

Open protocol:
  1. Fetch the newest snapshot         (a single S3 GET, ~200 KB gzipped)
  2. Fetch ops since that snapshot     (a bounded range scan, typically < 500 ops)
  3. Apply the tail                    (milliseconds)
  Total: one round trip and a small delta, independent of the document's age.

# Snapshot policy: bounded work on open, bounded storage growth.
SNAPSHOT_EVERY_OPS = 1000
SNAPSHOT_EVERY_SECONDS = 300

async def maybe_snapshot(doc):
    if doc.ops_since_snapshot < SNAPSHOT_EVERY_OPS and \
       doc.seconds_since_snapshot < SNAPSHOT_EVERY_SECONDS:
        return
    state = doc.encode_state()            # Yjs: Y.encodeStateAsUpdate(doc)
    await s3.put(f"snap/{doc.id}/{doc.revision}", state)
    await meta.set_latest_snapshot(doc.id, doc.revision)
    # Keep the last N snapshots for version history; the op log stays authoritative
    # for fine-grained history but moves to cold storage beyond 90 days.

Tombstone garbage collection is the CRDT-specific half. A tombstone can be removed once every client has acknowledged a revision beyond it — no future operation can reference it. Track a per-document min_acked_revision across all active clients, and compact below it. For clients that have been offline longer than the compaction horizon (say 30 days), treat their reconnect as a full re-sync rather than a merge; that is what 4.5 handles.

Also worth stating: keep the op log for history and audit (it is append-only and cheap in cold storage) but never make interactive loading depend on it. Two different systems with two different SLAs sharing one write path.

4.4 Presence: 12,500 messages/second for one document

Why it's hard. Cursor and selection updates fire on every keystroke and every mouse move. With 50 editors, naive broadcast is 50 senders × 50 receivers × several updates/sec — tens of thousands of messages per second for a single document, carrying information that is stale before it is rendered.

Solution — treat presence as a fundamentally different data class from content.

	Content ops	Presence
Durability	Persisted forever	Never persisted
Delivery	Guaranteed, ordered	Best-effort, droppable
Rate	As fast as typed	Throttled to ~10 Hz, coalesced
On disconnect	Nothing lost	State evicted after a timeout

// Coalesce: only the newest cursor position matters. Batch the room's awareness
// state and flush on a fixed tick — 50 editors produce 10 frames/sec, not 2,500.
class PresenceHub {
  constructor(room) { this.pending = new Map(); setInterval(() => this.flush(), 100); }
  update(userId, state) { this.pending.set(userId, state); }   // overwrite, don't queue
  flush() {
    if (!this.pending.size) return;
    this.room.broadcast({type: 'presence', updates: [...this.pending]});  // one frame
    this.pending.clear();
  }
}

Cursor positions must be expressed as relative positions (in CRDT terms, a reference to a character identity plus an offset), not absolute indices. An absolute index becomes wrong the moment anyone types above it, producing the jittery, wandering cursors that make naive implementations feel broken.

4.5 A client that has been offline for a month

Why it's hard. Real-time merge assumes small divergence. A client returning after a month may have 5,000 local operations while the server has 200,000 — and the server has likely compacted the history the client would need to transform against. In OT this is close to unsolvable; transforming 5,000 ops against 200,000 is 10^9 transformations, and if the base revision has been compacted away there is no correct answer at all.

Solution — bound the real-time path and hand long divergence to a batch path.

async def reconnect(client_state, doc_id):
    server = await load(doc_id)
    gap = server.revision - client_state.base_revision

    if gap < FAST_PATH_OPS:                # ~1,000: transform inline, milliseconds
        return await room.merge_incremental(client_state)

    if client_state.base_revision >= server.compaction_horizon:
        # State-based CRDT merge: exchange full states, merge by identity.
        # Cost is O(state), not O(ops) — this is why CRDTs win at long divergence.
        return await offline_merge.state_merge(client_state, server)

    # Past the horizon: we cannot merge correctly. Do NOT guess.
    return ForkDocument(
        canonical=server,
        fork=f"{server.title} (offline copy from {client_state.device})",
        note="Merged automatically where possible; review changes.")

The third branch is the honest one, and interviewers notice honesty here: when you cannot merge correctly, fork visibly rather than silently losing work. Same principle as Dropbox's conflicted copies.

This is the strongest practical argument for CRDTs: a state-based merge is well-defined regardless of how long the divergence lasted, because merging is a join on identities rather than a replay of history.

4.6 One document, one actor — and what happens when it is hot

Why it's hard. Correctness depends on serialising operations per document. But the room actor is a single point of failure and a single point of throughput for that document: if the node hosting it dies, editing stops; if a document has 500 concurrent viewers of a live-edited doc, one actor is broadcasting to 500 sockets from one thread.

Solution.

• Route by consistent hash on document_id so every client for a document reaches the same node, with sticky WebSocket routing at the gateway. Cloudflare Durable Objects and Akka Cluster Sharding both provide exactly this primitive; naming them shows you know the pattern has a name.
• Fail over from the log. The actor's state is a cache of the op log. On node loss, the document is rehydrated elsewhere from snapshot + tail, and clients reconnect with their last known revision and replay their unacked ops. Editing pauses for the failover duration (~1–2 seconds) rather than losing data. Say the number.
• Split editors from viewers. Viewers do not need the room actor at all. Attach them to a read-only fan-out tier subscribed to the room's op stream — a tree of relays if the audience is large. The actor then broadcasts to a handful of relays instead of 500 sockets.
• Backpressure a hot document. If op rate exceeds what the room can broadcast, batch ops into 50ms frames. Users perceive 50ms batching as instantaneous, and it converts 250 messages/sec into 20.

4.7 Permissions that change while people are typing

Why it's hard. An admin revokes Bob's access mid-session. Bob has an open WebSocket, a full local copy of the document, and pending unsent operations. Checking the ACL only at document open means Bob keeps editing for hours. Meanwhile, "anyone with the link can comment but not edit" needs enforcement per operation type, not per connection, and a link-shared document can have thousands of anonymous sessions.

Solution — authorise per operation at the room, and push revocations.

def handle_op(session, op):
    # Cheap: the room holds the ACL in memory, refreshed on change events.
    perm = room.acl.for_user(session.user_id)
    if not perm.allows(op.kind):          # edit / comment / suggest / read
        session.send({"type": "denied", "op": op.id, "reason": perm.reason})
        return
    room.apply(op)

# The ACL service publishes revocations; the room reacts immediately.
async def on_acl_change(doc_id, user_id, new_perm):
    room = rooms.get(doc_id)
    room.acl.update(user_id, new_perm)
    if new_perm.is_none():
        room.evict(user_id, reason="access_revoked")   # close the socket now

Two details worth adding: suggestions mode means an operation is recorded but applied to a parallel branch, which is naturally expressible as a separate CRDT sub-document merged on accept; and revocation cannot recall the copy Bob already has — be explicit that you are preventing future access, not achieving DRM, because pretending otherwise is a worse answer than acknowledging it.

5. What breaks first

Event	First failure	Mitigation
50 editors in one doc	Broadcast fan-out from a single actor	50ms op batching; relay tier for viewers
Document with 5 years of edits	Load time, tombstone bloat	Snapshot every 1k ops; GC tombstones below min_acked_revision
Room node crash	Editing pauses for that document	Rehydrate from snapshot + tail; clients replay unacked ops
Client offline for a month	Merge impossible past the compaction horizon	State-based CRDT merge; visible fork as the honest fallback
Paste of a 10 MB document	One enormous op stalls the room	Split large inserts into bounded chunks; per-session op rate limits
Link shared publicly, 10k viewers	Connection tier saturation	Read-only relay tier; viewers never touch the room actor

6. Cheat sheet

• Algorithm: CRDT (Yjs) for a greenfield build — offline and reconnect are free. OT if the server is authoritative anyway and memory is tight. Never hand-roll either.
• Undo: per-user stack of op IDs; derive the inverse at undo time and transform it forward; apply as a new op.
• History: snapshot every 1k ops or 5 minutes; open = snapshot + tail; op log retained separately for audit.
• Presence: ephemeral, coalesced, 10 Hz, relative positions. A different data class from content.
• Topology: one actor per document, consistent-hash routed, rehydrated from the log on failure; viewers on a relay tier.
• Offline: fast path under ~1k ops, state merge beyond it, visible fork past the compaction horizon.
• The one-liner: "Serialise per document with a single-threaded room actor so ordering is trivial, pick a convergent algorithm off the shelf, and spend your real engineering on snapshots, undo semantics, and long divergence — which is where the actual bugs live."