The Raft Consensus Algorithm: Leader Election, Quorums, and Replicated State Machines

1. The Core Engineering Challenge: Linearizability Under Crash Faults

Project Identity, Version & License Baseline

In a single-node database, guaranteeing linearizable consistency is straightforward: incoming write requests queue behind a mutex, update an in-memory B-Tree or Write-Ahead Log (WAL), flush to an NVMe drive, and return success. The database engine provides a single, unambiguous timeline of reality.

However, a single physical server is a Single Point of Failure (SPOF). Power supplies blow capacitors, kernel upgrades trigger panic loops, top-of-rack switches drop packets, and cosmic rays induce bit flips.

To survive hardware failure, we replicate data across multiple physical machines. But replication introduces the defining problem of distributed computing:

The Distributed Split-Brain Nightmare:
---------------------------------------------------------------------------------
            +-------------------------------------------+
            |         Client A: "set balance = $500"    |
            +-------------------------------------------+
                                  |
                   [ NETWORK PARTITION CUTS LINK ]
                                  |
            +---------------------+---------------------+
            |                                           |
            v                                           v
+-----------------------+                   +-----------------------+
|  Datacenter US-East   |                   |  Datacenter US-West   |
|  Server 1 (Leader?)   |                   |  Server 2 (Leader?)   |
|  Writes balance=$500  |                   |  Writes balance=$100  |
+-----------------------+                   +-----------------------+
            ^                                           ^
            |                                           |
            +-------------------------------------------+
            |         Client B: "set balance = $100"    |
            +-------------------------------------------+
-> Two servers both believe they are the authoritative leader!
-> Data silently diverges; transactions contradict; state corrupted!

If the network links between datacenters sever, both partitions might attempt to accept writes. This is Split-Brain: the catastrophic divergence of system state where two or more nodes independently act as the authoritative master.

To prevent split-brain and provide Linearizability (the illusion that there is only one copy of the data, and every read observes the latest committed write), the cluster must achieve Consensus: a collection of independent processes must agree on values or state machine transitions, even if some of the processes fail or messages are lost or delayed.

2. Mental Model: The Replicated State Machine (RSM)

Modern distributed consensus systems do not solve consensus for isolated, disconnected values. Instead, they implement the Replicated State Machine (RSM) architecture.

SYSTEM ARCHITECTURE BLUEPRINTDISTRIBUTED SYSTEMS

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 5

1. Client Proposes State Machine Command

Client issues PROPOSE { op: 'set x=10' } to Node 1 (Elected Leader, Term 2). Leader assigns log index 4.

Architectural Invariant: Strong Leader: Only the elected leader accepts client proposals; followers redirect clients to the known leader.

ARCHITECTURAL FLOW · STEP 2 OF 5

2. Leader Uncommitted Local Log Append

Leader writes entry [T2: x=10] to its local log at index 4. The entry remains UNCOMMITTED until replicated to a majority.

Architectural Invariant: Durability Invariant: The leader cannot mutate its state machine until the log entry is safely stored on a majority quorum.

ARCHITECTURAL FLOW · STEP 3 OF 5

3. Dispatch AppendEntries RPC to Peers

Leader broadcasts AppendEntries(term=2, leaderId=1, prevLogIndex=3, prevLogTerm=2, entries=[T2:x=10]) to Node 2 and Node 3.

Architectural Invariant: Log Matching Property: If two logs contain an entry with the same index and term, they are identical up to that point.

ARCHITECTURAL FLOW · STEP 4 OF 5

4. Follower Match Verification & ACK

Node 2 verifies prevLogIndex 3 matches term 2. It appends entry 4 to disk and returns AppendEntriesResult(success=true, matchIndex=4).

Architectural Invariant: Majority Quorum: Node 1 (Leader) + Node 2 (Follower) form 2 out of 3 nodes — a strict majority quorum is reached!

ARCHITECTURAL FLOW · STEP 5 OF 5

5. Commit Index Advance & State Machine Apply

Leader advances commitIndex to 4. Leader applies command 'set x=10' to its in-memory KV state machine and responds to the client.

Architectural Invariant: Linearizability Guarantee: Once an entry is committed, it will never be overwritten or lost by any future leader in any higher term.

The Deterministic State Machine Principle

A deterministic state machine is a program that transitions through a sequence of discrete states:

If two identical, deterministic state machines start in the exact same initial state $S_0$ and apply the exact same sequence of input commands:

They are mathematically guaranteed to arrive at the exact same final state $S_k$, yielding identical results for every query.

The Role of Consensus in RSM

The consensus algorithm’s sole responsibility is ordering the distributed Write-Ahead Log (WAL):

1. Clients submit state machine operations (e.g., set x = 10, create_pod web-frontend).
2. The Consensus Module (Raft) ensures that every replica’s log contains the exact same entries in the exact same sequence.
3. Once an entry is committed by consensus, the State Machine applies the command sequentially to its local data structure.

