# Log Replication with AppendEntries — Distributed Systems & Consensus (Raft / Paxos)

Source: https://www.skillbyai.com/en/distributed-consensus/dc-raft-append

> Explain the Log Matching property and how a leader repairs a follower's divergent log.

## 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.

![Four stages: leader appends locally, AppendEntries to followers, majority acknowledgement, commit and apply.](assets/figures/distributed-consensus/section-7-map.svg) — Figure 7.1: leader append -> AppendEntries -> majority ack -> commit and apply

## 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.

```python
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.

**Quiz:** What does a Raft follower do when AppendEntries' prevLogIndex/prevLogTerm do not match its log?

- [ ] Accepts the entries and fixes the log later
- [x] 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

*Answer:* Rejects the request so the leader retries from an earlier index. A mismatch means the logs diverge at or before that index. The follower rejects, and the leader backs nextIndex up until it finds the last matching entry.