Design a Collaborative Editor: OT vs CRDT Explained

In "design a collaborative editor", the hard part is not storage or scale but one paragraph. Two people type into it at the same moment; each must see their own keystroke instantly, and a second later both screens must show the same text with both edits in it. The two families of answers are operational transformation (OT) and conflict-free replicated data types (CRDTs), and the interviewer wants to hear why each works and what each costs.

The problem it solves

• Instant local typing. A keystroke that waits for a round trip feels broken, so edits apply locally first.
• Convergence. Once everyone has seen every edit, every copy is identical.
• Intention. An insert lands where its author meant it.
• Presence. Everyone sees everyone's cursor: frequent, disposable data.
• History and offline, which push the choice between OT and CRDTs.

The core difficulty: "insert at index 8" describes one version of the text. Once someone inserts three characters earlier in the line, index 8 names a different spot.

The intuition

OT keeps position-based edits and fixes them on arrival. Every edit carries the version it was written against; a server puts all edits in one order and transforms a late edit past each one its author had not seen. An insert behind someone else's insert shifts right by that insert's length; a delete of an already deleted character becomes nothing; ties at one index need a deterministic rule, such as lower site id first. The property that matters: a then b-transformed-past-a gives the same text as b then a-transformed-past-b. With a central server ordering everything, that property is enough (from memory).

A CRDT removes positions. Every character gets a permanent unique id, a counter plus a site id, and an insert says "put this after character X". A delete leaves a tombstone so later edits can still refer to it. Since ids never change, edits merge in any order that respects causality, with no sequencer, which suits peer-to-peer and offline editing. The cost is metadata for every character ever typed.

Both share the rest: a WebSocket per client, a document service persisting the log or merged state, snapshots so a new client need not replay everything, and presence on a separate, non-durable channel.

Watch it run

The animation follows the lesson's design. Both people are in one paragraph, "the cost" at version v4, and both expect their keystroke immediately. User A types; it appears locally first, at 0 ms, because waiting for the network would feel broken. Only then is the edit sent with the version it was written against: insert at 8, v4. User B typed at the same moment, against the same version, at the same index. A lands first and the document changes underneath B's edit in flight: "the cost is", v5. Index eight now points somewhere else, and applied as written, B's edit lands in the wrong place: "the cost 40 usd is". The server shifts B's index past the three characters A inserted, from 8 to 11, and both screens converge on "the cost is 40 usd" at v6. That transform needs one place that sees every operation, so the server cannot be skipped. Give each character an identity instead and edits merge in any order, carrying their history forever: metadata per character. Last, cursors ride a separate channel, because a moving caret is not worth storing.

The code

A toy model of OT on single characters: inserts carry text and a site id, deletes remove one character. The animation's conflict, applied naively and then transformed:

def apply(doc, op):
    if op is None:                                   # an edit transformed into nothing
        return doc
    if op[0] == "ins":
        _, p, text, _ = op
        return doc[:p] + text + doc[p:]
    _, p, _ = op
    return doc[:p] + doc[p + 1:]

def transform(a, b):
    """Rewrite a so it still means the same thing after b, both written against one text."""
    if a is None or b is None:
        return a
    if a[0] == "ins":
        _, p, text, site = a
        if b[0] == "ins":
            q, other = b[1], b[2]
            before = q < p or (q == p and b[3] < site)   # same index: lower site id goes first
            return ("ins", p + len(other), text, site) if before else a
        return ("ins", p - 1, text, site) if b[1] < p else a
    _, p, site = a
    if b[0] == "ins":
        return ("del", p + len(b[2]), site) if b[1] <= p else a
    if b[1] == p:
        return None                                  # both deleted the same character
    return ("del", p - 1, site) if b[1] < p else a

doc = "the cost"
a = ("ins", 8, " is", "A")
b = ("ins", 8, " 40 usd", "B")
print(apply(apply(doc, a), b))                   # the cost 40 usd is
print(apply(apply(doc, a), transform(b, a)))     # the cost is 40 usd
print(apply(apply(doc, b), transform(a, b)))     # the cost is 40 usd

Now the protocol. The server transforms each arriving edit past every logged edit its author had not seen. Each client applies its edit at once and keeps one in flight; others' edits are transformed against that pending edit, and it against them. The server's echo of a client's own edit is its acknowledgement:

