The milk that came back
Ana and Ben share a shopping list. On the bus, Ana removes milk because she bought some. At the same time, Ben adds milk because the fridge looks empty.
When their phones sync, should milk be on the list? There is no single right answer, but every phone must give the same one.
By the end of this lesson
Note
I can merge two replicas of an observed-remove set.
Key words
| Word | What it means | Example |
|---|---|---|
| Register | a CRDT that holds one value | |
| Grow-only set | a set you can add to but never remove from | G-Set |
| Tag | a unique label given to one add | |
| OR-set | an observed-remove set: a remove deletes only the tags it saw | |
| Add wins | a concurrent add beats a remove |
The cells students fill in are left blank in this preview.
A register keeps the larger stamp
Lesson 1 met the last-writer-wins register. As a CRDT, its state is a value and a stamp of time and replica name. The merge keeps the pair with the larger stamp.
Taking the larger is a join, so registers always agree. But they agree by throwing a value away, which is fine for a colour and bad for a shopping list.
Three ways to share a set
Grow-only set: merge is union. Nothing can ever be removed. Two-phase set: an added set and a removed set, both unions. An item removed once can never come back. OR-set: every add gets a new tag. A remove deletes the tags it has seen. An item is in the set while it has a live tag.
Try it: a two-phase set
# A two-phase set: one set of adds, one set of removes.
# An item is in the set if it was added and never removed.
def members(state):
return sorted(state["added"] - state["removed"])
def merge(a, b):
return {"added": a["added"] | b["added"],
"removed": a["removed"] | b["removed"]}
ana = {"added": {"milk", "eggs"}, "removed": set()}
ben = {"added": {"milk", "eggs"}, "removed": set()}
ana["removed"].add("milk") # Ana removes milk, offline
ben["added"].add("milk") # Ben adds milk again, offline
both = merge(ana, ben)
print("after sync:", members(both))
both["added"].add("milk") # try adding milk once more
print("after another add:", members(both))
# Could anybody ever get milk back on this list?
Why the new add survives
Ana's remove can only delete the tags Ana has seen. Ben's add made a new tag that Ana never saw, so it is not removed.
After the merge, milk still has a live tag and stays on the list. This rule is called add wins. A remove made after seeing every tag does remove the item.
Keep the milk with an OR-set
docker exec jupyter python3 steps/orset.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Moment | Ana | Ben |
|---|---|---|
| Start | eggs, milk (tag ana:1) | eggs, milk (tag ana:1) |
| Offline | removes milk: ana:1 removed | adds milk: tag ben:1 |
| After sync | eggs, milk | eggs, milk |
| Ben removes milk, seeing ben:1 | eggs | eggs |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think a remove deletes the element, wherever it came from. In an OR-set a remove deletes only the tags its replica has seen. An add made elsewhere, at the same time, keeps its tag, so the element stays.
Sync three replicas after many edits
docker exec jupyter python3 steps/offline.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.