google-doc

Start with the simplest case: one user creates a document and expects it to still exist after a refresh. This means we need a stable document identity and durable storage.

Document ID Generation

Use opaque, globally unique IDs (e.g., ULIDs or UUIDs) rather than sequential auto-increment. Sequential IDs expose document count and allow enumeration. Opaque IDs are safe for sharing links and work across distributed servers without coordination.

Metadata vs Content Split

Store document metadata (title, owner, timestamps) in a relational database and document bodies in object storage (S3, GCS). The access patterns are fundamentally different:

• Metadata is small, queried frequently (list user's docs, check ownership)
• Content is large, accessed on document open (read once, edit in real-time layer)

Splitting them keeps metadata queries fast and allows content storage to scale independently.

✅ Works for: A single user creating and editing their own documents

❌ Missing: No real-time collaboration — other users can't see edits until they refresh. No version history. No permissions. No concurrent edit handling.

Single-user CRUD can't support collaboration. We need a live channel that streams edits as they happen. If we only poll every few seconds, the editor feels laggy and we waste requests when nothing changes.

Communication Protocol: WebSocket

WebSocket provides bidirectional, persistent connections. Clients send edits and receive other users' edits over the same channel. This is better than:

• Polling: wastes requests when nothing changes, adds latency
• SSE: server-to-client only — we'd need a separate channel for client edits

Fan-Out via Pub/Sub

With a single gateway server, broadcasting to all connected clients is trivial. But once we scale to multiple gateway instances, collaborators on different gateways won't receive updates. A pub/sub system (Redis Pub/Sub, Kafka) solves this:

1. Client sends an edit → gateway forwards to the service layer
2. Service persists the edit and publishes to the pub/sub topic for that document
3. All gateway instances subscribed to that document's topic receive the update
4. Each gateway broadcasts to its connected clients

The pub/sub layer decouples the edit pipeline from the delivery pipeline.

✅ NFRs addressed: Low-latency edit delivery via WebSocket, horizontal gateway scaling via pub/sub

❌ Still missing: No handling of concurrent edits — if Alice inserts at position 10 and Bob deletes at position 5 simultaneously, the positions are now wrong. Edits are delivered but not merged correctly.

Live streaming isn't enough. If two users edit the same sentence at the same time, each client can end up with a different result. We need convergence — all replicas reach the same final state — not just fast delivery.

The Problem Illustrated

Document state: "Hello World"

• Alice: insert "Beautiful " at position 6 → "Hello Beautiful World"
• Bob: delete "World" (positions 6-10) → "Hello "

Without transformation, applying both operations naively could produce:

• On Alice's screen: "Hello Beautiful " (Bob's delete removes part of her insert)
• On Bob's screen: "Hello Beautiful World" (Alice's insert before Bob's delete)

The documents have diverged. This is unacceptable.

Operational Transformation (OT)

OT solves this by transforming concurrent operations so they account for each other's effects. The Collaboration Service receives all operations and:

1. Assigns a monotonic sequence number per document (the Sequencer)
2. Compares each incoming operation's base_revision_id against the current head
3. If the operation is based on a stale revision, transforms it against all operations that happened since that revision
4. Appends the transformed operation to the Operation Log (append-only)
5. Updates the document state and publishes the result to pub/sub

The key constraint: one sequencer per document. This ensures a total order of operations within a document. Different documents have independent sequencers — parallelism across documents, serialization within a document.

OT Transform Example

With OT, the server transforms Bob's delete to account for Alice's insert:

• Alice's insert at position 6 added 10 characters
• Bob's delete was at positions 6-10, but now those characters shifted right by 10
• Transformed delete: positions 16-20

Both clients end up with: "Hello Beautiful " — converged.

Why OT over CRDTs?

We already have a Collaboration Service in the middle of every edit — a natural ordering point. OT leverages this to keep client logic simple. CRDTs are better for offline-first scenarios (no central server needed), but add metadata complexity to every character.

✅ NFRs addressed: Convergence guaranteed by server-ordered OT, read-your-writes via optimistic local apply

