Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Replication

CRDTs: Conflict-Free Replicated Data Types

Learn CRDTs: how G-Counters, PN-Counters, G-Sets, OR-Sets and LWW-registers merge without conflicts, with the three merge laws and convergence tests.

In the previous lesson you saw that concurrent writes need a merge rule, and that last-write-wins throws information away. A conflict-free replicated data type (CRDT) is a data structure designed so that the merge rule is built in and always works. Replicas can be updated independently, with no coordination and no locks, even while offline. When they later exchange state, in any order, any number of times, they end up identical.

CRDTs power collaborative editors, shopping carts, presence indicators, distributed counters and parts of databases such as Riak and Redis Enterprise. In this lesson you will build five of them in Python and test the laws that make them safe.

State-based CRDTs and the three laws

In a state-based CRDT each replica keeps a local state and, from time to time, sends its entire state to another replica, which combines it with its own using a merge function. Convergence is guaranteed when merge is:

  • Commutative: merge(a, b) == merge(b, a): order of the two arguments does not matter.
  • Associative: merge(merge(a, b), c) == merge(a, merge(b, c)): grouping does not matter.
  • Idempotent: merge(a, a) == a: receiving the same state twice changes nothing.

Together, these make merge the join of a semilattice: states only move "upwards" in a partial order. That is why a network that duplicates, delays and reorders messages cannot break the result. (Operation-based CRDTs send operations instead of state and need reliable, exactly-once delivery; we stay with state-based here.)

Why merges converge

Commutative Order of arrival does not matter.
Associative Grouping of merges does not matter.
Idempotent Duplicates change nothing.

Lose, repeat or reorder messages, and replicas still converge.

1 / 2

G-Counter: a counter that only grows

A plain integer fails in replication: if two replicas both start at 5 and each adds 1, a "merge by max" gives 6, not 7. The G-Counter (grow-only counter) keeps one slot per replica. Each replica only ever increments its own slot. The value is the sum of all slots, and merge takes the maximum per slot.

Python G-Counter and the three merge laws

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because each slot is written by exactly one replica and only grows, taking the max never loses an increment and never double-counts one.

PN-Counter: increments and decrements

To support decrement, use two G-Counters: P counts increments and N counts decrements. The value is P - N, and merge merges each half. You cannot make a single G-Counter decrease, because the merge-by-max would ignore a smaller number.

G-Set and OR-Set

A G-Set (grow-only set) supports add and merges by union. It is perfect when you never delete, but the moment you want remove, a naive approach breaks: if replica A removes x while replica B concurrently re-adds x, what is the right answer?

The OR-Set (observed-remove set) gives a clear rule: an add wins over a concurrent remove. Every add creates a unique tag. A remove deletes only the tags the remover has observed. If another replica concurrently added the element with a fresh tag, that tag survives the merge, so the element stays.

Python PN-Counter and OR-Set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The merged set still contains apple: r1 removed only the tag it had observed, and r2's new tag was unknown to it. The cost of this design is tombstones: the removed set grows, so real systems add garbage collection once every replica has seen a removal.

LWW-Register

A register holds one value. The LWW-register stores (timestamp, replica_id, value) and merges by keeping the largest triple; the replica id breaks timestamp ties so the choice is deterministic. It satisfies all three laws, but it inherits LWW's weakness from the previous lesson: concurrent writes lose one, and clock skew can make the "winner" wrong. Use a multi-value register, which keeps concurrent values as siblings, when losing a write is not acceptable.

Testing convergence

Do not trust a merge function because it looks right: test the laws on many random states. The simulation below creates random OR-Set replicas, shuffles message delivery (including duplicates), and checks that all replicas converge to the same answer.

Python Random convergence test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This style, generating many random inputs and checking a law, is called property-based testing, and it is the best way to gain confidence in a merge function. We return to it in testing distributed systems.

Limits of CRDTs

CRDTs give you strong eventual consistency: replicas that have seen the same updates are in the same state. They do not give you constraints that need coordination. You cannot enforce "balance never below zero" with a PN-Counter, because two replicas may each approve a withdrawal. Metadata (tombstones, per-replica slots) also grows and needs care. Use CRDTs where merging is natural, and use consensus where you need a single agreed decision.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which three properties must a state-based CRDT's merge function have?

    These laws make the result independent of message order, grouping and duplication.
  2. 2. Why does a G-Counter keep one slot per replica instead of a single number?

    A single number cannot be merged correctly: two replicas that both add 1 would merge by max to a value that lost an update.
  3. 3. In an OR-Set, replica A removes an element while replica B concurrently adds it. What is the merged result?

    A remove only deletes the tags it has seen. The concurrent add carries a fresh tag, so the add wins.
  4. 4. Which requirement can a PN-Counter NOT enforce by itself?

    A non-negative invariant needs coordination, because independent replicas can each approve an action that is safe alone but unsafe together.

Summary

  • A CRDT has a built-in merge so replicas converge without coordination.
  • State-based merges must be commutative, associative and idempotent.
  • G-Counter: per-replica slots, merge by max. PN-Counter: two G-Counters. G-Set: union. OR-Set: unique tags, add wins over concurrent remove. LWW-register: keep the largest timestamp.
  • Test merge laws with random inputs.
  • CRDTs cannot enforce invariants that need coordination, and their metadata needs garbage collection.

Next: Partitioning and Sharding, splitting data across nodes.