Part 5 of 8 · 2 min read
CRDTs
Give every character an identity.
Idea. Instead of positions that shift, give each character a unique, permanent identity that also says where it sits relative to others. An insert says "put this character after the character with identity Z". A delete says "mark the character with identity Y as deleted". Neither depends on position numbers, so applying edits in any order gives the same result.
Identity for text (a simple scheme). Each character gets an id made of a pair: (a counter, the id of the user's site). The id is unique because each site has its own number. Each insert names the id of the character to its left. When two users insert after the same character, the ids break the tie, say the higher id first. Everyone applies the same rule, so everyone gets the same order.
Deletes leave tombstones. A deleted character is not removed but marked deleted (a tombstone). This lets a late insert that points to it still find its place. Tombstones accumulate, so a periodic clean-up (garbage collection) is needed once all replicas have seen the delete.
Properties.
- Operations commute: order of arrival does not matter.
- Operations are idempotent in effect, since ids make a repeat detectable.
- No central server is needed for ordering, so peer-to-peer and offline work are natural. A server is still used for storage and to relay.
A worked example (made up). "CAT" has ids c1 (C), a1 (A), t1 (T). User 1 inserts "H" with id h1 before c1. User 2 deletes t1. The edits arrive at each replica in opposite orders. The result is the same: H, C, A, and t1 hidden. No positions were used.
OT versus CRDT.
| Point | OT | CRDT |
|---|---|---|
| Central server | Needed to order operations | Not required |
| Offline and peer-to-peer | Harder | Natural |
| Metadata | Small | Larger (ids, tombstones) |
| Complexity | In the transform rules | In the data structure and clean-up |
| Examples | Etherpad, Google Docs, as in the book | Newer editors and databases such as Riak |
For the curious Deeper
Kleppmann points out that databases have only begun to adopt these algorithms. A third approach keeps history explicitly and merges three ways, as Git does, while CRDTs merge two ways. For a product with rich text, tables and comments, large systems often start with OT because of its small metadata, and use CRDTs where offline and peer-to-peer matter.
Check yourself: 1. What replaces positions in a CRDT? 2. Why keep tombstones? 3. When is a CRDT a better fit than OT?