Operational transforms and CRDTs

01The intuition

The problem it solves

Two friends, Asha and Ravi, are editing the same sentence in a shared document. The sentence is "the cat sat". Asha, at position 4, inserts "big " so her screen reads "the big cat sat". At the same moment Ravi deletes the word "sat" at positions 8 to 10, so his screen reads "the cat ". Each change travels over the network and arrives at the other person a fraction of a second later.

Now the naive approach: apply the other person's edit exactly as it was sent. Ravi receives "insert 'big ' at position 4" and applies it, which is fine. Asha receives "delete positions 8 to 10". But on her screen the text has already shifted right by four characters, so positions 8 to 10 are now "cat", not "sat". She ends with "the big sat" while Ravi has "the big cat ". The two copies have diverged, and neither person did anything wrong. With ten people typing, the copies diverge within seconds.

A central server that applies edits one at a time does not fix this: each client still has to show the user's own keystroke immediately, before the server has seen it, or typing feels like a 300 ms delay on every key.

Build it one piece at a time

Step 1: name every edit as an operation. Instead of sending a new copy of the text, each client sends small operations: insert(position, text) or delete(position, length). Both friends start from the same version, call it version 0.

Step 2: tag each operation with the version it was made against. Asha's insert says "made against version 0". Ravi's delete also says "made against version 0". Now a receiver knows the two operations are concurrent: neither saw the other.

Step 3: transform an incoming operation past the ones it did not see. This is the operational transform (OT). Asha receives delete(8, 3) tagged version 0, but she has already applied her own insert of 4 characters at position 4, which is before position 8. So she shifts the delete right by 4: delete(12, 3). That removes "sat". The rule is a small table: if the other edit happened before yours in the text, shift your position by its length; if after, leave it.

Step 4: let a server order the operations. With many clients, each operation goes to a server, the server assigns it the next version number and broadcasts it. A client that has unacknowledged local operations transforms every incoming operation past them. Google Docs works this way: the server is the single source of order.

Step 5: or remove the need for order entirely with a CRDT. A conflict-free replicated data type gives every character a permanent identity, for example (author, counter), plus a position between two existing identities. "Insert after character X" means the same thing on every machine no matter when it arrives, and a delete marks a character as a tombstone instead of shifting anything. Operations can then be applied in any order and all copies converge, which is what an offline client that reconnects after an hour needs.

Why it works, with the numbers

The guarantee both approaches give is convergence: once every client has received every operation, all copies are identical. OT proves it with the transform property, which for two concurrent operations a and b says

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

Both orders land on the same document. A CRDT gets the same result because its merge is commutative and idempotent, like a set union: adding the same element twice, in any order, gives one set.

The costs differ. An OT server does O(k) transforms per incoming operation where k is the number of unacknowledged local operations, usually under ten, so a keystroke costs microseconds. A text CRDT stores an identity per character, roughly 20 to 40 bytes each, so a 100 KB document can carry a few megabytes of metadata, and tombstones for deleted text stay until garbage collection. The failure modes are honest ones: OT needs the server to be reachable to assign order, and CRDT documents grow with their history.

The trade-off you must say out loud

OT keeps documents small and needs a central ordering server; CRDTs work peer to peer and offline but pay in memory and in a harder merge for rich text and tables. The follow-up an interviewer asks is "what happens when a client is offline for a day": with OT you queue operations and transform them on reconnect, and the user may see a surprising merge; with a CRDT the merge is automatic but you must explain how tombstones are compacted.

Where it shows up in the 100 Google problems

• Design Google Docs: the server orders operations and every client transforms incoming edits past its own pending ones, so typing stays instant and all screens converge.
• Design an offline-first client that syncs and resolves conflicts: a CRDT per note or list lets a phone edit for hours without a server and still merge cleanly on landing.
• Shared lists and chat drafts use the same idea on smaller structures, where a last-writer-wins register per field is often enough.

02Used in these problems

• Design Google Docs
• Design an offline-first client that syncs and resolves conflicts