Raft 共识算法

分布式 , 评论

概述

Raft 是一个共识算法（consensus algorithm），也称作 Raft 协议。所谓共识就是多个节点就某个事情达成一致，即使是在部分节点故障、甚至网络分区的情况下也是可行的。在分布式系统中，共识算法更多用于提供系统的容错性。

Raft 算法是在兰伯特 Multi-Paxos 思想的基础上进行了简化和限制，目标就是容易理解。Raft 虽然增强了可理解性，但在性能、可靠性、可用性方面是不输于 Paxos 的。Raft 算法将共识的关键要素进行了拆分，以简化流程和提供算法的可理解性。

复制状态机

共识算法的实现一般是基于复制状态机（Replicated state machines），即所有节点都是从同一个 state 出发，都经过同样的一些操作序列（log），最后到达同样的 state ，架构图如下：

这是一个共识系统的典型架构，其中涉及到三个组件：

  1. 状态机：处理来自 Log 的指令序列，将执行结果对外输出。状态机具有确定性，只要 Log 的指令序列相同，产生的结果也是相同的。
  2. Log：保存了所有写操作记录。
  3. 共识模块：保证包含来自客户端的指令的 Log 的一致性，充当管理日志的角色。（这也是 Raft 算法核心内容）

复制状态机通常使用复制日志来实现。每个服务节点存储一个包含一系列命令的日志，日志会被其状态机所使用，用于计算其中的指令。注意，只要各个服务节点上的日志是相同的或者大多数节点日志相同，说明系统已经达成共识，这些具有相同日志的服务节点上的状态机就能以相同的顺序执行相同的命令，执行的结果也是相同的。不难看出，复制日志充当数据副本的角色。

保证复制日志的一致性是共识算法的工作。服务节点上的共识模块从客户端接收命令，并将其添加到其 Log 中，然后与其它服务节点的共识模块进行通信，以完成日志复制。正确复制指令后，每台服务节点将命令应用到状态机（状态机执行对应的指令）。

Raft 算法概览

Raft 是一种用于管理复制日志的算法，它采用领导者模式，将共识问题分解为三个相对独立的子问题：Leader 选举、日志复制、安全（约定）。下面对 Raft 算法进行总体说明，并就关键特性进行列举。图中的相关元素会在后文具体说明。

算法简要

状态数据结构

  • 所有服务节点上的持久性状态（在响应RPC请求之前，已经更新到了稳定的存储设备）
    • currentTerm: 服务节点已知最新任期（在服务节点首次启动时初始化为 0，该值是单调递增的）
    • votedFor: 当前任期内收到选票的候选者id,如果没有投给任何候选者，则为空
    • log[]: 日志条目
  • 所有服务节点上的易失性状态
    • commitIndex: 已知已提交的最高的日志条目的索引（初始值为 0，单调递增）
    • lastApplied: 已经被应用到状态机的最高的日志条目的索引（初始值为 0，单调递增）
  • 领导者（服务节点）上的易失性状态（选举后已经重新初始化）
    • nextIndex[]: 对于每个服务节点，发送到该服务节点的下一个日志条目的索引（初始值为领导者最后的日志条目的索引+1）
    • matchIndex[]: 对于每一台服务节点，已知的已经复制到该服务节点的最高日志条目的索引（初始值为0，单调递增）

选举 RPC 数据结构

  • 由候选人负责调用，用来征集选票
    • term：候选人的任期编号
    • candidatedId: 请求选票的候选人的 id
    • lastLogIndex: 候选人最后日志条目的索引值
    • lastLogTerm: 候选人最后日志条目的任期编号
  • 返回值
    • term: 响应中的任期号，以便于候选人去更新自己的任期号（候选人任期号较小时）
    • voteGranted: 候选人赢得了此张选票时为真

日志复制｜心跳 RPC 数据结构

  • 领导者用于日志条目的复制 RPC 和 心跳 RPC
    • term: 领导者任期
    • leaderId: 领导者Id，跟随者可以根据该值对客户端进行重定向
    • prevLogIndex: 上一个日志条目的索引
    • prevLogTerm: 上一个日志条目的任期
    • entries[]: 需要被保存的日志条目（如果是心跳 RPC，则为空；为了提高效率可能一次性发送多个）
    • leaderCommit: 领导者的已知已提交的最高的日志条目的索引

