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
| Word | What it means |
|---|---|
| CRDT | a data type whose replicas always merge to the same state |
| State-based | replicas send their whole state and merge it |
| Join | a merge that is order free and safe to repeat |
| G-Counter | a counter that only goes up, one entry per replica |
| PN-Counter | two 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
docker exec jupyter python3 steps/gcounter.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Moment | Phone | Laptop | Tablet |
|---|---|---|---|
| Before sync | 3 | 5 | 2 |
| After sync, any order | 10 | 10 | 10 |
| Phone merges laptop twice more | 10 | 10 | 10 |
| A plain number with a repeated report | 19 | none | none |
The cells students fill in are left blank in this preview.
Try it: six orders, one total
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
docker exec jupyter python3 steps/pncounter.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.