Implement Dotted Version Vectors - The Timekeeper

                      TASK
                    

Implementation

Standard vector clocks have an O(N) storage cost that grows with every node that ever participated. Dotted version vectors (DVVs), used in Riak, solve this by separating the causal context from the event dot.

A DVV has two parts:

dot: (node_id, counter) — the single event this value represents
version_vector: the causal context (everything that happened before the dot)

Implement a DVV-based versioning system:

Request:  {"type": "dvv_update", "msg_id": 1, "key": "x", "value": "hello", "context": {}}
Response: {"type": "dvv_update_ok", "in_reply_to": 1, "dot": ["n1", 1], "version_vector": {}}

Request:  {"type": "dvv_update", "msg_id": 2, "key": "x", "value": "world", "context": {"n1": 1}}
Response: {"type": "dvv_update_ok", "in_reply_to": 2, "dot": ["n1", 2], "version_vector": {"n1": 1}}

Request:  {"type": "dvv_get", "msg_id": 3, "key": "x"}
Response: {"type": "dvv_get_ok", "in_reply_to": 3, "values": [{"value": "world", "dot": ["n1", 2]}], "context": {"n1": 2}}

Sample Test Cases

First write creates a dotTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"dvv_update","msg_id":2,"key":"x","value":"hello","context":{}}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "dvv_update_ok", "in_reply_to": 2, "dot": ["n1", 1], "version_vector": {}, "msg_id": 1}}

Sequential update with context supersedes old valueTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"dvv_update","msg_id":2,"key":"x","value":"v1","context":{}}}
{"src":"c1","dest":"n1","body":{"type":"dvv_update","msg_id":3,"key":"x","value":"v2","context":{"n1":1}}}
{"src":"c1","dest":"n1","body":{"type":"dvv_get","msg_id":4,"key":"x"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

Standard vector clocks grow linearly with the number of nodes that ever participated

Hint 2▾

Dotted version vectors separate the causal context (version vector) from the event dot

Hint 3▾

A dot is a (node_id, counter) pair representing a single event

Hint 4▾

The version vector represents everything that happened before the dot

Hint 5▾

This allows pruning of old entries while preserving correctness

Resources

Dotted Version Vectors - Riak Core Concepts

How Riak replaced vector clocks with dotted version vectors for efficiency

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

dotted version vectorsspace optimizationversion vectorsRiak

main.py

python