02. Collaborative Editor — Low-Level Design¶

~22 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)

The HLD named the boxes. This file opens the ones that carry the design's weight — the OT transform engine on the server, the client sync loop that makes typing feel instant, and the presence and cursor machinery — and pins down the data, the transform math, and the concurrency corners where a collaborative editor actually breaks. The core algorithm is stepped through with the 50-editors-in-one-paragraph scenario.

Data models¶

An operation is the atom of the system. Everything durable is a sequence of these.

Op {
  doc_id     : string
  rev        : int64        // server-assigned, total order; 0 for un-acked client ops
  client_id  : string       // stable per editing session
  client_seq : int64        // per-client monotonic; the idempotency key
  base_rev   : int64        // server rev the client had when it created this op
  actions    : [ Action ]   // usually one; batched keystrokes may hold several
}

Action =
  | Insert { pos: int, text: string }     // insert text at char offset pos
  | Delete { pos: int, len: int }         // delete len chars starting at pos
  | Retain { len: int, attrs?: {...} }    // (rich text) advance, optionally re-style

Three fields are non-obvious. base_rev is what makes transformation possible: it tells the server exactly which concurrent ops this edit had not seen, so the server knows precisely the set to transform against. client_seq is the idempotency key — the pair (client_id, client_seq) uniquely identifies an edit for the life of the document, so a resent op after a reconnect is recognized and never applied twice. rev is assigned only by the server; a client op in flight carries rev = 0 and receives its real revision in the ack.

The op-log is the system of record, append-only, partitioned so reads are one ordered scan:

# Wide-column layout
partition key : doc_id
clustering key: rev  (ascending)
value         : { client_id, client_seq, actions, wall_ts }

# The only two queries that exist:
#   append : put(doc_id, rev, op)                    — one row
#   catch-up: scan(doc_id, rev > X order by rev asc) — ordered tail

Snapshots exist only to bound cold-open cost and are keyed by the rev they represent:

Snapshot { doc_id, rev, content: string, created_at }
# written every SNAPSHOT_INTERVAL (≈1000) ops or after an idle gap

Presence is ephemeral and never touches the log:

# Redis hash, key = presence:{doc_id}, TTL ≈ 10s per field, refreshed by heartbeat
field client_id -> { cursor_pos, sel_anchor, name, color, last_seen }

Cursor positions are stored as plain integer offsets, which means — like every other offset in the system — they must be transformed when text shifts under them. That is handled below, not stored.

Component internals¶

Component 1 — The OT transform engine (server side)¶

Responsibility: turn a stream of concurrent, differently-based edits into one total order such that every client replaying that order arrives at identical text.

The engine rests on one function, transform, and one property it must satisfy. Given two ops a and b that were both created against the same base revision (they are concurrent), transform(a, b) returns a': the version of a adjusted to apply after b has already been applied. The property that must hold is TP1 (convergence):

apply(apply(doc, a), transform(b, a))  ==  apply(apply(doc, b), transform(a, b))

In words: applying a then the transformed b, versus b then the transformed a, must yield identical documents. That is exactly the guarantee the 50 editors need.

For two inserts, transform is position adjustment with a deterministic tie-break:

def transform_insert_insert(a: Insert, b: Insert) -> Insert:
    if b.pos < a.pos:
        return Insert(a.pos + len(b.text), a.text)   # b landed before a → shift a right
    if b.pos > a.pos:
        return Insert(a.pos, a.text)                 # b landed after a → a unaffected
    # SAME position: break the tie the SAME way on every machine, or clients diverge.
    if a.client_id < b.client_id:
        return Insert(a.pos, a.text)                 # a wins the earlier slot
    else:
        return Insert(a.pos + len(b.text), a.text)   # a yields, shifts right past b

