Build a Conflict-Detecting Key-Value Store - The Timekeeper

                      TASK
                    

Implementation

Use vector clocks to detect write-write conflicts in a key-value store. When two nodes write to the same key concurrently (neither write causally depends on the other), the store keeps both values as siblings (like Amazon DynamoDB).

Conflict rules:

If write's VC dominates stored VC: simple overwrite
If stored VC dominates write's VC: reject (stale write)
If neither dominates (concurrent): store both as siblings

Implement handlers:

Request:  {"type": "kv_put", "msg_id": 1, "key": "user:1", "value": "Alice", "clock": [1, 0]}
Response: {"type": "kv_put_ok", "in_reply_to": 1, "status": "written"}

Request:  {"type": "kv_put", "msg_id": 2, "key": "user:1", "value": "Bob", "clock": [0, 1]}
Response: {"type": "kv_put_ok", "in_reply_to": 2, "status": "conflict", "siblings": 2}

Request:  {"type": "kv_get", "msg_id": 3, "key": "user:1"}
Response: {"type": "kv_get_ok", "in_reply_to": 3, "values": [
    {"value": "Alice", "clock": [1, 0]},
    {"value": "Bob", "clock": [0, 1]}
]}

Request:  {"type": "kv_resolve", "msg_id": 4, "key": "user:1", "value": "Alice+Bob", "clock": [1, 1]}
Response: {"type": "kv_resolve_ok", "in_reply_to": 4, "status": "resolved"}

Sample Test Cases

Simple write to empty keyTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"kv_put","msg_id":2,"key":"x","value":"hello","clock":[1,0]}}
{"src":"c1","dest":"n1","body":{"type":"kv_get","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": "kv_put_ok", "in_reply_to": 2, "status": "written", "msg_id": 1}}

Concurrent writes create siblingsTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"kv_put","msg_id":2,"key":"x","value":"v1","clock":[1,0]}}
{"src":"c1","dest":"n1","body":{"type":"kv_put","msg_id":3,"key":"x","value":"v2","clock":[0,1]}}
{"src":"c1","dest":"n1","body":{"type":"kv_get","msg_id":4,"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": "kv_put_ok", "in_reply_to": 2, "status": "written", "msg_id": 1}}

Hints

Hint 1▾

Each key stores a value along with its vector clock

Hint 2▾

On write, compare the incoming vector clock with the stored one

Hint 3▾

If the incoming clock dominates the stored clock, overwrite (no conflict)

Hint 4▾

If neither dominates, store both values as siblings (write-write conflict)

Hint 5▾

On read, return all sibling values so the client can resolve the conflict

Resources

Dynamo: Amazon Highly Available Key-Value Store

The original Dynamo paper describing vector clock conflict detection

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

conflict detectionwrite-write conflictmulti-value registerDynamoDB style

main.py

python