System Design HLD-19.20
Design a collaborative editor (Google Docs / Figma)
Design a collaborative editor: OT versus CRDTs, a server that orders edits per document, presence and cursors, persistence, and offline edits.
The problem
Three people have the same document open. Alice types a sentence at the top, Bob fixes a typo in the middle, Carol deletes a paragraph at the end, all in the same second. Each sees their own keystrokes instantly, sees the others' a moment later, and a minute later all three screens show exactly the same text. Nobody pressed save, and nobody's edit was lost.
The hard part is that "instantly" means each person applies their own edit before anyone else knows about it. So edits are concurrent by design, and they arrive at each screen in a different order. Applying "insert 'h' at position 1" is only correct if position 1 still means what it meant when Bob typed it. The design is about making every replica converge despite that, plus the plumbing: a live connection per user, presence and cursors, storage, and edits made offline.
Requirements
Functional
- Many users edit the same document at once; local edits appear immediately.
- Everyone converges to the same document; no edit is silently lost.
- Show who is present and where their cursors and selections are.
- Version history; work offline and sync on reconnect.
Non-functional
- Latency: remote edits visible within about 100 to 200 ms on a good connection.
- Scale: millions of documents open at once, most with 1 to 5 editors, a few with hundreds of viewers.
- Durability: an acknowledged edit survives server crashes.
Out of scope
- Comments and suggestions mode (they reuse the same machinery), permissions, and rich layout rendering.
Estimates
- Edits: a typing user produces about 5 keystrokes a second. Clients batch them every 50 to 100 ms, so an active editor sends about 10 small messages a second. With 1 million users actively typing at peak, that is 10 million messages a second across the fleet, but only tens per second per document.
- Fan-out: each edit goes to the other people in the document. With 3 editors on average that is about 2 deliveries per edit; a document with 200 viewers turns one edit into 200 deliveries.
- Storage: an operation is tens of bytes. A document edited for an hour by one person accumulates tens of thousands of operations, so the operation log is periodically compacted into a snapshot, and loading a document means "latest snapshot plus the operations after it".
- The load is wide (many documents) rather than deep (any one document is small), so the natural unit of partitioning is the document.
API
WS /v1/docs/{doc_id}/session
client -> server: { op: insert "h" at 1, base_version: 41, client_seq: 7 }
server -> client: { ack: 7, version: 42 } # your op is now version 42
server -> client: { op: ..., version: 43, author: "bob" } # someone else's op
client -> server: { presence: { cursor: 118, selection: [118, 130] } } # not persisted
GET /v1/docs/{doc_id}/snapshot -> { version, content }
GET /v1/docs/{doc_id}/ops?after=41
Data model
- Operation log (append-only, per document, Event-driven architecture and event sourcing ):
doc_id, version, author, op, created_at. The version is a per-document sequence number assigned by the server. - Snapshots (object storage):
doc_id, version -> full content, written every few thousand operations. - Presence (in memory only):
doc_id -> {user: cursor, selection, colour, last_seen}. Lost on restart and nobody minds. - Session routing:
doc_id -> session server, so all editors of one document reach the same server.
High-level design
- Edit path Alice's client applies her keystroke immediately and sends the operation with the version it was based on. The gateway routes it to the one session server that owns this document.
- Broadcast path The session server transforms the operation against anything accepted since version 41, gives it version 42, acknowledges Alice and broadcasts it. Bob's client transforms it against his own edits not yet acknowledged, then applies it.
- Persist path Each accepted operation is appended to the durable log before the acknowledgement. Every few thousand operations the server writes a snapshot, so loading a document is the snapshot plus a short tail of operations.
Deep dives
Deep dive 1: Why concurrent edits break, and operational transformation
Alice and Bob both start from "cat". Alice types "the " at the start; Bob types "h" after the "c". Alice applies her edit and gets "the cat"; then Bob's "insert 'h' at 1" arrives, and applied as sent it produces "thhe cat". Bob, meanwhile, has "the chat". Two screens, two documents, forever.
Operational transformation (OT) fixes this by adjusting a remote operation for the concurrent operations it did not know about. Alice's insert of 4 characters before position 1 shifts Bob's insert to position 5, giving "the chat" on both screens. Rules exist for each pair (insert/insert, insert/delete, delete/delete), with a tie-break when two inserts land on the same spot. Try it:
Try this:
- With "applied as sent", find a pair of edits that still converges, and one that diverges. What do the converging pairs have in common?
- Switch to OT and choose "delete t" for both. What does the second delete become, and why?
- Choose Alice's "s" at the end and Bob's "!" at the end. Which tie-break rule decides the order?
OT's catch is that the transformation functions are subtle, and with many concurrent operations and no central order, proving they always converge is notoriously hard. In practice OT systems use a central server that puts all operations into one order, so each client only needs to transform against that sequence. This is the design in Figure 1.
Deep dive 2: CRDTs
A conflict-free replicated data type takes the opposite approach: instead of fixing positions after the fact, never use positions. Every character gets a unique, permanent id (a counter plus the id of the site that created it, like a Lamport timestamp, Time and clocks ), and an insert says "put this after character X". Deletes leave a hidden tombstone so later inserts can still find X. Concurrent inserts after the same character are ordered by id, the same everywhere:
# A tiny sequence CRDT (RGA style). Every character gets a unique id
# (counter, site) and remembers the id it was typed after. Deletes only mark
# a tombstone. Replicas that receive the same operations, in any order
# that keeps each sender's own operations in sequence, end up with the
# same text, with no server deciding.
import itertools, math
class Replica:
def __init__(self, site):
self.site, self.clock = site, 0
# each entry: (id, id it was typed after, char, deleted?)
self.chars = [((0, ""), None, "", False)] # start marker
def _index(self, cid):
return next(i for i, c in enumerate(self.chars) if c[0] == cid)
def apply(self, op):
kind, cid, after, ch = op
self.clock = max(self.clock, cid[0])
if kind == "del":
i = self._index(cid)
self.chars[i] = self.chars[i][:3] + (True,)
return
if any(c[0] == cid for c in self.chars):
return # already applied
i = self._index(after) + 1
# concurrent inserts at the same spot: the bigger id goes first
while i < len(self.chars) and self.chars[i][0] > cid:
i += 1
self.chars.insert(i, (cid, after, ch, False))
def type(self, text, after): # local edit -> ops
ops = []
for ch in text:
self.clock += 1
op = ("ins", (self.clock, self.site), after, ch)
self.apply(op)
ops.append(op)
after = op[1]
return ops
def text(self):
return "".join(c[2] for c in self.chars if not c[3])
base = Replica("base")
start = base.type("cat", (0, ""))
c_id, a_id, t_id = (op[1] for op in start)
alice, bob = Replica("alice"), Replica("bob")
for r in (alice, bob):
for op in start:
r.apply(op)
ops_a = alice.type("the ", (0, "")) # at the start
ops_a.append(("del", t_id, None, None)) # and delete "t"
alice.apply(ops_a[-1])
ops_b = bob.type("h", c_id) # "chat"
ops_b += bob.type("s", t_id) # "chats"
print("alice alone:", alice.text(), "| bob alone:", bob.text())
for r, ops in ((alice, ops_b), (bob, ops_a)):
for op in ops:
r.apply(op)
print("after exchanging edits:", alice.text(), "|", bob.text())
# a third replica receives the ops in every possible interleaving
# (each person's own ops stay in their order, as a real network ensures)
results = set()
n = len(ops_a) + len(ops_b)
for slots in itertools.combinations(range(n), len(ops_a)):
ia, ib, order = iter(ops_a), iter(ops_b), []
for k in range(n):
order.append(next(ia) if k in slots else next(ib))
r = Replica("third")
for op in start + order:
r.apply(op)
results.add(r.text())
print(f"third replica, {math.comb(n, len(ops_a))} arrival orders:", results)Output
alice alone: the ca | bob alone: chats
after exchanging edits: the chas | the chas
third replica, 21 arrival orders: {'the chas'} Alice typed "the " and deleted "t"; Bob typed "h" and "s". After exchanging operations both have "the chas", and a third replica got the same text for every one of the 21 possible arrival orders. No server decided anything, which is why CRDTs suit peer-to-peer sync and long offline periods.
The costs: every character carries metadata, tombstones accumulate until garbage collected, and some intentions merge oddly (Bob's "s" survives after Alice deleted the "t" it followed, giving "chas"). OT keeps documents compact but needs the central order; CRDTs tolerate any delivery order at the cost of memory and some surprising merges. Many products combine ideas: a central server for ordering and authority, with CRDT-like ids or per-property last-writer-wins for structured data.
Deep dive 3: One server per document
Routing every editor of a document to one session server gives a single, authoritative order of operations per document. The gateway looks up doc_id -> server in a routing table or by consistent hashing ( Consistent hashing ). The session server keeps the document in memory, assigns versions, appends to the log before acknowledging, and broadcasts.
If the server dies, clients reconnect, the document moves to another server, which loads the snapshot plus the log tail. Clients resend operations that were never acknowledged, with their client_seq, so the server can drop duplicates. A very popular document (a company all-hands agenda) stays on one server; its viewers can be served by read-only fan-out replicas.
Deep dive 4: Presence, cursors and offline edits
Presence and cursors ride the same WebSocket but are never persisted and never transformed through the log: a cursor update is just "Alice is at position 118 as of version 42", and receivers adjust it locally. They are sent at a low rate and dropped freely, because the next one replaces them.
Offline edits are just very late concurrent operations. The client keeps its unacknowledged operations, and on reconnect sends them based on the last version it saw; the server transforms them against everything since. With a CRDT the merge is automatic. Either way, a long offline period can produce surprising merges, so editors often show the user what changed while they were away.
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| Edits applied at stale positions | Replicas diverge | OT against the server order, or CRDT ids |
| Session server crash | Editing pauses | Reload from snapshot plus log; clients resend unacknowledged ops with ids |
| Huge documents or long histories | Slow loads | Periodic snapshots; compact the log |
| Hundreds of viewers on one doc | Broadcast hot spot | Read-only fan-out replicas for viewers |
| Cursor flood | Wasted bandwidth | Throttle presence; never persist it |
| Long offline period | Odd merges | Show changes on reconnect; version history to restore |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Central server per document (chosen) | One authoritative order; simpler OT; easy persistence | Needs a connection to the server; routing and failover |
| Peer-to-peer CRDT | Works without a server and offline for long periods | Metadata and tombstone overhead; some odd merges |
| Optimistic local apply (chosen) | Typing feels instant | Clients must reconcile their pending edits with the server order |
| Snapshots plus operation log (chosen) | Fast loads and full history | Compaction jobs and two storage systems |
Extensions
- Rich text with formatting spans, which need their own transformation or CRDT rules.
- Undo that only undoes your own edits without overwriting others'.
- Suggestions mode and comments anchored to text that moves.
- End-to-end encryption, which hides operations from the server and favours CRDTs.
In the wild
Figma
How Figma's multiplayer technology works (opens in a new tab)Figma runs a separate server process for each multiplayer document, which every editor of that document connects to over WebSockets, and the server is the central authority. The 2019 post says OT was unnecessarily complex for their problem, so they built a system inspired by CRDTs but not a true CRDT, dropping CRDT overhead because the server is central. A document is a map from object id to a map of property to value, and conflicts are resolved by last writer wins per property on the server. Clients apply their own changes immediately and discard incoming server changes that conflict with their unacknowledged ones, to avoid flicker. Objects created on a client include the client id in their id, and offline clients download a fresh copy on reconnect and reapply their edits on top.
Check yourself
-
Why does applying a remote insert at its original position sometimes produce the wrong text?
Show answer
B. A concurrent local edit has already shifted the text, so the position means something else Positions are relative to the document version the edit was made on.
-
What does OT do with Bob's 'insert h at 1' after Alice inserted 4 characters at 0?
Show answer
B. Shifts it to position 5 Transforming against Alice's insert moves Bob's position past her text.
-
How do CRDTs avoid the position problem?
Show answer
B. Each character has a unique id and inserts refer to ids, with a fixed order for concurrent inserts Ids do not shift when other text changes, so any delivery order converges.
-
Why are cursor positions not written to the operation log?
Show answer
B. They are ephemeral and replaced constantly; persisting them adds load with no value Presence is best-effort, in memory and throttled.
Recap
- Clients apply their own edits instantly, so concurrent edits are normal and arrive in different orders.
- OT transforms remote operations against concurrent ones; a central server order keeps it tractable.
- CRDTs give every character a unique id, so replicas converge in any delivery order, at a metadata cost.
- Route each document to one session server that orders, persists and broadcasts its operations.
- Snapshots plus an operation log for storage; presence stays in memory; offline edits are late concurrent edits.
Next up
- Crack the system design round learning path