从零实现Raft共识算法：领导者选举、日志复制与安全性约束

在上一篇文章中，我们从零实现了一个MVCC事务引擎，覆盖了版本链、快照隔离与写冲突检测。那篇文章聚焦的是单机数据库的并发控制。这一次我们把视角转向分布式系统，目标是一个完整的Raft共识算法实现。

分布式系统中最难的问题是一致性。多个节点如何就某个值达成一致？如何保证在部分节点故障时系统仍然可用？如何保证在任意时刻最多只有一个领导者？Paxos在理论上解决了这些问题，但它的工程实现极其困难，以至于Google的工程师在实现Paxos时也经常出错。Raft的设计目标就是"可理解性"——它将共识问题分解为三个相对独立的子问题：领导者选举、日志复制和安全性约束，每个子问题都有清晰的算法描述。

本文用纯前端JavaScript从零实现一个完整的Raft共识算法，不依赖任何库。完整链路是：节点状态机 → 领导者选举 → 日志复制 → 安全性约束 → 网络分区处理 → 持久化模拟。代码可以在浏览器中模拟三到五个节点的集群，观察选举和日志复制的完整过程。

一、Raft的核心设计

Raft将共识问题分解为三个子问题：

**领导者选举**：集群中有一个领导者节点，负责接收客户端请求并复制日志到其他节点。如果领导者故障，其他节点自动选举出新的领导者。

**日志复制**：领导者将客户端请求作为日志条目追加到本地日志，然后并行复制到所有跟随者。当日志被多数节点确认后，领导者将条目提交并应用到状态机。

**安全性约束**：Raft保证任何时刻最多只有一个领导者，且已提交的日志条目永远不会被覆盖或丢失。

Raft的核心数据结构是**任期（Term）**。任期是一个单调递增的整数，每次选举开始时递增。任期在Raft中扮演逻辑时钟的角色——如果节点A的任期小于节点B的任期，A会立即更新自己的任期并转为跟随者状态。如果候选者的任期小于当前任期，选举请求会被拒绝。

二、节点状态机

每个Raft节点处于三种状态之一：跟随者（Follower）、候选者（Candidate）或领导者（Leader）。

```javascript
const NodeState = {
  FOLLOWER: 'follower',
  CANDIDATE: 'candidate',
  LEADER: 'leader'
};

class RaftNode {
  constructor(id, clusterSize) {
    this.id = id;
    this.clusterSize = clusterSize;

    // 持久化状态（所有节点）
    this.currentTerm = 0;
    this.votedFor = null;
    this.log = [];  // 日志条目数组

    // 易失状态（所有节点）
    this.state = NodeState.FOLLOWER;
    this.commitIndex = 0;
    this.lastApplied = 0;

    // 易失状态（领导者）
    this.nextIndex = {};   // 每个跟随者的下一个要发送的日志索引
    this.matchIndex = {};  // 每个跟随者的已复制日志索引

    // 选举超时
    this.electionTimeout = 150 + Math.random() * 150;  // 150-300ms
    this.lastHeartbeat = Date.now();

    // 网络层
    this.transport = null;
    this.peers = [];

    // 状态机
    this.stateMachine = {};
  }

  // 日志条目结构
  createLogEntry(command) {
    return {
      term: this.currentTerm,
      index: this.log.length + 1,
      command
    };
  }

  // 获取最后一条日志的索引和任期
  getLastLogInfo() {
    if (this.log.length === 0) {
      return { index: 0, term: 0 };
    }
    const last = this.log[this.log.length - 1];
    return { index: last.index, term: last.term };
  }
}
```

日志条目包含三个字段：任期（term）、索引（index）和命令（command）。日志索引从1开始单调递增，任期是创建该条目时的领导者任期。日志条目一旦被多数节点确认，就不能被修改。

三、领导者选举

领导者选举由选举超时触发。每个跟随者维护一个选举定时器，如果在超时时间内没有收到领导者的心跳，就转为候选者并开始选举。