import random

class Server:
    def __init__(self, doc):
        self.doc, self.log = doc, []
    def receive(self, op, version):
        for done in self.log[version:]:              # everything the sender had not seen
            op = transform(op, done)
        self.log.append(op)
        self.doc = apply(self.doc, op)
        return op

class Client:
    def __init__(self, doc, site):
        self.doc, self.site, self.version = doc, site, 0
        self.waiting, self.pending = False, None     # one edit in flight at a time
    def edit(self, rng):
        if rng.random() < 0.6 or not self.doc:
            op = ("ins", rng.randint(0, len(self.doc)), rng.choice("xyz"), self.site)
        else:
            op = ("del", rng.randrange(len(self.doc)), self.site)
        self.doc = apply(self.doc, op)               # shown at once, before any reply
        self.waiting, self.pending = True, op
        return op, self.version
    def hear(self, op, mine):
        self.version += 1
        if mine:                                     # the server's echo is our ack
            self.waiting, self.pending = False, None
            return
        op, self.pending = transform(op, self.pending), transform(self.pending, op)
        self.doc = apply(self.doc, op)

def session(seed, start="abc", sites="ABC", steps=60):
    rng = random.Random(seed)
    server, clients = Server(start), {s: Client(start, s) for s in sites}
    up, down = {s: [] for s in sites}, {s: [] for s in sites}     # FIFO channels
    def deliver_up(s):
        op = server.receive(*up[s].pop(0))
        for t in sites:
            down[t].append((op, t == s))
    for _ in range(steps):
        s = rng.choice(sites)
        c, roll = clients[s], rng.random()
        if roll < 0.35 and not c.waiting:
            up[s].append(c.edit(rng))
        elif roll < 0.7 and up[s]:
            deliver_up(s)
        elif down[s]:
            c.hear(*down[s].pop(0))
    while any(up.values()) or any(down.values()):    # let every message arrive
        for s in sites:
            if up[s]:
                deliver_up(s)
            while down[s]:
                clients[s].hear(*down[s].pop(0))
    return server, clients

server, clients = session(4)
print(server.doc, [c.doc for c in clients.values()])   # xzxzzxxcy ['xzxzzxxcy', 'xzxzzxxcy', 'xzxzzxxcy']

A detail that bit the first draft: when two people delete the same character, the pending edit transforms into None but is still in flight. Using pending is None to mean "nothing sent" let a client send a second edit and mistake the first one's echo for its acknowledgement; copies diverged in 11 of 300 seeded sessions. Hence the separate waiting flag.

The CRDT alternative, in the style of a replicated growable array. Concurrent inserts after one character are ordered by id, newest first, so every replica picks the same order:

class Replica:
    """A sequence CRDT in the RGA style: every character has a permanent id."""
    def __init__(self, site):
        self.site, self.clock, self.nodes = site, 0, []    # nodes: [id, char, visible]

    def text(self):
        return "".join(ch for _, ch, alive in self.nodes if alive)

    def insert(self, index, ch):
        alive = [n for n in self.nodes if n[2]]
        after = alive[index - 1][0] if index > 0 else None
        self.clock += 1
        return self.apply(("ins", (self.clock, self.site), after, ch))

    def delete(self, index):
        return self.apply(("del", [n for n in self.nodes if n[2]][index][0]))

    def apply(self, op):
        if op[0] == "del":                                  # a tombstone, never removal
            next(n for n in self.nodes if n[0] == op[1])[2] = False
            return op
        _, nid, after, ch = op
        self.clock = max(self.clock, nid[0])
        i = 0 if after is None else 1 + next(k for k, n in enumerate(self.nodes) if n[0] == after)
        while i < len(self.nodes) and self.nodes[i][0] > nid:   # newer siblings stay first
            i += 1
        self.nodes.insert(i, [nid, ch, True])
        return op

a, b = Replica("A"), Replica("B")
base = [a.insert(i, ch) for i, ch in enumerate("the cost")]
for op in base:
    b.apply(op)
ops_a = [a.insert(8 + i, ch) for i, ch in enumerate(" is")]
ops_b = [b.insert(8 + i, ch) for i, ch in enumerate(" 40 usd")]
for op in ops_b:
    a.apply(op)
