朱德平的博客

记录学习和生活

0%

Raft 译文

发表于

原论文：《In Search of an Understandable Consensus Algorithm (Extended Version)》

寻找一种易于理解的一致性算法（扩展版）

斯坦福大学：Diego Ongaro 和 John Ousterhout

摘要

Raft 是一种管理复制日志的一致性算法，功能和性能与 Multi-Paxos 算法相当，但结构上的差异使其更易理解和实现。为提高可理解性，Raft 抽离了一致性算法中的关键模块：leader 选举（leader election）、日志复制（log replication）、安全性（safety），并通过增强一致性来减少必须考虑的一致性状态的数量。此外 Raft 还实现了新的机制让集群节点动态变化，通过重叠大多数（overlapping majorties）来保障其变化安全。

1. 简介

一致性算法能使多节点组成的集群像单机一样工作，哪怕集群内的部分节点不可用。过去十年内 Paxos 协议几乎成为了分布式一致性算法的代名词，但其晦涩难懂且需进行大幅修改才能应用于实际系统中。于是我们实现了更易理解和学习的一致性算法：Raft，为提升可理解性，Raft 分解了一致性算法中的几个模块：leader 选举、日志复制和安全性，并减少了状态机的状态数量（比 Paxos 降低了不确定性的程度，减少了多节点数据不一致的方式）

Raft 和一些现有的一致性算法类似，但也有创新之处：

  • 强 leader：Raft 相比其他一致性算法，赋予了 leader 更高的领导能力，比如日志 entry 只能从 leader 流向其余节点，这种简化版的复制方式让日志更易管理，也让 Raft 更易理解。
  • leader 选举：Raft 使用随机 timer 来选举新 leader，基于算法本身的心跳机制即可实现，还能简化了竞选平票时冲突的处理。
  • 成员关系调整：Raft 为调整成员配置变更使用了联合一致性（joint consensus），在配置切换时集群中新旧配置的大多数节点会重叠，以此保证对外持续可用。

论文剩余章节安排如下：第 2 节介绍复制状态机（replicated state mechine）问题，第 3 节讨论 Paxos 算法的不足之处，第 4 节介绍 Raft 更易理解之处，第 5-8 节解释了 Raft 算法的细节，第 9 节评价了 Raft 算法，第 10 节讨论相关话题。

2. 复制状态机（Replicated state machines）

一致性算法在 《replicated state mechines》 背景下衍生而来。其要求多个主机上的状态机要能生成相同状态的副本，所以哪怕部分主机宕机，整个集群对外依旧可用。复制状态机在分布式系统中常用于解决节点容错相关的问题。如 GFS, HDFS 等大规模系统均使用单一 leader 节点机制，并使用独立的复制状态机来管理 leader 选举和存储配置信息，以实现在 leader 宕机的情况下依旧存活并快速恢复集群状态。复制状态机的应用案例有 Chubby 和 Zookeeper

复制状态机使用复制日志来实现，其结构如下图：

图1：复制状态机结构图。一致性算法管理的是记录客户端状态命令的日志，多台状态机以相同的顺序执行日志中相同的命令，从而产生相同的输出，保持状态一致性。

复制状态机通常基于复制日志实现，如上图中每台服务器（节点）都保存着存储一系列命令的日志，各自日志中的命令相同且顺序一致，所以多个节点执行系列命令的结果都是相同的，因此状态机的状态才能保持一致。

保持复制相同日志就是一致性算法的工作了。某个节点的一致性模块负责接收来自客户端的命令并将其写入自己的日志，同时它还要和其余服务器上的一致性模块进行通信以确保每条命令都以同一顺序写入它们的日志中，即使部分节点已宕机。一旦命令被正确复制，其余节点上的状态机都会以相同顺序应用日志中的命令，并将输出返回给客户端。最终使得多个节点组成的集群就像一台独立且高可靠的状态机。

实际应用中的一致性算法大多有如下特性：

  • 安全性保证（绝不返回错误的结果）：在所有非拜占庭错误下，比如网络延迟、网络分区、丢包、包冗余和包乱序等情况下都要保证安全性。
  • 可用性保证：只要集群中大多数节点正常运行、能相互通信、能与客户端通信，就要保证可用性，因此在 5 个节点的集群中要能容忍 2 个节点不可用。节点不工作即认为不可用，随后它们可能恢复正常存储并重新加入集群。
  • 日志的一致性不依赖于时序性：时钟出错或超高延迟等最坏情况下才会引起可用性问题
  • 尽快响应命令的执行：通常一条命令需尽快在大多数节点响应 RPC 后响应客户端，少部分慢节点不能成为整个系统的性能瓶颈。

3. Paxos 的不足之处

一言以蔽之：Paxos 虽然高效，但过于晦涩难懂。在工程应用中还需进行大量结构调整。

4. 更易于理解的设计

Raft 的几个设计目标：

  • 易于实现并应用在实际系统的开发中
  • 所有情况下保证安全性，大多数情况下保证可用性
  • 大部分操作要保证高效
  • 最重要也最困难的目标：提升可理解性

Raft 使用两种方式提高可理解性：

  • 分解子问题：将一致性问题分解为 leader 选举、日志复制和安全保障。
  • 减少待考虑的状态数量来简化状态空间：尽可能加强系统一致性并降低不确定性。

5. Raft 一致性算法

Raft 是一种用来管理第 2 节所述复制日志的算法。下边的图 2 简要总结了算法内容以便参考，图 3 列出了 Raft 的原则和特性。图中内容将在本节介绍。

Raft 通过选举产生 leader 并让其全权管理复制日志来实现一致性。leader 接收来自客户端的日志条目（log entries），并将这些日志复制到其余节点，同时 leader 还要在保证安全时告知其他节点将日志应用到他们的状态机中。单一 leader 极大简化了复制日志的管理工作，比如它无需和其他节点商议就能决定将新日志放到什么位置，并且限制了数据只能从 leader 流向其余节点。当 leader 不可用后其他节点可重新选举出新 leader

