CRDT Visualization | G-Counter, PN-Counter and OR-Set Merges

The idea: write offline, merge later, agree for sure

Some systems must accept writes even when replicas can't talk to each other: a phone with no signal, two data centres cut apart, a collaborative editor on a train. Each replica changes its own copy. Later the copies meet and must end up equal, with no update lost and no coordinator to ask. A CRDT (conflict-free replicated data type) is a data type built so that this always works.

Three replicas R1, R2 and R3 each take updates while partitioned and end up with different states; after they exchange states and merge, all three hold the same state — While partitioned the replicas drift apart; once every state has reached every replica, they hold the same state.

The page shows the state-based kind (a CvRDT). A replica sends its whole state, and the receiver merges it into its own. The canvas has three replicas, R1, R2 and R3. Each takes updates alone. Press Send state to ship one replica's state to another. Under each replica, a naive version of the same type runs on the same operations, so you can see what goes wrong without a CRDT.

G-Counter: one slot per replica

Counting likes, page views or votes on three replicas looks easy, but a single integer can't be merged. If R1 counted 2 and R2 counted 3, is the total 3, 5 or something else? The integer doesn't say which increments the two counts share.

A G-Counter (grow-only counter) keeps one slot per replica. A replica only increments its own slot. Merging takes the maximum of each slot, and the value is the sum of the slots. Each slot has a single writer, so the larger number is always the newer one, and max never loses an increment.

R1's state [2,0,0] merged with R2's state [0,3,0] by max per slot gives [2,3,0] with value 5, which is correct; the naive counter takes max(2,3) = 3, which loses two increments — Max per slot keeps both replicas' increments (5); max of two plain integers keeps only one side (3).

Demo 1: offline increments, then merge: R1 counts 2, R2 counts 3 and R3 counts 1. After four sends every replica holds [2,3,1] = 6. The naive counter (one integer, merge = max) also ends up the same everywhere, but at 3: it converged on the wrong number.

Why any order works

A merge function is safe to use without coordination when it is:

commutative: merge(a, b) = merge(b, a), so it doesn't matter who sends first;
associative: merge(merge(a, b), c) = merge(a, merge(b, c)), so the grouping doesn't matter;
idempotent: merge(a, a) = a, so a state that arrives twice does no harm.

Max per slot and set union have all three. Replicas that have seen the same updates hold the same state, whatever order the messages came in. This is called strong eventual consistency. (Demo 2: different merge orders converge: R2 merges R1 then R3, R1 merges R3 then R2, and all end at [2,1,3]. Demo 3: duplicate merge is harmless: R2 gets R1's state twice and its value stays 3.)

merge rule	commutative	associative	idempotent	what goes wrong
max per slot (G-Counter)	✓	✓	✓	nothing
max of one integer	✓	✓	✓	loses the other side's increments
sum of two integers	✓	✓	✗	a resent state is counted twice
last write wins on the whole value	✓	✓	✓	throws away a concurrent update

PN-Counter: counting down too

A G-Counter can't go down. If R2 lowered its slot from 3 to 2, the next merge with a replica that still has 3 would bring 3 back. A PN-Counter uses two G-Counters: P counts increments and N counts decrements. Both only grow, both merge by max, and the value is ΣP − ΣN. (Demo 4: PN-Counter with a decrement: +2 at R1, −1 at R2 and +2 at R3 merge to 3 everywhere; the naive counter says 2.)

OR-Set: add wins

Sets are harder. Suppose R2 removes milk from a shopping cart while R1, unaware, adds milk again. Should the merged cart have milk? A plain set can't tell a new add from the old one.

The OR-Set (observed-remove set) gives every add a unique tag, here the replica name and a count (R1-1, R1-2). A remove marks as removed only the tags its replica has observed. An element is in the set while it has a tag that isn't marked removed. Merging is the union of the tags and the union of the removed tags. A concurrent add has a tag the remover never saw, so it survives: add wins.

Time flows down. R1 adds milk with tag R1-1 and sends its state to R2. R2 removes milk, marking R1-1 removed. At the same time R1 adds milk again with tag R1-2. After the states are exchanged, the OR-Set keeps milk because R1-2 is live, while the naive tombstone set has milk gone for ever — The remove only covers the tag R2 had seen (R1-1); the concurrent add's tag R1-2 is still live, so milk stays.

The naive set on the page is a tombstone set (a 2P-Set): a removed element goes into "gone for ever", and merge is union. It converges too, but the concurrent add is lost, and milk can never be added again. (Demo 5: OR-Set, concurrent add and remove.)

type	state	update	merge	value
G-Counter	one slot per replica	own slot + 1	max per slot	sum
PN-Counter	two G-Counters P and N	own slot of P or N + 1	max per slot	ΣP − ΣN
OR-Set	(element, tag) pairs + removed tags	add: new tag; remove: mark the seen tags	union of both	elements with a live tag

State-based, operation-based, and where they are used

A state-based CRDT can send its state over any channel, even one that loses, repeats or reorders messages. The cost is size: the whole state travels. An operation-based CRDT (a CmRDT) sends only the update ("+1 at R1", "add milk R1-2"), but needs a channel that delivers every operation exactly once and in causal order. Delta-state CRDTs send only the part of the state that changed and keep the forgiving merge.

CRDTs are used in Riak data types, Redis Enterprise active-active databases, Azure Cosmos DB multi-region writes, AntidoteDB, and in collaborative editing libraries such as Automerge and Yjs. They give up one thing: there is no global order, so they can't enforce invariants such as "stock never goes below zero". That still needs coordination (Raft, Paxos). See also Consistency Patterns (where last-write-wins loses a concurrent write), the CAP theorem (CRDTs are the AP side done right), Primary–Replica Replication, Lamport and vector clocks (the version vectors inside many CRDTs), gossip and Merkle anti-entropy (how states get spread in practice).

What the page leaves out

Real OR-Sets don't keep removed tags for ever: the optimized OR-Set (and Riak's ORSWOT) uses a version vector per replica to forget them. Other CRDTs: LWW-Register, MV-Register (keeps concurrent values as siblings), maps of CRDTs, and sequence CRDTs (RGA, Logoot, Yjs's YATA) for text editing. Delta-state CRDTs and garbage collection of old state. How states travel: the page sends one state at a time when you press a button; real systems gossip states periodically or on every change. Replicas joining and leaving, which changes the set of slots.