Design Google Docs: Real-Time Collaborative Editing Without Losing a Keystroke

Listen

Listen. Users create and edit rich text documents. Many people can edit at once and see each other's cursors live. There is version history with restore, comments anchored to ranges of text, and sharing with view, comment and edit permissions. Non-functional: others see your edit within a couple of hundred milliseconds, every copy of the document converges to the same text, and an edit that was acknowledged is never lost.

Scope out spreadsheets, slides and export. Ask the questions that bound the hard part. How many simultaneous editors per document? About a hundred, with more people just viewing. Is offline editing required? Yes, for minutes or hours, which matters for the algorithm choice. How big can a document get? Tens of megabytes, with images stored separately as blobs.

Ask scale

Ask about scale. Fifty million daily users; at peak, five million documents are open and two million people are actively typing. Clients batch keystrokes roughly every two hundred milliseconds, so each typist sends about one operation a second: two million operations a second overall. At a hundred bytes each, raw op logs would be many terabytes a day, so we must compact them into snapshots. Crucially, a single document usually has only one to three editors.

50M daily users
peak: 5M docs open, 2M users
  actively typing
client batches keystrokes
  every ~200 ms → ~1 op/s each
  → ~2M ops/s overall

op ≈ 100 B → 200 MB/s
  ≈ 17 TB/day raw at peak
  → compact into snapshots
per doc: usually 1 to 3 editors

Define API

Define the API. Over HTTP: create a document, load the latest snapshot together with its revision number, list history and manage sharing. Then the client opens a WebSocket for the document. It sends operations tagged with the revision they were based on and a client sequence number. The server acks with the new revision, and pushes other people's operations and cursor positions.

REST:
  POST /docs → { doc_id }
  GET  /docs/{id} → snapshot
        + revision
  GET  /docs/{id}/history
  POST /docs/{id}/share
WebSocket /docs/{id}/live:
  → op { base_rev, client_id,
         client_seq, ops[] }
  ← ack { client_seq, rev }
  ← remote op, cursor

Data model

The data model has three parts. Document metadata and access control lists in a relational database, where transactions and joins help. An append-only operation log keyed by document and revision number, in a wide-column store built for heavy appends. And snapshots: the full document at some revision, stored as blobs in object storage. The current document is the latest snapshot plus the operations after it.

docs (SQL): id, owner, title,
  latest_rev, snapshot_rev
acl: (doc_id, principal, role)

ops (wide-column, append):
  PK (doc_id, rev)
  client_id, client_seq,
  op payload, ts

snapshots (object storage):
  docs/{id}/rev-4200.bin

High-level design

Draw the high-level design, starting with opening a document. Editor A's connection lands on an edge gateway, which checks their permission in the metadata database, then asks the session registry which server owns document nine. If no server owns it yet, one takes a lease on it, loads the latest snapshot, replays the operations after it, and holds the document in memory. All editors of document nine connect through to that one server.

Now an edit. Editor A types, and the client sends insert s at position three, based on revision forty-one. The session server is the single place that orders operations for this document. It adjusts the operation if needed, assigns revision forty-two, appends it to the op log, acks A and broadcasts it to B and the other editors. The interesting word there is adjusts, and that is the first deep dive.

Deep dive: conflicts

Deep dive one: why concurrent edits conflict. The document says cat. Editor A appends s at position three, making cats. At the same time editor B inserts the, with a space, at position zero. If B's copy applies A's operation unchanged, it inserts s at position three of the cat and produces nonsense. Positions shift whenever someone else edited earlier in the text. Locking paragraphs or last-writer-wins would lose work, so we need an algorithm.

doc: "cat"  (both at rev 1)
A: insert "s" at 3  → cats
B: insert "the " at 0
        → the cat

apply both naively on B:
  "the cat" + "s" at 3
  → "thes cat"   ✗

positions shift when someone
else edits before them

Deep dive: OT

Deep dive two: operational transformation, or OT. The server orders operations. B's insert became revision two. A's arrives based on revision one, so the server transforms it against everything A had not seen: B inserted four characters before position three, so A's insert moves to position seven. Everyone ends with the cats. OT is mature and compact, and it relies on one central server ordering each document's operations, which we have.

server order: B’s op is rev 2
A’s op arrives based on
  rev 1, so transform it:
  B inserted 4 chars at 0,
  before position 3
  → A’s op becomes
    insert "s" at 7
result everywhere: "the cats"

needs one central ordering
  point per document

Deep dive: CRDT

The alternative is a CRDT, a conflict-free replicated data type. Every character gets a unique ID, and an insert says after character X, not at position three, so positions never shift. Operations can merge in any order and all copies converge, which is excellent for long offline sessions and peer-to-peer. The cost is metadata per character and tombstones for deleted text. With a central server already in the design, OT is a fine choice; mention CRDTs as the offline-first option.

Deep dive: ownership

Deep dive three: ownership. OT needs exactly one server ordering each document at a time. A session server takes a lease on a document in etcd or ZooKeeper and renews it every few seconds; edge gateways route all connections for that document to the lease holder. Each server owns thousands of small documents. To be safe against a paused old owner, every op log write carries the lease epoch and the log rejects writes from an older one.

Deep dive: durability

Deep dive four: durability. Never ack an operation until it is durably appended to the op log; batching appends every fifty milliseconds keeps that cheap. Every five hundred operations or so, or when the last editor leaves, write a snapshot. Loading a document is the latest snapshot plus the few operations after it. Old operations are compacted into history checkpoints a few minutes apart, so raw logs do not grow forever.

Deep dive: failover

Deep dive five: failover. If the session server dies, its lease expires within about ten seconds and another server takes over, rebuilding the document from the snapshot and the op log. Clients reconnect and resend any operations that were never acked. The server dedupes on client ID and client sequence, so an op that was logged but not acked is not applied twice. Since we ack only after logging, nothing acknowledged is lost.

Deep dive: offline

Deep dive six: offline editing. The client keeps editing its local copy and queues operations with the revision they were based on. On reconnect, it sends the queue, and the server transforms them against every operation since that revision before applying them. The client does the mirror image for operations it missed. For hours of heavy offline edits the merges get messy, which is exactly where CRDT-based editors shine.

Deep dive: extras

Deep dive seven: the extras. Cursors and selections are ephemeral: never logged, throttled to about twenty updates a second, and broadcast only within the document's session. Version history is a list of pointers to snapshot revisions; restoring an old version is simply a new edit that replaces the content, so history is never rewritten. Comments are anchored to a range, and that range is transformed by every operation, just like a cursor.

Deep dive: access

Permissions. The edge checks the role at connect, and the session server caches it and checks each operation: viewers receive operations but cannot send them, commenters may only send comment operations. When an owner revokes access, the change is published as an event and the session drops that user's connection immediately, instead of waiting for them to reload. Link sharing uses a signed token carrying the granted role.

Trade-offs

The trade-offs. One owner per document makes ordering simple, but caps a single document at what one server can handle, which is fine with a hundred editors. OT is compact and central; CRDTs are better offline but heavier. Failover costs a pause of several seconds. Monitor op ack latency, transform errors, lease churn, log write lag and snapshot age. At ten times the users, simply add session servers; documents spread across them by lease.

Interview summary

The summary. Editors connect over WebSockets to the single session server that owns the document, enforced with a lease and a fencing epoch. That server uses operational transformation to adjust concurrent edits and assigns each a revision. Operations are logged before they are acked, with snapshots every few hundred. On failover a new owner replays the log and clients resend unacked operations, deduped by sequence. Cursors are ephemeral. A CRDT is the offline-first alternative.