通过单一 leader 的机制，Raft 将一致性问题分解为 3 个独立的子问题：

  • leader 选举：当现有 leader 不可用时要选举出新 leader
  • 日志复制：leader 需接收客户端的请求命令，随后复制到集群中的其他节点，并强制要求其余节点日志与自己保持一致
  • 安全性保证：Raft 保证数据安全源于如下的状态机特性（原文图 3）：任意一个节点在自己的状态机上应用了一条确定的日志，那其他节点的状态机在同一日志索引上不会应用不同的日志（5.4）：
原则 解释
选举安全原则（Leader Election Safety） 每个任期内最多有一个 leader 会被选出
Leader Append-Only 原则 leader 绝不能覆盖或删除自己的日志，对新日志只能进行 append 操作
日志匹配原则（Log Matching） 若两份日志在某个相同索引位置上条目的任期也相同，就认为从两份日志从头到这个索引间的日志都相同。
Leader 完整性原则（Leader Completeness） 若一条日志在某个任期内已提交（commited），那它也一定会出现在所有更高任期的 Leader 中
状态机安全原则（State Mechine Safety） 若一个节点的状态机应用（applied）了给定索引位置的日志，那其余节点在相同索引位置应用的必定也是相同的日志。

图3：Raft 无时无刻都能保障以上特性。

如下 4 个小点是关于 Raft 的简要总结（不包含节点身份变更和日志复制的细节）（原文图 2）

（1）节点的状态

状态 所有节点均持久化存储的状态
currentTerm 节点已知的最后一个任期号（首次启动后从 0 开始递增）
votedFor 当前任期内获得选票的候选人 id（没有则为 null）
log[] 日志条目集合，每个条目包含：待执行的命令、收取日志时 leader 的任期号
状态 所有节点上经常变更的状态
commitIndex 节点上已知的最大 commited 日志索引（从 0 自增）
lastApplied 节点上最后一条被状态机 applied 的日志索引（从 0 自增）
状态 leader 中易变更的状态（选举后会重新初始化）
nextIndex[] 对其他节点，分别记录下一个要发送的日志索引（初值为 leader 最后一条日志的索引 +1）
matchIndex[] 对其他节点，分别记录已成功 replicated（复制）的最大日志索引（从 0 自增）

（2）Append Log RPC

此 RPC 用于 leader 向其余节点复制日志、发送心跳请求。

入参 注释
term leader 自己的任期号
leaderId leader id，便于 follower 节点将客户端请求重定向给 leader 处理
prevLogIndex 新日志的上一条日志的索引
prevLogTerm prevLogIndex 日志任期号
entries[] 要存储的日志数据（心跳请求的日志为空，为提升效率可能一次发送多条）
leaderCommit leader 的 commitIndex
返回值 注释
term follower 的 currentTerm，用于 leader 更新自己的任期号
succ 若 follower 在 prevLogIndex 和 prevLogTerm 处的日志都一致则为 true

RPC 被调用方（followers）需实现：

  • 若 term < currentTerm 则 succ 返回 fasle（5.1） // 已有更新 leader
  • 若在 prevLogIndex 处日志的任期号与 prevLogTerm 不一致，则返回 false（5.3） // 日志不一致
  • 若已存在的日志和新日志冲突（索引相同，任期不同），则删除本条及随后的所有日志条目（5.3） // follower 本地日志过旧，强制更新
  • Append 任意本地不存在的新日志
  • 若 leaderCommit > commitIndex，则将 commitIndex 重置为 leaderCommit 和自己最新日志索引中较小的一个值。

（3）RequestVote RPC

此 RPC 用于候选人发起投票，征集选票。

入参 注释
term 候选人的任期号
candidateId 候选人 id
lastLogIndex 候选人节点上最新日志的索引（5.4）
lastLogTerm 候选人节点上最新日志的任期号（5.4）
返回值 注释
term follower（选民）的任期号，用于候选人更新自身任期号
voteGrandted 赢得本张选票则为 true

RPC 的被调用方（选民 followers）需实现：

  • 若 term < currentTerm 则不投票，返回 false（5.1） // 已有更新的 leader
  • 若 votedFor 为 null 或为 candidateId，且候选人的日志和自己的一样新，则投票返回 true（5.2，5.4）

（4）所有节点需准从的规则

全部节点：

  • 若 commitIndex > lastApplied：将 lastApplied 自增 1，同时在状态机上执行 log[lastApplied] 日志命令（5.3）
  • 如果 RPC 请求或返回的 term T > currentTerm：将 currentTerm 重置为 T，并自降身份为 follower（5.1）

对于 Follwers：

  • 响应 leader 和 candidate（候选人）的 RPC 请求
  • 若选举超时还未收到 leader 心跳，也没收到候选人的投票请求，则自抬身价为候选人

对于候选人：

  • 成为候选人后开始选举：
    • currentTerm 自增 1
    • 给自己投一张选票
    • 重置选举超时定时器
    • 向其余节点发起 RequestVote RPC
  • 若收到了大多数节点的选票：升级为 leader
  • 若收到了来自新 leader 的 AppendEntries RPC：降级为 follower
  • 若本轮选举超时，开启下一轮选举

对于 Leader：

  • 成为 leader 后向其余节点发送心跳 RPC 请求，并在无日志请求的空闲时段重复发送心跳请求以防 followers 超时（5.2）
  • 接收到来自客户端的命令后，将其 Append 到本地日志，当该日志被状态机成功应用后再响应客户端（5.3）
  • 若 follower 最后一条日志索引 >= nextIndex，则 leader 对 nextIndex 开始的日志发起 Append Log RPC
    • 若 RPC 调用成功：更新相应 follower 的 nextIndex, matchIndex（5.3）
    • 如 RPC 因为日志不一致导致调用失败：自减 nextIndex 再重试（5.3）
  • 若存在 N 满足 N > commitIndex，同时大多数节点满足 matchIndex[i] >= N，并且 log[N].term == currentTerm：直接将 commitIndex 重置为 N（5.3，5.4）

