Raft

Raft replicates state machines: multiple nodes agree on a committed order of commands, then execute deterministic state transitions in that same order. It tolerates crashes, restarts, and network anomalies within the protocol's assumptions, but not arbitrary malicious nodes.

When learning, distinguish three facts: the log is stored on a node, the log is committed by the protocol, and the command is applied to the state machine. These moments usually differ. Raft guarantees that committed history will not be overwritten by a later legitimate leader, allowing uncommitted tails to diverge temporarily and be replaced upon recovery.

Terms and Roles: Freshness is Not Physical Time

A term is a monotonically increasing logical term number. A Follower enters the Candidate state after an election timeout, increments the term, and initiates a vote; upon receiving a majority of votes required by the configuration, it becomes the Leader. Random timeouts reduce the probability of simultaneous contention, do not guarantee a successful election in one attempt, and there is no fixed millisecond value applicable to all networks.

Upon receiving a protocol message with a higher term, a node updates its term and reverts to follower. An isolated old leader may not immediately receive this message and might still consider itself in office; safety relies on its inability to obtain the required quorum to complete a new legitimate commit, rather than all nodes immediately knowing who the leader is. Access to external resources also requires appropriate fencing and cannot rely solely on the role variable in the process.

State That Must Be Preserved

When persistent state changes, the persistence requirement must be met before the successful acknowledgment depending on that change; this does not mean every heartbeat without state change requires a separate fsync. If the state machine has already persisted the result, the corresponding command must not be blindly executed a second time during recovery.

Election: One Vote Per Person Is Not Enough

The candidate sends the (lastLogTerm, lastLogIndex) of its tail log. The voter, upon satisfying term and voting conditions, must also confirm that the candidate's log is at least as up-to-date as its own: first compare the term of the last log entry, and if terms are equal, compare the index. Looking only at log length is insufficient; a longer tail from an old term is not necessarily more qualified.

Each node votes for at most one candidate in the same term. Since two majorities intersect, it is impossible to have two leaders both receiving a legal majority in the same term. The retention of committed logs across terms requires log matching, election restrictions, and commit rules to prove together. You cannot directly equate "log update" with "necessarily containing any old entry."

Log Replication: Find the Common Prefix First

The Leader's AppendEntries carries the index and term of the previous log entry. The Follower only accepts subsequent entries after this prefix check passes; upon encountering a conflict with the same index but different term, it deletes the conflicting entry and its subsequent tail, then appends the new content.

After rejection, the leader adjusts nextIndex to re-find the common prefix; implementations can use conflict term information to accelerate rollback. Do not truncate the follower's log just because a shorter heartbeat was received: when there are no entry conflicts, the absence of a specific tail in the message is not a reason to delete it.

The log matching property states: if two logs have the same term at the same index, their preceding prefixes are consistent. This allows the leader to gradually establish a consistent log with short prefix checks, without comparing the entire history each time.

Why Empty Heartbeats Cannot Truncate the Tail

The following simulates only the log and commit position parts of AppendEntries, assuming the request term and leader identity have already passed protocol checks. Logs are represented as (term, command), with a sentinel at position 0; this does not implement election, persistence, or index conversion after snapshots.

def append_entries(log, committed, prev_index, prev_term, entries, leader_commit):
    if not 0 <= prev_index < len(log) or log[prev_index][0] != prev_term:
        return False, list(log), committed
    updated = list(log)
    for index, entry in enumerate(entries, start=prev_index + 1):
        if index < len(updated) and updated[index][0] != entry[0]:
            if index <= committed:
                raise ValueError("Legal Raft history cannot conflict with committed prefix")
            del updated[index:]
        if index == len(updated):
            updated.append(entry)
        elif updated[index] != entry:
            raise ValueError("Same index, same term, but different command, violating input assumptions")
    matched_end = prev_index + len(entries)
    new_commit = max(committed, min(leader_commit, matched_end))
    return True, updated, new_commit

