Log Replication with AppendEntries

One RPC, one consistency check

A client sends a command to the leader. The leader appends it to its own log as a new entry tagged with the current term and sends AppendEntries to all followers in parallel. Each AppendEntries carries prevLogIndex and prevLogTerm, the position and term of the entry just before the new ones. A follower rejects the RPC if it has no entry at prevLogIndex with that term. This simple check gives the Log Matching property: if two logs contain an entry with the same index and term, the logs are identical in all entries up to that index. When a follower rejects, the leader decrements that follower's nextIndex and retries (real implementations use a conflict hint to skip back a whole term at a time). Once they find the last matching entry, the follower deletes any conflicting entries after it and appends the leader's. Leaders never delete or overwrite their own log; logs flow in one direction only.

Replicating an entry

The leader appends an entry, sends AppendEntries with prevLogIndex and prevLogTerm, a majority acknowledges, and the leader advances its commit index and applies the entry.

A follower's AppendEntries handler

The follower holds an uncommitted entry from a crashed leader in term 2. The new leader's first attempt fails the consistency check; the second matches at index 2, truncates the stale entry and appends the new ones.

def append_entries(log, prev_index, prev_term, entries):
    """log is a list of (term, cmd); indexes start at 1. Returns success flag."""
    if prev_index > len(log):
        return False                                   # gap: follower is behind
    if prev_index > 0 and log[prev_index - 1][0] != prev_term:
        return False                                   # term mismatch at prev
    for i, entry in enumerate(entries):
        idx = prev_index + i                           # 0-based slot
        if idx < len(log) and log[idx][0] != entry[0]:
            del log[idx:]                              # conflict: truncate
        if idx >= len(log):
            log.append(entry)
    return True

follower = [(1, "x=1"), (1, "y=2"), (2, "x=9")]       # entry 3 is from a dead leader
print(append_entries(follower, 3, 3, [(3, "z=4")]))   # prev term 3 != 2 -> False
print(append_entries(follower, 2, 1, [(3, "x=5"), (3, "z=4")]))
print(follower)

Output:

False
True
[(1, 'x=1'), (1, 'y=2'), (3, 'x=5'), (3, 'z=4')]

Truncate only on conflict

A follower must not blindly truncate everything after prevLogIndex. A delayed, older AppendEntries could then erase entries the follower already acknowledged. Truncate only from the first entry whose term actually conflicts.

त्वरित जाँच: What does a Raft follower do when AppendEntries' prevLogIndex/prevLogTerm do not match its log?

• Accepts the entries and fixes the log later
• Rejects the request so the leader retries from an earlier index
• Starts an election because the leader is faulty
• Overwrites the leader's log with its own