5.1 Raft 基础

一个 Raft 集群包含多个服务器节点，比如典型的集群有 5 个节点，能容忍 2 个节点不可用。任何时刻任意节点的状态只会有三种身份：leader，follower，candidate，通常集群中只会有 1 个 leader，其余节点均为 follower，其身份转换如下图 4：

  • leader 处理所有客户端的请求：若客户端请求了 follower 那 follower 会将请求重定向给 leader 处理

  • follower 是被动响应的：它们不会发起任何请求，只会响应来自 leader 或候选人的请求

  • 候选人身份只会在 （5.2）中选举新 leader 时才会用到

三种身份更迭如下图4：

图4：节点身份转变过程。follower 只响应其余节点的请求，如果它在超时时间内未收到任何请求或心跳，则转变为候选人并开始新一轮选举。候选人如果收到大多数节点的选票则升级为 leader。而 leader 会保持 leader 身份直到自己宕机。

如下图 5，Raft 将集群时间换分割成多个任意长度的任期，任期使用连续整数标识，即任期号。每次任期都始于选举，如果候选人引得了选举（5.2），则它会变为下一任期的 leader。一些特殊情况下，选票可能被多个候选人瓜分导致未选出 leader，即当前任期内无 leader，不过此情形仅持续很短时间就开始下一轮选举。Raft 能保证任一任期内至多有一个 leader

图5：Raft 将集群时间划分成多个连续的任期，每个任期均始于选举。在选举成功后，单一 leader 会管理集群直到任期结束。有些选举会因为任期结束都还未选出 leader 而失败，会导致该任期内无 leader。

不同节点在不同时间内可观察到任期变更，某些情况下节点也可能不知道发生了 leader 选举，甚至感知不到整个任期。Raft 的任期发挥了逻辑时钟的作用，让节点能检测过期信息比如过期的 leader。每个节点都会维护一个 currentTerm 数字，它只会单调递增。在节点间通信时会交换彼此的 currentTerm：

  • 若一个节点任期号比另一个小，那它会将自己的任期号更新为较大的一个
  • 若 leader 或候选人发现自己的任期号过期了，那它会降低身份变为 follower
  • 若节点收到的请求对应的任期号已过期，则拒绝处理此请求

节点间通过 RPC 通信，基本的一致性算法只需要 2 种 RPC：

  • RequestVote RPC：在候选人开始发起选举时调用（5.2）
  • AppendEntries RPC：在 leader 复制日志或发送心跳到其他节点时调用（5.3）

第 7 节会添加在节点间传输快照的第三种 RPC。当 RPC 调用未及时返回则节点会重试调用，而且通常会将多个调用并行化以提高性能。

5.2 Leader 选举

Raft 使用心跳机制来触发 leader 选举。当集群刚启动时节点都是 follower 身份，只要收到 leader 或候选人的有效 RPC 调用，节点就会继续保持 follower 身份。leader 会定期发送心跳（无条目的空日志 AppendEntries RPC）给所有 follower 来维持自己的 leader 身份，如果某个 follower 在选举超时时间段内都未收到来自 leader 的任何调用，则认为 leader 已失效并成为候选人开启新一轮 leader 选举。

选举开始，follower 自增自己的任期号并升级为候选人身份，它会先投自己一票，随后并行地向其余节点发起 RequestVote RPC 调用，它会继续保持候选人身份直到下述情形发生：

  • 它在本轮选举中赢得多数票

    如果候选人在一轮选举中获得了全部节点中大多数节点的选票，就算赢得本轮选举。每个节点依照先来先服务（first-come-first-served）的原则（5.4 对新加额外的限制），在每轮选举中最多投一个候选人。因此 大多数原则 能确保每轮选举最多选只会有一个候选人会获胜。一旦候选人赢得选举成为了新 leader，它就会发送心跳给其余节点来树立自己的领导地位，以阻止新一轮选举。

  • 已有其他节点成为 leader

    候选人在收集选票时可能会收到其他已成为 leader 的节点发来的 AppedLog RPC 请求：

    • 若请求任期不小于自己的任期号，那就认可对方的 leader 身份，自己降为 follower
    • 若请求中的任期比自己的小，则拒绝响应调用并继续保持自己的候选人身份

  • 选票被瓜分，选举超时后还未选出 leader

    若多个 follower 同时变更为候选人，那选票可能会被瓜分导致没有一个候选人能收到大多数选票。这种情况下多个候选人会在选举超时后分别开启下一轮选举，继续向其他节点发起 RequestVote RPC 请求。然而如果没有额外机制来分配选票，这种情况会周而复始地发生。

    Raft 使用随机的选举超时时长来避免出现选票被瓜分的情况，就算出现了也能很快解决。为了从根源上阻止选票被瓜分，各候选人的选举超时时长是从固定的时长区间（如 150-300ms）中随机选取的，这种机制保证多数情况下只有一个候选人超时，随后赢得选举并在其他候选人选举超时前发送心跳请求。同样的，每个候选人在开启新一轮选举前都要随机重置自己的选举超时时长，超时再重启下一轮选举。此种随机超时机制能有效避免选票被瓜分的情况。

    随机选举超时机制不仅容易理解和实现，而且明确高效。

5.3 日志复制

一旦成功选举出 leader，它就开始接收并处理客户端请求，每个请求都包含一个状态机要执行的命令。leader 会将此命令 append 到本地日志，随后向其余节点发起 AppendEntries RPC 请求来 replicate（复制）该命令日志。当日志成功复制后（如下详述），leader 的状态机才会应用本条日志并将执行结果返回给客户端。若 followers 不可用或发生了网络丢包，leader 会无限次重试调用 AppendEntries RPC（即使已将执行结果响应给了客户端），直到 followers 成功存储所有的日志条目。

