Design a Collaborative Editor (Google Docs), stage 4 of 12: decide
Merging concurrent edits
Alice and Bob both see "The cat sat." Alice inserts "black " before "cat" at position 4. At the same moment, Bob deletes "sat" at positions 8-10. Each sends an op computed against the text they saw. Applied naively in the server's order, Bob's delete removes the wrong characters on Alice's machine. And offline users may send hours of such ops at once.
System so far· 4 parts
Select a component to see what it is responsible for and which state it owns.
- 1Editor client → Document router: WebSocket: ops, acks, remote ops, presence
- 2Document router → Document owner: Route by document id to the current owner
What you need to know
Alice and Bob both edit "The cat sat." Alice inserts "black " at position 4. Bob deletes positions 8–10 ("sat"). Each op was computed against the text they saw.
Once Alice's insert has happened, everything after position 4 has shifted by 6 characters. Applied as-is, Bob's "delete 8–10" now removes the wrong characters.
Think first
After Alice's insert the text is "The black cat sat." Applied naively, Bob's delete of positions 8–10 (counting from 0) removes which characters?Two families of algorithms make concurrent edits converge. See Conflict resolution and convergence:
- Operational transformation (OT): a central server transforms each incoming op against the ops it hadn't seen (shift Bob's delete by Alice's insert), then applies it in one agreed order.
- CRDTs: every character gets a stable identity, so ops say "delete character #a17" instead of "delete position 8". Ops then commute: they give the same result in any order.
Check
A user edits offline for three hours, then reconnects. Which approach handles that more naturally?