CSE Roadmap

Specialist tier · about 5 hours · 8 parts

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?