```javascript
class RaftNode {
  // ... 之前的代码

  // 选举超时处理
  onElectionTimeout() {
    if (this.state === NodeState.LEADER) return;

    // 转为候选者
    this.state = NodeState.CANDIDATE;
    this.currentTerm++;
    this.votedFor = this.id;
    this.lastHeartbeat = Date.now();

    console.log(`节点 ${this.id} 开始选举，任期 ${this.currentTerm}`);

    // 统计选票
    let votesGranted = 1;  // 自己投自己
    const votesNeeded = Math.floor(this.clusterSize / 2) + 1;

    // 向所有其他节点发送投票请求
    const lastLog = this.getLastLogInfo();
    const request = {
      type: 'RequestVote',
      term: this.currentTerm,
      candidateId: this.id,
      lastLogIndex: lastLog.index,
      lastLogTerm: lastLog.term
    };

    for (const peer of this.peers) {
      this.transport.send(peer, request, (response) => {
        if (response.term > this.currentTerm) {
          // 发现更高任期，转为跟随者
          this.currentTerm = response.term;
          this.state = NodeState.FOLLOWER;
          this.votedFor = null;
          return;
        }

        if (this.state !== NodeState.CANDIDATE) return;
        if (response.term !== this.currentTerm) return;

        if (response.voteGranted) {
          votesGranted++;
          if (votesGranted >= votesNeeded) {
            this.becomeLeader();
          }
        }
      });
    }
  }

  // 处理投票请求
  handleRequestVote(request) {
    // 如果请求任期小于当前任期，拒绝
    if (request.term < this.currentTerm) {
      return { term: this.currentTerm, voteGranted: false };
    }

    // 如果请求任期大于当前任期，更新任期并转为跟随者
    if (request.term > this.currentTerm) {
      this.currentTerm = request.term;
      this.state = NodeState.FOLLOWER;
      this.votedFor = null;
    }

    // 检查是否已经投票给其他候选者
    if (this.votedFor !== null && this.votedFor !== request.candidateId) {
      return { term: this.currentTerm, voteGranted: false };
    }

    // 检查候选者的日志是否至少与自己的日志一样新
    const lastLog = this.getLastLogInfo();
    const logIsNewer =
      request.lastLogTerm > lastLog.term ||
      (request.lastLogTerm === lastLog.term && request.lastLogIndex >= lastLog.index);

    if (!logIsNewer) {
      return { term: this.currentTerm, voteGranted: false };
    }

    // 投票
    this.votedFor = request.candidateId;
    this.lastHeartbeat = Date.now();

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

  // 成为领导者
  becomeLeader() {
    if (this.state !== NodeState.CANDIDATE) return;

    this.state = NodeState.LEADER;
    console.log(`节点 ${this.id} 成为领导者，任期 ${this.currentTerm}`);

    // 初始化 nextIndex 和 matchIndex
    const lastLog = this.getLastLogInfo();
    for (const peer of this.peers) {
      this.nextIndex[peer.id] = lastLog.index + 1;
      this.matchIndex[peer.id] = 0;
    }

    // 立即发送心跳
    this.sendHeartbeats();
  }
}
```

投票请求的处理有三个关键判断：任期比较、是否已投票、日志新旧比较。其中日志新旧比较是Raft安全性约束的核心——只有日志至少与接收者一样新的候选者才能获得选票。这保证了新领导者一定包含所有已提交的日志条目。

四、日志复制

领导者接收客户端请求后，将命令追加到本地日志，然后并行发送给所有跟随者。当日志被多数节点确认后，领导者将其提交并应用到状态机。