By reducing system coordination to replicated log synchronization, Raft enables complex distributed databases (etcd, CockroachDB, TiKV) to build arbitrary transactional capabilities on top of a rock-solid, ordered log foundation.

3. Quorum Mathematics: Majority Intersections & The $2f+1$ Bound

Why does a Raft cluster require 3 nodes to tolerate 1 failure, and 5 nodes to tolerate 2 failures? Why can a 4-node cluster still only tolerate 1 failure?

The answer lies in the Pigeonhole Principle and Quorum Intersection.

Mathematical Derivation of Quorums

Let $N\ge 1$ be the total number of voting nodes in a cluster. A Quorum $Q$ is defined as a strict majority of nodes:

Now consider any two arbitrary majorities $Q_1,Q_2\subseteq \{1,\dots ,N\}$. Because $|Q_1|$ and $|Q_2|$ are integers strictly greater than $N/2$, their sum satisfies (for both odd and even $N$):

(Specifically, $2(\lfloor N/2\rfloor +1)=N+1$ when $N$ is odd, and $N+2$ when $N$ is even.) Since the total number of physical nodes in the cluster satisfies $|Q_1\cup Q_2|\le N$, by the Pigeonhole Principle the two majorities must intersect by at least one node:

Quorum Majority Intersection:
---------------------------------------------------------------------------------
Cluster of N = 5 Nodes: { Node 1, Node 2, Node 3, Node 4, Node 5 }
Majority Quorum Size = 3

Quorum 1 (Nodes that committed Entry X):      { Node 1, Node 2, Node 3 }
Quorum 2 (Nodes that elect Leader Y):                  { Node 3, Node 4, Node 5 }
                                                          ^
                                                INTERSECTION NODE!
-> Node 3 witnessed Entry X AND voted for Leader Y.
-> Node 3 guarantees Leader Y learns about Entry X before taking office!

Fault Tolerance Bound: $N=2f+1$

If we want a distributed system to remain fully operational when $f$ nodes crash, the surviving $N-f$ nodes must still constitute a strict majority:

Since $N$ must be an integer, the minimal number of nodes required to survive $f$ crash faults is:

+-------------------------------------------------------------------------------+
|                      CLUSTER SIZE & QUORUM FAULT TOLERANCE                    |
+-------------------------------------------------------------------------------+
| Total Nodes (N) | Majority Quorum | Crash Faults Tolerated (f) | Evaluation   |
+-----------------+-----------------+----------------------------+--------------+
| 1               | 1 (100%)        | 0                          | SPOF         |
| 2               | 2 (100%)        | 0 (Loss of 1 kills quorum) | Wasteful     |
| 3               | 2 (66.7%)       | 1                          | Minimal Prod |
| 4               | 3 (75.0%)       | 1 (Same as N=3, more msgs) | Antipattern  |
| 5               | 3 (60.0%)       | 2                          | Recommended  |
| 7               | 4 (57.1%)       | 3                          | High-Security|
+-------------------------------------------------------------------------------+

4. The Raft Consensus Algorithm: Deconstructed

Historically, distributed systems used Multi-Paxos (Lamport, 1998) for consensus. However, Paxos is notoriously opaque, lacking clean abstractions for leader election and cluster membership changes.

In 2014, Diego Ongaro and John Ousterhout (Stanford University) introduced Raft, designed explicitly for understandability and operational tractability.

Raft decomposes consensus into three independent subproblems:

1. Leader Election: When an existing leader fails, a new leader must be elected.
2. Log Replication: The leader accepts log entries from clients and forces followers to duplicate its log.
3. Safety: If any server has applied an entry to its state machine, no other server may ever apply a different entry for that log index.

1. The Three Node States

At any given millisecond, every server in a Raft cluster exists in one of three mutually exclusive states:

        +----------------------------------------------------+
        |                                                    |
        v                                                    | Discovers server
+---------------+  Times out, starts election  +---------------+ with higher term
|   FOLLOWER    | ---------------------------> |   CANDIDATE   | ---------------+
+---------------+                              +---------------+                |
        ^                                              |                        |
        |                                              | Wins election          |
        | Discovers server with higher term            v (Majority votes)       |
        |                                      +---------------+                |
        +------------------------------------- |    LEADER     |                |
                                               +---------------+                |
                                                       |                        |
                                                       +------------------------+

1. Follower: Passive state. Responds to incoming RPCs from leaders and candidates. Never issues requests. If no communication is received within an election timeout, transitions to Candidate.
2. Candidate: Active election state. Increments the current term, votes for itself, and broadcasts RequestVote RPCs to all peers.
3. Leader: Authoritative master. Handles all client reads and writes, drives log replication, and dispatches periodic heartbeats to maintain its authority.

2. Terms as Distributed Logical Clocks

Physical time cannot coordinate servers. Raft divides time into arbitrary Terms, represented by strictly increasing integers ($1,2,3,\dots$):

• Terms act as Lamport Logical Clocks (covered in CORE-M17-002).
• Each term begins with an election. If an election results in a split vote, the term ends with no leader, and a new term begins immediately.
• Fundamental Rule of Terms: If a node observes a message with a term greater than its own current term ($T_{\text{msg}}>T_{\text{local}}$), the node immediately updates its current term to $T_{\text{msg}}$ and drops down to the Follower state.
• If a leader or candidate receives an RPC with an obsolete term ($T_{\text{msg}}<T_{\text{local}}$), it rejects the request immediately.

3. Leader Election & Split-Vote Mitigation

How does Raft elect a single leader without deadlocking in tied votes?

Randomized Election Timers (150ms - 300ms):
---------------------------------------------------------------------------------
Node 1: [========= Timer: 162ms =========] -> TIMES OUT! Becomes Candidate!
Node 2: [=================== Timer: 248ms ===================]
Node 3: [============================= Timer: 291ms =============================]

1. Node 1 times out first:
   - Increments currentTerm (e.g. Term 1 -> 2)
   - Votes for itself (votesCount = 1)
   - Broadcasts RequestVote RPC to Node 2 and Node 3

2. Node 2 and Node 3 receive RequestVote(term=2):
   - Term 2 > local Term 1 -> update term to 2
   - Node 2 has not voted yet in Term 2 -> grants vote to Node 1!
   - Node 1 now has 2 votes out of 3 (Majority achieved!)

3. Node 1 transitions to LEADER:
   - Dispatches empty AppendEntries heartbeat to assert authority
   - Node 2 and Node 3 reset their election timers upon receiving heartbeat

Split-Vote Mitigation via Randomized Timers

If multiple followers time out at the exact same millisecond, they all become candidates and split the votes (e.g., in a 4-node cluster, Candidate A gets 2 votes, Candidate B gets 2 votes). Neither achieves a majority ($3$).

Raft prevents split-vote deadlocks using Randomized Election Timeouts chosen uniformly from an interval $[T_{\text{min}},2T_{\text{min}}]$ (typically $150\text{ ms}-300\text{ ms}$ within an availability zone, or $1000\text{ ms}-2000\text{ ms}$ across multi-region WANs):

• Because timeouts are randomized, one node will almost always time out before its peers.
• That node increments its term and collects majority votes before any competing candidate’s timer expires.
• If a tie occurs, the candidates time out again with fresh random timers, breaking the tie in the subsequent election round.

The Formal Raft Liveness Timing Inequality

While Raft’s safety properties hold unconditionally regardless of network delays, clock skew, or GC pauses, election liveness (converging on and maintaining a stable leader) requires the cluster to satisfy Ongaro & Ousterhout’s timing inequality:

• $T_{\text{broadcast}}$: Average time for a server to send RPCs in parallel to all peers, persist state (votedFor / WAL fdatasync) where required, and receive replies (typically $0.5\text{ ms}-15\text{ ms}$ on local NVMe + intra-region Ethernet).
• $T_{\text{election}}$: Randomized election timeout window, sized at $10\times$ to $20\times T_{\text{broadcast}}$ (e.g., $150\text{ ms}-300\text{ ms}$ when $T_{\text{broadcast}}\approx 10\text{ ms}$), with periodic leader heartbeats dispatched every $T_{\text{hb}}\approx T_{\text{election,min}}/3$ to $T_{\text{election,min}}/5$ ($30\text{ ms}-50\text{ ms}$) so a single dropped UDP/TCP packet never triggers a spurious election.
• $\text{MTBF}$: Mean Time Between Failures of an individual server (typically months, $\sim 10^7\text{ s}$). When $T_{\text{election}}=0.3\text{ s}$ and $\text{MTBF}=10^7\text{ s}$, leader failover consumes less than $\frac{T_{\text{election}}}{\text{MTBF}}=3\times 10^{-8}$ ($0.000003\%$) of cluster wall-clock uptime.

4. Log Replication & The AppendEntries RPC

Once elected, the leader serves client writes through the AppendEntries RPC:

+-------------------------------------------------------------------------------+
|                       AppendEntries RPC Payload Anatomy                       |
+-------------------------------------------------------------------------------+
| Parameter    | Type       | Description                                       |
+--------------+------------+---------------------------------------------------+
| term         | int        | Leader's current term number                      |
| leaderId     | int        | Leader identifier (so followers can redirect CLI) |
| prevLogIndex | int        | Index of log entry immediately preceding new ones |
| prevLogTerm  | int        | Term of prevLogIndex entry                        |
| entries[]    | Entry[]    | Log entries to store (empty for periodic heartbeat|
| leaderCommit | int        | Leader's commitIndex                              |
+-------------------------------------------------------------------------------+

5. The Formal Raft Safety Invariants

Consensus algorithms cannot be validated by casual testing; they require mathematical proofs of correctness. Raft guarantees five fundamental safety invariants at all times:

+-------------------------------------------------------------------------------+
|                         THE 5 RAFT SAFETY INVARIANTS                          |
+-------------------------------------------------------------------------------+
| Invariant               | Formal Guarantee                                    |
+-------------------------+-----------------------------------------------------+
| 1. Election Safety      | At most one leader can be elected in a given term.  |
|                         |                                                     |
| 2. Leader Append-Only   | A leader never overwrites or truncates its own log; |
|                         | it only appends new entries.                        |
|                         |                                                     |
| 3. Log Matching Property| If two logs contain an entry with the same index    |
|                         | and term, then the logs are identical in all        |
|                         | entries up through the given index.                 |
|                         |                                                     |
| 4. Leader Completeness  | If a log entry is committed in a given term, that   |
|                         | entry will be present in the logs of the leaders    |
|                         | for all higher-numbered terms.                      |
|                         |                                                     |
| 5. State Machine Safety | If a server has applied an entry at a given index   |
|                         | to its state machine, no other server will ever     |
|                         | apply a different log entry for the same index.     |
+-------------------------------------------------------------------------------+

Deep Dive: The Log Matching Property Proof

The Log Matching Property rests on an elegant inductive check executed during every single AppendEntries RPC:

1. Induction Base: Log index 0 matches trivially across all nodes (empty entry).
2. Consistency Check: When a leader sends AppendEntries, it includes (prevLogIndex, prevLogTerm).
3. A follower refuses the append if it does not find an entry in its local log at prevLogIndex with matching term prevLogTerm.
4. Therefore, whenever AppendEntries succeeds, the leader knows that the follower’s log is 100% identical to its own up to that index.

Follower Log Conflict & Repair:
---------------------------------------------------------------------------------
Leader Log:     [T1:idx1] [T1:idx2] [T2:idx3] [T3:idx4] [T3:idx5] (Leader Term 3)
                                        ^
                                        prevLogIndex=3, prevLogTerm=2

Follower A Log: [T1:idx1] [T1:idx2] [T2:idx3] <- Matches! Appends [T3:idx4], [T3:idx5].

Follower B Log: [T1:idx1] [T1:idx2] [T1:idx3] <- CONFLICT! Term at Index 3 is T1 != T2!
                                                 Entry fails prevLogTerm check!
                                                 Follower B returns false!
                                                 Leader decrements nextIndex to 3,
                                                 matches (prevLogIndex=2, T1), and
                                                 overwrites Follower B's uncommitted tail!

6. Log Compaction & Snapshot Transfer

In a long-running system, the append-only log cannot grow indefinitely. An etcd cluster processing $1,000\text{ writes/sec}$ generates $86,400,000$ log entries per day ($10\text{ GB}-50\text{ GB}$ of disk space).

Raft resolves this via Log Compaction using State Machine Snapshots:

Log Compaction Pipeline:
---------------------------------------------------------------------------------
WAL Log before Compaction:
Index:   1       2       3       4       5       6       7       8       9
Log:   [x=1]   [y=2]   [x=3]   [z=9]   [x=7]   [y=5]   [a=1]   [z=4]   [x=2]

1. State Machine takes Snapshot at Index 6:
   { x: 7, y: 5, z: 9 }  <-- Compact state representation!

2. Discard Log Entries 1 through 6:
   Retain metadata: lastIncludedIndex = 6, lastIncludedTerm = 2

WAL Log after Compaction:
[ SNAPSHOT at Index 6, Term 2 ]  -->  [Index 7: a=1]  [Index 8: z=4]  [Index 9: x=2]

The InstallSnapshot RPC

If a follower crashes, remains offline for three days, and reconnects, the leader will have already compacted and deleted the log entries the follower needs.

In this scenario, the leader bypasses AppendEntries and transmits an InstallSnapshot RPC:

1. The leader streams the serialized snapshot file across the network in chunks.
2. The lagging follower discards its entire local log, resets its state machine to the snapshot’s lastIncludedIndex, and resumes standard AppendEntries synchronization.

7. Real-World Architecture: etcd, TiKV, and Kafka KRaft

Consensus is not a theoretical exercise; it powers the mission-critical control planes of modern computing:

+-------------------------------------------------------------------------------+
|                       PRODUCTION RAFT IMPLEMENTATIONS                         |
+-------------------------------------------------------------------------------+
| System        | Implementation Role                 | Scale Architecture      |
+---------------+-------------------------------------+-------------------------+
| etcd          | Kubernetes cluster brain: stores    | Single Raft consensus   |
| (Go)          | cluster state, API objects, locks   | group (3 or 5 nodes)    |
|               |                                     |                         |
| TiKV          | Distributed ACID SQL storage engine | Multi-Raft: millions of |
| (Rust)        | for TiDB                            | consensus groups/range  |
|               |                                     |                         |
| Kafka KRaft   | Metadata management replacing       | Event-driven Raft quorum|
| (Java)        | ZooKeeper                           | of controller brokers   |
|               |                                     |                         |
| CockroachDB   | Distributed SQL transactional MVCC  | Multi-Raft across 64MB  |
| (Go)          | database                            | range partitions        |
+-------------------------------------------------------------------------------+

Multi-Raft: Breaking the Scalability Bottleneck

A single Raft consensus group is bottlenecked by the leader’s network bandwidth and single-core write serialization (typically peaking at $10,000-50,000\text{ writes/second}$).

To scale to millions of operations per second, modern distributed databases (such as TiKV and CockroachDB) use Multi-Raft:

• The global keyspace is split into contiguous chunks called Ranges (e.g. $64\text{ MB}-96\text{ MB}$ each).
• Each Range runs its own independent, lightweight Raft consensus group.
• A cluster with $1,000$ servers can host $100,000$ independent Raft consensus groups simultaneously.
• A server can act as a Leader for Range 1, a Follower for Range 2, and a Follower for Range 3.
• Writes to distinct keys execute in parallel across different Raft groups with zero coordination overhead!

8. Cluster Membership Reconfiguration: Joint Consensus

In production, servers fail permanently, hardware is decommissioned, and clusters must be resized (e.g., expanding from 3 nodes to 5 nodes).

A naive transition from Old Configuration $C_{\text{old}}$ to New Configuration $C_{\text{new}}$ is disastrous: because nodes update their configurations at different moments, two independent majorities can form simultaneously, causing immediate split-brain!

The Membership Reconfiguration Split-Brain Hazard:
---------------------------------------------------------------------------------
Cluster resizing from 3 nodes to 5 nodes:
C_old = { Node 1, Node 2, Node 3 }          (Majority = 2)
C_new = { Node 1, Node 2, Node 3, 4, 5 }    (Majority = 3)

Timeline:
- Node 1 and Node 2 switch to C_new: need 3 nodes for quorum -> { 1, 2, 3 }
- Node 3 has NOT received the update yet: still operates under C_old!
- Node 3 forms a quorum under C_old with Node 2 -> { 2, 3 }!
-> Two disjoint majorities elect two distinct leaders simultaneously!

The Joint Consensus Solution

Raft prevents this vulnerability via Joint Consensus: a two-phase configuration transition over the combined server set $C_{\text{old,new}}=C_{\text{old}}\cup C_{\text{new}}$ where any quorum $Q$ must satisfy independent majorities from BOTH the old and new configurations simultaneously:

1. Phase 1: Log $C_{\text{old,new}}$: Leader appends the joint configuration entry to its log. As soon as a node appends $C_{\text{old,new}}$ (even before commit), it uses the joint quorum rule. Once $C_{\text{old,new}}$ is committed, no leader can be elected without winning majorities in both $C_{\text{old}}$ and $C_{\text{new}}$.
2. Phase 2: Log $C_{\text{new}}$: Once $C_{\text{old,new}}$ is committed, the leader appends $C_{\text{new}}$ to its log. Once $C_{\text{new}}$ commits, removed nodes from $C_{\text{old}}\setminus C_{\text{new}}$ can be safely decommissioned. (Note: Ongaro’s 2014 dissertation also proves an even simpler Single-Server Membership Change protocol—adding or removing strictly 1 voting node per committed step—which guarantees overlapping majorities without an explicit joint entry.)

9. Design Alternatives & Trade-offs: Raft vs. Multi-Paxos vs. Zab vs. EPaxos

10. Operational Failure Modes & Production Troubleshooting

+-------------------------------------------------------------------------------+
|                    PRODUCTION RAFT FAILURE MODES & FIXES                      |
+-------------------------------------------------------------------------------+
| Failure Mode            | Root Cause                | Mitigation Strategy     |
+-------------------------+---------------------------+-------------------------+
| 1. fsync Disk Stalls    | NVMe write barrier or     | Isolate WAL onto        |
|    Triggering Elections | SSD garbage collection    | dedicated NVMe disk;    |
|                         | delays AppendEntries fsync| tune election timeout   |
|                         |                           |                         |
| 2. Asymmetric Network   | Node A can reach Node B;  | Pre-Vote Protocol       |
|    Partitions           | Node B cannot reach A;    | (check election chances |
|                         | disrupts stable leader    | before incrementing term|
|                         |                           |                         |
| 3. Snapshot Transfer    | Slow follower saturated   | Rate-limit snapshot sync|
|    Network Starvation   | network link, starving    | bandwidth; separate     |
|                         | heartbeats to peers       | replication network     |
|                         |                           |                         |
| 4. Phantom Reads on     | Partitioned leader serves | ReadIndex / LeaseRead:  |
|    Stale Leader         | local reads without       | confirm leader validity |
|                         | verifying quorum presence | with majority heartbeat |
+-------------------------------------------------------------------------------+

Deep Dive: The Pre-Vote Protocol

Consider an asymmetric network partition where Node 3 can transmit packets to peers, but cannot receive heartbeats from Leader 1.

1. Node 3’s election timer expires.
2. Node 3 increments its term ($T=5\to T=6$) and broadcasts RequestVote.
3. When Leader 1 receives $T=6$, the leader is forced to step down to follower, disrupting cluster throughput.
4. Node 3 cannot win (it lacks up-to-date log entries), so another election occurs.
5. Node 3 repeatedly times out, incrementing terms and continuously dethroning legitimate leaders!

Remediation: The Pre-Vote Protocol: Before incrementing its term, a candidate enters a speculative Pre-Vote phase. It asks peers: “If I were to call an election, would you vote for me?” Peers reject the pre-vote if they are receiving regular heartbeats from a valid leader. Node 3 remains isolated without incrementing its term, protecting the cluster from disruptive term inflation.

11. Concrete Implementation: Mini-Raft Consensus Node

The following complete, runnable TypeScript implementation models the core Raft consensus mechanics: state transitions, randomized election timeouts, RequestVote, and AppendEntries quorum handling.

// mini-raft.ts
import { EventEmitter } from 'node:events';

export type NodeRole = 'FOLLOWER' | 'CANDIDATE' | 'LEADER';

export interface LogEntry {
  term: number;
  index: number;
  command: string;
}

export interface RequestVoteArgs {
  term: number;
  candidateId: number;
  lastLogIndex: number;
  lastLogTerm: number;
}

export interface RequestVoteReply {
  term: number;
  voteGranted: boolean;
}

export interface AppendEntriesArgs {
  term: number;
  leaderId: number;
  prevLogIndex: number;
  prevLogTerm: number;
  entries: LogEntry[];
  leaderCommit: number;
}

export interface AppendEntriesReply {
  term: number;
  success: boolean;
  matchIndex: number;
}

export class RaftNode extends EventEmitter {
  public readonly id: number;
  public readonly peers: Map<number, RaftNode> = new Map();

  // Persistent state on all servers
  public currentTerm = 0;
  public votedFor: number | null = null;
  public log: LogEntry[] = [{ term: 0, index: 0, command: 'NOOP' }]; // 1-based indexing

  // Volatile state on all servers
  public commitIndex = 0;
  public lastApplied = 0;
  public role: NodeRole = 'FOLLOWER';

  // Leader-specific volatile state
  public nextIndex: Map<number, number> = new Map();
  public matchIndex: Map<number, number> = new Map();

  // Timers
  private electionTimer: NodeJS.Timeout | null = null;
  private heartbeatTimer: NodeJS.Timeout | null = null;

  constructor(id: number) {
    super();
    this.id = id;
  }

  public start(): void {
    this.resetElectionTimer();
  }

  public stop(): void {
    if (this.electionTimer) clearTimeout(this.electionTimer);
    if (this.heartbeatTimer) clearInterval(this.heartbeatTimer);
  }

  private resetElectionTimer(): void {
    if (this.electionTimer) clearTimeout(this.electionTimer);
    // Randomized election timeout between 150ms and 300ms
    const timeout = Math.floor(Math.random() * 150) + 150;
    this.electionTimer = setTimeout(() => this.startElection(), timeout);
  }

  public startElection(): void {
    this.role = 'CANDIDATE';
    this.currentTerm += 1;
    this.votedFor = this.id;
    let votesReceived = 1; // Vote for self

    this.resetElectionTimer();
    const lastEntry = this.log[this.log.length - 1];

    const args: RequestVoteArgs = {
      term: this.currentTerm,
      candidateId: this.id,
      lastLogIndex: lastEntry.index,
      lastLogTerm: lastEntry.term,
    };

    // Broadcast RequestVote to all peers
    for (const [peerId, peer] of this.peers.entries()) {
      peer.handleRequestVote(args).then((reply) => {
        if (this.role !== 'CANDIDATE' || reply.term !== this.currentTerm) return;

        if (reply.term > this.currentTerm) {
          this.currentTerm = reply.term;
          this.role = 'FOLLOWER';
          this.votedFor = null;
          this.resetElectionTimer();
          return;
        }

        if (reply.voteGranted) {
          votesReceived += 1;
          const totalNodes = this.peers.size + 1;
          const quorum = Math.floor(totalNodes / 2) + 1;

          if (votesReceived >= quorum) {
            this.becomeLeader();
          }
        }
      });
    }
  }

  private becomeLeader(): void {
    this.role = 'LEADER';
    if (this.electionTimer) clearTimeout(this.electionTimer);

    // Initialize leader volatile state
    for (const peerId of this.peers.keys()) {
      this.nextIndex.set(peerId, this.log.length);
      this.matchIndex.set(peerId, 0);
    }

    // Send immediate heartbeat and start periodic heartbeat interval (50ms)
    this.broadcastHeartbeat();
    this.heartbeatTimer = setInterval(() => this.broadcastHeartbeat(), 50);
    this.emit('leader_elected', { term: this.currentTerm, leaderId: this.id });
  }

  private broadcastHeartbeat(): void {
    for (const [peerId, peer] of this.peers.entries()) {
      const pIndex = this.nextIndex.get(peerId) || this.log.length;
      const prevEntry = this.log[pIndex - 1] || { term: 0, index: 0 };
      const entriesToSend = this.log.slice(pIndex);

      const args: AppendEntriesArgs = {
        term: this.currentTerm,
        leaderId: this.id,
        prevLogIndex: prevEntry.index,
        prevLogTerm: prevEntry.term,
        entries: entriesToSend,
        leaderCommit: this.commitIndex,
      };

      peer.handleAppendEntries(args).then((reply) => {
        if (reply.term > this.currentTerm) {
          this.currentTerm = reply.term;
          this.role = 'FOLLOWER';
          this.votedFor = null;
          if (this.heartbeatTimer) clearInterval(this.heartbeatTimer);
          this.resetElectionTimer();
          return;
        }

        if (this.role === 'LEADER') {
          if (reply.success) {
            this.matchIndex.set(peerId, reply.matchIndex);
            this.nextIndex.set(peerId, reply.matchIndex + 1);
            this.checkAndAdvanceCommitIndex();
          } else {
            // Log mismatch: decrement nextIndex and retry
            const cur = this.nextIndex.get(peerId) || 2;
            this.nextIndex.set(peerId, Math.max(1, cur - 1));
          }
        }
      });
    }
  }

  private checkAndAdvanceCommitIndex(): void {
    // If there exists an N > commitIndex, a majority of matchIndex[i] >= N,
    // and log[N].term == currentTerm: set commitIndex = N
    for (let N = this.log.length - 1; N > this.commitIndex; N--) {
      if (this.log[N].term !== this.currentTerm) continue;

      let count = 1; // Self
      for (const mIndex of this.matchIndex.values()) {
        if (mIndex >= N) count += 1;
      }

      const totalNodes = this.peers.size + 1;
      if (count >= Math.floor(totalNodes / 2) + 1) {
        this.commitIndex = N;
        this.emit('entry_committed', { index: N, command: this.log[N].command });
        break;
      }
    }
  }

  public async handleRequestVote(args: RequestVoteArgs): Promise<RequestVoteReply> {
    if (args.term > this.currentTerm) {
      this.currentTerm = args.term;
      this.role = 'FOLLOWER';
      this.votedFor = null;
    }

    const lastEntry = this.log[this.log.length - 1];
    const logOk =
      args.lastLogTerm > lastEntry.term ||
      (args.lastLogTerm === lastEntry.term && args.lastLogIndex >= lastEntry.index);

    const canVote =
      args.term === this.currentTerm &&
      (this.votedFor === null || this.votedFor === args.candidateId) &&
      logOk;

    if (canVote) {
      this.votedFor = args.candidateId;
      this.resetElectionTimer();
      return { term: this.currentTerm, voteGranted: true };
    }

    return { term: this.currentTerm, voteGranted: false };
  }

  public async handleAppendEntries(args: AppendEntriesArgs): Promise<AppendEntriesReply> {
    if (args.term < this.currentTerm) {
      return { term: this.currentTerm, success: false, matchIndex: 0 };
    }

    this.resetElectionTimer();

    if (args.term > this.currentTerm || this.role === 'CANDIDATE') {
      this.currentTerm = args.term;
      this.role = 'FOLLOWER';
      this.votedFor = null;
    }

    // Verify log matching property at prevLogIndex
    if (args.prevLogIndex > 0) {
      const entry = this.log[args.prevLogIndex];
      if (!entry || entry.term !== args.prevLogTerm) {
        return { term: this.currentTerm, success: false, matchIndex: 0 };
      }
    }

    // Append new entries and truncate conflicts
    for (let i = 0; i < args.entries.length; i++) {
      const newEntry = args.entries[i];
      const existing = this.log[newEntry.index];
      if (existing) {
        if (existing.term !== newEntry.term) {
          this.log = this.log.slice(0, newEntry.index);
          this.log.push(newEntry);
        }
      } else {
        this.log.push(newEntry);
      }
    }

    if (args.leaderCommit > this.commitIndex) {
      this.commitIndex = Math.min(args.leaderCommit, this.log.length - 1);
    }

    return {
      term: this.currentTerm,
      success: true,
      matchIndex: args.prevLogIndex + args.entries.length,
    };
  }

  public clientPropose(command: string): boolean {
    if (this.role !== 'LEADER') return false;

    const entry: LogEntry = {
      term: this.currentTerm,
      index: this.log.length,
      command,
    };
    this.log.push(entry);
    this.broadcastHeartbeat();
    return true;
  }
}

async function runDemo(): Promise<void> {
  console.log("=== Raft Consensus Algorithm: Election & Replicated Log ===");
  const cluster = [new RaftNode(1), new RaftNode(2), new RaftNode(3)];
  for (const node of cluster) {
    for (const peer of cluster) {
      if (node.id !== peer.id) node.peers.set(peer.id, peer);
    }
  }

  try {
    console.log("Initialized Raft cluster of 3 nodes in FOLLOWER state (Term 0)");
    console.log("Node 1 election timeout triggered! Starting election for Term 1...");
    cluster[0].startElection();
    await new Promise((resolve) => setTimeout(resolve, 10));

    console.log(`Election result: Node 1 role is now '${cluster[0].role}' with term ${cluster[0].currentTerm}`);
    if (cluster[0].role === 'LEADER') {
      const accepted = cluster[0].clientPropose("SET counter=100");
      await new Promise((resolve) => setTimeout(resolve, 10));
      console.log(`Proposed command 'SET counter=100' to leader: ${accepted}`);
      console.log(`Leader commitIndex: ${cluster[0].commitIndex}, Node 2 log length: ${cluster[1].log.length}, Node 3 commitIndex: ${cluster[2].commitIndex}`);
    }
  } finally {
    for (const node of cluster) node.stop();
  }
}

runDemo();

Simulation Execution Output & State Transitions

=== Raft Consensus Algorithm: Election & Replicated Log ===
Initialized Raft cluster of 3 nodes in FOLLOWER state (Term 0)
Node 1 election timeout triggered! Starting election for Term 1...
Election result: Node 1 role is now 'LEADER' with term 1
Proposed command 'SET counter=100' to leader: true
Leader commitIndex: 1, Node 2 log length: 2, Node 3 commitIndex: 0

12. Exercises with Observable Deliverables

Exercise 1: Simulate the Raft 3-Node Cluster Lifecycle

Deliverable: Using the RaftNode implementation above:

1. Initialize a 3-node cluster: Node 1, Node 2, and Node 3. Connect their peer maps.
2. Start all three nodes and observe leader election. Capture which node becomes leader.
3. Call leader.clientPropose("set x=100"). Verify that commitIndex advances on the leader and that the entry appears in all 3 nodes’ logs.
4. Simulate a network partition: remove the leader from the other two nodes’ peer maps. Verify that the two surviving nodes elect a new leader in a higher term.

Exercise 2: Prove the Leader Completeness Edge Case

Scenario: Review Figure 8 from the Raft paper (Ongaro & Ousterhout).

1. Explain why a leader in Term 4 cannot commit an entry from Term 2 merely because it is stored on 3 out of 5 servers.
2. Write a short proof detailing how an older leader could be elected and overwrite that entry unless the leader commits an entry from its own current term first.

13. Summary & Architectural Decision Guide

+-------------------------------------------------------------------------------+
|                    THE RAFT ENGINEER'S DECISION GUIDE                         |
+-------------------------------------------------------------------------------+
| Problem Dimension         | Battle-Tested Architectural Pattern               |
+---------------------------+---------------------------------------------------+
| Cluster Sizing            | Always deploy odd node counts (3 or 5 nodes)      |
| Fault Tolerance           | N = 2f + 1 nodes mathematically tolerate f faults |
| Split-Vote Prevention     | Randomized election timeouts (150ms - 300ms)      |
| Log Synchronization       | Inductive prefix match via (prevLogIndex, term)   |
| Stale Read Prevention     | ReadIndex / LeaseRead (verify quorum before read) |
| Large State Storage       | Periodic snapshotting + InstallSnapshot RPC       |
| Throughput Scaling        | Multi-Raft (partition keyspace into 64MB ranges)  |
| Asymmetric Split Defense  | Pre-Vote protocol before term increments          |
+-------------------------------------------------------------------------------+

1. Consensus is Overkill for Unordered Data: Do not deploy Raft when weak consistency or Last-Write-Wins suffices. Consensus incurs mandatory disk fsync and network round-trip overhead on every write.
2. Never Commit Cross-Term Entries Directly: A Raft leader must only advance commitIndex by counting replicas for entries from its current term. Older entries are committed transitively.
3. Isolate the Write-Ahead Log: The #1 cause of Raft election instability in production is disk write contention. Always mount the Raft WAL directory onto a dedicated NVMe SSD drive separate from application logging or general storage.
4. Odd Nodes Always: A 4-node cluster provides the exact same failure tolerance as a 3-node cluster ($f=1$) while doubling the probability of node failures and increasing network traffic. Never deploy even-sized consensus clusters in production.

14. Authoritative References & Version Context

• Version Baseline: Raft implementation references align with etcd-io/raft v3.5+, HashiCorp Raft v1.6+, tikv/raft-rs v0.7, and Apache Kafka KRaft v3.7+/v4.0 (KIP-595).
• Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm (Extended Version). Proceedings of the 2014 USENIX Annual Technical Conference (USENIX ATC ‘14).
• Ongaro, D. (2014). Consensus: Bridging Theory and Practice. Ph.D. Dissertation, Stanford University (formalizing Pre-Vote §9.6, ReadIndex §6.4, and Single-Server Membership Changes §4.1).
• etcd Project Authors. go.etcd.io/raft/v3 Package Architecture & State Machine Specification.
• Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News, 32(4), 51–58.