Conflict-free Replicated Data Types
Concurrent updates converge with no coordination at all, provided the merge is a join and the operations commute - and provided no invariant crosses a replica.
Read the original ↗The paper that turned "the copies will sort it out" into a theorem with conditions attached. Its real contribution is not the catalogue of merge-safe data types everyone quotes - it is the precise statement of what a data type must satisfy for concurrent updates to converge with no coordination, no rollback and no conflict handler. The word conflict-free means the fight was settled in advance, not that nobody fought.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardNeither OT nor CRDTthe rebuttal, in the company's own words: a CRDT assumes nobody is in charge, and centralisation is the clock
- BoardThe Maplast writer wins per property - the one line a whole product is built on, and what you can have instead when a server exists
- BoardReplicationmulti-leader write conflicts, where CRDTs sit in a list of four resolutions next to the one that silently drops a write
- BoardThe Copy Clerksreplicas a beat behind, which is the world this algebra was written for
- BoardThe Cut Phone Lineanswering anyway, which is the only reason a merge function has to exist
- BoardCharged Twicethe duplicate request - idempotent and commutative, derived by hand under time pressure
- BoardNo One Is in Charge - Emergencelocal rules, no coordinator, a coherent global result; a CRDT is that arranged on purpose rather than observed
- LabThe copy clerksthe divergence window a merge function is being asked to close
- LabThe cut phone lineanswer anyway or refuse - CRDTs are the first answer, done with the resolution decided in advance
- LabCharged twiceat-least-once and the set of seen ids that survives it - a grow-only set, built by an engineer who had never read this paper
- VideoReplication: the copy clerksthe lag between copies, before anyone tries to merge it away
- VideoCAP: the cut phone linethe partition that makes independent writes unavoidable
- VideoIdempotency keys: how a retry stops being a second chargethe client-supplied key that makes a retry safe - commutative and idempotent, one operation at a time
- LessonFigma - the case studyUses the board Neither OT nor CRDT
- LessonReplicationUses the board Replication
- LessonKV: quorumUses the board The Copy Clerks
- LessonThe copy clerks (database replication)Uses the board The Copy Clerks
- LessonKV: everythingUses the board The Cut Phone Line
- LessonThe cut phone line (CAP, done properly)Uses the board The Cut Phone Line
- LessonCharged Twice (idempotency & exactly-once)Uses the board Charged Twice
- LessonNo One Is in ChargeUses the board No One Is in Charge - Emergence
Further reading
Read the original for the full argument and its evidence.
- A comprehensive study of Convergent and Commutative Replicated Data Types ↗INRIA research report 7506, 2011. The long version, and the one to actually read - the conference paper is a summary of it. Sections on the specification framework first, then the catalogue; the set types are where the design choices become visible.
- crdt.tech ↗The maintained index of everything that happened afterwards: delta CRDTs, the sequence types that replaced the ones in the original catalogue, and the implementations worth reading.
- How Figma's multiplayer technology works ↗The honest counterweight, and the source for this site's Figma boards. A company that considered both operational transform and CRDTs, took the idea, and declined the machinery because a central server already provides the ordering the machinery exists to reconstruct.