```javascript
class RaftNode {
  // ... 之前的代码

  // 客户端请求处理（仅领导者）
  async appendCommand(command) {
    if (this.state !== NodeState.LEADER) {
      throw new Error('不是领导者，无法处理请求');
    }

    const entry = this.createLogEntry(command);
    this.log.push(entry);
    const logIndex = entry.index;

    console.log(`领导者 ${this.id} 追加日志 [${logIndex}]，任期 ${this.currentTerm}`);

    // 并行复制到所有跟随者
    await this.replicateLog();

    // 检查是否已提交
    if (this.isCommitted(logIndex)) {
      this.commitIndex = logIndex;
      this.applyToStateMachine();
      return { success: true, index: logIndex };
    }

    return { success: false, index: logIndex };
  }

  // 复制日志到所有跟随者
  async replicateLog() {
    for (const peer of this.peers) {
      this.sendAppendEntries(peer);
    }
  }

  // 发送日志追加请求
  sendAppendEntries(peer) {
    const nextIdx = this.nextIndex[peer.id];
    const prevLogIndex = nextIdx - 1;
    const prevLogTerm = prevLogIndex > 0
      ? this.log[prevLogIndex - 1].term
      : 0;

    // 从 nextIndex 开始的所有日志条目
    const entries = this.log.slice(nextIdx - 1);

    const request = {
      type: 'AppendEntries',
      term: this.currentTerm,
      leaderId: this.id,
      prevLogIndex,
      prevLogTerm,
      entries,
      leaderCommit: this.commitIndex
    };

    this.transport.send(peer, request, (response) => {
      if (response.term > this.currentTerm) {
        this.currentTerm = response.term;
        this.state = NodeState.FOLLOWER;
        this.votedFor = null;
        return;
      }

      if (this.state !== NodeState.LEADER) return;
      if (response.term !== this.currentTerm) return;

      if (response.success) {
        // 更新 nextIndex 和 matchIndex
        this.nextIndex[peer.id] = nextIdx + entries.length;
        this.matchIndex[peer.id] = nextIdx + entries.length - 1;

        // 检查是否达到多数派
        if (this.checkCommit()) {
          this.applyToStateMachine();
        }
      } else {
        // 日志不匹配，递减 nextIndex 重试
        if (response.conflictIndex !== undefined) {
          this.nextIndex[peer.id] = Math.max(1, response.conflictIndex);
        } else {
          this.nextIndex[peer.id] = Math.max(1, nextIdx - 1);
        }
        // 立即重试
        this.sendAppendEntries(peer);
      }
    });
  }

  // 处理日志追加请求
  handleAppendEntries(request) {
    // 任期检查
    if (request.term < this.currentTerm) {
      return { term: this.currentTerm, success: false };
    }

    // 更新任期，转为跟随者
    if (request.term > this.currentTerm) {
      this.currentTerm = request.term;
      this.votedFor = null;
    }
    this.state = NodeState.FOLLOWER;
    this.lastHeartbeat = Date.now();

    // 检查 prevLogIndex 和 prevLogTerm 是否匹配
    if (request.prevLogIndex > 0) {
      if (this.log.length < request.prevLogIndex) {
        return {
          term: this.currentTerm,
          success: false,
          conflictIndex: this.log.length + 1
        };
      }

      const prevEntry = this.log[request.prevLogIndex - 1];
      if (prevEntry.term !== request.prevLogTerm) {
        // 找到冲突任期的第一个索引
        let conflictIndex = request.prevLogIndex;
        while (conflictIndex > 1 &&
               this.log[conflictIndex - 1].term === prevEntry.term) {
          conflictIndex--;
        }
        return {
          term: this.currentTerm,
          success: false,
          conflictIndex
        };
      }
    }

    // 追加新日志条目（处理冲突）
    for (let i = 0; i < request.entries.length; i++) {
      const entry = request.entries[i];
      const existingIndex = entry.index - 1;

      if (existingIndex < this.log.length) {
        // 已有条目：检查任期是否匹配
        if (this.log[existingIndex].term !== entry.term) {
          // 任期冲突：删除该条目及其后的所有条目
          this.log = this.log.slice(0, existingIndex);
          this.log.push(entry);
        }
        // 任期匹配：跳过
      } else {
        // 新条目：追加
        this.log.push(entry);
      }
    }

    // 更新 commitIndex
    if (request.leaderCommit > this.commitIndex) {
      this.commitIndex = Math.min(request.leaderCommit, this.log.length);
      this.applyToStateMachine();
    }

    return { term: this.currentTerm, success: true };
  }
}
```

日志复制中有几个关键设计。`prevLogIndex`和`prevLogTerm`用于一致性检查——跟随者只有在自己日志的`prevLogIndex`位置存在且任期匹配时，才接受新条目。如果不匹配，跟随者返回冲突索引，领导者据此递减`nextIndex`并重试。这个回退机制保证了日志最终一致。

`checkCommit`方法判断是否有过半节点已复制该日志条目：

```javascript
class RaftNode {
  // ... 之前的代码

  checkCommit() {
    const lastLog = this.getLastLogInfo();

    for (let n = lastLog.index; n > this.commitIndex; n--) {
      // 只检查当前任期的条目（Raft安全性约束）
      if (this.log[n - 1].term !== this.currentTerm) continue;

      // 统计已复制该条目的节点数
      let count = 1;  // 自己
      for (const peer of this.peers) {
        if (this.matchIndex[peer.id] >= n) {
          count++;
        }
      }

      if (count > this.clusterSize / 2) {
        this.commitIndex = n;
        return true;
      }
    }
    return false;
  }

  applyToStateMachine() {
    while (this.lastApplied < this.commitIndex) {
      this.lastApplied++;
      const entry = this.log[this.lastApplied - 1];
      this.stateMachine[entry.index] = entry.command;
      console.log(`节点 ${this.id} 应用日志 [${entry.index}]: ${entry.command}`);
    }
  }
}
```

