Raft

Raft 用于复制状态机：多个节点对一串命令形成一致的已提交顺序，再按同样顺序执行确定性的状态转换。它容忍的是协议假设范围内的宕机、重启和网络异常，不是任意恶意节点。

学习时先分清三个事实：日志已经存到某个节点、日志已经被协议提交、命令已经应用到状态机。这三个时刻通常不同。Raft 保证已提交历史不会被后来的合法 leader 改写，允许未提交尾部暂时分歧并在恢复时被替换。

任期与角色：新鲜度不是物理时间

term 是单调递增的逻辑任期号。Follower 在选举超时后进入 Candidate，增加 term 并发起投票；取得该配置要求的多数票后成为 Leader。随机超时降低同时竞争的概率，不保证一次选举必成功，也没有适用于所有网络的固定毫秒数。

节点收到更高 term 的协议消息后更新任期并退回 follower。隔离的旧 leader 未必立即收到该消息，可能仍自认为在任；安全性依赖它无法取得所需 quorum 完成新的合法提交，而非所有节点立即知道谁是 leader。外部资源访问还需要相应 fencing，不能只依靠进程里的角色变量。

必须保留哪些状态

持久状态发生变化时，要在依赖该变化的成功应答之前满足持久化要求；不等于每个无状态变化的心跳都必须单独 fsync。若状态机已经持久保存结果，恢复时不能把对应命令盲目执行第二次。

选举：一人一票还不够

候选者发送末尾日志的 (lastLogTerm,lastLogIndex)。投票者在任期与投票条件满足时，还要确认候选日志至少与自身一样新：先比较最后一条日志的 term，term 相同再比较 index。单看日志长度不够，一份更长的旧任期尾部不一定更有资格。

同任期每个节点最多投给一个候选者，两个多数集相交，因此同任期不可能有两位都获得合法多数票的 leader。跨任期已提交日志的保留，则还需要日志匹配、选举限制以及提交规则一起证明。不能把“日志更新”直接当作“必然包含任意旧条目”。

日志复制：先找到共同前缀

Leader 的 AppendEntries 携带前一条日志的 index 与 term。Follower 只有在该前缀检查通过后才接收后续条目；遇到同 index 不同 term 的冲突时，删除冲突条目及其之后的尾部，再追加新内容。

拒绝后 leader 调整 nextIndex 重新寻找共同前缀，实现可以用冲突任期等信息加速回退。不能每收到一个较短的心跳就截断 follower：没有条目冲突时，消息中没有包含某段尾部并不是删除它的理由。

日志匹配性质是：若两份日志在同一 index 具有相同 term，则此前的前缀一致。这使 leader 能以简短的前缀检查逐步建立一致日志，而不用每次比较整个历史。

空心跳为什么不能顺手删除尾部

以下只模拟 AppendEntries 的日志与提交位置部分，假设请求任期和 leader 身份已经通过协议检查。日志用 (term, command) 表示，位置 0 放一个哨兵；没有实现选举、持久化或快照后的索引换算。

def append_entries(log, committed, prev_index, prev_term, entries, leader_commit):
    if not 0 <= prev_index < len(log) or log[prev_index][0] != prev_term:
        return False, list(log), committed
    updated = list(log)
    for index, entry in enumerate(entries, start=prev_index + 1):
        if index < len(updated) and updated[index][0] != entry[0]:
            if index <= committed:
                raise ValueError("合法 Raft 历史不能冲突到已提交前缀")
            del updated[index:]
        if index == len(updated):
            updated.append(entry)
        elif updated[index] != entry:
            raise ValueError("同 index、同 term 却不同命令，违反输入假设")
    matched_end = prev_index + len(entries)
    new_commit = max(committed, min(leader_commit, matched_end))
    return True, updated, new_commit

log = [(0, "sentinel"), (1, "a"), (2, "b"), (2, "c"), (2, "d")]
ok, same, commit = append_entries(log, 1, 2, 2, [], 4)
assert ok and same == log and commit == 2
ok, fixed, commit = append_entries(log, 2, 2, 2, [(3, "new-c")], 3)
assert ok and fixed == log[:3] + [(3, "new-c")] and commit == 3
assert append_entries(fixed, 3, 2, 2, [(3, "new-c")], 3) == (True, fixed, 3)
assert append_entries(log, 2, 2, 99, [], 4) == (False, log, 2)