需要特别说明的是，prevLogIndex 和 prevLogTerm 是动态变化的，不是很好理解。

  • 结果
    • term: 响应中的任期，对于领导者而言，它会更新自己的任期（其它领导者任期更高）
    • success: 如果跟随者所含有的条目和 prevLogIndex 以及 prevLogTerm 匹配上了，则结果为 true
  • 接受者的实现
    • 如果领导者的任期小于接收者的当前任期，则返回 false
    • 如果接受者日志中不能找到一个和 prevlogIndex 以及 prevLogTerm 一样的索引和任期的日志条目，则返回 false
    • 如果接受者的条目和新条目发生了冲突（索引相同，任期不同），那么就删除这个已存在的条目以及它之后的所有条目

服务节点规则

  • 所有服务节点
    • 如果commitIndex > lastApplied，那么 lastApplied 加一，并把log[lastApplied]应用到状态机中。
    • 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者
  • 跟随者
    • 响应来自候选人和领导者的请求
    • 如果超过选举超时时间没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，就自己变成候选者
  • 候选者
    • 节点在转变成候选者后就立即开始选举过程
    • 如果接收到大多数服务节点的选票，那么就变成领导者
    • 如果接收到来自新的领导者的 AppendEntries RPC，转变成跟随者
    • 如果选举过程超时，再次发起一轮选举
  • 领导人
    • 选举后，向每个服务节点发送 AppendEntries RPC（心跳）；以一定的时间间隔不停的重复发送，以阻止跟随者超时
    • 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端
    • 如果跟随者的最后一个日志条目的索引值大于等于 nextIndex ，则以 AppendEntries RPC 发送从 nextIndex 开始的所有日志条目
      • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
      • 如果因为日志不一致而失败，则递减 nextIndex 并进行重试

关键特性

  • Election Safety: 选举安全性。对于一个给定的任期号，最多只会有一个领导人被选举出来。
  • Leader Append-Only: 领导者只附加原则。领导人绝对不会删除或者覆盖自己的日志，只会增加。
  • Log Matching: 日志匹配原则。如果两个日志在相同的索引位置的日志条目的任期号相同，那么就可以认为这两个日志从头到这个索引位置之间全部完全相同。
  • Leader Completeness: 领导者完全特性。如果某个日志条目在某个任期中已经被提交，那么该条目必然出现在更大任期号的所有领导者中。
  • State Machine Safety: 状态机安全特性。如果一个领导者已经将给定的索引值位置的日志条目应用到状态机中，那么其它任何的服务节点在这个索引位置不会应用一个不同的日志。

Raft 在任何时候都保证以上的各个特性，这也是 Raft 实现共识算法的基础。

阶段状态（角色）

在任何时候，每个服务节点都处于以下三种状态之一：

领导者（Leader）：处理所有客户端的交互以及日志复制，一个任期内只能有一个领导者。
跟随者（Follower）：绝大多数服务节点在大多数时间都处于跟随者的状态，这些服务节点完全处于被动状态，它们不会发起任何 RPC 请求，仅仅对其它服务节点发起的 RPC 请求做出响应。
候选者（Candidate）：处于领导者（Leader）与跟随者（Follower）之间的一种状态，只在选举新领导者的过程中临时出现，当系统处于稳定状态，只会有一个领导者，其他的服务节点都是跟随者。

下图展示了相关状态图，描述了三种状态以及变化情况。

领导者任期

每届领导者都会有一个任期 term，term 是随着任期数递增的，并且不会被重复使用。Raft 系统中的服务节点会持久化相关数据，其中包括当前任期 term 值。任期这个概念非常重要，Raft 可以根据该值判断过期信息。服务节点之间在通信时会交换当前任期号。如果一个服务节点的当前任期小于另一个服务节点，则它将其当前任期更新为较大的值。如果候选者或领导者发现其当前任期已过时，则将立即恢复为跟随者状态。如果服务节点收到带有过期任期的请求，则会拒绝该请求。

超时处理

Raft 中有两个控制选举的超时设置，第一个是选举超时时间（election timeout），另一个是心跳超时时间（heartbeat timeout）。Leader 发送心跳消息是以心跳超时指定的时间间隔进行的，也就是根据 heartbeat timeout 发送心跳信息。Follower 会在 election timeout 内等待 RPC 消息，如果没有等到则会主动发起选举请求。

在 Raft 中定义了随机超时时间，巧妙地使用随机选举超时时间策略把超时时间都分散开来，在大多数情况下只有一个服务节点先发起选举，这样就能减少因选票瓜分导致选举失败的情况。

