Skip to content
Conflict-Free Replicated Data Types 4 min

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski · SSS 2011

Conflict-Free Replicated Data Types

How to let every replica accept writes and still merge without conflicts: strong eventual consistency, grow-only counters and add-wins sets, with a three-replica playground.

Read the original paper

Systems & Distributed · Black Belt · Pro · 4 min read

Conflict-Free Replicated Data Types

Two people edit the same shopping list on their phones while the train goes through a tunnel. One adds milk. The other removes milk and adds eggs. When the signal returns, the app has to merge the lists. Someone's change might be lost, or the app might ask you to resolve a conflict.

That is the everyday face of eventual consistency: let every copy accept writes right away, and sort things out later. It scales beautifully and it stays available when networks fail. The catch is that merging by ad hoc rules is error-prone. This paper gives a clean answer: build data types that cannot conflict.

A conflict-free replicated data type (CRDT) is built so that any two copies can be merged automatically and every copy that has seen the same updates ends in the same state, in any order. Counters, sets and registers can all be designed this way.

Strong eventual consistency

Plain eventual consistency only promises that copies will agree eventually, if updates stop. It says nothing about how conflicts are settled, so every team invents its own rules.

The authors define strong eventual consistency: any two replicas that have received the same set of updates are in the same state, immediately, with no further coordination. If you can build a data type that guarantees this, replicas can accept writes without asking anyone, even during a network partition.

The paper gives two recipes, both with a precise mathematical condition.

  • State-based. Replicas send their whole state to each other and combine it with a merge function. For this to work, merge must be commutative (order does not matter), associative (grouping does not matter) and idempotent (merging the same state twice changes nothing). Together with states that only grow, these properties form a join semilattice.
  • Operation-based. Replicas send each small update (an operation) instead of the whole state. The operations must commute, and the network must deliver each one exactly once, in causal order.

Think of merge as "take the maximum." The maximum of 3 and 5 is the same as the maximum of 5 and 3, the same however you group, and taking it twice changes nothing. Design your data so that merging is a kind of maximum, and conflicts disappear.

The simplest example: a counter that cannot lose votes

Suppose three servers count likes. The naive plan is for each server to store one number and merge by taking the larger one. It fails. If two servers both start at 5 and each adds one, both now say 6. Merging by maximum gives 6, but the right answer is 7. One like was lost.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 2 more diagrams and 2 interactive elements to play with

  • Sets: when add and remove collide
  • Where this shows up

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.