30-Second Glance
- Write path: client → leader appends to its log → AppendEntries fan-out → commit on majority ack → apply to state machine → reply.
- Committed writes are linearizable and survive leader crashes — safety comes from the majority commit rule.
- Log matching: same index + same term implies identical prefix everywhere; the leader backfills (overwrites from the first divergent index) to reconverge followers.
- Prefix is the shared head, suffix the missing/divergent tail (e.g. leader [A,B,C,D] vs follower [A,B] ships [C,D]).
- Liveness: missing heartbeats trigger re-election; lagging followers get backfilled rather than snapshotted from scratch.
Introduction
Once a leader is elected, it is responsible for handling all client write requests. Here’s how a typical write operation occurs:
Step-by-Step Process:
- Client Request: A client sends a write request to the leader.
- Appending to the Log: The leader appends the new entry (the client’s request) to its log. The log is a sequence of commands that modify the state of the system.
- Replication: The leader then sends an AppendEntries RPC to all followers to replicate the new log entry.
- Commitment: Once the leader receives acknowledgment from a majority of followers, it marks the entry as committed. The entry is then applied to the leader’s state machine, making the changes visible to the client.
- Response: The leader responds to the client, confirming that the write was successful.
Key Points:
- Linearizability: Writes are linearizable, meaning each write appears to happen instantaneously and will be visible to all subsequent operations.
- Safety: Once a log entry is committed, it will not be lost, even if the leader crashes.
Log Consistency in Raft
Raft ensures that the logs on all non-faulty servers are consistent, even in the presence of network partitions or server crashes.
Log Matching Property:
- If two logs contain an entry with the same index and term, then the logs are identical up to and including that entry.
- This property is crucial for maintaining consistency across all servers.
Log Backfilling:
When a leader finds that a follower’s log is missing entries or has conflicting entries (entries that don’t match the leader’s log at the same index and term), the leader will "backfill" the follower’s log. If a follower’s log diverges from the leader’s, the leader will overwrite the follower’s log starting from the first conflicting index to ensure consistency. This mechanism, often referred to as log backfilling, helps keep all logs in sync, ensuring that the system’s state remains consistent across all servers.
Prefix and Suffix:
- Prefix: The sequence of log entries that are shared between the leader and a follower up to a certain index.
- Suffix: The sequence of log entries that are not yet present on the follower or need to be overwritten. Example:
- Suppose the leader’s log is [A, B, C, D] and the follower’s log is [A, B]. Here, [A, B] is the prefix. The follower lacks [C, D], which forms the suffix. The leader will send [C, D] to the follower to backfill its log.
Log Commitment and Safety
- Commitment: An entry in the log is considered committed when the leader has replicated it to a majority(Quorums) of the servers.
- Consistency: Raft ensures that once an entry is committed, it will be present in the logs of future leaders. This prevents conflicting commands from being applied to the state machine, preserving the system’s consistency.
Handling Failures
Raft is designed to handle server failures gracefully:
- Leader Crash: If the leader crashes, followers will detect the absence of heartbeats and start a new election.
- Follower Lag: If a follower falls behind, the leader will bring it up to date using the backfilling mechanism.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Majority-commit before reply | Linearizable, durable writes | Pays a majority round-trip on every write | Correctness-critical state |
| Ack-after-leader-append (no quorum) | Minimal latency | Lost on leader crash; not linearizable | Volatile or best-effort data |
| Leader overwrite backfill | Simple convergence; no operator merge | Divergent uncommitted suffix data is discarded | Standard Raft follower repair |
| Read from leader / quorum-gated follower | Fresh reads | Leader load; extra coordination | Reads that must see committed writes |
Interview One-Liners
Q: Walk a Raft write end to end. A: Client sends to leader, leader appends to its log, replicates via AppendEntries, commits on majority ack, applies to its state machine, then replies.
Q: When is an entry committed? A: When the leader has it on a majority of servers (quorum) — only then is it applied and visible.
Q: State the log matching property. A: If two logs share an entry with the same index and term, they are identical up to and including that entry.
Q: How does backfilling repair a follower? A: The leader finds the first conflicting index and overwrites everything from there with its own suffix until the logs match.
Q: Prefix vs suffix in the note's example? A: Leader [A,B,C,D] vs follower [A,B]: [A,B] is the shared prefix, [C,D] the suffix the leader ships.
Q: What happens if the leader crashes mid-write? A: Followers miss heartbeats and elect a new leader; any majority-committed entry survives via leader completeness, uncommitted tails may be overwritten.