Raft 算法中，随机超时时间具有 2 种含义：可以定义为不一样

  • Follower 等待 Leader 心跳信息超时的时间间隔是随机的。
  • Candidate 在一个随机时间间隔内没有获得 majority 投票（含自己一票），那么选举无效，然后 Candidate 发起新一轮的选举。该过程的选举超时时间间隔是随机的。

在 Raft 算法中，选举超时时间随机分配在 [150ms,300ms] 区间中，当 Follower 收到 RPC 消息时（包括选举 RPC、AppendEntries RPC） 都会重置其选举超时时间。

通信

Raft 服务节点使用远程过程调用（RPC）进行通信，其中主要包括以下两种类型的 RPC （Raft 在传输快照时使用的是第三种 RPC）。

  • RequestVote RPC

    由候选人在选举期间发送的 RPC 请求，该 RPC 请求对应的数据结构可以参见前文的 选举 RPC 数据结构 。

  • AppendEntries RPC

    领导者在发送心跳和复制日志条目时会发送该 RPC 请求，该 RPC 请求对应的数据结构可以参见前文的 日志复制｜心跳 RPC 数据结构 。需要注意的是，心跳 RPC 相比日志复制 RPC 缺少了日志条目。

注意：AppendEntries RPC 具有一致性检查的功能，它是实现各节点间日志的一致性（或者说副本数据）的重要机制。

领导者选举

Raft 使用心跳超时机制触发领导者选举。前面已经介绍，如果存在 Follower 在 election timeout 内没有收到来自 Leader 的心跳，则会主动发起选举。没有收到 Leader 的心跳的原因可能是：此时还没有 Leader、Leader 挂了、网络故障。

选举 Leader

下面我们以初始化状态下，集群中所有的节点都是跟随者的状态为例介绍选举过程。

设定，节点初始化状态都是 Follower 状态，任期为 0 ，各节点随机分配的 election timeout 如上图所示 。需要注意的是，节点都会对相关属性进行持久化，防止节点宕机后数据丢失。

等待超时

通过上图可知，集群中没有领导者，而节点 A 的选举超时时间最小（150ms），因此它会最先因为没有等到领导者的信息（不仅仅心跳信息）而发生超时，进而主动发起选举。

切换到 Candidate 状态

节点 A 增加自己的任期编号并推荐自己为候选者，先给自己投上一张票，然后向其它节点发送请求投票 RPC 消息，通常这些请求是并行发出的。注意此时 RPC 消息携带的信息。

响应投票请求

如果其它节点收到候选者 A 的投票请求，在任期编号为 1 的这一任期内还么没有进行过投票，那么就会把票投给节点 A 并将自己记录的任期替换成候选者的任期编号（投票 RPC 中会携带），此外节点的选举超时时间会被重置。投票请求对应的数据结构可参考前文。

切换到 Leader 状态

如果候选人在选举超时时间内获得 majority 投票，那么它就会成为本届任期内新的领导者。

发送心跳消息
节点 A 当选领导者后，它会立刻向其它节点发送心跳消息（AppendEntries RPC），避免其它节点触发新的选举，以维护自己领导者的地位。注意心跳消息一致性检查的作用，通过这种机制，领导者在获得权力的时候就不需要任何特殊的操作来恢复一致性，只需要进行正常的操作，然后日志就能自动的在回复附加日志 RPC 的一致性检查失败的时候自动趋于一致。关于日志复制内容下文详细介绍。以上是正常流选举 Leader 的过程，下面对候选者选举的所有可能情况进行介绍。

选举结果

第一、在选举超时时间内得到了 majority 投票，然后它会将自己的状态切换到 Leader 并立即向集群中其它服务节点发送心跳消息，以建立它的领导者地位并防止进行新的选举。注意，收到 Leader 的 RPC 消息后（包括日志复制消息和心跳消息），其它节点的选举超时时间会重置。这也是前面介绍的正常流的过程。

第二、在等待投票结果时收到其它节点发送的 AppendEntries RPC 消息（以领导者身份），如果该领导者的任期（包括在此次 RPC 消息中）不小于候选者当前任期，则候选者转成 Follower 状态，并更新自己的任期，否则候选者拒绝该 RPC 请求并继续处于候选人的状态。

第三、没有任何服务节点获胜。可能存在有多个服务节点同时成为 Candidate 导致了分票，没有服务节点获得 majority 投票。发生这种情况时，每一个 Candidate 都等待选举超时，其中先超时的会增加其任期，然后进行一轮新的选举。注意这里选举超时时间的重要性，没有该机制的话，选票就可能会被无限地瓜分，那么就延长了系统不可用的时间（没有leader是不能处理客户端相关请求的）。

