TASK
Implementation
Implement the key-value store interface on top of Raft:
- GET(key) - Return current value or null
- PUT(key, value) - Set key to value
- CAS(key, expected, new) - Compare-and-swap
Each write operation:
- Leader receives request
- Append to Raft log
- Wait for commitment
- Apply to state machine
- Return result to client
Sample Test Cases
Put and get 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":"write","msg_id":2,"key":"x","value":1}}
{"src":"c1","dest":"n1","body":{"type":"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":"write_ok","in_reply_to":2,"msg_id":1}}
{"src":"n1","dest":"c1","body":{"type":"read_ok","in_reply_to":3,"msg_id":2,"value":1}}
Hints
Hint 1▾
Support get, put, cas operations
Hint 2▾
Each operation becomes a log entry
Hint 3▾
Wait for commit before responding
Resources
OVERVIEW
Theoretical Hub
Building on Consensus
Raft provides ordered, replicated log. We build a KV store by interpreting log entries as operations. All nodes apply the same operations in order, producing the same state.
Maelstrom KV Workloads
Maelstrom tests lin-kv (linearizable KV) and lww-kv (last-write-wins). Linearizable requires waiting for Raft commit. LWW can accept local writes immediately.
Key Concepts
key-valueAPIoperations
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
#!/usr/bin/env python3
import sys
import json
import threading
class KVStore:
def __init__(self, raft_node):
self.raft = raft_node
self.pending = {} # index -> (event, result)
self.lock = threading.Lock()
def get(self, key, timeout=5):
# TODO: For linearizable read, go through Raft
pass
def put(self, key, value, timeout=5):
# TODO: Submit to Raft, wait for commit
pass
def cas(self, key, expected, new, timeout=5):
# TODO: Compare-and-swap through Raft
pass
def _submit_and_wait(self, operation, timeout):
# TODO: Submit to Raft, wait for result
pass
def on_apply(self, index, operation, result):
# TODO: Called when Raft applies entry
pass