Operational transformation vs CRDTs

Two families of algorithms let many people edit one document at once. Operational transformation came first, powers Google Docs, and dominated for two decades. Conflict-free replicated data types came out of distributed systems research, and almost everything built since the late 2010s uses one.

The comparison is usually reduced to “CRDTs use more memory, OT is more complicated”. Both halves are outdated. Here is what the trade-off actually consists of.

The shared problem

A document reads hello. Client A inserts X at position 0. Concurrently, client B inserts Y at position 1. Each applies its own edit immediately, so A sees Xhello and B sees hYello.

Now the operations cross the network. If each is applied literally, A computes XYhello and B computes XhYello. The replicas have diverged, and nothing downstream will ever repair it.

The problem is that position 1 was measured against a document that no longer exists. OT and CRDTs are two answers to that one sentence.

Operational transformation: repair the index

OT keeps the intuitive representation — the document is a string, operations carry integer positions — and fixes the operation at the moment it is applied.

Every client keeps a record of the operations it has applied that the sender had not yet seen. When B’s insert(Y, 1) arrives at A, A notices it was generated against a state that predates insert(X, 0). It calls a transform function:

transform(insert(Y, 1), against: insert(X, 0))
  → insert(Y, 2)

An insertion at or before your position shifts you right by one. Apply the transformed operation and A gets XhYello, matching B. B performs the mirror-image transform on A’s operation and also stays at XhYello. Converged.

For insert-versus-insert on plain text, that is genuinely all there is to it, and it is a pleasant algorithm to implement.

Where it gets expensive

You need a transform function for every ordered pair of operation types. Insert-vs-insert, insert-vs-delete, delete-vs-insert, delete-vs-delete. Introduce rich text and you add mark-vs-insert, mark-vs-delete, mark-vs-mark. Introduce a tree structure — headings, lists, nested blocks — and you add move-vs-move, which is notoriously capable of producing a cycle where a node ends up as its own ancestor. The matrix grows quadratically in the number of operation types, and every cell is a small correctness proof somebody has to get right.

Then there are the transformation properties. TP1 says that transforming two concurrent operations against each other and applying them in either order gives the same result. That is achievable. TP2 extends the requirement to three or more concurrent operations converging along different paths — and TP2 is hard enough that several published, peer-reviewed OT algorithms were later shown not to satisfy it.

Production systems duck TP2 rather than solve it: put a single server in the middle, have it impose one total order on all operations, and make every client transform against that same sequence. With one authoritative history there is only ever one path, so the three-way case cannot arise.

This is a completely legitimate engineering decision and it is what Google Docs does. It also means the central server is not an implementation detail — it is load-bearing. The algorithm’s correctness argument depends on it.

CRDTs: make the index unnecessary

A CRDT attacks the same sentence from the other side. If unstable positions are the problem, remove positions.

Each character gets a globally unique, permanent identifier, and an insertion is expressed relative to a neighbouring identifier rather than an index: “Y goes immediately after the character (A,3)”. That description stays true no matter what else is inserted or deleted, so the operation needs no repair on arrival. Concurrent insertions at the same anchor are ordered by a deterministic tie-break on the identifiers themselves.

The full mechanics — tombstones, run-length compression, why deletion cannot actually delete — are covered in how CRDTs work. The structural point for this comparison is that merging is correct on each replica independently, with no reference to any global sequence.

The comparison

The memory objection, revisited

“CRDTs use too much memory” was true, was repeated for a decade after it stopped being decisive, and is now mostly folklore.

Early implementations stored a separate object per character, with a multi-part identifier attached to each, and never reclaimed deleted ones. Overheads of 10× to 100× the raw text were normal, and for a large document that is disqualifying.

What changed is that implementations began encoding runs. People type in sequences, so consecutive characters have consecutive IDs and share an anchor; a hundred characters typed in a row collapse into one internal item with a length field. Deleted regions compress the same way. Since real editing is overwhelmingly sequential, the pathological case — a document assembled by inserting single characters at random positions — essentially does not occur outside benchmarks.

Contemporary libraries handle multi-megabyte documents with hundreds of thousands of edits inside a browser tab. The overhead is not nothing, and it is no longer the thing that decides the architecture.

When OT is still the right answer

Two honest cases.

You already have one that works. A mature, debugged OT implementation with years of production traffic behind it is a valuable asset. Rewriting it because CRDTs are fashionable is how teams spend a year reintroducing bugs they fixed in 2019.

You need server-side authority over content. If the server must inspect, validate, transform or reject edits — content policy, permissions at sub-document granularity, server-side indexing — then it has to understand the document anyway. Half of the CRDT argument is that the server can be ignorant; if it cannot be, you are paying the CRDT’s costs without collecting its main benefit.

Outside those, the calculus strongly favours CRDTs, and mainly for a reason that is about people rather than algorithms: with OT the hard part lives in your codebase and grows every time you add a feature, whereas with a CRDT it lives in a library that many teams share, test and fix.

The practical choice

NoobProMax uses Yjs, and the deciding factor was precisely the server-complexity row of that table. Because merging is correct on every client independently, the backend never has to understand a document — it stores and forwards encoded blobs, which is a job a generic realtime database can do without any bespoke server code.

That has a second consequence worth noticing. A server that does not need to read the updates can be handed updates it cannot read. Under OT, encrypting the payload would break the algorithm outright, because the component doing the transformation is the one you are hiding the data from. Choosing a CRDT is what makes end-to-end encrypted collaboration possible at all.