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

Free lesson

Registers and sets: what add wins means

After this lesson: I can merge two replicas of an observed-remove set.

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

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

WordWhat it meansExample
Registera CRDT that holds one value
Grow-only seta set you can add to but never remove fromG-Set
Taga unique label given to one add
OR-setan observed-remove set: a remove deletes only the tags it saw
Add winsa 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

Code: python
# 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

Command
docker exec jupyter python3 steps/orset.py

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

Worked example: what the lab printed

MomentAnaBen
Starteggs, milk (tag ana:1)eggs, milk (tag ana:1)
Offlineremoves milk: ana:1 removedadds milk: tag ben:1
After synceggs, milkeggs, milk
Ben removes milk, seeing ben:1eggseggs

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

Command
docker exec jupyter python3 steps/offline.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.