TASK
Implementation
Apply committed log entries to the state machine:
- Track lastApplied - highest entry applied to state machine
- When commitIndex > lastApplied, apply entries in order
- State machine executes each command
- Increment lastApplied after each application
The state machine must be deterministic - same commands produce same state.
Sample Test Cases
Apply entries in orderTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c0","dest":"n1","body":{"type":"seed_committed_log","msg_id":2,"entries":[{"index":1,"term":1,"command":{"op":"put","key":"x","value":1}},{"index":2,"term":1,"command":{"op":"put","key":"y","value":2}}],"commit_index":2}}
{"src":"c0","dest":"n1","body":{"type":"get_state","msg_id":3}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c0","body":{"type":"seed_committed_log_ok","in_reply_to":2,"msg_id":1}}
{"src":"n1","dest":"c0","body":{"type":"state_reply","in_reply_to":3,"msg_id":2,"state":{"x":1,"y":2},"last_applied":2}}
Hints
Hint 1▾
Apply entries in order
Hint 2▾
Track lastApplied index
Hint 3▾
State machine must be deterministic
OVERVIEW
Theoretical Hub
State Machine Replication
Raft replicates a log; the state machine interprets it. Each node applies the same commands in the same order, so all nodes converge to the same state. This is the foundation of replicated services.
Apply Order
Entries must be applied in index order. Gaps are not allowed - if entry 5 is committed but entry 4 is not, wait. In practice, commitment proceeds in order anyway.
Key Concepts
state machineapplydeterminism
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
#!/usr/bin/env python3
import sys
import json
import threading
class StateMachine:
def __init__(self):
self.state = {} # Key-value store
def apply(self, command):
# TODO: Execute command, return result
# Commands: {"op": "get", "key": "x"}
# {"op": "put", "key": "x", "value": 1}
pass
class ApplyLoop:
def __init__(self, log, state_machine):
self.log = log
self.sm = state_machine
self.last_applied = 0
self.pending_results = {} # index -> result
self.lock = threading.Lock()
def run(self):
# TODO: Continuously apply committed entries
pass
def apply_up_to(self, commit_index):
# TODO: Apply all entries from lastApplied+1 to commitIndex
pass
def get_result(self, index):
# TODO: Return result for applied index
pass