Log Consistency and the Matching Property
What you'll learn: How Raft guarantees that matching log entries at the same index across servers imply all preceding entries also match—a critical safety property.
The Core Idea
In Raft's replicated state machine, each server maintains a log of commands. The log matching property ensures consistency across servers with a simple guarantee:
If two logs contain an entry with the same index and term, then:
- The entries store the same command
- All preceding entries in both logs are identical
This property emerges from how AppendEntries works: the leader includes the index and term of the entry immediately preceding the new entries. If a follower doesn't have a matching entry at that position, it rejects the append request.
Why This Matters
Think of it like a blockchain or Jenga tower: if block #100 matches between two chains, you can trust blocks #1-99 also match. You don't need to verify every single entry—checking one point guarantees everything below it.
When a leader sends AppendEntries, it's performing an inductive consistency check:
- Base case: Empty logs trivially match
- Inductive step: If entry at index i-1 matches (same term), and we append the same entry at index i, then entries 0 through i match
How It Works
The leader includes prevLogIndex and prevLogTerm in every AppendEntries RPC. A follower only accepts new entries if its log has an entry at prevLogIndex with term prevLogTerm. This creates a chain of verified consistency backward through the log.
If a follower's log diverged (perhaps it was offline), it will reject the append, and the leader will retry with earlier entries until they find the point of agreement.
Key Takeaway: Raft's log matching property guarantees that identical entries at any index imply all preceding entries match, enabling efficient consistency verification through a simple backward-chaining check in AppendEntries.