❌ Still missing: No cursor presence (users can't see where others are editing). No permissions. No version history.

Content syncing is working, but collaboration feels incomplete without seeing where other users are editing. Cursor updates are frequent (every keystroke) and short-lived (meaningless after a user disconnects). Treating them like durable edits wastes resources.

Ephemeral Presence Store

Cursor state lives in an in-memory store (Redis) with TTL-based expiry. If a user's cursor updates stop arriving (disconnect, tab switch), the TTL expires and the cursor disappears from other users' screens. No database write, no cleanup job.

The Flow

1. Client sends presence_update over WebSocket: {cursor_pos: 42, selection: [42, 50]}
2. Gateway forwards to the Presence Service
3. Presence Service writes to the in-memory store with a 5-second TTL
4. Presence Service broadcasts to other collaborators via pub/sub

Throttling and Coalescing

Cursor moves happen on every keystroke — potentially 10+ updates/second per user. To prevent flooding:

• Client-side throttle: batch cursor updates to 4-5/second
• Server-side coalesce: if multiple updates arrive for the same user before broadcast, only send the latest position

Presence is best-effort. Under load, dropping cursor updates is acceptable — the next update will correct the position. This is fundamentally different from edit operations, which must never be dropped.

✅ NFRs addressed: Low-latency presence updates, graceful degradation under load (presence is best-effort)

❌ Still missing: No access control — anyone with the document URL could potentially connect. No version history for recovery.

Collaboration only works if access is controlled. Every read and write — including WebSocket messages — must check permissions.

Dedicated Access Control Service

Permissions live in a separate Access Control Service with its own store, rather than embedded in document metadata. This keeps permission checks fast and independent from document reads.

Permission Model

Permission Checking Points

• Document open (REST): Document Service checks with Access Control Service before returning content
• WebSocket connect: Gateway checks permissions before upgrading the connection
• Edit operation: Collaboration Service verifies the user still has edit access before processing
• Share link: Maps a token → permission record with role and optional expiry

Caching Permissions

Permission checks happen on every operation. To avoid per-operation database queries, cache permission results with a short TTL (30-60 seconds). When permissions change (user revoked), the cache entry expires and the next check fetches the latest state.

✅ NFRs addressed: Security (every read/write is permission-checked), separation of concerns

❌ Still missing: No version history — users can't recover from accidental deletions or see what changed over time.

The final piece: users need to see what changed and recover from mistakes. Version history requires storing document states over time without exploding storage costs.

Hybrid Snapshots + Deltas

Three approaches, each with a flaw:

• Full snapshots only: fast restore, but 100KB × every edit = massive storage
• Deltas only: storage-efficient, but restoring version #1 of a document with 10,000 edits means replaying all 10,000 operations
• Hybrid (recommended): periodic snapshots (every N operations) with deltas in between

The Snapshot Writer runs as a background process:

1. Monitors the Operation Log
2. Every ~100 operations, compacts them into a full snapshot
3. Writes the snapshot blob to Object Storage
4. Creates a Revision record pointing to the snapshot

To restore version V:

1. Find the nearest snapshot before V
2. Replay deltas from that snapshot to V
3. Maximum replay: 99 operations (bounded by snapshot interval)

Compaction and Retention

The Operation Log grows continuously. Compaction merges older operations into snapshots and discards the raw ops. Retention policy: keep all snapshots for 30 days, then downsample to weekly snapshots for the first year, and monthly snapshots thereafter.

NFR Scorecard

This is one of the most frequently asked questions in a Google Docs interview. The answer depends on where you want complexity and what your product prioritizes.

Operational Transformation (OT)

A central service orders edits and rewrites (transforms) them so user intent is preserved.

• Server-side complexity, client stays lightweight
• Requires a central sequencer (ordering point)
• Used by: Google Docs (original), Microsoft Office Online

Conflict-free Replicated Data Types (CRDTs)

Each character carries metadata (a unique ID, position markers) so replicas can merge without a central order.

• Client-side complexity, no central coordination needed
• Great for offline-first and peer-to-peer collaboration
• Used by: Figma, Apple Notes, Notion (partial)

Our Choice: With a centralized Collaboration Service and online-first workflow, OT fits better. We already operate a sequencer — OT leverages it to keep client logic simpler. If offline-first becomes a primary requirement, CRDTs become more attractive despite their metadata overhead.

All clients must apply edits in the same sequence. The ordering mechanism is the heart of the collaboration engine.

Three Ordering Strategies

1. Client timestamps: Sort by client-provided timestamps. Fails due to clock skew — two clients with 500ms clock difference produce different ordering.
2. Global sequencer: One sequencer for all documents. Correct but becomes a bottleneck — every edit across all documents must go through a single point.
3. Per-document sequencer (recommended): Each document gets its own independent ordering stream. Correctness is local to a document, and the system scales by sharding documents across sequencer instances.

How It Works

1. Client sends operation with base_revision_id (the last revision it saw)
2. The sequencer checks: is base_revision_id the current head?
   • Yes: assign next sequence number, append to log
   • No: transform the operation against all ops since base_revision_id, then assign and append
3. Broadcast the (possibly transformed) operation to all clients

Sharding

Sequencers are sharded by document_id. A consistent hash ring maps each document to a sequencer instance. If a sequencer instance fails, the document is reassigned to another instance. In-flight operations may need to be replayed from the Operation Log.

A single document with 100 concurrent editors creates a fanout hotspot. The sequencer must stay single-threaded per document (for ordering correctness), but it can't also handle 100× fanout for every operation.

The Problem: Fanout Amplification

With 100 editors, each producing ~1 op/sec:

• Sequencer processes 100 ops/sec (manageable)
• But each op must be broadcast to 99 other users
• That's 100 × 99 = 9,900 outbound messages/sec per document

If the sequencer handles fanout directly, it becomes I/O bound on outbound messages rather than the ordering logic.

Solution: Fanout Tree

Separate ordering from delivery:

1. The sequencer publishes each ordered operation once to a pub/sub topic
2. Multiple gateway nodes subscribe to the topic
3. Each gateway relays the operation to its connected clients (a subset of the 100 editors)
4. The total fanout is distributed across gateways

If 4 gateway nodes each serve 25 clients, each gateway sends 25 messages per operation — the fanout is parallelized across gateways.

Backpressure

If a gateway is slow (network issue, overloaded), it falls behind on the pub/sub topic. Backpressure ensures the slow gateway doesn't block the sequencer or other gateways. The slow gateway's clients may see a brief delay, but the system continues operating.

Revision storage balances restore speed vs storage cost:

Snapshot Interval Tuning

The snapshot interval controls the tradeoff:

• Snapshot every 50 ops → max 49 ops to replay, more storage
• Snapshot every 500 ops → max 499 ops to replay, less storage

For a 100KB document, each snapshot costs ~100KB. At 1 edit/sec, a snapshot every 100 ops creates one snapshot every ~2 minutes:

$100 \text{ KB} \times \frac{86{,}400 \text{ sec}}{100 \text{ ops}} = 86.4 \text{ MB/doc/day}$

For 1M documents with active edits (10% of total), that's ~8.6 TB/day before retention policies kick in.

Compaction

After creating a snapshot, the operations between the previous snapshot and the new one can be discarded from the live Operation Log. They're already captured in the snapshot. This keeps the Operation Log bounded.

Retention policy: All snapshots for 30 days → weekly snapshots for 1 year → monthly snapshots indefinitely.

Offline editing creates a divergent history. The client has a local branch of operations that the server hasn't seen, while the server has accepted operations from other collaborators that the offline client hasn't seen.

Queue and Rebase Strategy

1. While offline, the client queues operations in a local log
2. On reconnect, the client sends its base_revision_id (last known server revision) and all queued operations
3. The server identifies the divergence point and transforms the client's operations against everything that happened since
4. The transformed operations are applied to the server state
5. The server sends back the transformed result + all operations the client missed

This is essentially a rebase (like in Git): the client's branch is replayed on top of the server's latest state.

Conflict Copy Fallback

If the offline period was very long (thousands of operations diverged), transformation may produce semantically unexpected results. In this case, create a conflict copy — a separate document with the user's offline changes — and let the user manually merge. This is the same approach Google Docs uses for extended offline periods.

Collaborators in Tokyo and New York editing the same document face a fundamental constraint: network latency between these regions is ~150ms round-trip. The OT sequencer, which must be a single ordering point per document, can't exist in both regions simultaneously.

Per-Document Home Region

Each document is assigned a home region where its sequencer runs. This is typically the region of the document creator, or can be migrated to the region with the most active editors.

• Users near the home region: connect to a local gateway → edit→ local sequencer → ~10ms round trip
• Users far from the home region: connect to a local gateway → edit forwarded to home region sequencer → ~150ms round trip

The gateway layer is fully distributed — users always connect to their nearest gateway. But the sequencer for their document may be in another region.

Mitigations for Cross-Region Latency

• Optimistic local apply: the client applies its own edits immediately (before server confirmation). The OT transform will adjust if needed, but the user never feels the 150ms delay for their own keystrokes.
• Read replica caching: document snapshots and metadata are replicated to all regions. Opening a document is always fast (local read). Only active editing goes through the home region.
• Home region migration: if all editors move to a different region, migrate the sequencer to reduce latency.

The following topics contain open-ended architectural questions for staff+ conversations.