A reply that arrives before the question
In a group chat, a reply sometimes shows up before the message it answers. The network delivered them in the wrong order.
Replicas have the same problem. To merge well, a replica needs to know which change came first, and which two changes nobody ordered.
By the end of this lesson
Note
I can compare two vector clocks and say which change happened first.
Key words
| Word | What it means | Example |
|---|---|---|
| Happened before | one change was known when the other was made | |
| Vector clock | one counter per replica, carried with every change | {"a": 1, "b": 2} |
| Op-based CRDT | replicas send operations instead of whole states | |
| Causal delivery | a change is applied only after the changes it saw | |
| Delta | only the part of a state that changed |
The cells students fill in are left blank in this preview.
A vector clock counts each replica
Each replica keeps a counter for every replica. Before a change, it adds one to its own counter. When it hears from another replica, it takes the larger of each counter.
Compare two clocks place by place. If every place in a is at most b's, and one is smaller, a happened before b. If each is larger somewhere, they are concurrent.
Compare vector clocks
docker exec jupyter python3 steps/clocks.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Clocks | Compared | Why |
|---|---|---|
| a {a: 1} and b {b: 1} | concurrent | each is larger in one place |
| a {a: 1} and b {a: 1, b: 2} | a before b | b heard a, then wrote |
| c {a: 1, b: 2, c: 1} and a | c after a | c heard b, who heard a |
| a and a copy of a | equal | every place the same |
The cells students fill in are left blank in this preview.
Sending operations instead of states
A state-based CRDT sends its whole state, which can be large. An op-based CRDT sends each operation, such as "add milk", which is small.
But operations must each arrive exactly once, and a change must arrive after the changes it saw. Otherwise a remove can arrive before the add it was removing.
Try it: two operations, swapped
# Op-based: replicas send operations, not whole states.
# Ana adds milk, then removes it. Cai receives both operations.
def apply(items, op):
kind, item = op
if kind == "add":
return items | {item}
return items - {item}
first = ("add", "milk")
second = ("remove", "milk")
in_order = apply(apply(set(), first), second)
swapped = apply(apply(set(), second), first)
print("arrive in order:", sorted(in_order))
print("arrive swapped: ", sorted(swapped))
# The network swapped two messages. What should Cai have done
# with the remove when it arrived first?
A common mistake
Warning
Many people think a timestamp is enough to order changes. Two clocks on two devices disagree, and a time cannot say that two changes were concurrent. A vector clock can, because it records what each replica had heard.
Deltas: the best of both
A delta-state CRDT sends only the part of its state that changed since the other replica last heard. It merges with the same join as a whole state.
So a lost or repeated delta is harmless, like a state, while the message stays small, like an operation. A vector clock says what the other replica already has.
Send a delta instead of the whole state
docker exec jupyter python3 steps/delta.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.