Code lab · World 05 · Consistency and Coordination

Vector clocks with siblings.

Compare and merge vector clocks, keep concurrent writes as siblings instead of losing one, and let a write that saw both collapse them.

Medium~35 min3 example + 9 hidden tests+90 XPJump to the code ↓

Saving also stores the Python runtime (~13.5 MB, once for every lab) so this lab runs with no internet.

PractisesW05 · D43.2 Comparing Vector Clocks W05 · D43.3 Vector Clock Implementation W05 · D41.2 The Lost Update Problem

Two people edit the same shopping cart on two replicas during a partition. Last-write-wins keeps one cart and silently drops the other (Day 4, section 1.2). A Dynamo-style store does better: it tags every version with a vector clock, and when two versions are concurrent it keeps both as siblings until a later write, made by someone who saw both, replaces them (sections 3.1 to 3.3).

A clock is a plain dict from node id to counter, e.g. {"A": 2, "B": 1}. A node that is missing counts as 0, so {"A": 1} and {"A": 1, "B": 0} are the same clock.

Implement two functions and a class:

Name	Returns
`compare(a, b)`	`"before"` (a happened before b), `"after"`, `"equal"` or `"concurrent"`
`merge(a, b)`	a new clock with the larger counter for every node
`Replica(node_id)`	one replica of a key-value store
`replica.get(key)`	`(values, context)`: every sibling's value in the order stored, and the merge of their clocks. An unknown key gives `([], {})`
`replica.put(key, value, context=None)`	writes on this replica and returns the new version's clock
`replica.receive(key, value, clock)`	applies a version replicated from another node. `True` if it was kept, `False` if it was ignored
`replica.versions(key)`	`[(value, clock), ...]`: what this replica sends to its peers

Rules the tests check:

put builds its clock from the context the client read: copy it and add 1 to this replica's own entry. With no context (None), the base is the merge of every sibling this replica holds, so a blind write replaces them all (the lesson's "fresh write").
put and receive store a version the same way. If any sibling is "after" or "equal" to the new version, the new one is stale or a duplicate: ignore it. Otherwise drop every sibling that is "before" it, then append it. Concurrent siblings stay.
Never mutate a clock you were given, and don't let callers mutate yours: return copies.
Keys are independent.

Why siblings and not a winner

Picking a winner is easy and loses data. Keeping both versions pushes the decision to whoever knows how to merge them: for a cart, the union of items. Amazon's Dynamo paper describes exactly this: "the client must perform the reconciliation" of divergent versions on the next read.

Python 3.14 loads on first run (~6.5 MB once)14

Loading the editor…

⌘/Ctrl + Enternot run yet · 8 s limit

press Run tests

Write your code, then run 3 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and Python restarts, your code stays.