选举规则

选举过程涉及的约定如下，其中包含了 Raft 安全约定中的部分内容。

  1. Leader 会周期性地向所有 Follower 发送心跳请求（不包含日志项的 AppendEntries RPC）来维持自己的权威，以并行的方式执行，防止 Follower 发起新的选举。
  2. 如果在 Follower 的选举超时时间内没有收到来自领导者的消息（心跳或日志复制），那么就推荐自己为候选人，发起领导者选举。
  3. 选举中获得 majority 投票（含自己一票）的 Candidate 将晋升为 Leader 。
  4. 一个任期内只允许有一个领导者，除非领导者宕机、网络故障等发生，其它节点才会发起新一轮的选举。
  5. 每一个服务节点最多会对一个任期号投出一张选票，按照先来先服务的原则。

    节点 C 的任期编号为 1，先收到一个来自节点 A 的包含任期编号为 2 的投票请求，接着又收到一个来自节点 B 的包含任期编号为 2 的投票请求。按照先来先服务的原则，C 会把唯一的一张票投给节点 A 并更新自己的任期编号，当再收到节点 B 的投票请求时，发现已经对任期编号为 2 的投票请求做出了响应，于是就拒绝节点 B 的投票请求。
  6. 日志完整性高的跟随者不会投票给日志完整性低的候选者，日志完整性高低依据节点最后一条日志条目对应的任期编号及索引号，任期编号更大、索引号更大完整性就越高。

上述涉及到的选票的安全性，会在 Raft 安全部分进行详细说明。

日志复制

日志结构

Log 具有持久化、保序的特点，是大多数分布式系统的基石。在 Raft 算法中，副本数据是以日志的形式存在的，Raft 中的日志结构如下图所示：

日志由有序序号标记的条目组成，每个日志条目包含了：索引（index）、任期编码（term）以及指令（command）。其中提交状态（ committed） 指日志条目被复制到大多数节点后日志条目的状态，applied 是指节点将日志条目应用到状态机。

索引：用来标识日志条目在日志中的位置，是一个连续的、单调递增的整数。
任期编号：创建当前日志条目的领导者的任期编号。
指令：一般由客户端请求指定的、状态机需要执行的指令，本质上是客户端指定的数据。

每个服务节点无论是领导者还是跟随者，都各自保存一个日志副本，日志条目格式如上图所示。每个服务节点都必须保证日志能在奔溃后还可以恢复，所以日志本身需要持久化。领导者将创建的日志条目复制到大多数的服务节点上的时候，该日志条目就会被提交（例如上图中的日志条目 7），同时该日志之前的所有日志条目也都会被提交，包括由其它领导者创建的日志条目。注意，领导者不能单独直接提交其它领导者创建的日志条目，只能在提交自己任期的日志时间接提交，这也是安全性规定的。

日志复制操作

客户端将指令发送给领导者，领导者首先将命令封装成一个日志条目并写入自己的日志中，然后向所有其它的跟随者发送 AppendEntries 的远程调用，通常以并行的方式将调用的消息发送到所有服务节点，然后等待这些消息的响应。一旦领导者收到足够多的响应，该日志条目也就具备提交状态，那么领导者就会将该日志条目的指令应用到状态机并将执行结果返回给客户端，否则返回异常给客户端。需要注意的是，领导者将日志条目应用到它的状态机时并不需要直接通知跟随者应用日志条目，领导者会通过后续的 AppendEntries 远程调用通知其它的服务节点，最终每个跟随者都会知道该记录已提交，然后也将该日志条目应用到它的状态机。

领导者不直接发送消息通知其它节点应用指定的日志条目，是 Raft 的一个优化。通过前文的 AppendEntries RPC 的数据结构，我们知道领导者的日志复制 RPC 消息或心跳消息，包含了领导者已知已提交的最高的日志条目索引，所以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。因此，当其它节点接收到领导者的心跳消息或日志复制消息后，就会将该日志条目应用到它的状态机。这个优化降低了处理客户端请求的延迟。

