Overview
Google Docs allows multiple users to edit the same document simultaneously with each user seeing changes from others in near-real time. The fundamental problem is concurrent edit conflict: if Alice inserts "Hello" at position 0 while Bob simultaneously deletes character at position 0, naively applying both operations results in data loss or corruption. Google Docs solves this with Operational Transformation (OT) — a server-side algorithm that adjusts the position and intent of concurrent operations before applying them. The system must handle offline edits, reconnection, cursor presence, and persistence — all while keeping the document consistent for every connected client.
Architecture
SESSION + SYNC
─────────────────────────────────────────────────────────────────────
Browser A (Alice) Browser B (Bob)
┌───────────────┐ ┌───────────────┐
│ Local doc │ │ Local doc │
│ OT client │ │ OT client │
│ Pending ops │ │ Pending ops │
└──────┬────────┘ └──────┬────────┘
│ WebSocket │ WebSocket
│ (wss://) │ (wss://)
▼ ▼
┌──────────────────────────────────────────────────────────────────┐
│ WebSocket Gateway (sticky sessions per document) │
│ │
│ doc-server-1 handles doc_id: abc, def, ... │
│ doc-server-2 handles doc_id: ghi, jkl, ... │
│ │
│ Consistent hashing → same doc always routes to same server │
└──────────────────────────┬───────────────────────────────────────┘
│
┌──────────▼──────────┐
│ OT Engine │
│ │
│ - Receive op from │
│ client │
│ - Transform against│
│ concurrent ops │
│ - Assign revision │
│ - Broadcast to all │
│ other clients │
└──────────┬──────────┘
│
┌─────────────────┼─────────────────┐
│ │ │
▼ ▼ ▼
┌──────────────┐ ┌──────────────────┐ ┌──────────┐
│ Operation │ │ Document │ │ Presence│
│ Log │ │ Snapshot Store │ │ Cache │
│ (DynamoDB │ │ (S3: full doc │ │ (Redis) │
│ append- │ │ every 100 ops │ │ │
│ only) │ │ or 5 min) │ │ cursor │
└──────────────┘ └──────────────────┘ │ positions│
└──────────┘
RECONNECTION / LOAD PATH
─────────────────────────────────────────────────────────────────────
Browser connects to doc for first time (or after crash):
1. Fetch latest snapshot from S3
2. Fetch all ops in DynamoDB after snapshot_revision
3. Replay ops on top of snapshot → current document state
4. Subscribe to live ops via WebSocket
┌──────────┐ GET snapshot ┌──────────┐
│ Client │─────────────────▶│ S3 │
│ │ GET ops since │ │
│ │─────────────────▶│ DynamoDB │
│ │ replay + join │ │
└──────────┘ WebSocket └──────────┘
Technical Implementation
OT Transform Function — Insert and Delete Operations
// src/ot/transform.ts
// An operation is either an insert or a delete at a character position.
// transform(op, concurrent) adjusts `op` so it can be applied AFTER
// `concurrent` has already been applied, without losing intent.
export type Op =
| { type: 'insert'; pos: number; char: string; revision: number; clientId: string }
| { type: 'delete'; pos: number; revision: number; clientId: string };
/**
* Transform `incoming` against a `concurrent` op that the server
* has already applied. Returns a new op with adjusted position.
*/
export function transform(incoming: Op, concurrent: Op): Op {
if (incoming.type === 'insert') {
if (concurrent.type === 'insert') {
// Both inserted at the same position: use clientId to break ties deterministically
if (concurrent.pos < incoming.pos || (concurrent.pos === incoming.pos && concurrent.clientId < incoming.clientId)) {
return { ...incoming, pos: incoming.pos + 1 };
}
return incoming;
}
if (concurrent.type === 'delete') {
if (concurrent.pos < incoming.pos) {
// Deletion was before our insert — shift left
return { ...incoming, pos: incoming.pos - 1 };
}
return incoming;
}
}
if (incoming.type === 'delete') {
if (concurrent.type === 'insert') {
if (concurrent.pos <= incoming.pos) {
// Insert was before or at our delete position — shift right
return { ...incoming, pos: incoming.pos + 1 };
}
return incoming;
}
if (concurrent.type === 'delete') {
if (concurrent.pos < incoming.pos) {
return { ...incoming, pos: incoming.pos - 1 };
}
if (concurrent.pos === incoming.pos) {
// Both deleted the same character — make incoming a no-op
return { ...incoming, type: 'delete', pos: -1 }; // pos -1 = no-op sentinel
}
return incoming;
}
}
return incoming;
}
/**
* Apply a (possibly transformed) op to a document string.
*/
export function applyOp(doc: string, op: Op): string {
if (op.type === 'insert') {
return doc.slice(0, op.pos) + op.char + doc.slice(op.pos);
}
if (op.type === 'delete') {
if (op.pos < 0 || op.pos >= doc.length) return doc; // no-op
return doc.slice(0, op.pos) + doc.slice(op.pos + 1);
}
return doc;
}
WebSocket Session Handler — Broadcast and Transform
// src/ws/doc-session.ts
import WebSocket from 'ws';
import { transform, applyOp, Op } from '../ot/transform';
import { OperationLogRepository } from '../db/operation-log.repository';
import { DocumentRepository } from '../db/document.repository';
interface ClientState {
ws: WebSocket;
clientId: string;
revision: number; // last revision this client acknowledged
}
export class DocSession {
private clients: Map<string, ClientState> = new Map();
private docContent: string = '';
private serverRevision: number = 0;
private opsSinceSnapshot: Op[] = [];
constructor(
private readonly docId: string,
private readonly opLog: OperationLogRepository,
private readonly docRepo: DocumentRepository,
) {}
async initialize(): Promise<void> {
const { snapshot, revision } = await this.docRepo.getLatestSnapshot(this.docId);
const pendingOps = await this.opLog.getOpsSince(this.docId, revision);
this.docContent = snapshot;
this.serverRevision = revision;
for (const op of pendingOps) {
this.docContent = applyOp(this.docContent, op);
this.serverRevision++;
}
}
addClient(clientId: string, ws: WebSocket, clientRevision: number): void {
this.clients.set(clientId, { ws, clientId, revision: clientRevision });
// Send the client ops it missed since its last known revision
const missedOps = this.opsSinceSnapshot.slice(clientRevision);
ws.send(JSON.stringify({ type: 'init', content: this.docContent, revision: this.serverRevision, missedOps }));
}
removeClient(clientId: string): void {
this.clients.delete(clientId);
}
async receiveOp(senderId: string, incomingOp: Op): Promise<void> {
// Transform the incoming op against all ops the server applied
// after the client's last known revision
const concurrentOps = this.opsSinceSnapshot.slice(incomingOp.revision);
let transformed: Op = incomingOp;
for (const concurrent of concurrentOps) {
transformed = transform(transformed, concurrent);
}
// Apply to server document
this.docContent = applyOp(this.docContent, transformed);
this.serverRevision++;
const serverOp = { ...transformed, revision: this.serverRevision };
// Persist to operation log (async, non-blocking for latency)
this.opLog.append(this.docId, serverOp).catch(console.error);
this.opsSinceSnapshot.push(serverOp);
// Snapshot every 100 ops to bound replay time on reconnect
if (this.opsSinceSnapshot.length >= 100) {
await this.docRepo.saveSnapshot(this.docId, this.docContent, this.serverRevision);
this.opsSinceSnapshot = [];
}
// Broadcast transformed op to all other connected clients
const message = JSON.stringify({ type: 'op', op: serverOp });
for (const [clientId, state] of this.clients) {
if (clientId !== senderId && state.ws.readyState === WebSocket.OPEN) {
state.ws.send(message);
state.revision = this.serverRevision;
}
}
}
}
Document Snapshot and Operation Replay for Load
// src/db/document.repository.ts
// On open, fetch snapshot from S3 + replay ops from DynamoDB.
// This bounds cold-start time to: snapshot size + ops since snapshot.
import { S3Client, GetObjectCommand, PutObjectCommand } from '@aws-sdk/client-s3';
import { DynamoDBClient, QueryCommand, PutItemCommand } from '@aws-sdk/client-dynamodb';
const s3 = new S3Client({ region: 'us-east-1' });
const dynamo = new DynamoDBClient({ region: 'us-east-1' });
const SNAPSHOT_BUCKET = 'docs-snapshots';
const OPS_TABLE = 'doc-operations';
export class DocumentRepository {
async getLatestSnapshot(docId: string): Promise<{ snapshot: string; revision: number }> {
try {
const res = await s3.send(new GetObjectCommand({
Bucket: SNAPSHOT_BUCKET,
Key: `${docId}/latest.json`,
}));
const body = await res.Body!.transformToString();
return JSON.parse(body); // { snapshot: "...", revision: 4200 }
} catch {
return { snapshot: '', revision: 0 }; // new document
}
}
async saveSnapshot(docId: string, content: string, revision: number): Promise<void> {
const payload = JSON.stringify({ snapshot: content, revision });
await s3.send(new PutObjectCommand({
Bucket: SNAPSHOT_BUCKET,
Key: `${docId}/latest.json`,
Body: payload,
ContentType: 'application/json',
}));
}
}
export class OperationLogRepository {
async getOpsSince(docId: string, fromRevision: number): Promise<any[]> {
const res = await dynamo.send(new QueryCommand({
TableName: OPS_TABLE,
KeyConditionExpression: 'doc_id = :d AND revision > :r',
ExpressionAttributeValues: {
':d': { S: docId },
':r': { N: fromRevision.toString() },
},
}));
return (res.Items ?? []).map((item) => JSON.parse(item.op_json.S!));
}
async append(docId: string, op: any): Promise<void> {
await dynamo.send(new PutItemCommand({
TableName: OPS_TABLE,
Item: {
doc_id: { S: docId },
revision: { N: op.revision.toString() },
op_json: { S: JSON.stringify(op) },
created_at: { N: Date.now().toString() },
},
// Conditional write: revision must not already exist (idempotency guard)
ConditionExpression: 'attribute_not_exists(revision)',
}));
}
}
Interview Preparation
Q: OT vs CRDT — which does Google Docs actually use, and what's the difference?
Google Docs uses Operational Transformation, specifically the Jupiter OT algorithm (published in the 1995 ACM CSCW paper). OT requires a central server to act as the arbiter of operation order — the server transforms operations against each other and broadcasts the canonical transformed form to all clients. This requires always-online connectivity to a single server per document. CRDTs (Conflict-free Replicated Data Types) take a different approach: each character gets a globally unique ID (e.g., a Lamport timestamp or fractional index), and because identities are unique, concurrent inserts at the "same position" naturally sort by ID. CRDTs work without a server and support true peer-to-peer collaboration — the tradeoff is that deleted characters must be tombstoned (not actually removed) so concurrent deletes can be detected, which causes unbounded document metadata growth. Figma and Notion use CRDT-based approaches. OT is simpler to reason about when you have a central server but is notoriously hard to implement correctly for complex rich-text operations.
Q: Why is ordering operations so hard in distributed systems?
The core problem is that there is no global clock. When Alice on the US-East server and Bob on EU-West both type at the same millisecond, their operations arrive at each other's servers out of order and at different times. Network latency means you cannot tell from timestamps alone which came "first." Without a single sequencer, you cannot guarantee that all nodes apply operations in the same order, which means each replica diverges. OT solves this by routing all operations through a single server that assigns a monotonic revision number — operations are then transformed into the server's canonical order. This is why collaborative editors almost always have a single "session server" per document: the server is not just a broadcaster, it's the total order oracle.
Q: How do you handle a user going offline for 30 minutes then reconnecting?
On reconnect, the client sends its last known revision number to the server. The server fetches the operation log from DynamoDB from that revision forward (potentially hundreds of ops), sends them to the client, and the client replays them on its local copy. Any pending local ops the user made while offline are then sent to the server, where they are transformed against all the ops that were applied during the offline window before being applied and broadcast. This is the same transform pipeline as online editing — it just involves a larger batch of concurrent operations. The key invariant is that the operation log is append-only and revision-numbered, so the server can always reconstruct the missing delta for any client at any revision.
Q: How do you scale to 1000 concurrent editors on one document?
The bottleneck is the session server broadcasting to all connected clients. At 1000 editors, every op triggers 999 WebSocket sends on a single server — at even 50 ops/sec that is 49,950 sends/sec per server. Mitigations: (1) Shard clients across multiple servers for the same document using a pub/sub fan-out layer (Redis Pub/Sub or Kafka) — the OT engine is still single-threaded but broadcast is distributed. (2) Batch small ops: instead of sending each keystroke individually, accumulate 50ms of ops and send a batch. (3) Compress WebSocket frames — most ops are tiny and compress extremely well. (4) Use WebRTC data channels for client-to-client broadcasts when you trust CRDTs, bypassing the server for the hot fan-out path. In practice, documents with 1000+ simultaneous editors are exceedingly rare — Google likely handles this with dedicated high-bandwidth session servers and presence throttling (cursor updates are low-priority vs. content ops).
Learning Resources
- Google Wave OT Paper (2010) — the formal model behind collaborative editing
- Operational Transformation FAQ — Joseph Gentle — the clearest explanation of why OT is hard
- CRDT.tech — comprehensive resource on CRDT algorithms with interactive demos
- Figma: How Figma's Multiplayer Technology Works — real-world CRDT in a production editor
- Designing Data-Intensive Applications — Martin Kleppmann, Chapter 9 (Consistency and Consensus); Kleppmann is also author of the Automerge CRDT library