The tie-break by client_id at equal positions is the crux of convergence when everyone types into the same spot: it is a total, deterministic rule every participant computes identically. Insert-vs-delete shifts the insert left if the delete removed text before it; delete-vs-delete clamps overlapping ranges so a character deleted by both peers is removed once, not twice (the second delete's effective length shrinks to zero over the already-gone range).

The server's receive loop applies transform against the exact concurrent set:

def receive(op):                       # op carries base_rev, actions, client_id, client_seq
    if seen(op.client_id, op.client_seq):        # idempotency: already committed
        return ack_of(op.client_id, op.client_seq)
    concurrent = log.scan(doc_id, rev > op.base_rev)   # ops the client hadn't seen
    for c in concurrent:
        op.actions = transform(op.actions, c.actions)  # fold op forward past each
    op.rev = (current_rev := current_rev + 1)          # assign the next total-order slot
    doc = apply(doc, op.actions)                       # advance authoritative text
    log.append(doc_id, op.rev, op)                     # DURABLE before ack
    remember(op.client_id, op.client_seq, op.rev)      # for idempotency + resend
    ack(op.client_id, op.client_seq, op.rev)
    broadcast(op, exclude=op.client_id)                # fan out transformed op

The single most important structural fact: because the server defines the one total order, each incoming op only ever transforms against a linear list of already-ordered ops. That is why this design needs only TP1 and never TP2 — the transform-of-transforms property required when three or more peers merge with no agreed order, which is famously hard to implement correctly. The central server is not just convenient; it deletes the hardest part of OT.

Component 2 — The client sync loop (Jupiter model)¶

Responsibility: render local edits at 0 ms, keep at most a bounded set of edits in flight, and merge incoming server ops without ever corrupting the user's uncommitted text.

The client holds pending (ops applied locally but not yet acked) and last_acked_rev.

def on_local_edit(action):
    doc = apply(doc, action)                    # optimistic: show it NOW
    op = Op(client_seq=next_seq(), base_rev=last_acked_rev, actions=[action])
    pending.append(op)
    if len(in_flight) == 0:                     # one op in flight at a time (Jupiter)
        send(op); in_flight = op

def on_server_op(remote):                       # a peer's already-transformed op
    r = remote.actions
    for p in pending:                           # transform incoming past my pending edits
        r, p.actions = transform_pair(r, p.actions)
    doc = apply(doc, r)                         # now safe to apply locally
    last_acked_rev = remote.rev

def on_ack(client_seq, rev):
    pending.remove(op_with(client_seq))
    last_acked_rev = rev
    if pending: send(pending[0]); in_flight = pending[0]   # release the next

Two design choices matter. Keeping one op in flight at a time (batching subsequent keystrokes into the next op) bounds the transform work per ack to the size of pending and matches the server's expectation of a single base_rev per client. And transform_pair mutates both sides — the incoming op is adjusted to apply over my pending edits, and my pending edits are adjusted to sit after the incoming op — so my uncommitted text and the peer's edit end up consistently ordered on my screen exactly as they will on the server.

Component 3 — Presence and cursor transform¶

Responsibility: show every collaborator's live cursor, anchored to the character it points at, even as text shifts beneath it.

A cursor at offset 140 is not a fixed number; it is a position in text that other people are changing. So every applied op must also transform live cursor offsets, using the same left/right shift rule as inserts:

def transform_cursor(cursor_pos, action):
    if is_insert(action) and action.pos <= cursor_pos:
        return cursor_pos + len(action.text)     # text inserted before me → I move right
    if is_delete(action) and action.pos < cursor_pos:
        return cursor_pos - min(action.len, cursor_pos - action.pos)  # text removed before me
    return cursor_pos

Cursor updates ride the ephemeral pub-sub with a heartbeat every ~2 s and a ~10 s TTL, so a departed collaborator's cursor simply ages out. Presence is deliberately lossy: under backpressure the gateway drops cursor frames to a slow client before it ever drops an edit, because a skipped cursor frame is invisible and a dropped edit is a bug.

Core algorithm — 50 editors converging on one paragraph¶

Walk the threaded scenario at its sharpest: the paragraph reads Hello at rev 10, and three of the 50 editors — clients A, B, C — each insert one character at the same offset 5 (the end), each based on rev 10, in the same instant. The server happens to receive them in the order A, B, C. Watch it produce one order that every client reproduces.

start: doc = "Hello", current_rev = 10
A: base_rev=10, Insert("X", pos 5), client_id="A"
B: base_rev=10, Insert("Y", pos 5), client_id="B"
C: base_rev=10, Insert("Z", pos 5), client_id="C"

A arrives. concurrent = scan(rev>10) is empty — A saw everything. No transform. Assign rev 11, apply → doc = "HelloX". Append, ack A, broadcast A@11.
B arrives. concurrent = [A@11]. Transform B's Insert("Y",5) against A's Insert("X",5): same position, so tie-break by client_id — "B" > "A", so B yields and shifts right past A to offset 6. Assign rev 12, apply → doc = "HelloXY". Broadcast B'@12 (the transformed op, insert at 6).
C arrives. concurrent = [A@11, B@12]. Transform C's Insert("Z",5) against A (same pos, "C">"A" → shift to 6) then against B' (now at 6, "C">"B" → shift to 7). Assign rev 13, apply → doc = "HelloXYZ". Broadcast C'@13 (insert at 7).

The server's document is HelloXYZ. Now the clients:

Client A already showed HelloX optimistically. It receives B'@12 (insert at 6) and C'@13 (insert at 7), transforms each past its now-empty pending queue, applies → HelloXYZ.
Client B optimistically showed HelloY. It receives A@11; transforming A's Insert("X",5) against B's still-pending Insert("Y",5) and applying yields HelloXY (B's Y shifted right to make room, matching the server's tie-break). Its own op is then acked as rev 12 at the transformed offset. C'@13 follows → HelloXYZ.
Client C the same way ends at HelloXYZ.

Every screen shows HelloXYZ, in that order, though all three humans "typed at position 5" simultaneously. Scale this to all 50 editors and 250 ops/second: the server lays every op into one linear revision sequence, transforms each against precisely the ops it missed, and the deterministic tie-break makes the order reproducible on every client. Convergence is not luck or last-writer-wins; it is the total order plus a transform that satisfies TP1. The 50 clients converge for the same reason A, B, and C did — there is exactly one order, and everyone computes it identically.

Sequence diagram — an optimistic edit under a concurrent peer¶

Client A            Gateway         Session Server (owner)      Op-Log      Client B
  │ type "X"@5        │                    │                      │            │
  ├─ apply local ─────┤ (0 ms feedback)    │                      │            │
  ├─ op(seq31,base10)▶│───── route doc ────▶│ concurrent=∅         │            │
  │                   │                    ├─ rev=11, apply        │            │
  │                   │                    ├─ append(doc,11) ─────▶│ (durable)  │
  │                   │◀──── ack seq31,11 ─┤                       │            │
  │◀─ ack: pop pending┤                    ├─ broadcast X@11 ──────┼───────────▶│ transform
  │                   │                    │                       │            │ vs pending
  │                   │                    │                       │            ├─ apply "X"
  │ (meanwhile B typed "Y"@5 based on rev 10 → arrives next)       │            │
  │                   │◀──────── op(Y,base10) from B ──────────────┼────────────┤
  │                   │                    ├ concurrent=[X@11]      │            │
  │                   │                    ├ transform Y vs X (tie: B>A → pos 6) │
  │                   │                    ├ rev=12, apply "…XY"    │            │
  │                   │                    ├ append(doc,12) ──────▶│            │
  │◀───── broadcast Y'@12 (insert @6) ─────┤                       │            │
  ├ transform Y' vs (empty) pending, apply → "HelloXY"             │            │

The ack pops A's op from its pending queue; the broadcast of the transformed peer op is what each client applies. One durable append precedes every ack, so an acknowledged edit is always recoverable.

Concurrency and edge cases¶

Idempotent replay after reconnect. A client that reconnects resends every unacked pending op with its original client_seq. The server checks (client_id, client_seq): if that op already has a committed rev, it re-acks with the existing rev and does nothing else, so a resend is never double-applied. This is the whole reason client_seq exists.
Same-position race. The A/B/C walk above is the race: two or more inserts at one offset. It is resolved not by rejecting either but by the deterministic client_id tie-break inside transform, so both survive in an order every machine agrees on. Never resolve this with last-writer-wins — that silently drops an edit the user watched themselves type.
Overlapping deletes. Two peers delete the same characters. The second delete transforms to a shorter (possibly empty) range over text that is already gone, so the character is removed exactly once. Length clamping in transform_delete_delete is what prevents an over-delete that would corrupt neighboring text.
Cursor drift. A remote cursor is transformed against every applied op (Component 3), so it stays glued to its character as text shifts. Skipping this makes cursors visibly slide to the wrong place during heavy concurrent typing — the classic "why is Ana's cursor three words off" bug.
Snapshot consistency. A snapshot is stamped with the exact rev it materializes. Cold open loads the snapshot and replays only rev > snapshot.rev; because the log is the single source of truth and snapshots are derived, a snapshot can never disagree with the log — at worst it is stale, and the tail replay closes the gap.
Ownership handoff. When a session server loses its lease (crash, deploy, rebalance), the new owner must not accept edits until it has replayed to the log's true tail; otherwise it could assign a rev that collides with an in-flight append from the old owner. The lease's fencing token, checked on every log append, rejects a write from a server that no longer owns the document, closing the split-brain window.
Un-acked local edits during a long outage. Pending grows while offline. On reconnect the client folds each pending op forward through everything committed in the gap. If the gap is enormous, the cheaper path is to discard local optimistic state, reload a fresh snapshot, and re-apply the user's pending ops as new edits against the current rev — bounded work instead of transforming against a very long concurrent list.