CRDT

Take the style edit of chapter 44 of the basic course, 146 word-level changes, and deal it out to three editors in turn: the first change to the first editor, the second to the second, the third to the third, the fourth to the first again. Each edits their own copy of the old version, knowing nothing of the others. Then the edits have to be combined. git compares lines, and in an HTML chapter a paragraph is one long line, so if two people edited a paragraph, that is a conflict. Scroll through the paragraphs.

Pair by pair, git merge-file finds 17, 18 and 16 conflicts: that many places where a person has to choose by hand what to keep. The word-level merge combines the three copies without a single question, and the result matches the real edit byte for byte, as if one person had edited the chapter. The secret is not a clever comparison. Each word remembers its place in the shared document, and an edit is expressed as “delete these words, insert new ones after that one”, and such edits combine in any order.

The idea

Copies change independently and send out changes however they can: with delay, in different orders, sometimes twice. If a data type is built so that merging does not depend on order and repeats, all copies that received the same changes end up in the same state, without a server, without leader election, without locks. Such types are called CRDTs, conflict-free replicated data types.

There are two ways to get this. In the first, copies send their whole state, and merging two states must be commutative, associative and idempotent: a ⊔ b = b ⊔ a, (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c), a ⊔ a = a. In the second, copies send operations, and then the operations themselves must commute, while delivery must be in causal order, without losses or repeats. This is the opposite of consensus: Raft achieves one order of all writes and pays for it with availability when a majority is unreachable; a CRDT needs no common order, and each copy always accepts changes, even without a network.

A counter

Start with the simplest case, likes. Three phones accept likes on their own and now and then exchange state. If each keeps one number, and on exchange the larger wins (“larger means newer”), likes get lost: phone A accepted five, B three, C four, and after the exchanges all show five instead of twelve.

A G-counter (from grow-only) keeps a vector: how many likes each phone accepted. A phone increases its own entry itself, and on exchange takes the componentwise maximum. The value is the sum of the vector. Nobody increases another phone's entry, so the maximum loses nothing: each entry is knowledge about someone's counter, and the knowledge is newer if the number is larger. These are the same vector clocks, counting likes instead of events.

A G-counter cannot be decreased: the maximum cannot “forget”. For likes that can be withdrawn, two G-counters are kept, pluses and minuses, and the difference is shown; this is a PN-counter.

A set

A set is harder: what if one copy removed an element while another added it at the same time? A simple set in which removal is an entry in “removed forever” will never bring back what was crossed out, even if it is added again. The OR-set (observed-remove) solves this with tags: each addition gets a unique tag, and a removal crosses out only the tags the remover has seen. An addition the remover did not know about stays in force: a concurrent addition wins over a removal. This is the first problem of the article, a shopping list for two.

Text

Text is a sequence, and inserting “at position five” means different things in different copies: in one of them two words have already been inserted before position five. So positions are replaced with ids. Each element, a word or a character, gets a unique id: a pair “counter, copy” where the counter is greater than all ids the copy has already seen, as with Lamport clocks. An insertion says not “at position 5” but “after the element with such-and-such id”. A deletion does not remove the element but turns it into a tombstone: other copies' insertions that arrive later may refer to it.

What remains is to decide what happens when two copies insert after the same element concurrently. In RGA (replicated growable array) the rule is: take a place after the neighbour element, but skip everyone whose id is greater than ours. These are concurrent insertions the rule gives precedence to, plus everything inserted after them later. Then all copies put concurrent insertions in the same order, by decreasing id, whatever the order of delivery. The second problem of the article is this rule.

Convergence does not mean the result makes sense. If two people corrected the same word differently, one writing “slow”, the other “fast”, RGA will delete the old word and keep both insertions side by side: “fastslow”. There is no conflict in the system's sense, all copies see the same thing, but a person has to decide what was meant. There is a subtler problem too: with concurrent typing at one place, some algorithms interleave the letters of the two authors. Martin Kleppmann and co-authors showed such interleaving in Logoot and LSEQ in 2019; RGA does not allow it with ordinary typing from left to right, but it can with typing in the opposite direction. Later algorithms such as Fugue reduce interleaving to a minimum.

Code

The listing shows the like counter with one number and with a vector, then RGA on the real edits of three editors: each copy receives the operations in its own order, and all three arrive at one text, matching the style edit. At the end two editors change the same word.

What it costs

Operations take almost no time: increasing a counter, adding a tag, inserting an element after a neighbour are O(1). The price is paid in memory. A G-counter keeps a number for each copy that has ever accepted likes. An OR-set remembers removed tags, otherwise an old state arriving later would bring back what was crossed out. Text keeps an id for each element and a tombstone for each deleted one: in the three editors' edit there are 327 tombstones on top of 16,684 visible elements, and a document edited for years can accumulate more tombstones than live text.

So real systems collect garbage: a tombstone can be thrown away once all copies have confirmed they saw the deletion, and for that they need to know who has seen what, which again means vectors. Libraries compress ids: characters typed in a row by one author are stored as one run with one id.

Where it is used

Storage. Riak offers CRDTs as data types: counters, sets, maps, flags. Redis Enterprise, in Active-Active databases that run at several sites at once, merges concurrent writes as CRDTs, with their own merge rules for counters, sets and strings.

Collaborative editing. Automerge and Yjs are libraries that let a document be edited on several devices without a constant connection and the edits merged later; inside are sequences with element ids and tombstones, as in RGA. Google Docs works differently: on operational transformation, where a server orders the edits. Figma in 2019 described its sync as inspired by CRDTs but simplified: since the system has a central server, part of the work of ordering can be left to it.

History

Collaborative editing without a centre has been sought since the late 1980s: in 1989 Clarence Ellis and Simon Gibbs proposed operational transformation, on which the first collaborative editors grew. Algorithms in which convergence follows from the design of the data appeared in the mid-2000s: WOOT in 2006, Treedoc in 2009, RGA in 2011. The general theory, the conditions under which copies are guaranteed to converge, and the name CRDT itself came in 2011 from Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski.

Problems

The first is the OR-set: a shopping list for two, where a concurrent addition wins over a removal. The second is RGA: assemble a document from operations that arrived in any order, including the real edits of three editors.