注意`checkCommit`中有一个关键约束：**领导者只能直接提交当前任期的日志条目**。这是Raft安全性约束的核心。如果领导者试图提交之前任期的条目（通过计数多数派），可能导致已提交的条目被覆盖。Raft通过"只提交当前任期条目"来间接提交之前任期的条目——当当前任期的条目被提交时，之前的所有条目也随之被提交。

五、安全性约束

Raft的安全性由五条规则保证：

**选举安全性**：每个任期内最多一个领导者。这由"每个节点每个任期只能投一票"保证。

**领导者只追加**：领导者从不覆盖或删除自己的日志条目，只追加新条目。

**日志匹配**：如果两个日志在某个索引处有相同的任期，则该索引之前的所有条目都相同。这由`prevLogIndex`和`prevLogTerm`的一致性检查保证。

**领导者完整性**：如果某个日志条目在某个任期内被提交，那么之后所有任期的领导者都包含该条目。这由选举时的日志新旧比较保证。

**状态机安全性**：如果某个节点将某个索引处的日志条目应用到状态机，则其他节点不会在该索引处应用不同的条目。这由上述四条规则共同保证。

其中领导者完整性是Raft最精妙的设计。它的证明如下：

假设任期T的领导者提交了索引N的条目，但任期U（U>T）的领导者没有包含该条目。任期U的领导者选举时，必须获得多数派选票。而任期T的条目已提交，说明多数派节点已复制该条目。这两个多数派必然有交集。交集中的节点在投票时，会拒绝日志比它旧的候选者。因此，任期U的领导者不可能不包含索引N的条目。矛盾。

六、网络分区与脑裂处理

网络分区是分布式系统中最棘手的问题。当集群被分为两个分区时，每个分区可能选出一个领导者，形成"脑裂"。

Raft通过多数派机制防止脑裂。只有获得多数派选票的候选者才能成为领导者。如果集群有5个节点，分为3节点和2节点两个分区，3节点的分区可以选出领导者（3 > 5/2），2节点的分区无法选出领导者。旧领导者如果在少数派分区，无法获得多数派确认，其提交操作会超时。

```javascript
class RaftNode {
  // ... 之前的代码

  // 处理网络分区恢复
  onNetworkHeal() {
    // 如果自己是领导者但任期较低，转为跟随者
    for (const peer of this.peers) {
      // 通过心跳响应检查对方任期
      const request = {
        type: 'AppendEntries',
        term: this.currentTerm,
        leaderId: this.id,
        prevLogIndex: 0,
        prevLogTerm: 0,
        entries: [],
        leaderCommit: this.commitIndex
      };

      this.transport.send(peer, request, (response) => {
        if (response.term > this.currentTerm) {
          this.currentTerm = response.term;
          this.state = NodeState.FOLLOWER;
          this.votedFor = null;
        }
      });
    }
  }
}
```

当网络分区恢复后，旧领导者发现新领导者的任期更高，会立即转为跟随者。新领导者通过日志复制将旧领导者的未提交条目覆盖或保留——如果旧领导者的条目与多数派不一致，会被覆盖；如果一致，会被保留。

七、持久化模拟

Raft要求节点在响应RPC之前将`currentTerm`、`votedFor`和`log`持久化到稳定存储。这保证了节点重启后不会丢失关键状态。

```javascript
class PersistentStorage {
  constructor() {
    this.data = {};
  }

  save(key, value) {
    // 模拟磁盘写入
    this.data[key] = JSON.stringify(value);
  }

  load(key) {
    const value = this.data[key];
    return value ? JSON.parse(value) : null;
  }
}

class RaftNode {
  // ... 之前的代码

  persist() {
    this.storage.save(`${this.id}:term`, this.currentTerm);
    this.storage.save(`${this.id}:votedFor`, this.votedFor);
    this.storage.save(`${this.id}:log`, this.log);
  }

  restore() {
    const term = this.storage.load(`${this.id}:term`);
    const votedFor = this.storage.load(`${this.id}:votedFor`);
    const log = this.storage.load(`${this.id}:log`);

    if (term !== null) this.currentTerm = term;
    if (votedFor !== null) this.votedFor = votedFor;
    if (log !== null) this.log = log;
  }
}
```

在实际实现中，持久化必须在发送RPC响应之前完成。这是Raft正确性的关键——如果节点在持久化之前崩溃，可能丢失投票信息，导致同一任期投出两票。