下图展示了正常流程的日志复制过程：

  1. 接收到客户端请求后，领导者基于客户端请求中的指令会创建一个日志条目并添加到本地日志中。
  2. 领导者通过日志复制 RPC ，将新的日志条目复制到其它的服务节点上。
  3. 当领导者将日志条目成功复制到大多数的服务节点上的时候，领导者会将该日志条目应用到它的状态机中。
  4. 领导者将执行的结果返回给客户端。
  5. 当跟随者接收到心跳消息或者日志复制消息后，如果跟随者发现领导者已经提交了某个日志条目而自己还没有，那么跟随者就将这条日志条目应用到本地的状态机中。

以上是理想状态下的日志过程，在实际环境中可能会遇到进程奔溃、服务节点宕机等问题，这些问题会导致日志不一致。下面我们对日志复制过程进行讨论，主要讨论 Leader 在不同阶段宕机的情况。关于跟随者节点或候选者节点宕机比较容易处理，我们会在后文简单介绍。

  1. 客户端数据到达 Leader 节点之前，Leader 宕机了。

    这种情况对数据的一致性没有影响。
  2. 客户端数据到达 Leader 节点，但未复制到 Follower 节点

    该阶段 Leader 挂掉，数据属于未提交状态，客户端不会收到响应。Follower 节点上没有该数据，重新选举 Leader 后客户端重试重新提交可成功。原来的 Leader 节点恢复作为 Follower 加入集群重新从当前任期的新 Leader 同步数据，强制保持和 Leader 数据一致。
  3. 客户端数据到达 Leader 节点，成功复制到 Follower 所有节点，但还未向 Leader 响应接收

    这个阶段 Leader 挂掉，虽然数据在 Follower 节点处于未提交状态，但是保持一致。重新选举出 Leader 后可完成数据提交。
  4. 客户端数据到达 Leader 节点，成功复制到 Follower 大多数节点，但还未向 Leader 响应接收

    这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以，拥有最新数据的节点会被选为 Leader ，然后再强制同步数据到 Follower ，数据不会丢失并最终一致。注意，如果是成功复制到少数 Follower ,那么数据就可能会丢失。
  5. 客户端数据到达 Leader 节点，成功复制到 Folloer 所有或多数节点，数据在 Leader 处于已提交状态，但在 Follower 处于未提交状态

    这个阶段 Leader 挂掉，选出的新 Leader 拥有最新的数据，对于数据缺失的 Follower 节点，执行同步机制会保证最终一致。
  6. 网络分区导致脑裂，出现双 Leader

    网络分区将原先的 Leader 节点和 Follower 节点分隔开，Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。这时就产生了双 Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点所以永远提交不成功。向新的 Leader 提交数据可以提交成功，网络恢复后旧的 Leader 发现集群中有更新任期的 Leader（任期更大），则自动降级为 Follower 并更新任期且从新 Leader 同步数据达成集群数据一致。

通过上述穷举不难看出，Raft 能很好地应对一致性问题。此外，跟随者崩溃了或处于慢响应状态，领导者会反复重试这个调用，直到跟随者恢复后，领导者就能重试成功。但是领导者并不需要等待每个跟随者的响应，它只需要等到足够数量的响应，保证记录已被大多数服务节点存储即可。所以这样就能在一般情况下获得很好的性能提升。也就是说，在通常情况下，只需要获得大多数最快的服务器的应答，领导者就可以立即执行命令，并将结果返回至客户端。

任期更新

出现网络分区时，可能使集群中出现两个 Leader，网络恢复时该如何处理两个 Leader 的问题呢？Raft 使用任期号来处理。每个 RPC 请求都包括发送者的任期号，接收者收到请求后会将其与自己的任期号相比较，如果不匹配，则会更新那些过期的记录。所以如果发送者的任期比接收者小，接收者会立即拒绝 RPC 请求，并将包括了接受者任期信息的响应发送回发送者，当发送者接收到响应时会发现自己的任期号是过期的，此时它就会停下并作为跟随者继续运行，同时更新自己的任期号。反之，如果接受者的任期号更小，它同样会更新自己的任期号。

选举过程也会导致任期号的更新。候选者发起投票请求时会将自己的任期号随着 RPC 请求发送出去，这样所有的接收者都会更新自己的任期号，与候选者保持一致。

日志的一致性

在 Raft 算法中，领导者处理不一致日志是通过强制跟随者直接复制自己的日志来解决的。也就是说，Raft 是通过以领导者的日志为准来实现各节点日志的一致，这意味着在跟随者中的冲突的日志条目会被领导者的日志覆盖。

