CRDTs: Conflict-Free Replicated Data Types

Data types that let every replica accept writes on its own and still end up identical: counters, registers, sets and text, how their merges work, what they cost, and where real systems use them.

Overview

Many systems want every replica to accept writes without asking the others first: a phone editing a note offline, two data centers each taking updates to a shopping cart, a counter incremented on whichever server is closest. The problem is what happens when those independent writes meet. Last-write-wins throws one away; storing both as siblings pushes the problem onto the application.

A CRDT (conflict-free replicated data type) is a data type designed so that concurrent updates never conflict. Every replica applies its own updates at once and sends them, or its whole state, to the others later, in any order. Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski formalized this in 2011 as strong eventual consistency: any two replicas that have received the same set of updates are in the same state, with no rollback and no conflict for anyone to resolve.

The price is that the data type decides the conflict rule in advance, and some rules need extra metadata. A counter is easy. A set has to choose what wins when one replica adds an item while another removes it. Text needs a unique ID for every character.

What you will be able to do

  • Explain strong eventual consistency and the merge properties that give it.
  • Compare state-based, operation-based and delta-state CRDTs, and what each needs from the network.
  • Build a G-Counter, a PN-Counter and an observed-remove set, and say which conflict rule each chooses.
  • Compare CRDTs with operational transformation for collaborative editing.
  • Say when a CRDT fits a design and when an invariant forces you back to coordination.

Key concepts

  • Strong eventual consistency
  • State-based CRDTs
  • Operation-based CRDTs
  • Delta-state CRDTs
  • G-Counter and PN-Counter
  • LWW and multi-value registers
  • OR-Set (add wins)
  • Tombstones
  • Sequence CRDTs
  • CRDTs vs OT

Interview questions

  • What is a CRDT, and what does strong eventual consistency guarantee?
  • Design a distributed like counter that works across regions without coordination.
  • State-based or operation-based CRDTs: what is the difference?
  • How does an OR-Set handle an add and a remove of the same item at the same time?
  • CRDTs or operational transformation for a collaborative editor?
  • What are the limitations of CRDTs?
  • Where would you use a CRDT in a system design interview?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio