Design a Distributed Consensus System (Raft / Paxos)

Raft Leader Election

Normal operation:
  - Leader sends heartbeats (empty AppendEntries) every 100ms
  - Followers reset election timer on heartbeat receipt

Leader failure:
  1. Follower's election timer expires (random: 150-300ms)
  2. Follower increments term, transitions to CANDIDATE
  3. Votes for self, sends RequestVote to all peers
  4. Includes: candidate's term, last log index, last log term
  5. Other nodes vote YES if: candidate's term >= voter's term, voter hasn't voted,
     candidate's log is at least as up-to-date
  6. If candidate gets majority → becomes LEADER
  7. If another leader discovered (higher term) → revert to FOLLOWER

Log Replication

1. Client sends write request to leader
2. Leader appends entry to local log: {term, index, command}
3. Leader sends AppendEntries RPC to all followers
4. Follower checks log consistency at prev_log_index + prev_log_term
5. If mismatch → follower rejects; leader backtracks until logs match
6. When majority reply success → leader commits entry, applies to state machine
7. Commit index propagated to followers in next heartbeat

Raft State Machine (Follower → Candidate → Leader)

Walk through the three states and the safety invariant: committed entries must appear in all future leader logs.

FOLLOWER: Accept AppendEntries from leader; reset election timer on heartbeat.
CANDIDATE: On election timeout → increment term, vote for self, RequestVote RPC.
LEADER: Send heartbeats; replicate client writes via AppendEntries; commit when majority ack.

Safety invariant: if entry committed in term T, it appears in logs of all future leaders.

Log Matching & Consistency Check

AppendEntries carries prev_log_index + prev_log_term.
Follower rejects if its log doesn't match at that index, forcing the leader to decrement until logs align.
This overwrites conflicting uncommitted entries on minority partitions after heal.

Snapshotting & Log Compaction

Snapshotting prevents unbounded log growth on disk and accelerates restart recovery, linking to Write-Ahead Logging (WAL) and Data Durability.

Without snapshots: log grows unbounded → replay on restart takes minutes.
InstallSnapshot RPC: leader sends compressed state machine snapshot + last included index/term.
Follower discards log prefix before snapshot index. Trade-off: snapshot frequency vs replay time.

Kafka KRaft (Raft in Production)

Kafka KRaft Controller Log (Raft in Production: NOT a generic event bus)

Kafka metadata quorum (KRaft mode, since Kafka 3.3):
  - 3-5 controller nodes run Raft consensus on metadata log
  - Leader replicates: topic configs, partition assignments, broker registrations
  - Commit rule: metadata entry committed when majority of controllers acknowledge
  - Replaces ZooKeeper (which used ZAB ≈ Paxos)

Partition leader election (per topic partition):
  - Each partition has one leader broker + ISR (in-sync replicas)
  - Leader replicates log entries to followers via Fetch requests
  - Unclean leader election disabled for durability (min.insync.replicas=2)

Compared to application-level Raft (etcd, Consul):
  - KRaft: optimized for high-throughput append-only logs (millions msg/sec)
  - etcd Raft: optimized for small KV config stores (thousands ops/sec)
  - Both: single leader per term, majority quorum, linearizable writes

This problem designs consensus primitives; Kafka is an example consumer of Raft, not a user-facing event bus here