八、完整集群模拟

把所有部分串联起来，模拟一个五节点集群：

```javascript
class RaftCluster {
  constructor(size) {
    this.size = size;
    this.nodes = [];
    this.transport = new NetworkTransport();

    for (let i = 0; i < size; i++) {
      const node = new RaftNode(i, size);
      node.transport = this.transport;
      node.storage = new PersistentStorage();
      this.nodes.push(node);
    }

    // 设置对等节点
    for (const node of this.nodes) {
      node.peers = this.nodes.filter(n => n.id !== node.id);
    }
  }

  start() {
    // 启动选举定时器
    for (const node of this.nodes) {
      this.startElectionTimer(node);
    }
  }

  startElectionTimer(node) {
    const check = () => {
      if (node.state === NodeState.LEADER) {
        setTimeout(check, 50);
        return;
      }

      const elapsed = Date.now() - node.lastHeartbeat;
      if (elapsed > node.electionTimeout) {
        node.onElectionTimeout();
        node.electionTimeout = 150 + Math.random() * 150;
        node.lastHeartbeat = Date.now();
      }

      setTimeout(check, 10);
    };
    setTimeout(check, node.electionTimeout);
  }

  // 查找当前领导者
  getLeader() {
    return this.nodes.find(n => n.state === NodeState.LEADER);
  }

  // 客户端提交命令
  async submit(command) {
    const leader = this.getLeader();
    if (!leader) {
      throw new Error('当前没有领导者');
    }
    return leader.appendCommand(command);
  }
}

// 测试
async function testRaft() {
  const cluster = new RaftCluster(5);
  cluster.start();

  // 等待选举完成
  await new Promise(resolve => setTimeout(resolve, 500));

  const leader = cluster.getLeader();
  console.log(`当前领导者: 节点 ${leader.id}`);

  // 提交几条命令
  await cluster.submit('set x = 1');
  await cluster.submit('set y = 2');
  await cluster.submit('set z = 3');

  // 检查所有节点的状态机
  for (const node of cluster.nodes) {
    console.log(`节点 ${node.id} 状态机:`, node.stateMachine);
  }
}

testRaft();
```

九、性能分析与优化方向

Raft的性能瓶颈主要有三个：

**心跳频率**。领导者需要定期发送心跳维持权威。心跳太频繁浪费带宽，太稀疏导致选举超时。典型配置是心跳间隔50-100ms，选举超时150-300ms。

**日志复制的批处理**。领导者可以将多个日志条目合并为一个AppendEntries请求，减少RPC次数。生产级实现（如etcd）支持批量复制。

**日志压缩**。随着日志增长，存储和复制成本增加。Raft通过快照（Snapshot）机制压缩日志——将状态机当前状态序列化为快照，删除快照之前的日志条目。新节点加入时通过快照快速同步。

```javascript
class RaftNode {
  // ... 之前的代码

  // 创建快照
  createSnapshot() {
    const snapshot = {
      lastIncludedIndex: this.lastApplied,
      lastIncludedTerm: this.log[this.lastApplied - 1].term,
      stateMachine: { ...this.stateMachine }
    };

    // 删除快照之前的日志
    this.log = this.log.slice(this.lastApplied);

    return snapshot;
  }

  // 从快照恢复
  restoreFromSnapshot(snapshot) {
    this.lastApplied = snapshot.lastIncludedIndex;
    this.commitIndex = snapshot.lastIncludedIndex;
    this.stateMachine = { ...snapshot.stateMachine };
    // 重建日志（保留快照之后的条目）
  }
}
```

十、总结

从节点状态机到领导者选举，从日志复制到安全性约束，从网络分区处理到持久化模拟——这个Raft共识算法的核心代码不到500行，但覆盖了分布式共识的全部关键机制。

Raft的核心设计哲学是"可理解性"。它将共识问题分解为三个相对独立的子问题，每个子问题都有清晰的算法描述和正确性证明。任期作为逻辑时钟、日志匹配作为一致性检查、多数派作为提交条件——这些机制共同保证了分布式系统在部分节点故障时仍然能够达成一致。

理解了这套最小内核，再去看etcd的Raft实现、Consul的Serf、TiKV的Multi-Raft，会发现它们在架构上遵循的是同一套思路——领导者选举、日志复制、快照压缩。差异只在工程细节：etcd用boltdb持久化日志，Consul用gossip协议传播成员变更，TiKV用Multi-Raft支持海量分片。Raft是这一切的起点。