Raft Consensus: Log Replication & Commit Index
In Raft, client writes pass exclusively through the Leader. The Leader appends the entry to its write-ahead log (WAL) and broadcasts `AppendEntries` RPCs. The entry becomes permanently committed only once safely replicated across a cluster majority ππ‘οΈ.
class RaftLogNode:
def __init__(self, node_id):
self.node_id = node_id
self.log = []
self.commit_index = -1
def append_entries(self, entries):
self.log.extend(entries)
return True
def leader_replicate(leader_log, followers, entry, cluster_size):
leader_log.append(entry)
acks = 1 # Leader self-ack
for follower in followers:
if follower.append_entries([entry]):
acks += 1
majority = (cluster_size // 2) + 1
is_committed = acks >= majority
return is_committed
f1 = RaftLogNode("Follower_1")
f2 = RaftLogNode("Follower_2")
leader_log = []
committed = leader_replicate(leader_log, [f1, f2], {"term": 1, "cmd": "SET k=1"}, cluster_size=3)
print(f"Entry committed to cluster state machine: {committed} π")
# 41. Raft Consensus: Log Replication & Commit Index Once a leader is crowned, all state changes flow strictly downstream. Followers never accept writes directly from clientsβthey redirect callers to the leader π. ```python # The Log Replication Flow: # 1. Client sends "SET key=val" to Leader. # 2. Leader appends command to local log (uncommitted). # 3. Leader sends AppendEntries RPC to Followers. # 4. Followers append to local log and respond ACK. # 5. Leader receives majority ACKs -> entry is COMMITTED. # 6. Leader applies entry to state machine and responds to Client. ``` ### The Log Matching Invariant 1. **Identical Index & Term**: If two entries in different logs have the same index and term, they store the identical command. 2. **Log Continuity**: If two entries in different logs have the same index and term, then their logs are identical in all preceding entries. 3. **Safety Guarantee**: The leader never overwrites or truncates its own log entries; it only appends new ones. Divergent followers are forced to overwrite conflicting entries to match the leader's log ππ‘οΈ. --- ### Interactive Pop-Quiz π§ #### When does a Raft Leader officially consider a log entry committed and apply it to its state machine? - [ ] When the entry has been replicated onto a strict majority of cluster nodes π - [ ] Immediately upon receiving the TCP payload from the client socket - [ ] Only when every single node in the cluster responds with an HTTP 200 OK - [ ] When the local disk cache flushes after a 60-second idle period --- ### Practical Challenge π― Implement a function `try_commit(leader_log, followers, entry, cluster_size)` where each follower has `append(entry)`. The leader appends to `leader_log` and calls `append(entry)` on followers. A follower with `f.alive = False` fails to append. In a 3-node cluster with 1 alive follower and 1 dead follower, verify `try_commit` succeeds (2 out of 3 = majority), advances `commit_index` to 0, and prints `'COMMITTED'`. <details> <summary>Solution</summary> ```python class Follower: def __init__(self, alive=True): self.alive = alive self.log = [] def append(self, entry): if not self.alive: return False self.log.append(entry) return True def try_commit(leader_log, followers, entry, cluster_size): leader_log.append(entry) count = 1 for f in followers: if f.append(entry): count += 1 majority = (cluster_size // 2) + 1 return count >= majority leader_log = [] f_alive = Follower(alive=True) f_dead = Follower(alive=False) entry = {"term": 1, "idx": 0, "op": "INSERT"} if try_commit(leader_log, [f_alive, f_dead], entry, cluster_size=3): commit_index = 0 print("COMMITTED") ``` </details>