图6：日志由有序序号标识的日志条目组成。每个条目包含创建时 leader 的任期号（图中盒子编号）、要应用到各自状态机的命令。日志条目的可提交（commited）状态标识它可安全应用到状态机。

日志的组织方式如上图。每条日志会记录：

  • 状态机命令
  • leader 接收到此命令时的任期号：用于检测不同节点上该日志的一致性，还能保证图 3 列出的部分特性
  • 索引：每条日志都有一个整数索引值标识其在日志中的位置

leader 决定何时将日志应用到状态机上是安全的，此时日志状态为已提交（commited）。Raft 能保证已提交的日志会持久化存储，最终都都会应用到集群中可用的状态机上。一旦 leader 创建的日志条目已在大多数节点上成功复制，那这条日志是已提交状态，比如图 6 中的条目 7（leader、2、4 共三个节点都已成功复制），同时意味着 leader 节点上该条日志前的所有日志都是已提交状态，即使有些日志是前任 leaders 创建的（5.4）。leader 会维护它所知已提交日志的最大索引 commitIndex，在以后调用 AppendEntries RPC 请求时会将此索引带上以便让其他节点知道 leader 的提交位置。当 follower 被告知某条日志为已提交状态，即可安全地在本地状态机上应用该日志。

Raft 的日志机制保证了不同节点上日志的一致性，此机制降低了系统复杂度，让系统行为变得可预测，同时也保障了安全（图 3 的安全性原则）

Raft 维护了以下特性：若在不同日志中，两条日志的索引号、任期号都一致，则：

  • 它们存储的命令是一致的：是因为 leader 在一个任期的一个日志索引上只存储一条日志，而且此后该条日志的位置不再修改，所以固定索引的日志值是不变的。

  • 它们在该条之前的所有日志都是一致的：由 leader 的一致性检查保证：leader 在复制日志发起 AppendEntries RPC 请求时会将上一条日志的索引 prevLogIndex、任期号 prevLogTerm 传入用于一致性检查。若 follower 在日志中没有发现相同索引、相同任期号的条目，则拒绝接收此次新日志。

    日志的一致性检查总结：集群初始状态的空日志是满足日志匹配原则（Log Matching Property），此后的一致性检查保证了新增日志后仍然是匹配的。因此只要 leader 收到 AppendEntries RPC 成功返回，就认为该 follower 的日志与自己的一致。

正常情况下，leader 和 followers 的日志是保持一致的，即 AppendEntries 一致性检查不会失败。然而，leader 宕机后很可能造成日志不一致（旧 leader 可能还没来得及将它的日志条目全部复制给 followers），不一致程度会随着 leader 和 follower 的一些列崩溃而愈发严重。

下图是 followers 日志和新 leader 不一致的情形：follower 的日志可能比现有 leader 的日志更少，也可能更多，这部分错开的日志可能在多个任期内都一直存在。

图7：当新 leader 当选时 followers 状态可能是（a-f），每个盒子即一条日志，盒子编号是该条日志的任期号。顶部是 leader 日志条目，其他：

  • a，b：follower 可能丢失部分日志
  • c，d：follower 本地可能 uncommited 的日志
  • e，f：follower 可能既缺少本该有的日志，也多出额外的日志

比如 f 场景：2 号任期 leader 新增的日志还没提交就宕机了，随后很快重启并被选举为任期 3 的 leader，继续接收请求新增日志。然而在 3 号任期内日志还没来得及提交就又宕机了。

在 Raft 中，leader 通过强制 followers 复制自己的日志来处理日志不一致的问题，即 follower 上有冲突的日志会被直接重写，5.4 节会增加额外机制来保证此操作是安全的。

为保证 follower 的日志和自己一致，leader 必须对比查找与 follower 最后一条相同的日志，删除 follower 在该位置后的所有日志，随后发送自己在该位置后的所有日志给 follower，从而保证日志一致性。

以上操作都在 AppendEntries RPC 做一致性检查时完成，leader 对每个 follower 都维护了 nextIndex，标识下一个要发送给 follower 的日志索引。当 leader 刚启动时，会将所有 nextIndex 重置为本地最后一条日志的索引加 1

若某个 follower 的日志与 leader 不一致（ follower 日志超前）：那下次 AppendEntries RPC 一致性检查会失败，随后 leader 递减该 nextIndex 再次调用，直至 leader 和 follower 的日志匹配成功。匹配成功后，follower 要删除该匹配点之后的所有日志，再 append leader 在匹配点后的日志（强制同步）。当 AppendEntries RPC 调用成功后，follower 的日志就和 leader 保持一致，直到该 leader 的任期结束。

算法实现时可通过减少 AppendEntries RPC 调用失败的次数进行优化。如 follower 在拒绝调用后，可记录下冲突日志的任期号，在该任期内存储的第一条日志索引。有了这些信息，leader 能增加 nextIndex 直接跳过该任期内的所有冲突日志，如此仅需一次 AppendEntries RPC 调用而非多次。

在这种机制下，leader 在任期内无需额外的操作来保证日志的一致性，它只需要处理常规操作，日志就能自动地在 AppendEntries RPC 一致性检查失败时趋于一致。

日志复制机制证实了第 2 节中的一致性特性：只要集群中的大多数节点正常工作，Raft 就正常 accept，replicate 和 apply 新日志。通常情况下，一条新日志能在一轮 RPC 调用中就复制到大多数节点上，所以单个低性能的慢 follower 不会影响到集群性能。

5.4 安全性

前两小节详述了 Raft 的 leader 选举和日志复制两种机制，截止目前还不能完全保证每个节点的状态机都会以相同顺序执行相同命令（能保证各节点的日志一致性）。如 leader 提交某些日志时某个 follower 不可用，之后该 follower 被选举成新 leader，会覆盖这些自己未接收到的日志，最终导致多台状态机执行的命令序列不一致。（解决办法：引入新机制，保证后续新 leader 一定含有之前 leaders 提交的所有日志）

本节在 leader 选举时加入限制措施继续完善 Raft 算法，这些选举限制能确保每个任期的 leader 都存有前任 leaders 的所有已提交日志（图 3 中的 Leader 完整性原则）。这一选举限制让日志提交的规则更为清晰。本节最后会用草图说明 leader 完整性原则是如何纠正各状态机行为的。

5.4.1 选举限制

在所有基于 leader 的一致性算法中，leader 最终都要存储所有已提交的日志。不过在一些算法中，如 Viewstamped，节点即使不存储所有已提交的日志也可被选举为 leader，是因为这些算法有额外机制来找到缺失的日志并传送给新 leader，这一过程会在选举时完成或选举后立即开始，不幸的是，这种机制过于复杂。Raft 用更简单的方式保证所有前任 leaders 提交的日志在选举时都会出现在新 leader 中，而不是要传输旧日志。因此日志只会有一个流动方向：从 leader 流向 followers，并且 leader 从不覆盖或删除已有日志。

Raft 通过投票来防止不含全部已提交日志的候选人赢得选举。候选人为了获胜需与大多数节点通信，这意味着每条已提交的日志至少会出现在一个节点上。若它的日志至少和大多数节点的一样新（下述），就说明它存有全部已提交日志。RequestVote RPC 需实现：RPC 请求参数会带上候选人的日志信息，若投票节点的日志比候选人的还新则不投票。

Raft 通过比较两份日志中最后一条日志的索引、任期来比较新旧：

  • 任期不同，则任期更大的日志新
  • 任期相同，则索引更大的日志新

5.4.2 提交前 leaders 任期内的日志

如 5.3 所述，当日志被大多数节点存储后 leader 才会认为该条日志是已提交的。如果 leader 在提交日志条前宕机，以后的新 leader 会尝试继续复制该条日志。不过新 leader 无法断定已存在于大多数节点上的日志是否真的已被提交。如图 8 (c) 中 S1 可能已将日志复制到大多数节点，但依旧可能被 (d) 中 S5 的日志覆盖。

图8：如上的时序图说明，为什么新 leader 不能判断之前任期内的日志的提交状态：

  • (a)：S1 作为 2 号任期的 leader 将索引为 2 的日志复制到节点 S2 上

  • (b)：S1 宕机。S5 获得来自 S3、S4 及自己共三张多数票，成为 3 号任期新 leader，随后在本地索引 2 上存储新日志。

  • (c)：S5 宕机。S1 重启，获得 S2、S3 的选票后重新选为 4 号任期 leader，继续复制索引 2 上的日志。

此时，任期号为 2 的日志已成功复制到（replicated）大多数节点（S1、S2、S3），但这条日志未提交（uncommitted）

  • (d) / (e)
    • (d)：若 S1 再次宕机。S5 能被 S2、S3、S4 选为新 leader，并将自己在 3 号任期还没来得及提交的日志强制覆盖到其他节点。
    • (e)：若 S1 在宕机前将自己任期内的新日志复制给了大多数节点（S2、S3），那后面产生的新日志就会被提交，从而导致 S5 不会赢得选举（日志旧 3 < 4），由此它之前的日志条目也已提交。

为解决图 8 中的问题，Raft 不会单纯地统计前任期内的某条日志的副本数来决定是否要提交。只有**当前任期内**的日志能统计副本数来判断是否已提交。一旦前任期内的日志以这种方式提交，因为日志匹配特性，该日志之前的所有日志都会被间接提交。（理解：从第一任期 leader 开始，通过判断自己的一条新日志是否已被大多数节点复制来判断是否已提交。之后 RPC 进行日志的一致性检查保证了 follower 的日志与自己匹配。由此迭代，后边的新 leader （旧 follower）也会保存有旧 leader 的所有已提交日志）

Raft 在复制之前任期内的日志时，会保留旧的任期号，这使日志提交更为复杂。但在其他一致性算法中，同样复制场景则会使用新的任期号。Raft 为已提交的日志维护了旧的任期号，因此在对比日志时更为简单，也让新 leader 发送更少的之前任期日志。

5.4.3 安全性证明

如上给定了完整的 Raft 算法，本节将讨论 leader 完整性原则（9.2 详述）。通过反证法，假设完整性原则不存在，推导出会引发的矛盾。假设任期 T 的 leaderT 在自己任期内提交了一条日志，但本条日志未保存在随后的新 leader 中，比如任期 T 随后任期是 U，leaderU 上未保存该条 leaderT 提交的日志：

图9：若节点 S1（任期 T 的 leader）在任期内提交了一条新日志，而 S5 在紧随的任期 U 内选为了新 leader，所以至少必有一个节点（S3）既接收了 leaderT 的新日志，还给 S5 投了一票。

  1. leaderU 肯定缺少 leaderT 已提交的那条日志（leader 不会覆写或删除日志）
  2. leaderT 成功将日志复制到大多数节点上，同时 leaderU 赢得了大多数节点的选票。因此至少会有 1 个节点（voter）及接收了 leaderT 发来的日志，还给 leaderU 投了一票。
  3. voter 一定是先收到 leaderT 的日志，再给 leaderU 投票的。如果先收到 leaderU 的投票请求，则会因为 T < U 直接拒绝 leaderT 的日志 AppendEntries RPC
  4. voter 在投票给 leaderU 时依旧会把该日志存下来，因为基于假设，T 任期后的任何 leader 都应包含该日志。leader 不删日志，而 follower 只会在与 leader 日志冲突时才删除自己的日志。
  5. voter 给 leaderU 投了票，那 leaderU 的日志至少和 voter 的一样新。矛盾 1：leader 日志更旧，voter 不应该投票
  6. 首先，若 voter 和 leaderU 的最后一条日志任期号一致，leaderU 的日志至少和 voter 的一样长。矛盾2：leaderU 的日志中并不包含 leaderT 复制到 voter 的那一条，不应该一样长
  7. 否则，leaderU 最后一条日志的任期号就一定比 voter 的大，也定比 T 大，因为 voter 的最后一条日志任期号最小都是 T（保存有任期 T 提交的日志）。创建了 leaderU 上最后一条日志的上一任 leader，一定也保存了已提交的日志（基于假设）。由日志匹配原则，leaderU 的日志一定包含已提交的日志。矛盾 3：leaderU 未包含前一任 leader 已提交的日志
  8. 矛盾论点推导完毕。根据反证法可得出：任期比 T 大的 leader 一定包含有任期 T 内提交的所有日志。
  9. 日志匹配原则保证了下一任新 leader 也会包含被间接提交的日志。如图 8 (d) 中索引为 2 的日志

