TASK
Implementation
Implement Raft log replication from leader to followers:
- Leader receives client commands, appends to local log
- Leader sends AppendEntries to all followers
- AppendEntries includes: prevLogIndex, prevLogTerm, entries[]
- Follower checks if log matches at prevLogIndex
- If match, append entries; if not, reject
Track nextIndex and matchIndex per follower to manage replication progress.
Sample Test Cases
Leader appends entry to logTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c1","dest":"n1","body":{"type":"raft_append","msg_id":2,"entry":{"term":1,"command":{"op":"put","key":"x","value":1}}}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c1","body":{"type":"raft_append_ok","in_reply_to":2,"msg_id":1,"index":1}}
Hints
Hint 1▾
Leader maintains log and nextIndex per follower
Hint 2▾
AppendEntries carries log entries
Hint 3▾
Followers append if log matches
OVERVIEW
Theoretical Hub
The Replicated Log
Raft replicates a log of commands. Each entry has an index and term. The leader appends entries and replicates them. Once a majority have an entry, it is committed and can be applied.
Log Matching Property
If two logs have an entry with the same index and term, they are identical up to that index. This is guaranteed by: (1) a leader creates at most one entry per index, and (2) AppendEntries consistency check.
Key Concepts
logreplicationAppendEntries
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
#!/usr/bin/env python3
import sys
import json
import threading
class LogEntry:
def __init__(self, term, command, index):
self.term = term
self.command = command
self.index = index
class RaftLog:
def __init__(self):
self.entries = [] # 1-indexed conceptually
self.commit_index = 0
self.last_applied = 0
def append(self, entry):
self.entries.append(entry)
def get_last_index(self):
return len(self.entries)
def get_last_term(self):
if not self.entries:
return 0
return self.entries[-1].term
def get_entry(self, index):
if index < 1 or index > len(self.entries):
return None
return self.entries[index - 1]
class Leader:
def __init__(self, node_id, peers, log):
self.node_id = node_id