log = [(0, "sentinel"), (1, "a"), (2, "b"), (2, "c"), (2, "d")]
ok, same, commit = append_entries(log, 1, 2, 2, [], 4)
assert ok and same == log and commit == 2
ok, fixed, commit = append_entries(log, 2, 2, 2, [(3, "new-c")], 3)
assert ok and fixed == log[:3] + [(3, "new-c")] and commit == 3
assert append_entries(fixed, 3, 2, 2, [(3, "new-c")], 3) == (True, fixed, 3)
assert append_entries(log, 2, 2, 99, [], 4) == (False, log, 2)

The first call only proves that the prefix at position 2 matches; you cannot delete entries 3 and 4 just because the message did not carry them, nor can you advance the commit to 4 just because the follower locally happens to have 3 and 4. The second call carries position 3, term 3, which truly conflicts with the local term 2, so it deletes the old tail from 3 onwards, then appends the new entry.

Repeating the second request will not append a second copy of the command. Implementations need to distinguish between "already existing matching entries," "new entries," and "conflicting entries"; you cannot unconditionally overwrite the local log with the entire suffix received. The above processing corresponds to Raft Figure 2's AppendEntries rules.

Commit: Why You Must Look at the Current Term

In a basic majority configuration, a leader can advance commitIndex to N, provided that: N is greater than the current commit position, at least a majority of nodes have matchIndex >= N, and log[N].term == currentTerm. Committing N simultaneously commits the log prefix preceding it.

Old term entries, even if temporarily present on a majority of nodes, cannot be declared committed solely based on the number of replicas currently seen. The reason is that voting prioritizes the tail term; another candidate with a higher term tail may still win subsequent elections in some executions and overwrite uncommitted entries. Majority replication of current term entries provides the additional condition required to safely advance the commit prefix.

A practical readable example: A new leader's current term is 7, inheriting an entry at index 40, term 6. It writes a no-op for term 7 at index 41 and safely commits it; index 40 is then committed along with the prefix. There is no need to replace the old command with a new term and re-execute it. For strict proofs and counterexamples, see Raft Paper Section 5.4 and Figure 8.

Majority Position Reached 40, But May Still Only Commit to 39

A five-node leader's current term is 7; log 40 belongs to term 6, and 41 is a no-op for term 7. It is committed up to 39. If the replication progress is [41,40,40,39,38], although 40 has three replicas, the current term condition is still not met; only after 41 also reaches the majority can it advance together with 40.

def advance_commit(committed, current_term, terms, matches):
    majority = len(matches) // 2 + 1
    eligible = [index for index, term in terms.items()
                if index > committed and term == current_term
                and sum(position >= index for position in matches) >= majority]
    return max([committed] + eligible)

terms = {39: 6, 40: 6, 41: 7}
assert advance_commit(39, 7, terms, [41, 40, 40, 39, 38]) == 39
assert advance_commit(39, 7, terms, [41, 41, 41, 39, 38]) == 41
assert advance_commit(41, 7, terms, [41, 41, 41, 39, 38]) == 41
assert (7, 10) > (6, 100)  # Election compares tail term first, not log length

Here, matches includes the leader itself and comes from the same fixed five-node configuration, with no missing nodes or treating duplicate ACKs as multiple replicas. If membership changes are in progress, you cannot continue to apply a fixed majority formula, but must use the quorum rules of the current configuration. This filtering function demonstrates the advancement condition and does not undertake a complete safety proof.

Why does majority replication not move commit?

Place replication evidence beside the commit condition to avoid treating replica count as a complete proof. Each slider selects an independent progress snapshot, recomputing from committed index 39; lowering it does not model loss of acknowledged durable logs. The separate apply action shows that a newly committed prefix still needs execution.

$$\#\{i:{\mathrm{matchIndex}}_i\ge n\}\ge 3\wedge \mathrm{term}(n)=7$$

Application and Client Retries

Nodes advance lastApplied in committed order. State machine execution must be deterministic: if random numbers, current time, or external query results affect the state, they should be incorporated into commands or consistent inputs via explicit protocols, rather than allowing each replica to freely take different values.

Even if the Raft log is safe, the client may still lose the response after the command has been committed, leading to a re-submission of the same business operation. Replicated state machines typically require request IDs and result deduplication. Raft itself does not automatically treat two duplicate business requests as the same command.

Linearizable Reads: Being the Leader Is Not Enough