通过 leader 完整性原则，能证明图 3 中的状态机安全原则成立。即某个节点将给定索引的日志应用到自己的状态机上，那其他节点在同一索引不可能应用其他日志。节点在应用某条日志到状态机时，那它在该条日志前的日志必定和 leader 一致，而且都处于已提交的状态。考虑在节点上应用的一条指定索引位置日志的最小任期号，Log 完整性原则能保证更高任期的 leaders 会存储相同的日志，即之后任期里某个索引位置的体质条目值也是相同的。由此，证明了状态机的安全特性。

最后，Raft 要求节点按日志索引顺序地应用条目到状态机，结合状态机安全特性来看，可知所有节点会以相同顺序将相同日志应用到各自的状态机上。

5.5 Follower 和 Cadidate 崩溃

到目前只讨论了 leader 崩溃的情况，相比之下 follower 和候选人崩溃后的处理简单得多，二者处理方式相同：崩溃后，发来的 AppendEntries RPC 和 RequestVote RPC 都会调用失败，对于这种失败 Raft 直接无限次重试调用。

如果崩溃节点重启，那对它的 RPC 调用完全可以成功。若节点完成了 RPC 调用，但还没来得及响应就已崩溃，那等它重启后会再次接收到相同的 RPC 请求，由于 Raft 中的 RPC 调用是幂等的，不会造成什么问题。比如 follower 收到对一个已经保存了的日志的 AppendEntries RPC 请求，它会直接忽视该调用。

5.6 时序性和可用性

Raft 的安全性不能依赖时序性（timing）来保证：系统不能因某些操作过快或过慢导致给客户端返回了错误的结果。但是，可用性（系统能及时响应客户端请求）是无可避免地要依赖时序性的。比如 RPC 调用时长比节点故障间隔（正常工作时长）还大，即每次调用还没成功就又宕机了，会导致候选人没有足够的时间赢得选举，而 Raft 没有可用的 leader 是无法工作的。

leader 选举是 Raft 对系统时序要求最高的地方，不过只要系统满足以下原则，Raft 就能选出并保持一个稳定的 leader：

broadcastTime 广播时间 << electionTimeout 选举超时时间 << MTBF 平均故障间隔时间

broadcastTime 是向其余节点开始并行调用 RPC 到收到响应的平均时间，electionTimeout 是 5.2 所述的选举超时时间，MTBF 则是节点失效间隔（正常运行时长）的平均时间。

  • broadcastTime 应比 electionTimeout 小一个数量级，才能让 leader 能及时发送心跳信息给 followers 以防它们发起新选举，通过随机生成的 electionTimeout 能让选票被瓜分的概率极低。

  • electionTimeout 应比 MTBF 小多个数量级，才能让系统稳定运行。当 leader 崩溃后系统也只是在选举超时时段内不可用，我们系统不可用的时间只占运行时间的一小部分。

broadcastTime 和 MTBF 的大小由系统环境决定，不过 electionTimeout 是由我们选定的。Raft 的 RPC 要求被调用方数据存储要可靠，即 broadcastTime 约在 0.5-20ms 范围内，具体是多少取决于系统的存储技术，对应的 electionTimeout 一般在 10-500ms 之间，而对应的 MTBF 时间则为几个月甚至更长。如上的三个时间量级才满足 Raft 时序性。

6. 集群成员变更

截止目前假定所有节点的配置都不会修改。而现实中偶尔还是要调整节点的配置，如替换宕机的节点、调整日志的复制级别等。可以先将整个系统下线，调整配置后重启上线，但会导致调整期间系统对外不可用。如果是人工手动调整配置，那操作失误也是有可能的。为避免这些问题，我们将配置调整集成到了 Raft 算法中。

为保障调整配置的安全，在调整期间一定不能出现同一时间选出两个 leader 的情况。不幸的是，无论用什么办法，节点的配置从旧转新的过程都是不安全的，不可能同时一次性调整好所有节点的配置，所以节点在调整配置期间会被分到 2 个不同的大多数群体：

图10：由于不同节点可在任何时间切换配置，导致节点直接切换配置是不安全的。

上图中，集群节点从 3 个增加到 5 个，不过在同一任期内与可能选举出 2 个不同的 leader，分别从旧配置节点 C_old 中选出，从新配置节点 C_new 中选出。

为保证安全，配置的调整需分成两个阶段。目前两阶段调整的方案有很多，一些系统在第一阶段直接将旧配置节点停用，不处理客户端请求，随后在第二阶段才加载新配置。在 Raft 中，集群先切换到称为 joint consensus的过渡配置，再切换到新配置。joint consensus 其实是新旧配置的组合：

  • 日志依旧都会复制到新、旧配置的所有节点上
  • 新旧配置的节点都能被选为 leader
  • 针对选举和提交操作，要想赢得选举必须在新配置节点、旧配置节点中都获得大多数票

