Google Docs

Interview scope and guarantees

Edit a shared document concurrently, show collaborators, reconnect after offline edits, retain history and enforce permissions. Choose the document model before the concurrency algorithm. Plain text, rich text and nested blocks have different operation semantics.

Capacity worksheet

Assume 100,000 concurrent documents with 5 active users sending 2 operations/s: 1 million operations/s globally. At 100 bytes/operation the raw stream is 100 MB/s before fanout. One document with thousands of collaborators is a separate hot-key problem from many ordinary documents.

Concrete API contract

POST /documents -> {documentId}
CONNECT /documents/{id}/session {lastVersion}
operation {clientId,opId,baseVersion,payload}
GET /documents/{id}/snapshot?version=...

Data model and access paths

documents(id PK,owner_id,permission_version,snapshot_version,head_revision,owner_epoch)
operations(document_id,sequence,actor_id,client_id,op_id,base_version,request_hash,payload); UNIQUE(document_id,client_id,op_id); PK(document_id,sequence)
snapshots(document_id,version,object_key,checksum); PK(document_id,version)
sessions(document_id,client_id,last_ack); PK(document_id,client_id)

Evolve a solution and explain each change

Figure — Three architecture decisions for Google Docs, including the pressure each introduces.

Step 1: Centralize edits

Assign a document authority and persist a canonical revision sequence. Concurrent offsets from old revisions cannot be applied blindly.

Step 2: Choose an operation model

Use a specified OT or CRDT protocol with stable operation identity and transformation/merge rules. Naming CRDT does not define deletion, undo, formatting, or convergence.

Step 3: Recover and enforce permissions

Snapshot with a log position, replay missing operations, and recheck edit grants. Presence messages and cursor positions are not durable content.

Responsibility overview

Figure — Connected responsibilities for Google Docs. Trace the authoritative and derived paths separately.

Worked end-to-end scenario

Two editors start with text AB at revision 10. A inserts X between A and B; B concurrently inserts Y at the same position. In a centralized OT design, the authority orders the operations and transforms the second position using a documented tie rule, so both clients converge to the same text. A retry retains its operation ID and does not insert X twice. A disconnected client obtains a snapshot at revision R and replays operations after R. Presence can expire without changing the document. Permission revocation prevents new edits even if the client still has an open connection.

Why these access paths matter

Store document identity, permission version, snapshot revision, and ordered operations. Operations include actor, client operation ID, base revision, and payload; uniqueness scopes retries correctly. OT and CRDT are alternative protocol choices here, not interchangeable labels. A content snapshot and its revision must form one consistent recovery boundary; independent reads can lose an operation.

Build the baseline first

1. Client optimistic edit → document owner → operation log.
2. Committed operation → collaborators → local reconciliation.
3. Reconnect → snapshot plus suffix → pending edit rebase.

Evolve the design under load

1. Document-key placement → independent collaboration owners.
2. Periodic snapshots → bounded log replay.
3. Presence channel → ephemeral cursor broadcasts.

Defend the hardest decision

For an OT design, transforms must preserve intended effects under concurrent operations; merely sorting arrival timestamps does not implement OT. A CRDT design uses stable identifiers and merge rules, often at the cost of metadata and tombstones. Pick one model and walk through simultaneous insertion and deletion. Presence can be best effort, but committed content must converge under replay and duplicate delivery.

Failure and recovery analysis

Two clients edit offline against the same old version. On reconnect, download a supported baseline, reconcile pending operations through the chosen algorithm and deduplicate op IDs. If the retained operation history is insufficient, the protocol needs a snapshot-based recovery path rather than silently discarding edits. Permission revocation must block new operations even on an existing socket.

Security and privacy boundary

Authorize document sessions and each mutation epoch, isolate tenants, and control access to historical snapshots.

Interview follow-ups with reasoning

Question: How do you compact history?

Question: How do you fail over a document owner?

Question: How do you validate convergence?

Operate and verify the design

Operation acknowledgement lag, replay failures, pending edits and snapshot recovery time.

Reorder and duplicate concurrent edits while revoking one editor; check convergence and authorization.

A second scenario to test transfer

Alice inserts “cat” at position 5 while Bob deletes the character at position 5 from the same base version. The protocol applies both using its declared transformation or CRDT ordering, producing a deterministic result at each client. Presence cursors can move without entering the durable edit log. A reconnecting client deduplicates operation IDs.

Two clients edit the same base version offline. What must the server provide when one reconnects after operation history expires?

