Raft 算法：从选主到日志复制的共识协议

一个服务只有一台机器时，状态放在本机就够了；但机器会宕机、磁盘会损坏、网络会中断。为了提高可用性，我们通常让多台服务器保存同一份状态。新的困难随之出现：客户端发来一条写命令后，谁来决定执行顺序？部分服务器失联时还能不能继续？旧领导者恢复后，怎样避免它用过期数据覆盖新结果？

Raft 是一种为可理解性设计的共识算法。它把问题拆成领导者选举、日志复制和安全性三部分：正常情况下所有写操作先经过领导者；领导者把操作按顺序写入日志并复制给多数服务器；只要仍有多数服务器互相通信，集群就能在不产生冲突决定的前提下继续工作。

Raft 到底解决什么问题

从复制状态机开始

确定性的状态机收到同一串命令，就会得到同一结果。例如一个键值服务从空状态开始，依次执行 set x 1、set x 2、delete x，最终状态一定相同。Raft 不直接复制整个内存，而是让服务器就“命令日志的顺序”达成一致，再由每台服务器依次应用日志。

客户端set x=7把写请求发送给当前领导者

共识层日志 8→多数派Raft 决定命令位于哪个日志位置

状态机节点 A节点 B节点 C各节点按相同顺序应用已提交命令

故障模型与不解决的事情

经典 Raft 通常假设服务器可能崩溃、重启，消息可能延迟、丢失、重复或乱序，但节点不会恶意伪造消息。它属于崩溃故障容错协议，不是拜占庭容错协议。

• 服务器重启后，持久化的任期、投票和日志仍然存在；
• 网络分区可能把集群切成多个互不通信的部分；
• 时钟不需要完全同步，正确性不依赖精确时间；
• 恶意节点、任意数据篡改和身份伪造需要 BFT、安全认证等额外机制；
• Raft 负责日志共识，业务状态机仍需保证命令执行是确定性的。

多数派为什么重要

Raft 的选举和提交都依赖多数派。含有 N 个节点的集群，多数派大小为 floor(N / 2) + 1。任意两个多数派一定至少共享一个节点，这个交集把不同时间做出的决定连接起来。

节点数从 3 增加到 4，多数派从 2 增加到 3，却仍然只能容忍 1 个故障，所以 Raft 集群常使用奇数个投票节点。偶数配置不是错误，只是通常不能带来对应的容错收益。

角色、任期与心跳

每个服务器在任一时刻处于三种角色之一：

• Follower：跟随者，正常情况下只响应领导者和候选人的请求；
• Candidate：候选人，选举超时后发起新一轮选举；
• Leader：领导者，接收客户端写请求并负责日志复制。

时间被划分为连续递增的任期（term）。每个任期最多有一个领导者，也可能因为选票分裂而没有领导者。任期像逻辑时钟：节点看到更大的任期就知道自己的信息已经过期，立即更新任期并转为跟随者。

正常状态Follower持续收到合法心跳就保持跟随

选举超时Follower→Candidate任期加一、投自己一票、向其他节点拉票

赢得多数Candidate→Leader立即发送空 AppendEntries 宣告领导权

更大任期任意角色→Follower旧领导者也必须退位

服务器保存哪些状态

领导者选举

选举过程

1. 跟随者在选举超时前没有收到合法心跳，就转为候选人；
2. 候选人把 currentTerm 加一，给自己投票并重置超时；
3. 它向其他节点发送 RequestVote；
4. 获得集群多数票后成为领导者，并立即发送心跳；
5. 若收到更高任期消息，立即退回跟随者；若本轮无人过半，超时后开始新任期。

为什么选举超时要随机

如果所有跟随者都使用完全相同的固定超时，它们可能同时成为候选人，各自只拿到自己的票，之后又同时重试，持续分票。随机选举超时让某个节点大概率先行动并在其他节点参选前获得选票。

广播一次 RPC 的时间  ≪  选举超时  ≪  节点平均故障间隔

示例只是量级说明：
心跳间隔 50 ms，选举超时随机取 150~300 ms。
真实参数必须依据网络尾延迟、磁盘抖动和部署环境测量。

时间参数影响的是活性与稳定性，不是安全性。超时太短会在网络抖动时频繁换主；太长则真正故障后的恢复较慢。

RequestVote 的关键字段

接收者只有在请求任期不旧、当前任期尚未投给别人，并且候选人日志至少和自己一样新时才投票。日志新旧先比较最后日志的任期，任期相同再比较索引：

bool upToDate =
    candidateLastTerm > myLastTerm ||
    (candidateLastTerm == myLastTerm &&
     candidateLastIndex >= myLastIndex);

这里不能只比较日志条数。一个日志更短的候选人，最后日志任期可能更大，因此反而更新。

日志复制

从客户端命令到提交

