The Raft Consensus Algorithm: Log Replication and Safety

Once a Leader is elected in Raft, it begins accepting write requests from clients and replicating them across the cluster.

To maintain absolute consensus, Raft enforces strict log invariants that guarantee replicated logs never diverge or corrupt historical committed data.

---

1. Structure of the Raft Replicated Log

Every log entry consists of three components:

1. Index: A monotonic integer indicating the entry's position in the log ($1,2,3,\dots$).
2. Term: The leader's term number when the entry was created.
3. Command: The deterministic state machine instruction (e.g. SET balance = 100).

---

2. The AppendEntries RPC Protocol

The leader coordinates log replication using the AppendEntries RPC:

---

3. The Log Matching Invariant & Consistency Check

Raft maintains the Log Matching Property:

$\text{If two logs contain an entry with the same index and term, they are identical in all entries up through that index.}$

The Follower Consistency Check:

When a follower receives an AppendEntries RPC:

1. It checks its local log at position prevLogIndex.
2. If the follower has no entry at prevLogIndex, or the term does not match prevLogTerm: It rejects the RPC (success: false).
3. If the terms match: The follower appends the new entries, overwriting any conflicting uncommitted entries in its local log.

---

4. The Leader Completeness Property

How does Raft guarantee that a newly elected leader will never overwrite previously committed log entries?

The Leader Completeness Property states:

$\text{If a log entry is committed in a given term, that entry will be present in the logs of the leaders for all higher terms.}$

The Election Restriction:

When a candidate requests votes, it includes its last log index and term in the RequestVote RPC:

• A voter denies its vote if its own log is more up-to-date than the candidate's log:
  1. If logs have different terms in their last entries, the log with the higher term is more up-to-date.
  2. If logs end with the same term, the longer log (higher index) is more up-to-date.

Because a committed entry exists on a majority of nodes, any candidate that wins an election must have received a vote from at least one node containing all committed entries.

---

5. The Critical Safety Nuance: Committing Entries from Prior Terms

A subtle edge case discovered by Ongaro & Ousterhout (Section 5.4.2 of the Raft paper):

A leader cannot determine that an entry from a PREVIOUS term is committed just because it is stored on a majority of nodes.

The Invariant:

• To commit past entries safely, a Raft leader must append and replicate at least one entry from its current term to a majority quorum. Once a current-term entry is committed, all prior entries are committed by induction.

---

6. Code Deep-Dive: Log Replication & AppendEntries Handler

---

7. Chapter Summary & Log Replication Invariants