Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Counters that merge: G-Counter and PN-Counter

After this lesson: I can merge two counter replicas so that every replica gets the same total.

60 min lesson2 commandsCRDT lab: local-first sync with counters, sets, vector clocks and text in Python

Counting likes on three phones

A post gets likes from people on three phones, and each phone is offline for a while. When they sync, the total should count every like once. It should not miss any, and it should not count any twice.

A shared number cannot do that alone. A CRDT counter can.

By the end of this lesson

Note

I can merge two counter replicas so that every replica gets the same total.

Key words

WordWhat it means
CRDTa data type whose replicas always merge to the same state
State-basedreplicas send their whole state and merge it
Joina merge that is order free and safe to repeat
G-Countera counter that only goes up, one entry per replica
PN-Countertwo G-Counters, one for ups and one for downs

The cells students fill in are left blank in this preview.

A merge that cannot go wrong

A state-based CRDT sends its whole state, and the other replica merges it. The merge must be a join, with three properties:

Commutative: a merged with b equals b merged with a. Associative: three merges give the same result in any grouping. Idempotent: merging the same state twice changes nothing.

Then a message can arrive late, twice or out of order, and replicas still agree.

A G-Counter keeps one number per replica

Each replica only adds to its own entry. The value is the sum of all entries.

To merge, take the larger number for each replica. Taking the larger of two numbers is commutative, associative and idempotent, so the whole merge is a join. Adding instead of taking the larger is not idempotent.

Merge three G-Counters in two orders

Command
docker exec jupyter python3 steps/gcounter.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Worked example: what the lab printed

MomentPhoneLaptopTablet
Before sync352
After sync, any order101010
Phone merges laptop twice more101010
A plain number with a repeated report19nonenone

The cells students fill in are left blank in this preview.

Try it: six orders, one total

Code: python
from itertools import permutations

def merge(a, b):
    out = dict(a)
    for name, count in b.items():
        out[name] = max(out.get(name, 0), count)
    return out

# Steps counted by three phones, offline
ana = {"ana": 4}
ben = {"ben": 7}
cai = {"cai": 2, "ana": 1}   # cai heard from ana earlier

for order in permutations([ana, ben, cai]):
    state = {}
    for replica in order:
        state = merge(state, replica)
    print(sum(state.values()), state)
# Every order gives the same total. Change merge to add instead of max.

A common mistake

Warning

Many people think a merge should add the two counters together. That counts a state twice when it arrives twice, which networks do. Take the larger number for each replica instead, so repeating a merge is harmless.

Going down needs a second counter

A G-Counter cannot go down, because a smaller number would lose every merge. So a PN-Counter keeps two G-Counters: one counts ups and one counts downs.

Each merges by taking the larger number per replica. The value is the ups minus the downs.

Merge likes and unlikes

Command
docker exec jupyter python3 steps/pncounter.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

About this lab and its source: CRDT lab: local-first sync with counters, sets, vector clocks and text in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.