1. 客户端把写命令发送给领导者；
2. 领导者把命令追加到本地日志，但此时还不能回复成功；
3. 领导者并行向跟随者发送 AppendEntries；
4. 日志复制到多数节点后，领导者推进 commitIndex；
5. 各节点按索引顺序把已提交但未应用的日志交给状态机；
6. 领导者向客户端返回结果，并通过后续心跳传播新的提交位置。

追加A: 8B: 7C: 7D: 7E: 7领导者 A 先写本地，尚未提交

复制A: 8B: 8C: 8D: 7E: 7A、B、C 已构成 3/5 多数派

提交commitIndex = 8D、E 可以稍后追赶，不阻塞本次提交

AppendEntries 的一致性检查

领导者发送新日志时，还会携带新日志之前的位置：

• prevLogIndex：新条目之前的日志索引；
• prevLogTerm：该位置日志所属任期；
• entries[]：需要追加的零条或多条日志，空数组就是心跳；
• leaderCommit：领导者已经提交到哪里。

跟随者只有在本地 prevLogIndex 处存在日志且任期等于 prevLogTerm 时才接受。若某个索引处已有日志却与领导者的新条目任期冲突，跟随者删除该条及其后的所有条目，再追加领导者日志。

索引 3 的任期一致，说明此前日志前缀一致；索引 4 首次冲突，因此跟随者从索引 4 开始截断，再复制领导者的任期 2、4、4 条目。

nextIndex 与 matchIndex

领导者为每个跟随者维护 nextIndex。复制失败时向前回退，直到找到双方一致的前缀；成功后更新 matchIndex 和下一发送位置。基础实现每次回退一个索引，正确但慢。工程实现通常让跟随者返回冲突任期及该任期第一条日志索引，使领导者一次跳过整段冲突任期。

最容易写错的提交规则

领导者不能仅因为“某条旧任期日志已经存在于多数节点”就直接用计数把它标记为已提交。Raft 的规则是：

这是为了避免下面的危险序列：旧领导者把某条日志复制到多数节点前后发生换主；由于不同多数派在不同时间的成员组合不同，某个日志仍可能被一个日志更新的新领导者覆盖。当前任期日志一旦被多数派接受，选举限制保证未来领导者一定包含它，它以及之前前缀才真正安全。

// 领导者推进提交索引时必须检查 log[n].term == currentTerm
for (std::size_t n = lastLogIndex(); n > commitIndex; --n) {
    if (log[n].term != currentTerm) continue;
    if (replicatedOnMajority(n)) {
        commitIndex = n;
        break;
    }
}

四条核心安全性质

选举安全性

同一任期最多产生一个领导者。每个节点在同一任期最多投一票，而两个候选人不可能各自获得两个互不相交的多数派。

日志匹配性质

如果两个日志在相同索引上的任期相同，那么这两个条目相同，并且它们之前的所有日志也相同。prevLogIndex + prevLogTerm 检查和冲突截断共同维持这条性质。

领导者完整性

一条日志如果在某任期提交，那么之后更高任期的所有领导者都包含它。原因是已提交日志位于一个多数派上，而新领导者也必须获得一个多数派；两者存在交集，加上 RequestVote 的日志新旧限制，缺少已提交日志的候选人无法当选。

状态机安全性

如果某个节点已经在日志索引 i 应用一条命令，那么其他节点不会在同一索引应用不同命令。领导者完整性保证已提交日志不会被未来领导者替换，各节点又严格按索引顺序应用日志。

网络分区时会发生什么

假设 5 个节点被分成 {A, B} 和 {C, D, E}。旧领导者 A 位于少数派：

1. A 可能暂时仍认为自己是领导者，也可能接收客户端命令；
2. 但 A 只能联系 2 个节点，无法形成 3 个节点的多数派，所以新日志不能提交；
3. C、D、E 超时后可在更高任期选出新领导者并继续提交；
4. 网络恢复后，A 收到更高任期消息立即退位；
5. A 上未提交且冲突的尾部日志会被新领导者覆盖。

因此 Raft 允许短时间内有多个节点自认为领导者，但只有拥有多数派且任期最新的领导者能推进提交。安全性要求的是不会出现两个冲突的已提交决定，而不是任何瞬间全世界都只能看到一个自称领导者的节点。

可编译的 C++17 教学核心

下面代码实现 RequestVote、AppendEntries 的核心状态转换，以及领导者推进提交位置的规则。它使用索引 0 的哨兵日志简化边界处理，重点展示协议不变量；生产实现还需要定时器、RPC、并发控制、稳定存储、快照和成员变更。

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <optional>
#include <string>
#include <utility>
#include <vector>

using Term = std::uint64_t;
using LogIndex = std::size_t;

struct LogEntry {
    Term term{};
    std::string command;
};

enum class Role { Follower, Candidate, Leader };