日志记录的索引以及任期编号可以唯一标识一条日志条目。Raft 维护着以下特性：

  1. 如果两条日志条目拥有相同的索引和任期号，那么它们存储的指令也是相同的。
  2. 如果两条日志条目拥有相同的索引和任期号，那么它们之前的所有日志条目也全部相同。

第一个特性来自领导者创建日志条目的原则，领导者最多在一个任期里在指定的日志索引位置创建一条日志条目，而且日志条目在日志中的位置不会改变。第二个特性由一致性检查来保证。此外，如果某条日志条目是已提交的，那么其所有前序的记录都应该处于已提交状态。

AppendEntries 一致性检查

Raft 强制在 AppendEntries 远程（日志复制和心跳）调用时进行一致性检查，如果发现问题则需要修复跟随者日志。要使得跟随者的日志和领导者一致，领导者就必须找到最后两者达成一致的地方，然后删除从那个点之后的所有日志条目，发送自己的日志给跟随者。而这些操作都在进行 AppendEntries 的一致性检查时完成。

领导者会为每个跟随者维护一个状态变量 nextIndex ，这个变量存储下一个需要发送给跟随者的日志条目的下标位置索引。当一个服务节点成为领导者后，它会将 nextIndex 值统一设置为自己最后一条日志条目的 index 加 1 。领导者会根据 AppendEntries 调用发现一致性问题，因为当跟随者接收到 AppendEntries 调用时都会进行检查。当领导者与跟随者进行 AppendEntries 通信时，都会包括日志条目下标索引 index 以及任期号 term 作为请求参数，这里日志条目就是 log[nextIndex-1] 的值。当消息到达跟随者后，它会将接收到的下标位置索引与任期与自己的日志信息进行比较，如果不一致就会拒绝当前请求。在被跟随者拒绝之后，领导者就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得领导者和跟随者的日志达成一致。当这种情况发生，附加日志 RPC 就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志 RPC 成功，那么跟随者的日志就会和领导人保持一致，并且在接下来的任期里一直继续保持。

一致性检查流程概括如下：

  1. Leader 初始化 nextIndex 为自己最后一个 log index + 1
  2. AppendEntries 中的 prevLogTerm 、prevLogindex 来自 logs[nextIndex -1]
  3. Follower 会将接收到的下标索引与任期与自己的日志信息进行比较，如果一致则返回 true，否则返回 false。
  4. Leader 收到 Follower 的回复，如果返回值是 false，则 nextIndex -= 1，回到第 2 步进行重试，否则同步 nextIndex 后的所有日志条目。

从一致性检查的过程不难发现，如果 Follower 和 Leader 的日志差异过大会造成 AppendEntries RPC 拒绝次数。但是在实践中，失败是很少发生的并且也不大可能会有这么多不一致的日志。如果一定要优化的话，那么可以采用：当 AppendEntries RPC 请求被拒绝的时候，跟随者可以包含冲突的条目的任期号和自己存储的那个任期的最早的下标索引。借助这些信息，领导者可以减小 nextIndex 越过所有那个任期冲突的所有日志条目，这样就变成每个任期需要一次 AppendEntries RPC 而不是每个条目一次。

一致性检查机制非常重要，如果一个跟随者接受了来自领导者的新记录，那么它的日志记录也与领导者的日志记录是完全匹配的。此外，领导者刚当选时不需要任何特殊的操作来恢复一致性，它只需要进行正常的操作，然后日志就能自动的在回复 AppendEntries RPC 的一致性检查失败的时候自动趋于一致。

日志压缩

Raft 的日志在正常操作中不断增长，但在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响系统的可用性。Raft 采用了快照技术进行日志压缩来解决日志过大问题。快照的缺点就是不是增量的，即使内存中某个值没有变，下次做快照的时候同样会被 dump 到磁盘。

快照结构

由快照结构可知，服务节点使用一个新的快照替换其日志中提交的日志条目（如上图中：索引1到索引5），快照只存储当前状态（如上图中的变量x和y）。并且快照包含一些元数据，其中 last included index、last included term 分别是快照覆盖的最后一条日志条目的索引以及任期号，这两个值用于 AppendEntries RPC 的一致性检查。此外，为了支持集群成员变更，快照中也保存了最新的配置信息。关于成员变更问题在下文中会有详细说明。

Raft 中每个节点独立的创建快照，只包括已经应用到状态机的日志条目。一旦节点完成一次快照，就可以删除最后索引位置之前的所有日志和快照了。

快照发送

