Operational Transformation

In one line: OT is what Google Docs actually runs. It is also the technique the design calls "notoriously difficult" — and the reason for that difficulty is worth understanding, because it is the argument for CRDTs.

The idea

Operational transformation (OT) is a widely used technique for conflict resolution in collaborative editing. OT emerged in 1989... It's a lock-free, non-blocking approach. If operations between collaborators conflict, OT resolves conflicts and pushes the correct converged state to end users.

OT performs operations using the positional index method... OT resolves the problems above by holding commutativity and idempotency.

What 'transformation' actually means

The design names the mechanism without demonstrating it, so here it is concretely.

An incoming operation carries an index that was computed against the sender's replica. The receiver's replica has moved on. OT rewrites the incoming index so that it means, in the receiver's document, what the sender intended in theirs.

Both start:  "Educative developers"

Alice, at her replica:  insert(10, "for ")
Bob,   at his replica:  insert(0,  "The ")

Bob's op arrives at Alice, who has already applied her own.
Applied raw:      insert(0, "The ") -> fine, index 0 is still index 0
Alice's op arrives at Bob, who has already applied his own.
Applied raw:      insert(10, "for ") -> WRONG. Bob's doc is now 4 chars longer,
                                        so position 10 points somewhere else.
TRANSFORMED:      insert(14, "for ") -> correct

That +4 is the transformation. The general rule for two inserts:

transform(insert(i, s), against insert(j, t)):
    if j <= i:  return insert(i + len(t), s)
    else:       return insert(i, s)

OT does not change what the operation does; it changes the coordinates in which the operation is expressed. Everything hard about OT is that this rule must be defined for every pair of operation types, and must be correct for every ordering of every number of concurrent operations.

The transformation, visualized

OT is lock-free but not coordination-free — and that distinction is the whole chapter

The design calls OT "lock-free, non-blocking," which is accurate and easy to over-read.

Lock-free means no user ever waits for a region of the document to be released. Every editor types into their local replica immediately, with no round trip. That is a genuine and important property — it is why Docs feels instantaneous.

But OT still requires a single authority to fix the order. Look at the diagram: the server decides that Alice's operation precedes Bob's, and transforms accordingly. Without that decision, Alice might transform Bob's operation while Bob transforms Alice's, each assuming they were first — and the results differ.

Lesson 8's evaluation says this outright: "a logically centralized server determines the final order of operations for all clients." That is the coordinator, and it is the operations queue from Lesson 3.

Lock-free       = no user blocks on another user   -> TRUE of OT
Coordination-free = no central authority needed    -> FALSE of OT

Conflating them is the most common misreading of OT, and it is exactly the confusion Lesson 7 has to untangle when the chapter attributes CRDT properties to an OT design.

The CC consistency model

Causality preservation: if operation a happened before operation b, then a is executed before b. Convergence: all document replicas across clients will eventually become identical.

Two properties, and only one of them is about ordering

These are worth separating because they fail in different ways.

Causality preservation is Lamport's happens-before applied to edits. If Bob saw Alice's insertion before typing his own, his operation depends on hers, and no replica may apply his first — the index he chose was computed against a document that included her text. Enforcing this requires tracking causal dependencies, usually with vector clocks or a per-site operation counter.

Note this is weaker than a total order. It constrains only operations that are genuinely causally related; genuinely concurrent operations may be applied in any order, provided all replicas pick the same one.

Convergence is the outcome guarantee: whatever order each replica applied things in, the documents end up identical. This is what transformation buys — replicas reach the same state through different sequences.

Causality preservation -> the system respects what users actually saw
Convergence            -> the system ends in one state

A collaborative editor needs both, and they are independent. A system can converge while violating causality (everyone agrees on a document that reflects an order nobody experienced), and can preserve causality without converging (everyone's history is sensible, the documents differ).

The full literature adds a third property, intention preservation — the effect of an operation should match what its author meant — and it is the hardest of the three. The design's model has only two.

The two disadvantages

Operations rely on positional indexes, making them order-dependent. An insertion at the beginning of a document shifts the indexes of all subsequent characters.

Implementing correct OT algorithms is notoriously difficult. The Google Wave team spent two years perfecting its OT implementation.

Why the transformation functions explode — the real reason for two years

"Notoriously difficult" is not hand-waving, and it is worth knowing where the complexity actually lives, because interviewers ask.

The number of transformation functions grows with the square of operation types. With insert, delete, and edit you need a rule for every ordered pair:

insert vs insert   insert vs delete   insert vs edit
delete vs insert   delete vs delete   delete vs edit
edit   vs insert   edit   vs delete   edit   vs edit

Add formatting — bold, italics, styles, tables, embedded objects — and a real editor has dozens of operation types. Every new feature multiplies the rules that must be written and proven correct.

Correctness must hold for arbitrary numbers of concurrent operations. Getting two right is manageable. The transformation properties (known as TP1 and TP2 in the literature) must hold for any set of concurrent operations transformed in any order — and TP2 in particular is famously hard to satisfy; several published OT algorithms were later shown to be wrong.

Failures are silent and permanent. A subtly incorrect transformation does not crash; it produces a document that is slightly different on Alice's screen than on Bob's, and since every subsequent operation is computed against a diverged replica, the divergence compounds and never self-heals.

Complexity that grows quadratically with feature count and fails silently is the worst combination there is. That is the Wave anecdote's real content, and it is the entire motivation for CRDTs.

'Order-dependent' is the more consequential disadvantage

The first disadvantage sounds mild — indexes shift when you insert. Its consequences are not.

Operations cannot be applied out of order, so a replica that receives operation 5 before operation 4 must buffer it. That means per-client sequencing state on the server, and it means a client that falls behind stalls.

Offline editing is hard. A client that has been disconnected for an hour returns with operations computed against an hour-old document. Every one must be transformed against everything that happened meanwhile — the transformation chain is as long as the divergence.

A slow client hurts everyone. The design's own closing Q&A asks about users with different internet speeds and answers: "operations are order-dependent in OT, whereas operations in CRDTs are order-independent. This is why CRDTs are a suitable solution to such a problem."

That is a good answer, and note what it concedes — the design's chosen technique is the wrong one for a scenario the design explicitly has, since Lesson 8's latency section is entirely about geographically distributed collaborators.

Order dependence turns network variance into correctness work. CRDTs remove it by making order irrelevant, which is the subject of the next lesson.

OT's decisive advantage is the one the design never states

Read the table again and notice the row with no cost: the document stays plain text.

An OT document is exactly what a text editor already holds — a string. There is no per-character metadata, no unique identifiers, no fractional positions. A 100 KB document occupies 100 KB.

Lesson 6 will show that a CRDT document does not. Every character carries a site ID, a position, and ordering metadata — commonly several times the size of the character itself.

That is very likely why Docs runs OT, and why the design can say "major platforms such as Google Docs and Etherpad rely on operational transformation" while also saying CRDTs are simpler. Simplicity of algorithm was traded for size of data, and at Google's scale the data won.

It is also the sharpest way to answer "OT or CRDT?" in an interview: OT puts the complexity in the code; CRDTs put it in the data.

Next: CRDTs, and the opposite bet.