An isolated old leader may possess stale state. For safe reading, it is necessary to confirm that the leader authority relied upon for this read is still valid, and wait for the state machine to apply to the corresponding safe commit position.

Quorum-based read methods usually contact a majority of nodes to establish a read barrier after the leader has confirmed the commit boundary of the current term, and then wait for the local lastApplied to reach the safe position. Lease-based reads can reduce some communication, but their correctness requires time and lease assumptions specified by the protocol. See Practical Systems for details.

Snapshots: Preserve State and Its Corresponding History Position

A snapshot records the state of an applied prefix, along with metadata such as lastIncludedIndex, lastIncludedTerm, and the configuration required for recovery. Only after the snapshot is reliably saved can the corresponding old logs be reclaimed according to the protocol.

If a lagging follower's required logs have been reclaimed, it can recover the prefix via InstallSnapshot and then catch up on subsequent logs. Installation must not allow a node to revert to a view older than the applied state; whether to retain subsequent logs also requires checking if the boundaries match. A snapshot is not an arbitrary copy of a changing data directory.

Membership Changes: The Definition of Quorum Also Changes

Directly splitting the old set into a new set may allow two disjoint majorities to act independently. Joint consensus requires the majority of the old set and the majority of the new set to be satisfied simultaneously, before transitioning to the new configuration. It is not combining the two sets of nodes and taking a majority of the total number.

Another class of implementations restricts changes to safe single-member steps and specifies when the configuration takes effect. Specific implementations may support different interfaces; you cannot skip their application order and recovery rules just because you see "single-node change." New replicas often start as non-voting learners to catch up, avoiding a new voting node with no data immediately raising the quorum threshold.

Joint Consensus Is Not Choosing Any Three Out of Five

Old configuration {A,B,C}, new configuration {C,D,E}. The old majority {A,B} and the new majority {D,E} can be completely disjoint, indicating that "each configuration using its own majority" is not enough. The joint phase requires a single decision to obtain confirmation from at least two nodes of the old configuration AND at least two nodes of the new configuration simultaneously.

from itertools import combinations
old, new = set("ABC"), set("CDE")

def majority(acks, members):
    return len(acks & members) >= len(members) // 2 + 1

def joint(acks):
    return majority(acks, old) and majority(acks, new)

assert majority(set("ABC"), old | new)  # Three out of five
assert not joint(set("ABC"))  # New config only has C, one ack is not enough
assert joint(set("ACD"))  # Old config A, C; New config C, D
assert not (set("AB") & set("DE"))
all_sets = [set(nodes) for size in range(6) for nodes in combinations("ABCDE", size)]
valid = [acks for acks in all_sets if joint(acks)]
assert all(a & b for a in valid for b in valid)

Acknowledgments from the shared node C can count for both sides, but acknowledgments for A and B from the old side cannot be treated as D and E from the new side. This rule affects availability: when the old group can form a majority but the new group cannot, the joint phase still cannot complete decisions requiring joint quorum. When configuration entries take effect and how to recover must follow the complete reconfiguration protocol; you cannot just replace a majority judgment function. Raft Membership Changes

Three out of five may still be insufficient

Joint consensus is the conjunction of two predicates, not a majority over the union. A,B,C provide three votes in total but only C in the new configuration; adding D satisfies both. Conversely, C,D,E lack an old-configuration vote. The static figure shows membership; the selectable acknowledgement set tests the boundary.

$$|A\cap C_{old}|\ge 2\wedge |A\cap C_{new}|\ge 2$$

Quick Reference: Several Non-Negotiable Restrictions

• Direct commit judgment based on majority persistence must satisfy the current term condition.
• Election compares the tail term of logs first, then the index.
• Leader identity alone cannot prove that local reads are fresh enough.
• Snapshots, deduplication state, and membership configurations are part of complete recovery.
• Safety can be maintained during communication anomalies, but continuous progress still requires a communicable quorum and appropriate timing conditions.

References

• In Search of an Understandable Consensus Algorithm.
• Raft Project and Paper Entry.

Keywords: Raft, term, election, log matching, commitIndex, ReadIndex, snapshot, joint consensus