正常情况下，Leader 的日志和 Follower 保持一致，但并不是所有情况都处于正常情况之下，有时可能因为 Follower 的反应缓慢或宕机造成日志不一致的情况，这时就需要 Leader 进行日志复制。如果在复制的过程中，Leader 需要发给 Follower 的日志条目被丢失了（因为 Leader 做了快照），这时会通过 InstallSnapshot RPC 发送快照给 Follower，如果没有丢失则直接从日志中复制即可。

InstallSnapshot RPC 数据结构的关键字段如下：

  1. term: Leader 的任期
  2. leaderId: Leader 的id，以便于跟随者重定向请求
  3. lastIncludedIndex: 快照中包含的最后一条日志条目的索引值
  4. lastIncludedTerm: 快照中包含的最后一条日志条目的任期号
    ……

当跟随者收到了 InstallSnapshot RPC 发来的快照，它会根据自身的日志进行处理：

  1. Follower 的日志信息不包括快照中的日志信息，或者包含与快照冲突的信息，这种情况直接使用快照内容替代自己的日志。
  2. 快照中的日志仅是 Follower 日志的子集（前缀）（由于网络重传或者错误），那么 Follower 中被快照包括的部分被代替，之后的部分仍然保留。

快照创建

各节点独立创建快照的方式背离了 Raft 的强领导者原则，因为跟随者可以在不知道领导者的情况下创建快照。虽然快照创建背离 Raft 的领导者原则，但是本质上还是以领导者为中心，并且这种背离是值得的。领导者的存在是为了解决在达成一致性时的冲突，但是在创建快照时一致性已经达成，因为创建快照是基于已经提交的日志条目的，所以没有领导者也是可以的。数据依然是从领导者传给跟随者。

不使用基于领导者的快照方案，一方面减少网络带宽的使用，降低了快照处理的时间，另一方面降低了 Leader 设计的复杂性。

存在问题

写入频率问题

快照不能创建的太频繁，否则会消耗大量磁盘带宽和其它资源。快照创建的频率太低，需要承受耗尽存储容量的风险，同时增加了回放日志的时间。解决上述问题一个简单策略就是设置一个阈值。

服务暂停问题

写入快照需要消耗显著的一段时间，并且我们不希望影响到正常的操作。可以通过 Copy-On-Write 技术解决该问题，如利用 Linux 上的 fork 指令复制父进程及所有内存中的状态，在子进程创建快照，父进程继续提供 Raft 基本服务。

安全性

Raft 的安全性是为了保证每一个状态机会按照相同顺序执行相同的指令，即保证每个服务节点上的日志（数据副本）是一致的。如果没有安全性，数据的正确性和一致性就不能得到保证。例如，一个跟随者可能会进入不可用状态，同时领导者已经提交了一些日志条目，如果没有安全性，这个跟随者可能会被选举为领导者并且覆盖这些日志条目。前面的章节主要描述了 Raft 算法是如何选举和复制日志的，其中已经穿插了不少的安全机制，本章节对安全性进行补充。

选举限制

Raft 是一种强领导者模型的算法，只有从集群中选举出 Leader 才能处理客户端请求和协调 Raft 内部运行机制（如：心跳、日志复制，以及它们对应的一致性检查等）。

一个任期内只允许有一个领导者，这是由一个服务节点某一任期内最多只能投一票 和 只有获得 majority 投票的服务节点才会成为 Leader 这两个原则来保证的。为了实现这种机制，服务节点需要保证将自己的投票信息持久化，这样就能在服务节点崩溃之后也能恢复到之前的状态。否则就会出现服务节点已经作出投票，但在崩溃重启后在同一任期内将票又投给了另外一个不同服务节点的情况。

当一个候选者发起投票请求，它会包括自身的日志记录信息，索引 index、任期号 term 。当跟随者接收到请求，它会将候选者的日志信息与自己的日志信息进行比较，如果投票者的日志更完整，那么它会拒绝投票。Raft 是通过比较两份日志中最后一条日志条目的索引值和任期号定义哪个日志更新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更新，如果两份日志最后的条目任期号相同，则索引值大的更新。

Raft 保证所有之前的任期号中已经提交的日志条目都会出现在新的领导者中，不需要传送这些日志条目给领导者。这意味着日志条目是单向传送的，只能从领导者传给跟随者，并且领导者从不会覆盖自身本地日志中已经存在的日志条目。

当前任期提交

