Skip to content

Operational transforms and CRDTs

Two ways to merge simultaneous edits without locks: operational transformation adjusts each edit's position against concurrent ones, in Jupiter and Google Wave through one server; a CRDT is a replicated type that resolves concurrent updates itself, without a coordinator.

On this page

What it is

Both techniques solve the same problem: two people edit copies of one document at the same time, each copy applies its own change immediately, and the copies must end up identical once the changes have crossed. Operational transformation (OT) treats each edit as an operation with a position, such as insert at index 0 or delete at index 2. Take the text abc: one user inserts x at index 0 while the other deletes the character at index 2. Applied as sent, the delete would remove b after the insert shifted the text. OT rewrites the incoming delete to index 3 so it still removes c; both copies finish at xab. The approach dates to Ellis and Gibbs's GROVE editor in 1989, and in 2009 it became the merge technique behind Google Wave and Google Docs.

Where the transforming happens matters. In Jupiter and Google Wave's OT, each operation goes through a central server that transforms it against the concurrent operations already accepted and broadcasts it in that order; other OT algorithms work without a server and track causality with state vectors. The hard part is the transformation functions: in the approach that defines operations per application, m kinds of operation need m times m functions, one per pair, and formal proofs that they combine correctly have been called complicated and error-prone even for plain insert and delete.

A conflict-free replicated data type (CRDT) moves the merging into the data structure itself. Each replica can be updated independently without coordinating, and a rule inside the type resolves whatever disagreement arises, so replicas that have seen the same updates hold the same state. The idea was formalized in 2011 by Shapiro, Preguiça, Baquero and Zawirski. Two flavors exist. A state-based CRDT merges states with a function that is commutative, associative and idempotent, so reordered or duplicated messages do no harm; the basic form sends the entire state, and delta variants send recent changes to it instead. An operation-based CRDT has no merge function: it sends small operations that are applied at each replica, and it needs the transport to deliver each operation once and in causal order.

For text, a sequence CRDT (Treedoc, RGA, WOOT, Logoot, LSEQ among them) replaces positions with some combination of unique symbol identifiers, vector timestamps and tombstones, so a later insert can refer to what it sits next to rather than to an index. That removes the need to transform positions, at the price of metadata inside the document; how much stays depends on the algorithm and on whether the implementation compacts it. Libraries package this up: Yjs exposes shared Map and Array types that distribute and merge changes over any network, including peer to peer and offline; Automerge merges concurrent changes without a central server and keeps the change history so old versions can be viewed.

When to use it

Reach for OT when there is one server anyway and the data is text-like with a small set of operation types. In the central-server designs the server becomes the order of record: it fixes the sequence in which operations apply, and the document itself carries no per-character identifiers or tombstones. Google Docs adopted OT in 2009, and the model suits a product where a single authority is acceptable and the client library is thin.

Reach for a CRDT when replicas must merge without a coordinator: a note taken offline on a phone and synced days later, a peer-to-peer session over WebRTC, or a local-first app that treats the device copy as primary. Automerge is built for that model and notes it also works fine with a central server, and Yjs is network agnostic, so the transport is a separate module you swap. A CRDT also fits data that is not text at all, such as a counter or a set replicated across regions.

When not to

Skip both when edits rarely overlap. A lock or section ownership (one person edits a paragraph at a time) is simpler and shows users what is happening, and a last-writer-wins timestamp per field is often enough for a settings form whose fields are independent. Be careful with data that has a hard invariant, such as a seat count or an account balance: a CRDT merge is designed to proceed without coordination, so before choosing one, ask how the limit will hold across replicas, whether through a server that validates an operation before accepting it or through a type built to reserve capacity ahead of time.

Prefer OT over a CRDT when document size matters and you already have a server. Sequence CRDTs carry identifiers and, in many designs, tombstones; a tombstone set can grow without bound unless the type is designed to avoid or compact it. Prefer a CRDT over OT when you have no server to order operations, or when the client must keep working offline for long stretches: an operation-based CRDT still needs a channel that drops nothing, duplicates nothing and respects causal order, so budget for that transport either way.

Compared

QuestionOTCRDTWhen the other is right

Who merges?

In Jupiter and Google Wave, a central server transforms and orders operations; other algorithms use state vectors instead

Each replica merges on its own; no coordinator

CRDT when there is no server or clients work offline; OT when one server is the record anyway

What travels?

Operations with positions, interpreted against the order the system fixes

State-based: states, or recent deltas; operation-based: the operations, which are typically small

Operation-based CRDT or OT when messages must stay small; state-based CRDT when the transport is unreliable gossip and a resend of state is cheaper than tracking what was delivered

What grows?

Whatever operation history the server keeps for transforming late arrivals

In sequence CRDTs, identifiers and often tombstones inside the document

OT when stored document size matters; CRDT when the client needs the full merge data locally

Where is the correctness proof?

In the transformation functions and control algorithm; proofs are hard even for insert and delete

State-based: a merge that is commutative, associative and idempotent; operation-based: operations that commute

CRDT when you can take a proven library; OT when your operation set is tiny and fixed

What does the network owe you?

Causal order for causally related operations; in central designs, a link to the server

State-based: any gossip; operation-based: no drops, no duplicates, causal order

OT when you have a reliable client-server link; CRDT when peers connect directly or intermittently

In a picture

OTCRDTUser types acharacterApply on this copyWhichapproach?Servertransforms the opSend update topeersBroadcast inserver orderPeer integrates ititselfPeer transformsit againIdentical copies
Central-server OT, as in Jupiter and Google Wave, orders and transforms each operation; a CRDT peer integrates each update on its own, by merging states or applying operations, with no coordinator.

How to say it in an interview

The common mistake

Quiz

Text is abc. One user inserts x at index 0 while another deletes index 2. Why does OT change the delete before applying it after the insert?
Why must a state-based CRDT's merge function be idempotent?
A notes app must let one user edit on a phone and a laptop while offline for days, then sync them with no server in the path. Which fits?
Which cost does a sequence CRDT carry that OT avoids?

Related

Sources

  1. Wikipedia: Operational transformation
  2. Wikipedia: Conflict-free replicated data type
  3. Yjs: Shared data types for building collaborative software (README)
  4. Automerge documentation: Welcome to Automerge
Sign in to report a mistake