joint consensus 机制能让节点在保证安全的前提下切换配置，不仅如此，它还能让集群在切换配置时依然能对客户端提供服务。

图11：调整配置的时间线。虚线：创建日志但未提交；实线：最新提交的配置日志。

leader 先自己创建 C_old,new 配置日志并将其复制到大多数节点（C_old 的大多数，C_new 的大多数）。之后它再创建 C_new 配置日志并提交给 C_new 的大多数节点。如此，C_old 和 C_new 做决策的时间点就被岔开了。

集群配置在复制日志中以特殊日志条目的形式进行存储和提交。上图 11 展示了集群配置变更的过程：

  • 当 leader 接收到配置从 C_old 切换到 C_new 的请求时，它先将 joint consensus（图中 C_old,new）存储并复制给大多数节点。

  • 一旦某个节点将更新的配置存到它的日志中，其后所有决策都使用该配置（节点使用的配置总是最新的，不管是否已提交）；即 leader 要用 C_old,new 的规则来决定何时提交 C_old,new 配置日志。如果 leader 崩溃，那新 leader 的配置不是 C_old 就是 C_old,new。在这一阶段，C_new 的配置不会应用。

  • 一旦 C_old,new 被提交，C_old 和 C_new 在没有其他节点的允许下都不会生效。且由 leader 完整性原则只有包含 C_old,new 配置的节点才有资格被选为新 leader。现在 leader 可以安全地将 C_new 配置日志复制到集群中，当节点收到新的配置后即刻生效。

  • 当 C_new 日志被提交后，旧配置节点就无关紧了。

如图 11 中，C_old 和 C_new 都无法单方面做出决策。由此保障了安全。

针对配置调整提出三个问题：

  1. 新节点启动时不含日志，若以这种初始状态加入集群，那它得需要一段时间追平日志，追赶的时间内它还不能提交新日志。为避免该节点的可用性间隙，Raft 在配置调整前处于额外的一个阶段：这个阶段内新加入的节点没有投票权（虽然 leader 依旧会向它复制日志，但在选举时不把它算作大多数）。一旦新节点的日志与其他节点同步，就可以像上边那样调整配置了。

  2. leader 的配置可能还是旧的，这种情况下一旦 leader 提交了 C_new 日志，就退位到 follower。这意为着在 leader 提交 C_new 日志的时间段内，leader 虽然管理集群但不管自己，虽然向大多数节点复制日志但不包括自己。C_new 提交后会发生 leader 更换，因为此时的 C_new 是新配置下能独立运行的最早时间点（C_new 下总是能选出新 leader）。在此之前，集群只能从 C_old 中选 leader

  3. 移除不在 C_new 中的节点会扰乱集群。这部分节点收不到心跳，超时后可能发起选举，即用一个新任期号发起 RequestVote RPC 请求，这会让当前 leader 退回到 follower 状态。最终选出新 leader 后，移除的节点会再次超时…这个过程周而复始，降低了系统可用性。

    为解决此问题，当某个节点确信 leader 已存在的情况下，它会直接忽视 RequestVote RPC。若节点在最小选举超时时间内收到了 RequestVote RPC，它既不更新自己的当前任期号，也不投票。这种机制不会影响到正常的选举流程，每个节点在开始选举前都会等待最小选举超时时间，这避免了已移除节点的干扰：如果 leader 还能向集群中发送心跳，它就不会被更大的任期号所罢免。

7. 日志压缩

Raft 生成的日志会不断增长，但在实际系统中不会无限制增长。日志累积得越多，占用空间也就越多，回放耗时也就越长。如果没有额外机制来清理那些积累在日志中的过期数据，长此以往会引发系统可用性问题。

系统快照是最简单的日志压缩方式。整个系统状态会被写入快照（snapshot）并存储在可靠介质中，这是日志可放心地清理掉。在 Chubby 和 Zookeeper 都用到了快照技术，本节将介绍它在 Raft 中的应用。

记录日志增量来实现压缩，如日志清理（log cleanin）、日志结构合并树（log-structured merge tree）都是可行的。这些方案每次都只处理部分日志，均分了日志压缩的负载。它们先选一个积累了大量已删除或已覆写的数据区域，随后重写该区域内还活跃的数据，最后释放该区域。相比于简单的快照操作，以上操作需要额外的复杂机制来实现。状态机可实现 LSM Tree 来使用和快照相同的接口，而日志清除的工作就得 Raft 自己实现了。

图12：节点用快照替换了索引 1-5 的日志，该快照只存储目前的状态（以 x, y 为例）、日志最后的索引和任期号

上图便是 Raft 的基础快照思想：每个节点都维护了各自的快照信息，只有已提交的日志会被拍进快照，其中的主要工作是将节点状态完整地写入快照中。此外，Raft 还在快照中嵌入了少量 metadata：

  • last included index：快照初的最后一条日志，即状态机最后应用的那条日志
  • last included term：快照最后一条日志的任期号

metadata 中的这两个值，用于紧随快照的 AppendEntries RPC 进行日志一致性检查。为了让第 6 节的成员关系变更，该快照也会记录最后一条索引日志包含的配置。一旦节点完成快照存储，它可能会清理 last included index 之前的所有日志，之前的所有旧快照也要删除。

虽然节点一般都各自处理各自的快照，但 leader 必须时不时地给那些落后的 followers 发送自己的快照，这种发送操作一般发生在 leader 已丢弃了本该发送给 followers 的日志。好在一般情况下这种情况下不太可能发生：与 leader 保持同步的 follower 多半已复制本条日志，不过运行较慢的 follower 或新加入集群的节点不会有这条日志，此时通过网络发送快照的方式即可同步本条日志。

InstallSnapshot RPC：leader 调用它来向 follower 有序地发送日志 chunk 片段。