只要日志条目被复制到大多数的服务节点上，领导者就可以提交当前任期内的这一日志条目。领导者不会根据大多数原则去提交一个之前任期内的日志条目，只会根据大多数提交当前任期的日志条目。一旦当前任期的日志条目被提交，那么根据日志匹配特性，之前的日志条目也都会被间接的提交。如果领导者被选举后迟迟收不到客户端的请求，也就是意味着该领导者还不能确认哪些日志条目被提交，基于这个问题 Raft 通过让每个 Leader 在其任期开始时向日志中提交一个空的没有任何操作的日志条目，立即尝试复制来处理这个问题。

状态机安全

Raft 中某个节点将某一位置的日志条目应用到状态机，那么其它节点在同一位置不能应用不同的日志，也就是说，所有节点在同一位置（index）必须应用同样的日志。

成员变更

Raft 算法是强领导者模型，领导者选举建立在大多数的基础之上，当集群中的成员变更时就可能同时存在新旧配置的 2 个大多数，进而出现两个领导者，这会破坏 Raft 集群的领导者唯一性，影响了集群的运行。

尽管可以通过暂停整个集群，更新所有配置，然后重启整个集群的方式来解决因集群变更带来的问题，但是在更改的时候集群会不可用。Raft 通过单节点变更来解决成员变更问题。这里我们需要明确两个定义：

配置

这里的配置是对集群中节点的描述，包括每台服务节点的 ID 、网络地址等。比如：A、B、C 组成的集群，那么集群的配置就是 [A、B、C] 集合。这些信息都非常重要，因为我们需要用它们来决定多数票的具体数量，从而进行领导者选举或用来提交日志。

单节点变更

单节点变更是利用一次变更一个节点，不会同时存在旧配置和新配置 2 个 大多数的特性，实现成员变更。

节点奔溃

前面的章节对领导者节点的奔溃进行不同场景的介绍，核心关注点在于领导者节点奔溃的时机，不同时机奔溃集群处理不同，但是关键一点是大多数共识的日志条目不会丢失。跟随者和候选者奔溃后的处理方式相对比较简单，并且它们处理的方式相同。如果跟随者或者候选者奔溃了，后续发送它们的 RPC 消息都会失败。Raft 中处理这种失败就是简单的通过无限重试，如果奔溃的节点恢复了，那么 RPC 消息就会成功。如果一个服务节点完成了一个 RPC 请求，但是还没有响应的时候奔溃了，那么恢复后就会再次收到同样的请求。Raft 的 RPC 都是幂等的，所以这样重试不会造成任何问题。

客户端协议

请求领导者

Raft 中的客户端发送所有请求给领导者，当客户端请求的不是领导者时，那么该服务节点会拒绝客户端的请求并向客户端提供它最近接收到的领导者的信息（AppendEntries RPC包含了领导者的网络地址）。如果领导者已经崩溃了，那么客户端的请求就会超时，客户端之后会再次重试随机挑选服务节点。

线性语意

Raft 的目标是要实现线性语义（每一次操作立即执行，只执行一次），但 Raft 是可以执行同一条指令多次的，如领导者提交日志条目后宕机了，那么客户端会和新的领导者重试这条指令，导致这条指令被再次执行。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

Raft 读取的是状态机运算后的数据。Raft 的读操作虽然直接从领导者节点读取，但是在网络分区的情况下可能会返回脏数据，而线性的读操作必须不能返回脏数据，Raft 使用两个额外的措施保证这一点。首先，领导者必须有关于被提交日志的最新信息，领导者完全特性保证了领导者一定拥有所有已经被提交的日志条目，但是在它任期开始的时候，可能还不知道哪些是已经被提交的，为了知道这些信息，它需要在它的任期里提交一条日志条目。Raft 中通过领导者在任期开始的时候提交一个空白的没有任何操作的日志条目到日志中去来实现。第二，领导者在处理只读的请求之前必须检查自己是否已经被废黜了（更新的领导者被选举出来）。Raft 中通过让领导人在响应只读请求之前，先和集群中的大多数节点交换一次心跳信息来处理这个问题。

小结

Raft 算法本质上是通过复制日志来实现共识的，和客户端的交互依赖状态机执行日志条目的指令，集群内部通过选举、心跳、日志复制来协调。Raft 具体的做法是将共识问题分解为多个独立的子问题，高度概括为：先选举出领导者，由它完全负责 replicated log 的管理。此外，接受客户端写请求，然后复制到跟随者节点，并在 安全 的时候执行这些请求。

gentryhuang xw

万丈高楼平地起