Compare alternatives

A design-changing exercise

Would last-write-wins on the whole document satisfy collaborative editing?

Design workshop: a concrete central OT protocol

Choose plain text editing with single-character insert/delete operations as the core teaching model. Rich formatting, multi-character atomic ranges and offline edits beyond retained history are extensions. This restricted model is explicit: it is not a complete Google Docs or Yjs implementation. Assume local optimistic response, ordered durable server revisions and eventual convergence after acknowledged/replayed operations.

An insert I(p,c) inserts c before zero-based position p; delete D(p) removes the character at p. An operation carries document, actor, client ID, op ID, baseRevision and payload fingerprint. The document owner serializes accepted operations into canonical revision order. It transforms an incoming operation against all accepted operations after its base. For simultaneous inserts at the same position, the already accepted server operation wins the earlier position. Clients reconcile to this order, not their local wall clocks.

# Transform incoming single-character operation against accepted op.
def transform(incoming, accepted):
    if incoming.kind == 'insert':
        if accepted.kind == 'insert' and accepted.pos <= incoming.pos:
            incoming.pos += 1  # accepted wins equal-position tie
        elif accepted.kind == 'delete' and accepted.pos < incoming.pos:
            incoming.pos -= 1
    elif incoming.kind == 'delete':
        if accepted.kind == 'insert' and accepted.pos <= incoming.pos:
            incoming.pos += 1
        elif accepted.kind == 'delete':
            if accepted.pos == incoming.pos: return NO_OP
            if accepted.pos < incoming.pos: incoming.pos -= 1
    return incoming

The same-position delete becomes an acknowledged no-op: it must still receive a stable result/revision mapping so a retry does not unexpectedly delete another character. Bounds are validated against the transformed current text. Log stores both base revision and canonical operation plus actor identity; request uniqueness is document/client/op, and a changed fingerprint returns 409. A valid no-op can be logged as a revision to simplify acknowledgments.

Figure — Transform against AB at base revision 7.

Both clients initially see AB. A optimistically inserts X and sees AXB; B optimistically inserts Y and sees AYB. Server accepts X first as revision 8. It transforms B's Y to position 2 and accepts it as 9. Clients must replace/reconcile optimistic state using canonical acknowledgments, not append a second insertion for their own echoed operation. A simple teaching client maintains authoritative snapshot+suffix and a queue of pending intents; on server updates it reconstructs canonical text and rebases pending intents under the same deterministic protocol. Production OT clients need a fully tested pending-operation transform protocol; the server sketch alone does not prove arbitrary client transforms converge.

Figure — Concurrent inserts converge to AXYB.

Snapshot(text,revision) is captured consistently with the operation log. Reconnect returns snapshot S plus operations after S to a declared high watermark. Retain the suffix until all supported clients can recover or the retention policy expires. An expired base cannot be transformed without its history: return history_expired with a new snapshot. This design preserves unsent client text as a recoverable draft and asks for explicit conflict reconciliation rather than claim an arbitrary offline patch merges safely.

A CRDT extension chooses stable character IDs and documented ordering/deletion metadata instead of offset transformations; do not mix the two models midway. If adopting Yjs, use its actual update/state-vector APIs and garbage-collection semantics rather than substituting this toy OT for that protocol. Rich-text attributes, undo and range deletes need additional transformation rules and convergence tests. This baseline excludes them honestly; their extension design must identify operation identity, range anchors and inverse intent rather than simply name CRDT.

Presence is ephemeral. Cursor positions can rebase through canonical inserts/deletes, but presence never enters the durable content log as an edit. A presence cursor at 2 moves to 3 after insertion at 1; deleted anchors need a declared nearest-valid-position rule. Permission checks apply on connect, every operation and snapshot read; a revoked editor's existing socket is not permanent authorization.

Owner failover reads the durable head, acquires a higher document epoch and fences old write commits. An acknowledged operation survives under the selected durability contract; a lost response retries its op ID. Compaction writes a verified snapshot and only removes suffix history beyond the supported reconnect horizon. Active pending clients cannot justify indefinite retention, but expiry must be explicit.

Exercise: At base AB, A inserts X at 1 and B deletes B at 1. A is accepted first. What happens to B's position and final text?

Yjs document updates documents a real CRDT alternative. This chapter's chosen baseline is the explicitly restricted central OT model above.

Technical references

Kafka processing and external-sink boundaries.

PostgreSQL transaction isolation and concurrent updates.