for op in ops_a:
    b.apply(op)
print(a.text(), "|", b.text())       # the cost 40 usd is | the cost 40 usd is

for _ in range(16):
    a.delete(0)
print(repr(a.text()), len(a.nodes))  # 'is' 18

The replicas agree without a server, on the other order: B's run has the larger id, and any order works if everyone picks the same one. Each word stays whole because every character is anchored to its author's previous one. After deleting 16 of 18 characters, all 18 nodes remain. The checks: the transform property on every pair of concurrent edits over three small documents, 300 seeded OT sessions with random delays, and 300 seeded CRDT histories, each replayed in ten random causal orders:

ok = True
for s1 in ["", "ab", "hello"]:
    ops = ([("ins", p, t, site) for p in range(len(s1) + 1) for t in ("x", "yz") for site in "AB"]
           + [("del", p, site) for p in range(len(s1)) for site in "AB"])
    for x in ops:
        for y in ops:
            if x[-1] != y[-1]:                           # concurrent edits from two sites
                ok &= apply(apply(s1, x), transform(y, x)) == apply(apply(s1, y), transform(x, y))
for seed in range(300):
    server, clients = session(seed, steps=random.Random(seed).randint(5, 80))
    ok &= all(c.doc == server.doc for c in clients.values())

def crdt_history(seed):
    rng = random.Random(seed)
    reps, log, seen = {s: Replica(s) for s in "ABC"}, [], {s: [] for s in "ABC"}
    for _ in range(rng.randint(1, 30)):
        s = rng.choice("ABC")
        r, roll = reps[s], rng.random()
        if roll < 0.25:                                 # sync: pull everything another has
            other = rng.choice("ABC")
            for k in seen[other]:
                if k not in seen[s]:
                    r.apply(log[k][0])
                    seen[s].append(k)
            continue
        if roll < 0.75 or not r.text():
            op = r.insert(rng.randint(0, len(r.text())), rng.choice("xyz"))
        else:
            op = r.delete(rng.randrange(len(r.text())))
        log.append((op, set(seen[s])))                   # the edit and its causal past
        seen[s].append(len(log) - 1)
    return log

for seed in range(300):
    log, texts = crdt_history(seed), set()
    for trial in range(10):
        rng, fresh, done = random.Random(seed * 100 + trial), Replica("Z"), set()
        while len(done) < len(log):
            k = rng.choice([k for k in range(len(log)) if k not in done and log[k][1] <= done])
            fresh.apply(log[k][0])
            done.add(k)
        texts.add(fresh.text())
    ok &= len(texts) == 1
print(ok)                            # True

The complexity

• OT server: each edit is transformed against the edits its author missed, usually a handful; the log grows with every edit and is compacted by snapshots.
• CRDT: no transformation, but per-character ids and tombstones, so memory grows with everything ever typed, not with the visible text. Removing tombstones safely requires knowing every replica has seen the delete (from memory).
• Presence: high-frequency and fire-and-forget, never persisted.

Where it goes wrong

• Applying remote positions as written. The animation's garbled sentence.
• No deterministic tie-break. Two inserts at one index land in different orders on different screens.
• OT without a single order. Peer-to-peer OT needs extra transform properties that are notoriously hard to get right (from memory); a central server sidesteps them.
• Losing track of an edit in flight, as above.
• Storing cursors. Presence through the durable log multiplies writes nobody replays.

When it shows up in interviews

As "design a collaborative document editor", and in shared whiteboards, code editors and spreadsheets. Follow-ups: two people typing at one spot, offline editing, undo, version history. It pairs with WebSockets vs polling for transport and the chat app design for presence. As of October 2026, both OT-style central servers and CRDT libraries run in production editors (from memory).

How to say it in an interview

"Keystrokes apply locally first, then go to the server over a WebSocket with the version they were written against. With OT, the server orders every edit and transforms a late one past the edits its author hadn't seen, with a deterministic tie-break; that needs one sequencer per document. With a CRDT, every character has a unique id and inserts say 'after this id', so edits merge in any causal order without a server, at the cost of per-character metadata and tombstones. Snapshots bound replay time, and cursors go over a separate ephemeral channel."