入参 注释
term 当前 leader 的任期
leaderId follower 用此来重定向客户端的请求给 leader 处理
lastIncludedIndex 快照中包含的最后一条日志的索引值
lastIncludedTerm 快照中包含的最后一条日志的任期号
offset 标识此日志 chunk 在快照中的字节偏移量
data[] 从 offset 开始的二进制快照 chunk数据
done 如果是最后一份 chunk 则为 true
返回值 注释
term 返回 currentTerm，用于 leader 更新自己的任期号

被调用方（follower）需实现：

  1. 若 term < currentTerm 就立刻返回调用
  2. 若是 offset 为 0 的首份 chunk，则新建快照
  3. 从给定的 offset 开始将日志写入快照
  4. 响应调用，之后只要 done 参数为 false 就等待接收更多 chunk
  5. 保存快照文件，清理掉任何本地索引更小的日志
  6. 若节点现有的日志条目和快照中的最后一条日志的索引、任期都相同，则保留其之后的日志并响应
  7. 丢弃日志
  8. 使用快照来重置状态机的状态（装载快照到集群配置）

图13：关于 InstallSnapshot RPC 的总结，快照会被分割成 chunk 块传输。follower 接收到 chunk 后可认为当前 leader 依旧存活，会重置选举超时计时器。

leader 使用新的 InstallSnapshot RPC 向过于落后的 follower 发送快照，如图 13 当 follower 收到此 RPC 发来的快照后，它得决定自己已有的日志怎么处理。

  • 通常日志会包含一些节点没有的新信息，这种情况下 follower 会直接丢弃自己的日志，用收到的快照来代替，不然本地未提交的日志可能与快照发生冲突。
  • 若由于传输错误等原因导致 follower 收到快照已是本地日志的前一部分，那它会将该前一部分日志删除，用快照代替，但之后的日志依旧保留。

每个 follower 都能在不知道 leader 情况时自己拍快照，这背离了 Raft 的强 leader 原则。不过我们认为这种背离是有用的。leader 是为了解决达成一致性时日志冲突而存在的，而拍快照时日志已一致，所以不会有冲突，由此拍快照时无 leader 介入也是可行的。不过数据依旧只有一个流动方向：从 leader 流动到 followers

我们也考虑过一种基于 leader 的快照方案：只有 leader 有权拍快照，随后将快照分发给 followers。此方案有 2 个大缺点：

  • 每次发送快照给 follower 都会消耗大量的网络带宽：followers 本地已有该快照的所有原料，它们在本地拍快照肯定比从 leader 拍好传过来代价要小得多
  • 这样会让 leader 实现起来更复杂：leader 需在向 followers 复制日志的同时将 snapshots 也发给它们，这样才不会阻塞新的客户端请求。

现在还有两个可能会影响快照性能的问题：

  • 节点需要决定何时拍快照：若拍得太频繁，则会浪费大量的磁盘空间和网络带宽；若拍得不及时，就会面临磁盘空间耗尽的风险，而且重启后重建日志耗时也会更长。一个简单的解决办法是在日志增长到一个固定大小的阈值后就拍快照，只要此阈值比快照大小大得多，那拍快照对磁盘、带宽的压力就会小很多。
  • 将快照写入磁盘会消耗一定时间：我们不希望节点因为写快照影响了正常操作。解决方案是使用写时复制（copy-on-write）技术，这样就可以继续接受新的更新请求而不会影响到快照。比如，状态机内置的函数式数据结构就原生支持写时复制，有的操作系统在底层支持（如 Linux 的 fork 操作）可用来拍下内存中的状态机的快照。

8. 与客户端的交互

本节描述 Raft 如何与客户端交互，比如客户端如何查找集群 leader、Raft 如何理解线性化语义，这些问题在大部分一致性系统中都存在，而 Raft 的解决方案也类似。

Raft 的客户端会将自己的所有请求都发送给 leader 处理，当客户端初次启动时，它会随机选择一个节点发送请求，如果此节点不是 leader，那节点会拒绝该请求并将它已知的 leader 信息返回（AppendEntries RPC 需带上 leader 地址），如果该 leader 早已宕机，那此请求会超时。客户端会再次随机选一个节点进行重试。

Raft 的设计目标之一是实现线性化语义（每次请求操作都立即执行，保证只执行一次）。然而到目前的实现中 Raft 会多次执行某个命令：当 leader 提交日志后还没来得及响应客户端就崩溃了，这时客户端会在新 leader 二次执行该命令。解决办法是客户端对每个请求命令都用唯一的序列号进行标识，leader 的状态机会追踪每个客户端的请求命令序号及其响应数据。若 leader 再次收到某个已执行过的命令，那就直接将响应返回而非二次执行。

只读（Read-Only）操作可以无需记录到日志而直接处理，但如果没有任何限制的话会有返回旧数据的风险：旧 leader 响应客户端只读操作时可能已被新 leader 作废，而它却不知。线性读操作一定不能返回旧数据，Raft 需使用两个额外的措施在不使用日志的前提下保证不返回旧数据：

  • leader 必须拥有最新的一条已提交日志信息：leader 完整性原则已经能保证 leader 包含所有已提交的日志，但在任期开始时它可能并不知道哪些日志已经被提交了。为此每个 leader 在其任期开始时提交一条空的无操作（no-op）日志。
  • 在处理只读请求时必须检查自己是否已被最新的 leader 罢免了（如果已选出新 leader 那它的数据就已经变旧了），Raft 让 leader 处理只读请求前先和大多数节点进行一次心跳交换来解决此问题。此外，leader 可通过心跳来实现租约机制，不过这种方案依赖时序性来保证安全性（假设时间误差有限）

9. 实现与评价

Raft 的可理解性比 Paxos 要好得多，正确性已得到证明，而性能与 Paxos 不相上下。

10. 相关工作

参考原论文或完整翻译即可。

参考

[GitHub: raft-zh_cn](<http://wibliss.com)

InfoQ: Raft 一致性算法论文译文