Phase 5 · Chapter 6

Google Docs: Real-Time Collaboration & CRDT

How multiple people edit the same document simultaneously without destroying each other's work

This is the hardest system design problem in this curriculum. Not because the components are exotic — you know WebSockets, you know databases, you know queues — but because the core problem is a distributed systems problem that cannot be solved with the tools you use everywhere else. Two users editing the same text at the same time produce a conflict that no amount of locking, transactions, or eventual consistency can resolve correctly without understanding the mathematics of the document itself. After this chapter you will understand why naive approaches to collaborative editing fail, how Operational Transformation solves it for two users and becomes intractable for many, how CRDTs eliminate the coordination problem entirely, and how to design the complete system — WebSocket server, persistence layer, presence, and conflict resolution — that makes real-time collaboration work at scale. If you can design and explain this system, you are in the top tier of system design candidates anywhere.

Part 1: The Problem — Concurrent Edits on Shared State

Two users are editing the same document. The document contains one word: "Hello".

User A, at position 5 (after the 'o'), types " World". The document should become "Hello World". User B, simultaneously, deletes "Hello" entirely. The document should become "".

Both operations are valid in isolation. Both users' intentions are clear. But they happened concurrently — neither user saw the other's change before making their own. The question is not "who wins" (last write wins destroys one user's work). The question is: what is the correct document state that respects both users' intentions?

There is no single obviously correct answer. But there is a class of clearly wrong answers:

• A's insert at position 5 applied after B's delete: "Hello" is gone, so position 5 does not exist. Inserting at position 5 either crashes or inserts at the wrong place.
• B's delete applied before A's insert, but the delete range was computed before A's insert: B's delete removes "Hello" from the document that now reads "Hello World", but B's operation was delete(0, 5) — it was computed against the 5-character document, not the 11-character one.

This is the core problem: operations are defined against a specific document state, but by the time they arrive at other users, the document state has changed. Every approach to collaborative editing is a different answer to the question: how do you transform an operation so it remains correct when applied to a document that has already been modified by concurrent operations?

Part 2: The Naive Approaches and Why They Fail

Last write wins

The simplest approach: whenever a user submits a change, overwrite the server's current document with their version. The last write wins.

This destroys concurrent work. While User A was typing " World", User B submitted their change (deletion). User B's version has no " World". When User A submits, User A's version has " World" but not B's deletion. Whichever arrives last overwrites the other's work. One user's changes silently disappear every time two users edit simultaneously.

Acceptable for: single-user documents with no concurrency. Completely unacceptable for any collaborative system. Google Docs cannot use this.

Locking — one user at a time

Lock the document when a user starts editing. Other users can only read, not write. Release the lock when the editing user saves.

This serialises all edits. Zero conflicts. But "collaborative editing" is now "taking turns editing." The defining feature of Google Docs — multiple cursors, real-time updates, simultaneous editing — is impossible. The lock is the product.

Differential sync (naive merge)

Each client maintains a shadow copy of the document (the last known server state). When a user edits locally, compute a diff between their current document and their shadow copy. Send the diff to the server. Apply the diff to the server's copy. Send the patched server version back.

This works for non-concurrent edits. It fails when two users edit simultaneously because both diffs are computed against the same shadow copy. When the server applies diff A and then diff B (computed against the pre-A state), diff B's position references are wrong. The same misalignment problem as before, just hidden inside a diff algorithm.

The real collaborative editing solutions — OT and CRDT — are fundamentally different approaches. They do not merge documents. They transform or redefine operations so that concurrent operations compose correctly regardless of order.

Part 3: Operational Transformation — The Classic Solution

Operational Transformation (OT) is the algorithm that powered Google Docs from its beginning (originally as EtherPad, acquired by Google). The core idea: when an operation arrives at a client that has made concurrent operations, transform the arriving operation to account for those concurrent operations before applying it.

Operations

A text document has two primitive operations:

Insert(position, character)   — insert character at position
Delete(position)              — delete the character at position

Every edit is expressible as a sequence of these two operations. Typing "World" at position 6 is five Insert operations. Deleting "Hello" is five Delete operations.

The transformation function

Given two concurrent operations O1 and O2 that were both applied against the same document state, the transformation function T produces transformed versions:

T(O1, O2) → O1'   (O1 transformed to account for O2 having already happened)
T(O2, O1) → O2'   (O2 transformed to account for O1 having already happened)

The transformed operations can then be applied in either order and produce the same result:

Document + O1 + T(O2, O1) = Document + O2 + T(O1, O2)

This is the convergence property — regardless of the order in which operations are received, all clients end up with the same document.

A concrete transformation

Document: "Hello" (positions 0-4)

O1: Insert(5, " World") — User A inserts " World" after position 5 O2: Delete(0) — User B deletes character at position 0 ("H")

These were concurrent — both computed against "Hello".

Client A applied O1 first. Its document is now "Hello World". It receives O2 = Delete(0). O2 as received is still Delete(0). Applying it to "Hello World" deletes "H" → "ello World". This is correct — B intended to delete "H" and "H" is at position 0 in Client A's current document. No transformation needed here because O2's position (0) is before O1's position (5).

Client B applied O2 first. Its document is now "ello" (deleted "H"). It receives O1 = Insert(5, " World"). But wait — after B deleted position 0, all subsequent positions shifted left by 1. Position 5 in the original document ("Hello") is now position 4 in B's document ("ello").

The transformation must adjust O1's position:

T(Insert(5, " World"), Delete(0)):
  If Delete.position < Insert.position:
    Insert.position -= 1   (shift left by 1)
  Result: Insert(4, " World")

Client B applies Insert(4, " World") to "ello" → "ello World". Client A applies Delete(0) to "Hello World" → "ello World".

Both clients converge on "ello World". Both users' intentions were respected.

Why OT becomes intractable

For two concurrent operations from two users, the transformation logic is manageable — insert vs insert, insert vs delete, delete vs delete, four cases.

For three concurrent users, you need to handle operation histories: O1, O2, O3 all concurrent. When Client C receives O1 (which it must apply to a state that already has O2 and O3), the transformation must account for the full history: T(O1, O2, O3) — transform O1 against both O2 and O3. This requires transform composition — the ability to transform an operation against a sequence of other operations.

The mathematics of transform composition for arbitrary operation sequences is the problem that has defeated many OT implementations. The original Jupiter protocol (Google's early OT system) used a central server to linearise all operations and reduce this to two-party transformation. The server applies all operations in arrival order and sends transforms back to each client. This is why Google Docs requires a server: without a central authority to define operation order, three-or-more-user OT is unsolved in the general case.

The algorithm has been implemented correctly (Google Docs, Quill, CodeMirror's ot module) but the transformation functions are complex, hard to extend to new operation types, and require careful correctness proofs.

Part 4: CRDTs — Conflict-Free by Design

Conflict-free Replicated Data Types (CRDTs) take a different approach. Instead of transforming operations after the fact, they design the data structure so that concurrent operations always compose correctly by construction — no transformation needed, no central server required.

The key insight: the reason concurrent operations conflict is that they use position references that become invalid as other operations happen. If you replace mutable positions with immutable, globally unique identifiers for each character, the conflict disappears.

The Logoot / LSEQ approach

Instead of storing characters at numeric positions, assign each character a permanent unique identifier based on its intended location in the total ordering.

In Logoot, a character's identifier is a sequence of numbers called a path that encodes its position in the document's total order. The path for a character inserted between two existing characters is chosen to fall strictly between their paths — like choosing a rational number between two other rational numbers. The document's order is determined by sorting characters by their paths.

A simplified illustration:

Document: "Hello"
Characters with identifiers (paths):
  [1.0]:'H'  [2.0]:'e'  [3.0]:'l'  [4.0]:'l'  [5.0]:'o'

User A inserts ' ' after [5.0]:'o':
  New character: [5.5]:' '  (between 5.0 and the end, represented as 6.0)

User B inserts '!' after [5.0]:'o':
  New character: [5.3]:'!'  (also between 5.0 and 6.0, but different value)

Both operations can be applied in any order.
After both: sort by identifier → 'H','e','l','l','o','!', '  '
                                  1.0  2.0  3.0  4.0  5.0  5.3  5.5

The characters do not conflict. Both insertions between "o" and the end are assigned unique paths. Sorted by path, the document is deterministic regardless of insertion order. No transformation required.

Deletion in CRDT systems is handled with tombstones — rather than removing a character, mark it as deleted. The character's identifier remains, preventing later insertions that reference it from breaking. Garbage collection removes tombstones when no active session references them.

Why CRDTs work without a server

Because each operation is defined in terms of immutable character identifiers (not mutable positions), any client can apply any set of operations in any order and reach the same document state. This is the commutativity property — the order of operations does not matter.

Apply(Op1, Op2) to Document = Apply(Op2, Op1) to Document

This means CRDTs do not require a central server to linearise operations. Clients can exchange operations peer-to-peer, or through a server that simply relays without ordering. The document converges eventually as long as all operations eventually reach all clients. This is strong eventual consistency — a specific, provable form of eventual consistency.

The tradeoff: CRDT identifiers are larger than numeric positions (a Logoot path can be a sequence of numbers). For a large document with millions of characters and thousands of edits, the metadata grows. Production CRDT implementations (Yjs, Automerge) use compact binary encodings and incremental garbage collection to manage this.

Yjs — the production CRDT library

Yjs is the dominant open-source CRDT library. It implements a highly optimised CRDT for sequences (text, arrays) and maps (key-value). It handles encoding, garbage collection, and network transport, leaving you to focus on the application layer.

import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

// Create a shared document
const ydoc = new Y.Doc();

// Connect to a WebSocket server for synchronisation
const provider = new WebsocketProvider('wss://sync.samiksha.app', 'document:123', ydoc);

// Get the shared text type
const ytext = ydoc.getText('content');

// Bind to a text editor (ProseMirror, CodeMirror, Monaco, Quill all have Yjs bindings)
// Changes to the editor automatically update ytext and propagate to all connected clients

// Manual usage:
ydoc.transact(() => {
  ytext.insert(5, ' World');
});

// Listen for remote changes:
ytext.observe(event => {
  event.changes.delta.forEach(delta => {
    if (delta.insert) console.log('Remote insert:', delta.insert);
    if (delta.delete) console.log('Remote delete:', delta.delete);
  });
});

Yjs's WebSocket provider handles: connection management, sending local updates to the server, receiving and applying remote updates, and reconnection with catch-up (when a client reconnects after being offline, it receives all operations it missed).

Part 5: The System Architecture

With the core algorithm understood, the system design becomes tractable.

Components

WebSocket layer

Each client maintains a persistent WebSocket connection to a collaboration server. When a client makes a local edit, Yjs encodes the operation as a binary update and sends it through the WebSocket to the server.

The server receives the update and must do two things: relay it to all other clients editing the same document, and persist it.

Multi-server relay with Redis Pub/Sub

When you have multiple collaboration servers (for horizontal scaling), a client on Server 1 and a client on Server 2 are editing the same document. Server 1 receives an update from its client. It must forward that update to Server 2, which will forward it to its connected clients.

Redis Pub/Sub is the standard solution. Each document has a channel: doc:updates:{documentId}. When Server 1 receives an update, it publishes it to that channel. All collaboration servers subscribe to all document channels. Server 2 receives the published update and forwards it to its connected clients.

// Collaboration server (simplified)
import { WebSocketServer } from 'ws';
import { Redis } from 'ioredis';
import * as Y from 'yjs';
import * as syncProtocol from 'y-protocols/sync';

const pub = new Redis(process.env.REDIS_URL);
const sub = new Redis(process.env.REDIS_URL);
const docs = new Map();  // documentId → Y.Doc

const wss = new WebSocketServer({ port: 4444 });

wss.on('connection', (ws, req) => {
  const documentId = getDocumentId(req.url);

  // Get or create the shared Y.Doc for this document
  if (!docs.has(documentId)) {
    const doc = new Y.Doc();
    docs.set(documentId, doc);
    // Subscribe to updates from other servers
    sub.subscribe(`doc:updates:${documentId}`);
  }

  const doc = docs.get(documentId);

  // Send the current document state to the new client
  const syncStep1 = syncProtocol.writeSyncStep1(Y.encodeStateVector(doc));
  ws.send(syncStep1);

  ws.on('message', (data) => {
    // Apply the update to the local Y.Doc
    Y.applyUpdate(doc, data);
    // Relay to all other clients on this server
    wss.clients.forEach(client => {
      if (client !== ws && client.readyState === WebSocket.OPEN) {
        client.send(data);
      }
    });
    // Relay to other servers via Redis
    pub.publish(`doc:updates:${documentId}`, data);
    // Persist the update
    persistUpdate(documentId, data);
  });
});

// Receive updates from other servers via Redis
sub.on('message', (channel, data) => {
  const documentId = channel.replace('doc:updates:', '');
  const doc = docs.get(documentId);
  if (doc) {
    Y.applyUpdate(doc, Buffer.from(data, 'binary'));
    // Forward to clients connected to this server
    wss.clients.forEach(client => {
      if (client.readyState === WebSocket.OPEN) {
        client.send(data);
      }
    });
  }
});

Persistence

The collaboration server holds the document in memory as a Y.Doc. This is fast for applying and sending updates, but memory is ephemeral. You need two persistence strategies:

Update log: Every incoming update is appended to a Postgres table. This is the full operation history and enables: recovering from server crashes (replay the log), providing catch-up updates to clients that were offline (send all updates since their last known state vector), and audit trails for document history.

CREATE TABLE document_updates (
  id          BIGSERIAL PRIMARY KEY,
  document_id UUID NOT NULL,
  update_data BYTEA NOT NULL,       -- the raw Yjs binary update
  created_at  TIMESTAMPTZ DEFAULT NOW()
);

CREATE INDEX idx_doc_updates_document_id
  ON document_updates(document_id, id);

Snapshots: As the update log grows (an active document can accumulate thousands of updates per hour), replaying the full log on server restart becomes slow. Periodically (every N updates or every M minutes), take a full snapshot of the Y.Doc state and save it. On restart, load the latest snapshot and replay only the updates since the snapshot.

async function persistUpdate(documentId, update) {
  // Append to update log
  await db.query(
    'INSERT INTO document_updates (document_id, update_data) VALUES ($1, $2)',
    [documentId, update]
  );

  // Snapshot every 500 updates
  const updateCount = await getUpdateCountSinceLastSnapshot(documentId);
  if (updateCount >= 500) {
    const doc = docs.get(documentId);
    const snapshot = Y.encodeStateAsUpdate(doc);
    await saveSnapshot(documentId, snapshot);
    await deleteUpdatesBeforeSnapshot(documentId);
  }
}

async function loadDocument(documentId) {
  const doc = new Y.Doc();

  // Load the latest snapshot
  const snapshot = await getLatestSnapshot(documentId);
  if (snapshot) {
    Y.applyUpdate(doc, snapshot.data);
  }

  // Apply all updates since the snapshot
  const updates = await getUpdatesSinceSnapshot(documentId, snapshot?.id ?? 0);
  updates.forEach(update => Y.applyUpdate(doc, update.data));

  return doc;
}

Part 6: Presence — Cursors, Selections, and "Alice is Typing"

Presence is the awareness layer: knowing who else is in the document, where their cursor is, and what they are doing. It is separate from document content and has different requirements: it is ephemeral (cursor positions do not need to persist), high-frequency (cursor moves on every keystroke), and best-effort (missing a cursor update is acceptable).

Yjs has a built-in presence protocol called Awareness:

import { Awareness } from 'y-protocols/awareness';

const awareness = new Awareness(ydoc);

// Set local user's presence
awareness.setLocalState({
  userId: currentUser.id,
  name: currentUser.name,
  color: '#' + Math.floor(Math.random() * 0xffffff).toString(16),
  cursor: { anchor: 45, head: 45 },  // cursor position in the document
});

// Listen for other users' presence changes
awareness.on('change', ({ added, updated, removed }) => {
  const states = awareness.getStates();
  states.forEach((state, clientId) => {
    renderRemoteCursor(clientId, state);
  });
});

Awareness states are gossiped between clients through the same WebSocket connection as document updates but on a separate protocol. They are not persisted. When a client disconnects, its awareness state is removed after a timeout.

The presence system should not use the document update channel — cursor updates would pollute the update log. Use a separate Redis channel: doc:awareness:{documentId}.

Part 7: Handling Offline and Reconnection

A client goes offline while editing. Local changes accumulate in its Y.Doc as pending updates. When reconnection occurs:

1. Client sends its current state vector — a compact summary of what updates it has seen. (Y.encodeStateVector(ydoc))
2. Server compares the client's state vector to its own. Computes the diff: what updates does the client not have?
3. Server sends only the missing updates to the client (not the full document). (Y.encodeStateAsUpdate(serverDoc, clientStateVector))
4. Client sends its pending offline changes to the server.
5. Server applies client's offline changes, relays them to other clients.

The CRDT property guarantees that after this exchange, the client's document converges with the server's — regardless of how many conflicting edits happened while the client was offline. No special offline conflict resolution is needed. The CRDT handles it.

This is the production advantage of CRDTs over OT for offline-first applications: OT requires the full operation history and a server to linearise it; CRDTs require only state vectors for efficient synchronisation.

Part 8: Scaling Considerations

Document hot spots: A document being edited by 1,000 simultaneous users (a public Google Doc gone viral) generates enormous update volume. A single collaboration server cannot handle the fan-out — receiving one update and sending it to 999 other WebSocket connections. The solution is a tree-based relay: collaboration servers form a tree, each one relaying to its children. Updates propagate down the tree with O(log N) latency rather than O(1) at the cost of O(N) fan-out on a single server.

For typical SaaS products (documents edited by 2-10 users simultaneously), a single server handles this trivially. Design for actual scale, not theoretical maximum.

Memory management: Keeping every active document in server memory is expensive. Use an LRU eviction policy: documents not accessed in N minutes are serialised (snapshot + update log merge) and removed from memory. On next access, reload from Postgres. Redis can serve as an intermediate cache for recently-evicted documents.

API compatibility (REST alongside WebSocket): Not all clients support WebSockets (some automation, server-to-server). Provide a REST API that reads the current document state from the Postgres snapshot. This REST API does not participate in real-time collaboration — it reads a point-in-time snapshot. For most read use cases (loading a document to view, not edit) this is sufficient.

Vocabulary Map

Practice Problems

Problem 1 — Transformation Logic: Document: "cat" (positions 0, 1, 2)

Two concurrent operations:

• O1: Insert(1, 'h') — User A inserts 'h' at position 1 → "chat"
• O2: Insert(1, 'o') — User B inserts 'o' at position 1 → "coat"

Both were computed against "cat". Derive T(O2, O1) — how must O2 be transformed to be applied after O1? What is the final document state on both clients? Is this the correct result — does it reflect both users' intentions? Now add a third concurrent operation O3: Delete(2) — User C deletes position 2. Describe why computing T(O3, O1, O2) is more complex than T(O2, O1). What specific information does the transformation function need that it did not need in the two-user case?

Problem 2 — CRDT vs OT Selection: You are building a collaborative code editor for AttemptIQ — students can work on code problems together in real time. The editor must support:

• Up to 20 simultaneous editors per document
• Offline editing on mobile (poor connectivity)
• Document history (replay edits step by step)
• No dedicated collaboration server (peer-to-peer between browser tabs is acceptable)

Should you use OT or CRDT? Justify the decision against each requirement. Which specific library would you use and why? What does the persistence model look like given the no-server constraint?

Problem 3 — System Failure Analysis: Your collaboration server crashes with 15 active users editing document doc:abc123. Redis Pub/Sub had queued 47 pending updates that were not persisted to Postgres before the crash. The document in Postgres reflects the state 47 updates ago.

What happens when each of the 15 users reconnects? Describe the exact synchronisation sequence. Which users' changes are permanently lost and which are recoverable? How would you change the persistence architecture to prevent this data loss?

Problem 4 — Presence at Scale: Samiksha launches a live exam feature: 5,000 students simultaneously edit their answer documents during a 3-hour exam. Each document is individual (one student per document) but the teacher's dashboard shows a live count of "students currently writing" with 5-second granularity.

Design the presence system for this. Do you use Yjs Awareness for the teacher's count? Why or why not? How do you aggregate presence across 5,000 individual WebSocket connections without the teacher's server receiving 5,000 WebSocket connections? What does the data flow look like?

Problem 5 — Connect to Previous Phases: In Phase 3 Chapter 3, you learned about Raft consensus and leader election. In this chapter, you learned that OT requires a central server to linearise operations, while CRDTs do not.

Consider a CRDT-based collaborative editor deployed across three data centres (Mumbai, Singapore, Frankfurt) for low-latency editing. Users in each region connect to their nearest data centre. The data centres sync CRDT updates to each other. A network partition isolates Frankfurt from the other two for 90 seconds. Users in Frankfurt continue editing.

What happens to the document during the partition? What happens when the partition heals? Would this system behave differently if it used OT instead of CRDT? Which CAP theorem properties does the CRDT system satisfy during the partition?

End of Phase 5, Chapter 6.