第一次调用只证明位置 2 的前缀匹配，既不能因为消息没有携带 3、4 就删除它们，也不能因为 follower 本地恰好有 3、4 就把提交推进到 4。第二次携带了位置 3、term 3，才与本地 term 2 产生真正冲突，于是删掉 3 及之后的旧尾部，再追加新条目。

重复第二条请求不会追加第二份命令。实现需要区分“已经存在的匹配条目”“新条目”和“冲突条目”，不能用收到的整个后缀无条件覆盖本地日志。上述处理对应 Raft Figure 2 的 AppendEntries 规则。

提交：为什么必须看当前任期

在基本多数配置下，leader 可以选取 N 推进 commitIndex，条件包括：N 大于当前提交位置、至少多数节点的 matchIndex≥N，并且 log[N].term == currentTerm。提交 N 同时提交其前面的日志前缀。

旧任期条目即使暂时存在于多数节点，也不能仅凭当前看到的副本数直接宣布提交。原因是投票按末尾 term 优先比较；另一个带有更高任期尾部的候选者，仍可能在某些执行中赢得后续选举并覆盖未提交条目。当前任期条目多数复制提供了安全推进提交前缀所需的附加条件。

一个实际可读的例子：新 leader 当前 term 为 7，继承 index 40、term 6 的条目。它将 term 7 的 no-op 写入 index 41 并安全提交后，index 40 随前缀一起提交。不需要把旧命令换成新 term 重新执行。严格论证与反例见 Raft 论文第 5.4 节和 Figure 8。

多数派位置到了 40，也可能仍只能提交到 39

五节点 leader 当前任期为 7，日志 40 属于任期 6，41 是任期 7 的 no-op。已提交到 39。如果复制进度是 [41,40,40,39,38]，虽然 40 有三个副本，当前任期条件仍不满足；等 41 也到达多数派后，才能连同 40 一起推进。

def advance_commit(committed, current_term, terms, matches):
    majority = len(matches) // 2 + 1
    eligible = [index for index, term in terms.items()
                if index > committed and term == current_term
                and sum(position >= index for position in matches) >= majority]
    return max([committed] + eligible)

terms = {39: 6, 40: 6, 41: 7}
assert advance_commit(39, 7, terms, [41, 40, 40, 39, 38]) == 39
assert advance_commit(39, 7, terms, [41, 41, 41, 39, 38]) == 41
assert advance_commit(41, 7, terms, [41, 41, 41, 39, 38]) == 41
assert (7, 10) > (6, 100)  # 选举时先比末尾 term，不是先比日志长度

这里 matches 包含 leader 自身且来自同一固定五节点配置，没有遗漏节点或把重复 ACK 当成多个副本。若正在成员变更，不能继续套用一个固定多数人数公式，而要使用当前配置的 quorum 规则。这个筛选函数展示推进条件，不承担完整安全性证明。

复制到了多数，提交线为什么还没动？

把复制证据画在提交条件旁边，可以避免把“副本够多”误当作完整证明。下面各滑杆选择一份独立的复制进度快照，修改时重新从已提交的 39 计算；它不表示真实节点丢失了已经确认的持久日志。应用按钮再单独展示：可提交前缀扩大后，状态机仍需执行这些命令。

$$\#\{i:{\mathrm{matchIndex}}_i\ge n\}\ge 3\wedge \mathrm{term}(n)=7$$

应用与客户端重试

节点按已提交顺序推进 lastApplied。状态机执行必须确定：随机数、当前时间和外部查询结果若影响状态，应通过明确协议纳入命令或一致输入，不能让每个副本自由取不同值。

即使 Raft 日志安全，客户端仍可能在命令已经提交后丢失响应，再次提交同一业务操作。复制状态机通常需要请求 ID 与结果去重。Raft 本身不把两个重复业务请求自动视为同一条命令。

线性一致读取：自认为是 leader 不够

隔离的旧 leader 可能拥有过时状态。为了安全读取，需要确认本轮读取所依赖的 leader 权限仍有效，并等待状态机应用到相应的安全提交位置。

基于 quorum 的读取方式通常在 leader 已确认当前任期的提交边界后，联系多数节点建立读取屏障，再等待本地 lastApplied 达到安全位置。租约读取可以减少部分通信，但其正确性需要协议规定的时间与租约假设。详见实际系统。

快照：保留状态和它对应的历史位置

快照记录某个已应用前缀的状态，以及 lastIncludedIndex、lastIncludedTerm 和恢复所需的配置等元数据。快照可靠保存后，才能按协议回收对应旧日志。

落后 follower 若所需日志已被回收，可通过 InstallSnapshot 恢复前缀，再追赶后续日志。安装不能让节点回退到比已应用状态更旧的视图；是否保留后续日志也要检查边界是否匹配。快照不是任意复制一份正在变化的数据目录。

成员变更：quorum 的定义也在变化

直接把旧集合切成新集合，可能让两个互不相交的多数各自行动。Joint consensus 用联合配置要求旧集合多数与新集合多数同时满足，再过渡到新配置。它不是把两组节点合在一起后，只取总人数的一个多数。

另一类实现将变化限制为安全的单成员步骤，并规定配置在何时生效。具体实现可能支持不同接口，不能仅看到“单节点变更”就跳过其应用顺序和恢复规则。新增副本也常先以不投票的 learner 追赶，避免一个尚无数据的新投票者立即提高 quorum 门槛。

联合配置不是五个人中任选三个

旧配置 {A,B,C}，新配置 {C,D,E}。旧多数 {A,B} 与新多数 {D,E} 可以完全不相交，说明“两个配置各自都用多数”还不够。联合阶段要求一次决定同时获得旧配置至少两个、新配置至少两个节点的确认。

from itertools import combinations
old, new = set("ABC"), set("CDE")

def majority(acks, members):
    return len(acks & members) >= len(members) // 2 + 1

def joint(acks):
    return majority(acks, old) and majority(acks, new)

assert majority(set("ABC"), old | new)  # 五人中的三个
assert not joint(set("ABC"))  # 新配置只有 C，一个确认不够
assert joint(set("ACD"))  # 旧配置 A、C；新配置 C、D
assert not (set("AB") & set("DE"))
all_sets = [set(nodes) for size in range(6) for nodes in combinations("ABCDE", size)]
valid = [acks for acks in all_sets if joint(acks)]
assert all(a & b for a in valid for b in valid)

共享节点 C 的确认可以同时计入两边，但不能把旧侧多出来的 A、B 确认当成新侧的 D、E。这个规则会影响可用性：旧组能组成多数、新组不能时，联合阶段仍不能完成需要联合 quorum 的决定。配置条目何时生效及如何恢复还需遵循完整重配置协议，不能只替换一个多数判断函数。Raft 成员变更

五张票中有三张，仍可能不够

联合条件是两个谓词的“并且”，不是把节点并集当成一个新多数问题。选择 A、B、C 时总共已有三票，但新配置只有 C 一票；再加入 D，才同时满足两侧。反过来，C、D、E 也缺旧配置的一票。原静态图给出配置关系，下面用可选确认集合检验这些边界。

$$|A\cap C_{old}|\ge 2\wedge |A\cap C_{new}|\ge 2$$

速查：几条不能省掉的限制

• 多数持久化的直接提交判断，要满足当前任期条件。
• 选举比较日志的末尾 term，再比较 index。
• Leader 身份不能独自证明本地读足够新。
• 快照、去重状态与成员配置属于完整恢复的一部分。
• 安全性可在通信异常时保持，持续进展仍需要可通信的 quorum 和合适的时间条件。

参考

• In Search of an Understandable Consensus Algorithm。
• Raft 项目与论文入口。

Keywords: Raft, term, election, log matching, commitIndex, ReadIndex, snapshot, joint consensus