TASK
Implementation
In databases like Riak, vector clocks detect write conflicts. When two clients write to the same key concurrently (neither saw the other's write), the database stores both values as siblings instead of silently losing one.
Implement a key-value store with vector clock-based conflict detection:
Write: {"type": "vc_write", "msg_id": 1, "key": "x", "value": "a", "context": {"n1": 0}}
Read: {"type": "vc_read", "msg_id": 2, "key": "x"}Read response with single value:
{"type": "vc_read_ok", "values": [{"value": "a", "vc": {"n1": 1}}], "siblings": 1}Read response after concurrent writes (conflict):
{"type": "vc_read_ok", "values": [
{"value": "a", "vc": {"n1": 1}},
{"value": "b", "vc": {"n2": 1}}
], "siblings": 2}Sample Test Cases
Write and read a single 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":"vc_write","msg_id":2,"key":"x","value":"hello","context":{}}}
{"src":"c1","dest":"n1","body":{"type":"vc_read","msg_id":3,"key":"x"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "vc_write_ok", "key": "x", "vc": {"c1": 1}, "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "vc_read_ok", "values": [{"value": "hello", "vc": {"c1": 1}}], "siblings": 1, "in_reply_to": 3, "msg_id": 2}}
Read nonexistent key returns emptyTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"vc_read","msg_id":2,"key":"missing"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "vc_read_ok", "values": [], "siblings": 0, "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
Each key stores a value paired with the vector clock at write time
Hint 2▾
On write, the client provides the vector clock it read (context)
Hint 3▾
If the write VC dominates the stored VC, it is a simple update
Hint 4▾
If the VCs are concurrent, store both values as siblings
Hint 5▾
A read returns all sibling values and their VCs
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
conflict detectionkey-value storesibling valueslast-writer-wins
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
def vc_dominates(a, b):
keys = set(list(a.keys()) + list(b.keys()))
all_gte = all(a.get(k, 0) >= b.get(k, 0) for k in keys)
any_gt = any(a.get(k, 0) > b.get(k, 0) for k in keys)
return all_gte and any_gt
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.store = {} # key -> list of {value, vc}
def send(self, dest, body):
body["msg_id"] = self.next_msg_id
self.next_msg_id += 1
msg = {"src": self.node_id, "dest": dest, "body": body}
print(json.dumps(msg), flush=True)
def reply(self, request, body):
body["in_reply_to"] = request["body"]["msg_id"]
self.send(request["src"], body)
def vc_write(self, key, value, context, writer):
# TODO: Write value with conflict detection
pass
def vc_read(self, key):
# TODO: Read all sibling values for key
pass
def main():
node = Node()
for line in sys.stdin:
line = line.strip()
if not line: