CRDT counters

A conflict-free replicated data type (CRDT) is a data structure that replicas can change independently. When they exchange their state, they always converge, without a coordinator. Counters are the simplest place to see how. This page covers the merge rules and two counters.

The big idea

Say you count page views in three data centers. Each one takes increments locally. If replica A has 10 and replica B has 12, is the total 12, because B saw A's views? Or 22, because the views were separate? A single integer cannot tell you.

The fix is one slot per replica. Each replica increments only its own slot. The total is the sum of all slots. Merging takes the maximum of each slot.

A merge must follow three rules, so that messages can arrive late, out of order or twice:

• Commutative: merge(a, b) = merge(b, a).
• Associative: grouping does not matter.
• Idempotent: merge(a, a) = a. Receiving the same state twice changes nothing.

Walking through it

Two replicas, A and B, start empty. A increments 3 times. B increments 2 times. They have not talked yet.

A = {A:3, B:0}     value 3
B = {A:0, B:2}     value 2

A sends to B:  merge = {A:3, B:2}   value 5
B increments:  {A:3, B:3}           value 6
B sends to A:  merge = {A:3, B:3}   value 6, both converged
A's old state arrives at B again:   {A:3, B:3}, unchanged

Here is the counter in TypeScript, with a short check.

type GCounter = Record<string, number>

const increment = (c: GCounter, replica: string, by = 1): GCounter =>
  ({ ...c, [replica]: (c[replica] ?? 0) + by })

const value = (c: GCounter): number =>
  Object.values(c).reduce((sum, n) => sum + n, 0)

function merge(a: GCounter, b: GCounter): GCounter {
  const out: GCounter = { ...a }
  for (const [k, v] of Object.entries(b)) out[k] = Math.max(out[k] ?? 0, v)
  return out
}

const a = increment(increment(increment({}, "A"), "A"), "A") // 3 local increments
const b = increment(increment({}, "B"), "B")                  // 2 local increments
const merged = merge(a, b)
console.log(value(merged))            // 5
console.log(value(merge(merged, a)))  // 5, the duplicate changes nothing

Output:

5
5

A PN-counter handles decrements. It is two G-counters, one for increments and one for decrements. The value is the sum of the first minus the sum of the second. It can go negative, so it cannot enforce "never below zero" without coordination.

Common mistakes

• Merging by sum. A duplicate state would be counted twice. Use the maximum per slot.
• Expecting a PN-counter to stop inventory going negative. It cannot. A global floor needs coordination, such as a single owner per item.
• Confusing convergence with the right answer. The replicas agree, but the agreed value still has to be the one users expect.

Check yourself

1. Why take the maximum of each slot instead of the sum when merging? Each slot holds the newest known count for one replica. Taking the maximum keeps the newest view and ignores duplicates. A sum would count repeats twice.
2. Can a PN-counter guarantee a stock count never drops below zero? No. Replicas can each decrement without seeing the others, so the count can go negative.

Key takeaways

• A CRDT converges because its merge is commutative, associative and idempotent.
• A G-counter keeps one slot per replica and merges by maximum.
• Summing the slots gives the total.
• A PN-counter supports decrements, but it cannot enforce a lower bound alone.

Further learning

Next, see how CRDTs handle sets, where removes are harder, in OR-sets.

The CRDT papers and resources are collected at crdt.tech.

CRDT resources and papers (crdt.tech)Resources and community around CRDT technology — papers, blog posts, code and more.Conflict-free Replicated Data Types