Operational transformation vs CRDTs

Shared editing breaks a simple assumption: that a position in a document means the same thing to everyone. Suppose Ana and Ben both have a note open. Ana types a word at the start. At the same moment Ben adds a full stop at the end of the first line, by position. When Ben’s edit reaches Ana, her text has moved along by one word, so applying Ben’s edit at the position he meant puts the full stop in the wrong place.

Both techniques make sure every copy ends up with the same text and that each person’s edit lands where they meant it. They differ in how they get there.

Operational transformation (OT) keeps edits as positional operations, such as “insert this at position x”, and fixes them up as they cross. When an edit arrives that was made without knowledge of a local edit, the receiver transforms it, adjusting its position to account for what has happened since. The technique dates from the late 1980s, from work by Ellis and Gibbs.

In practice, OT systems usually route edits through a server. Google described the protocol behind Google Docs in 2010:

• Each client tracks the last revision it received from the server, its unsent changes, and changes sent but not yet acknowledged.
• The server keeps a revision log of every processed change.
• When a client’s change arrives late, the server transforms it against every change committed since that client last synced, then stores it as the next revision.

Google Wave took the same approach, starting from the Jupiter collaboration system. Wave made each client wait for the server to acknowledge one batch of operations before sending more, so the server only had to keep a single history.

Shapiro and colleagues sum up the difference in approach: OT makes concurrent operations commute after the fact, by transforming them, rather than designing them to commute.

A CRDT designed for text avoids positional edits altogether. Every character gets a unique identifier, and insertions refer to those identifiers, for example “after this character”, rather than to a numeric position. Because identifiers do not shift when other people type, concurrent edits can be applied in any order and every copy reaches the same result. The Yjs README puts it simply: OT transforms index positions to reach convergence, while CRDTs use structures such as linked lists that usually involve no index transformations.

The first CRDT for co-editors, WOOT, was proposed around 2006. Yjs, for example, provides shared maps, arrays, and text built this way, and describes itself as network agnostic, with support for offline editing.

The need for a server. The OT systems described above are built around a server that fixes the order. The Yjs README states that OT approaches without a central source of truth require too much bookkeeping to be viable in practice. CRDTs need no authority on order, which suits devices that edit offline for long periods or sync peer to peer.

Correctness is hard either way. OT depends on its transformation functions being right, and Shapiro and colleagues cite work by Oster and others showing that most OT algorithms for a decentralised setting are incorrect. CRDTs have their own traps. Kleppmann and colleagues showed that two published text CRDTs, Logoot and LSEQ, can interleave two people’s concurrent insertions character by character into an unreadable jumble. Convergence alone does not make an editor usable.

Metadata. The Yjs README notes that CRDTs suited to text only grow in size, because deleted characters must leave markers, called tombstones, behind to keep a unique order. Yjs reduces this overhead but cannot remove it entirely.

Track record. Sun and colleagues argue that OT remains the choice for the vast majority of working co-editors and that claims of CRDT superiority over OT do not hold up. Even the Yjs README, written for a CRDT library, calls OT the de facto standard for shared text editing.

The deciding question is whether you can rely on a server being reachable.

• Always connected, real-time text. OT with a central server is the model Google Docs and Google Wave were built on, and it keeps the server as the single authority on order.
• Long offline periods, or peer-to-peer sync. A CRDT lets each device edit its own copy and merge whenever it meets another, through a server, a relay, or a direct link, with no server deciding the order.
• Structured data, not just text. CRDT libraries offer maps, lists, and counters as well as text, so one model can cover a whole document.

Neither technique enforces business rules. Two people can still merge cleanly into a state that breaks an invariant, so decisions such as bookings or stock still need an authority, as described in How are sync conflicts resolved?