struct RequestVoteArgs {
    Term term{};
    int candidateId{};
    LogIndex lastLogIndex{};
    Term lastLogTerm{};
};

struct RequestVoteReply {
    Term term{};
    bool voteGranted{};
};

struct AppendEntriesArgs {
    Term term{};
    int leaderId{};
    LogIndex prevLogIndex{};
    Term prevLogTerm{};
    std::vector<LogEntry> entries;
    LogIndex leaderCommit{};
};

struct AppendEntriesReply {
    Term term{};
    bool success{};
};

class RaftNode {
public:
    explicit RaftNode(int id) : id_(id) {
        log_.push_back({0, "<sentinel>"});
    }

    RequestVoteReply onRequestVote(const RequestVoteArgs& args) {
        if (args.term < currentTerm_) return {currentTerm_, false};
        if (args.term > currentTerm_) becomeFollower(args.term);

        const bool upToDate =
            args.lastLogTerm > lastLogTerm() ||
            (args.lastLogTerm == lastLogTerm() &&
             args.lastLogIndex >= lastLogIndex());
        const bool canVote =
            !votedFor_.has_value() || votedFor_ == args.candidateId;

        if (canVote && upToDate) {
            votedFor_ = args.candidateId;
            // 生产实现：先持久化 term 和 votedFor，再回复并重置选举定时器。
            return {currentTerm_, true};
        }
        return {currentTerm_, false};
    }

    AppendEntriesReply onAppendEntries(const AppendEntriesArgs& args) {
        if (args.term < currentTerm_) return {currentTerm_, false};

        if (args.term > currentTerm_) becomeFollower(args.term);
        role_ = Role::Follower;
        leaderId_ = args.leaderId;
        // 收到当前任期的合法领导者消息后，应重置选举定时器。

        if (args.prevLogIndex >= log_.size()) {
            return {currentTerm_, false};
        }
        if (log_[args.prevLogIndex].term != args.prevLogTerm) {
            return {currentTerm_, false};
        }

        LogIndex index = args.prevLogIndex + 1;
        std::size_t offset = 0;

        while (offset < args.entries.size() && index < log_.size()) {
            if (log_[index].term != args.entries[offset].term) {
                log_.resize(index);
                break;
            }
            ++index;
            ++offset;
        }
        log_.insert(log_.end(),
                    args.entries.begin() + static_cast<std::ptrdiff_t>(offset),
                    args.entries.end());
        // 生产实现：先持久化新增日志，再返回成功。

        if (args.leaderCommit > commitIndex_) {
            commitIndex_ = std::min(args.leaderCommit, lastLogIndex());
        }
        return {currentTerm_, true};
    }

    void advanceLeaderCommit(const std::vector<LogIndex>& followerMatch,
                             std::size_t clusterSize) {
        assert(role_ == Role::Leader);
        for (LogIndex n = lastLogIndex(); n > commitIndex_; --n) {
            if (log_[n].term != currentTerm_) continue;

            std::size_t replicated = 1;  // 领导者自己
            for (LogIndex match : followerMatch) {
                if (match >= n) ++replicated;
            }
            if (replicated * 2 > clusterSize) {
                commitIndex_ = n;
                break;
            }
        }
    }

    void startLeaderForTest(Term term) {
        currentTerm_ = term;
        votedFor_ = id_;
        role_ = Role::Leader;
    }

    void appendLocalForTest(Term term, std::string command) {
        log_.push_back({term, std::move(command)});
    }

    Term currentTerm() const { return currentTerm_; }
    LogIndex commitIndex() const { return commitIndex_; }
    LogIndex lastLogIndex() const { return log_.size() - 1; }
    Term termAt(LogIndex index) const { return log_.at(index).term; }

private:
    Term lastLogTerm() const { return log_.back().term; }

    void becomeFollower(Term newTerm) {
        if (newTerm > currentTerm_) {
            currentTerm_ = newTerm;
            votedFor_.reset();
        }
        role_ = Role::Follower;
        leaderId_.reset();
    }

    int id_{};
    Term currentTerm_{};
    std::optional<int> votedFor_;
    std::vector<LogEntry> log_;
    LogIndex commitIndex_{};
    LogIndex lastApplied_{};
    Role role_{Role::Follower};
    std::optional<int> leaderId_;
};

int main() {
    RaftNode follower(2);
    follower.appendLocalForTest(2, "set x 1");

    const auto vote = follower.onRequestVote({3, 7, 1, 2});
    assert(vote.voteGranted && follower.currentTerm() == 3);

    const auto append = follower.onAppendEntries(
        {3, 7, 1, 2, {{3, "set x 2"}}, 1});
    assert(append.success);
    assert(follower.lastLogIndex() == 2);
    assert(follower.commitIndex() == 1);

    // 更高任期领导者在索引 2 产生冲突，旧尾部必须被替换。
    const auto replace = follower.onAppendEntries(
        {4, 9, 1, 2, {{4, "set x 3"}}, 2});
    assert(replace.success);
    assert(follower.termAt(2) == 4);
    assert(follower.commitIndex() == 2);

    RaftNode leader(1);
    leader.startLeaderForTest(5);
    leader.appendLocalForTest(2, "old");
    leader.appendLocalForTest(5, "current");
    leader.advanceLeaderCommit({2, 2, 0, 0}, 5);
    assert(leader.commitIndex() == 2);

    std::cout << "Raft core checks passed";
}

客户端语义仍需额外设计

重试与重复执行

客户端把命令发给领导者后，可能在收到响应前断线。命令或许已经提交，客户端却不知道；若它直接重试，状态机可能执行两次扣款。常见方案是为每个客户端维护唯一标识和单调递增序列号，状态机缓存最近响应，让重复请求返回旧结果而不是再次执行。

线性一致读

跟随者本地读取可能返回旧数据，旧领导者也可能在分区中误以为自己仍掌权。线性一致读通常使用以下方式之一：

• 把读也写入日志，简单但成本较高；
• 领导者先通过多数派心跳确认自己仍是当前领导者，再读取已应用状态；
• 使用经过严格实现的 ReadIndex 或租约读；租约读还需要额外的时钟假设。

仅仅“从 Leader 读”并不足以自动保证线性一致，因为网络分区中的旧领导者可能暂时还没有看到更大任期。

日志压缩与快照

日志不能无限增长。节点可以在状态机应用到某个索引后生成快照，保存该索引、对应任期和业务状态，再丢弃更早日志。若跟随者落后到领导者已删除的日志之前，领导者通过 InstallSnapshot 发送快照，而不是继续用 AppendEntries 逐条追赶。

• 快照必须与 lastIncludedIndex、lastIncludedTerm 一起保存；
• 快照文件应原子替换，避免崩溃后只留下半个文件；
• 安装快照和应用日志不能并发破坏状态机顺序；
• 压缩阈值需要平衡磁盘空间、恢复时间和快照开销。

成员变更为什么不能直接替换名单

如果节点各自在不同时间从旧配置切换到新配置，旧配置多数派和新配置多数派可能互不相交，从而同时选出两个领导者。Raft 使用联合共识过渡：

1. 先提交同时包含旧配置和新配置的联合配置；
2. 联合阶段的决定必须分别获得旧配置多数和新配置多数；
3. 联合配置提交后，再提交只包含新配置的最终配置。

工程中还常使用 learner / non-voting member 先同步新节点，追上后再赋予投票权，避免一个空日志新节点立即拖慢多数派。

常见误区

1. “领导者写本地就算成功”：未复制到规定多数派的日志可能被未来领导者覆盖。
2. “日志最长的人一定最新”：Raft 先比较最后日志任期，再比较索引。
3. “心跳只是保活包”：空 AppendEntries 仍携带任期、前一日志位置和提交索引，并执行一致性检查。
4. “看到同任期领导者就清空 votedFor”：只有进入更高任期才重置投票；否则可能在同一任期投两票。
5. “多数副本都有就一定能提交”：领导者直接按多数计数推进时，还必须检查目标日志属于当前任期。
6. “Raft 保证所有请求只执行一次”：协议保证日志顺序，客户端去重需要会话编号等额外设计。
7. “从任意副本读取都一样”：跟随者可能落后；线性一致读需要专门协议。
8. “加节点就是改配置文件”：投票成员变化必须通过安全的配置变更协议。

实现与测试清单

除了普通单元测试，Raft 很适合使用确定性模拟器：把网络投递、定时器和磁盘结果都变成可控制事件，再随机生成故障序列，持续检查“同一索引不能应用不同命令”“提交索引不能回退”等不变量。更严格的系统还会使用模型检查验证状态空间。

最后的记忆线索

1. 所有命令先排进一份有序日志，再驱动复制状态机；
2. 任期识别新旧，节点看到更大任期就退回跟随者；
3. 候选人的日志必须足够新，才有资格获得选票；
4. AppendEntries 用前一索引和任期验证日志前缀；
5. 当前任期日志复制到多数派后才能直接推进提交；
6. 多数派交集把已提交历史带入未来领导者；
7. 快照、成员变更、线性读和客户端去重都是完整实现不可忽略的部分。

Raft 的“容易理解”不等于“容易正确实现”。它把证明拆成了可以分别理解的规则，但每条规则——任期持久化、投票限制、日志匹配、当前任期提交——都是安全性链条上的一环。真正掌握 Raft，不只是会画三种角色，而是能解释每个字段在阻止哪一种错误历史。

延伸阅读：In Search of an Understandable Consensus Algorithm。