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

Free lesson

Vector clocks, operations and deltas

After this lesson: I can compare two vector clocks and say which change happened first.

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

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

WordWhat it meansExample
Happened beforeone change was known when the other was made
Vector clockone counter per replica, carried with every change{"a": 1, "b": 2}
Op-based CRDTreplicas send operations instead of whole states
Causal deliverya change is applied only after the changes it saw
Deltaonly 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

Command
docker exec jupyter python3 steps/clocks.py

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

Worked example: what the lab printed

ClocksComparedWhy
a {a: 1} and b {b: 1}concurrenteach is larger in one place
a {a: 1} and b {a: 1, b: 2}a before bb heard a, then wrote
c {a: 1, b: 2, c: 1} and ac after ac heard b, who heard a
a and a copy of aequalevery 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

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

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