Loading page…
Compare and merge vector clocks, keep concurrent writes as siblings instead of losing one, and let a write that saw both collapse them.
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.In JavaScript and TypeScript a clock is a plain object ({ A: 2, B: 1 }), Replica takes nodeId, tuples become arrays (get returns [values, context] and versions returns [[value, clock], ...]), and None is null (put(key, value, context = null)). Copy a clock with { ...clock }.
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.
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 the runtime restarts, your code stays.