Raft 实现日志复制同步

阳光穿透心脏的1/2处 2022-07-11 14:58 110阅读 0赞

# Raft 实现日志复制同步 #

本篇文章以 John Ousterhout（斯坦福大学教授） 和 Diego Ongaro（斯坦福大学获得博士学位，Raft算法发明人） 在 Youtube 上的讲解视频及 ppt 为蓝本，深入分析 Raft 的内部机制，并以日志复制同步（Replicated Logs）为背景，详细介绍使用 Raft 协议实现日志复制的共识性问题。

![image][]

## 目标：日志复制同步 ##

![image][image 1]

Raft 的目标是将日志完整地复制到集群内的所有服务器，这些复制的日志会被状态机所使用。假设我们希望程序或应用能可靠地执行，能够实现的一种方式是保证集群中所有服务器内的状态机都能按照相同的方式执行命令，这就是状态机复制同步的目的，这里的状态机通常指的是一个输入输出程序或应用。日志可以保证状态机执行相同的命令。下面介绍它的运作机制。

如果系统的客户端将要执行的命令传递给集群中的一台服务器，假设命令是 X ，那么它会被该台服务器记录，然后命令会被发送到其他服务器，并被其他服务器上的日志所记录。一旦命令被安全的复制到日志中，那么它们就能被发送到状态机供执行。当其中的一台状态机完成了命令的执行，结果会被返回给客户端。可以注意到只要各个服务器上的日志是相同的，各个服务器上的状态机就能以相同的顺序执行相同的命令，这样它们执行的结果也都是一样的。所以共识性模块的任务就是管理这些日志，并保证它们正确的在集群内复制并且决定何时将命令传送给状态机才是安全的。

我们将这一过程称为共识性方法的原因是我们不需要所有的服务器在任何时候都处于运行状态，实际上，系统只要在大多数服务器存活的状态下能继续正常运行和相互通信就可以。所以例如可能有 3 台服务器，那么我们就可以接受其中 1 台服务器宕机，只要有两台服务器是存活的即可；当服务器有 5 台时，我们就可以接受其中的 2 台服务器宕机，只要其中三台是正常运行的。

现在我们来简短地介绍希望系统能够处理的失败的情况。我们允许服务器崩溃，不过我们希望它们是 “失败-停止（fail-stop）” 的方式。也就是说，它们只是停止工作，或者在停止后又恢复，不过要求只要它们是处于运行状态的，它们的行为就必须正确。这个协议要求服务器不能有 拜占庭行为 做一些错误的操作。我们还允许网络的通信可以被打断，消息可以出现延迟或丢失的状态，甚至出现消息到达处于无序的状态。网络也有可能出现隔离的情况，然后又恢复正常。

## 达成共识性的方式 ##

![image][image 2]

想要实现共识性算法主要有两种方式：第一种方式称为对称式或无主式，在这种方式下，所有的服务器都有相同的角色，它们有同等的权力，它们任何时候的行为几乎都是一样的，客户端可以与任何一台服务器进行通信。第二种方式称为非对称式或基于领导者（leader），服务器在任何时候都不是对等的，只有其中的一台服务器是领导者（leader），领导者负责集群的所有操作，其他的服务器只是简单地服从领导者发出的指令，在这种系统下，客户端永远与领导者通信，只有领导者才与其他的服务器发送通信。

Raft 就是使用上面第二种方式。它将共识性算法的问题分解成两类不同的问题，一种是在领导者正常运行下，进行的普通操作；另一种是在领导者崩溃时，需要对领导者进行重新选举，这种方式有其优势，它让普通的操作变得非常简单，不需要关心是否有多个领导者相互发生冲突，或同时发出指令，只要有一个领导者控制全局，就可以完全按照它的指令来运行。Raft 算法的复杂之处在于领导者发生变化时，因为当领导者崩溃时，会使系统处于不一致的状态，后续被选举的领导者需要对此这些不一致状态进行清理。总体上说，基于领导者的方式要比无领导者的方式简单，因为无须担心不同服务器间会出现冲突，只须关心领导者发生变化的情况。

## Raft 概览 ##

![image][image 3]

Raft 算法共分成 6 个部分，首先我们要介绍的就是领导者的选举。

1.  如何从所有的服务器中选择领导者？如何在当作为领导者的服务器崩溃时能检测到故障并挑选另一个领导者来替代它？
2.  会介绍当领导者接收到客户端请求时，系统是如何处理正常操作的。这是 Raft 算法中最简单的部分。
3.  会讨论领导者发生改变的情况，这部分是 Raft 中最复杂的，也是保证整个系统行为最重要的部分。首先，会讨论什么叫做安全，如何保证安全？其次，领导者是如何识别日志的一致性的，从而可以将系统恢复到处于一致状态下。
4.  会讨论领导者发生改变时的另一个问题。如何让曾经崩溃死机的老领导者，重新回归到集群后集群的状态仍然能保持一致。
5.  会谈论客户端是如何与集群交互的。关键点在于客户端是如何处理服务器崩溃，如何保证客户端发送的命令是线性的，即操作执行也仅执行一次。
6.  最后会讨论如何处理配置变更的情况，即如何对集群增加或移除服务器。

## 服务器的状态 ##

![image][image 4]

在对这六步进行详细地介绍前，先来介绍一些总体信息。

任何时候，服务器都处于以下三种状态中的一种：

*  **领导者（Leader）**：如前面已介绍的，领导者处理所有客户端的交互以及日志的复制同步，在任何时候只能有一个领导者。
 *  **跟随者（Follower）**：绝大多数的服务器在大多数时间下都处于跟随者的状态，这些服务器完全处于被动状态，它们不会发起任何 RPC 调用，它们所做的只是对其他服务器发起的 RPC 调用做出响应。
 *  **候选者（Candidate）**：它是处于领导者（Leader）与跟随者（Follower）之间的一种状态，它在只在选举新领导者的过程中临时出现，在系统处于普通状态下，只会有一个领导者，其他的服务器都是跟随者。

在上图最下面展现了一个状态图，它展示了三种状态，以及三种状态在不同条件下发生转变的情况。现在不会对此进行详细解释，但是在随后对算法作详细介绍时，就能发现它们之间的联系。

## 领导者任期 ##

![image][image 5]

时序被分割为领导者任期，每段领导者任期都有一个序号，这些序号随着任期数的增加会自动增长，不会被重复使用。每段任期都分为两个部分，首先，任期是由选举开始的，这个过程会挑选任期内的领导者，如果选举成功，被选择的领导者会服务至本任期结束。在同一任期内，只有一台服务器可以被选择为领导者。不过也会存在某些任期没有任何领导者，如果出现分票就会出现这种情况，不存在获得大多数投票的领导者，当发生这种状况时，系统会即刻进入到下一个新的任期并尝试重新选举。在 Raft 系统的所有服务器都保持着一个被称为当前任期的值，这个信息必须存于服务器的可靠媒介中（如硬盘）。这样就能在服务器崩溃之后得以重启并恢复。任期这个概念十分重要，它使 Raft 可以判断过期的信息。例如，如果一台服务器认为当前的任期号是 2 与另一台认为当前任期号为 3 的服务器进行通信，那么我们就能知道来自于服务器 2 的信息是过期的，我们只会使用来自于最新任期的信息。所以我们将会看到在某些情况下，会使用到任期来检查并消除过期的信息。

## Raft 协议总览 ##

![image][image 6]

上图是 Raft 协议的完整概括，目前还不会对它们进行详细的介绍，但是会简单介绍一些它的特性。

首先分别描述 Raft 协议里的三种角色：跟随者（Followers）、候选者（Candidates）和领导者（Leaders）。

其次描述需要在服务器磁盘上进行持久化存储的信息。

第三描述服务器是如何进行通信的，Raft 的所有通信都是基于远程过程调用的（RPCs），这里只有两种类型的调用：一种被称为远程过程调用投票（RequestVote RPC），它在选举的过程中被用来挑选领导者；另外一种远程过程调用是领导者用来执行正常操作，复制日志记录的。这是 Raft 系统使用的唯一两种远程过程调用的方式。这两种调用都可以很好的处理日志复制同步以及消息丢失等问题。

## 心跳检测及超时处理 ##

![image][image 7]

现在让我来一一讲解 Raft 协议的六个组件。Raft 协议的第一个组件是选举。Raft 必须保证在任何时候只能有一台服务器作为集群的领导者。服务是以跟随者角色启动的，处于这种状态时，它不会与其他的服务器进行通信，跟随者完全是被动的，它只是简单地对来自于其他服务器的远程调用做出响应。不过，为了让跟随者一直处于跟随者的状态，必须使它们相信集群有一个活跃的领导者存在。唯一能实现的方式就是，如果它接收到来自于其他服务器的通信，无论是领导者或是候选者，所以如果领导者想要保持它的领导地位，它就必须定期与集群的其他服务器进行通信，如果它没有与其他服务器进行主动通信的需要，那么它也必须发送心跳检测的消息，在 Raft 协议中，这些心跳检查消息也只是一些不含任何数据信息的 AppendEntries 远程调用。如果在一段时间内，跟随者没有接收到任何的远程调用，那么它会假定集群内没有可达或可用的领导者，所以它就会开始进行选举，看它是否有必要成为新的领导者。这段时间周期被称为选举超时（electionTimeout），通常集群将这个时间定为 100ms 到 500ms 。所以当集群启动时，所有的服务器都是作为跟随者的，没有领导者，所以它们都会等待这段超时，然后它们都会开始进行选举。

## 选举 ##

现在让我们看看，选举是如何工作的。

![image][image 8]

当服务器开始进行选举的时候，它所做的第一件事情就是增加当前的任期号，创建一个比之前使用过的任何值都要大的新任期号。随后，服务器将它们自己从跟随者状态转换到候选者状态，在这种状态下，它的目标就是要让自己当选为领导者，为了这么做，它需要接收来自于大多数服务器的投票。候选者要做的第一件事情就是给自己投票，然后它会给其他所有服务器发送投票请求的远程调用（RequestVote），通常这些请求是并行发出的。如果它没有获得响应，它就会持续发送重试的请求，直到获得响应为止。

最终会出现三种情况中的其中一种：

第一，在大多数情况下，也是我们希望出现的情况就是候选者得到了多数票，然后它会将自己的状态转换为领导者并立即向集群其他服务器发送心跳检测，这可以建立它的领导者地位，有效的标记领导者所管理的范围。

第二，可能出现有其他的候选者也同时在运行，或许它们也有可能获得多数票成为领导者，在这个点上，如果候选者收到来自于有效领导者的 RPC 调用，那么它会立即放弃成为领导者的可能，随即回到跟随者的状态。

第三，有可能没有任何服务器得以获胜，如果存在有多个服务器都同时成为候选者，它们会导致分票，没有服务器会获得多数选票。为了检测到出现这种状况的可能性，随着时间的推移，当没有出现以上第一、第二种情况时，它既没有成为领导者，也没能获得来自于其他领导者的响应，那么它就会假定出现分票的情况。在这种情况下，只要简单地增加任期号，重新选举即可。

## 选举的安全及可用 ##

![image][image 9]

选举有两个重要的属性：安全（Safety）和可用（Liveness）

**安全（Safety）** 指的是必须最多只有一个候选者可以在某一任期内赢得领导者地位。Raft 可以保证这件事。每台服务器只给一个候选者投票，一旦它投出选票，它就会拒绝来自其他候选者的任何请求。服务器并不关心它的票到底投给了哪台服务器。为了实现这种机制，服务器需要保证将自己的投票信息存储到磁盘，这样就能在服务器崩溃之后也能恢复到之前的状态。否则就会出现服务器已经作出投票，并在崩溃重启后，在同一任期内将票又投给了另外一个不同服务器的情况。因为每台服务器只能进行一次投票，而且每个候选者都必须获得多数票，也就可以发现，不可能出现两个候选者同时获胜的情况。

比方说有三台服务器在某一任期内进行选举，另外两台服务器显然无法获得多数票。不过后面会介绍不同任期间会出现不同候选者获胜的情况，但在某一确定的任期内，只有一个候选者可以被选举为领导者。

**可用（Liveness）** 需要保证一定有获胜者，这样系统不会永远处于没有领导者的状态。问题在于理论上，会反复出现分票的情况，多个候选者在同一任期内同时开始进行选举，这样就会导致分票，在超时之后，又进行新一轮的选举又再次出现分票，所以从理论上说这样的状态可以无限循环下去。Raft 需要分散出现超时的间隔，每台服务器都会随机的计算下次超时的间隔时间，这个时间间隔在 \[T, 2T\] 之间。T 代表着选举超时的时间，即服务器可能出现超时的最短时间。通过将超时时间分散，可以降低两台服务器同时开始选举的机率，先启动的那台有足够的时间向其他所有服务器发起请求，并在其他服务器参与竞争之前就完成选举这个过程。当这个超时间隔时间远大于广播投票请求的时间时，这个策略会变得更为有效。这里的广播时间指的是，一台服务器与其他所有服务器通信所需的时间。

## 日志的结构 ##

![image][image 10]

现在进入 Raft 协议的第二部分，即领导者用普通操作来处理日志复制同步时使用的机制。

首先，让我们说说日志本身。每台服务器无论是领导者还是跟随者，都各自保存一个日志副本。日志本身被分成了多条记录（Entries），记录是由下标索引的位置来进行唯一标识的，在记录内部有两个主要信息：首先，每条记录都包括供状态机执行的一条命令，命令的格式可以是客户端与状态所达成一致的某种格式。其次，每条记录都包括一个任期号，这个任期号是该条记录创建时，领导者所处的任期，随着日志记录的增多，这个任期号也会单调上升。每台服务器都必须保证日志能在崩溃后还可以恢复，所以日志本身通常是存于磁盘或其他一些稳定的存储介质中。无论服务器作何更新，它都需要在收到来自于其他服务器的响应之前，将内容写入到磁盘。如果某条记录已存储于大多数服务器，例如上图中的记录 7 （Entry-7），那么我们就称该条记录已提交（committed）。这是 Raft 协议里非常重要的一个属性。如果一条记录是已提交的，那么它就能安全被传送给状态机进行执行，Raft 可以保证该条记录的耐久性。在上图中记录 7 是已提交的，所有先于记录 7 的记录也是已提交的状态，但是记录 8 还处于未提交状态，因为它只存储于两台服务器上。

现在需要注意的是，在稍后讨论如何管理跨服务器日志间的一致性的时候，我会对提交（commitment）这个概念的定义作些许修改。

## 普通操作 ##

![image][image 11]

普通操作比较简单，客户端将命令发送给领导者，领导者首先将命令写入它自己的日志中，然后向所有其他的跟随者发送 AppendEntries 的远程调用。通常这些调用的消息会被同时发送所有服务器，以并行的方式执行，并等待这些消息的响应。一旦领导者收到足够多的响应，可以它认为该条命令已经在多数服务器上处于已提交状态时，那么该条命令就可以被执行。领导者这时会将命令发送给状态机，当执行结束后，它会将结果返回给客户端。不仅如此，一旦服务器知道某个记录已经处于提交状态，它就会通过后续的 AppendEntries 远程调用告知其他的服务器。所以最终，每个跟随者都会知道该记录已提交，并且将该命令发送至自己本地的状态机执行。如果跟随者崩溃了或处于慢响应状态，领导者会反复重试这个调用，直到跟随者恢复后，领导者就能重试成功。但是领导者并不需要等待每个跟随者的响应，它只需要等到足够数量的响应，保证记录已被大多数服务器存储即可。所以这样就能在一般情况下获得很好的性能提升。也就是说，在通常情况下，只需要获得大多数最快的服务器的应答，领导者就可以立即执行命令，并将结果返回至客户端。例如，如果某个服务器很慢，这并不能影响客户端获得响应的速度，因为领导者并不需要一直等待该台服务器。

## 日志的一致性 ##

![image][image 12]

Raft 期望能将集群日志维持高水准的一致性。理想状态下，这些日志在任何时候都是相同的，甚至是服务器崩溃时也如此。Raft 会尽可能的保证在不同服务器上的日志是一样的。上图的内容会列出一些重要的属性，它们在任何时候都是有效的。

第一，日志记录的索引以及任期号的组合可以唯一标识一条日志记录。也就是说如果有两条记录的索引是一样的，任期号也是一样的，那么就可以保证它们所存储的命令也是相同的。除此之外，还能保证在这条记录之前的所有记录都能相互匹配。所以任期号和索引的组合可以唯一标识整个日志的起始至该点的位置。如果某条记录是已提交的，那么其所有前序的记录都应该处于已提交状态。这也与之前介绍的规则一致，如果发现服务器存储记录（如上图的记录 5），因为有了以上规则，它们存储的前序记录也必须相同。所以这些前序记录也存在于集群的大多数服务器上。

## AppendEntries 一致性检查 ##

![image][image 13]

这个属性强制在 AppendEntries 远程调用时进行检查，当领导者向跟随者发起 AppendEntries 调用时，除了新创建的新日志记录，它还包括两个值。他包括当前新记录前序记录的下标位置索引以及任期号，跟随者只会接受与它日志匹配的远程调用，如果跟随者的日志没有相应的记录，那么它会拒绝这个远程调用。

让我们来看一个例子，假设领导者从客户端接收到一个新命令 jmp ，它将这个命令以 AppendEntries 远程调用的方式发送给跟随者，包括它前序记录的下标位置索引以及任期号，这里下标位置索引是 Index-4 ，任期号是 Term-2 。这样跟随者会将此信息与它自己当前日志的记录匹配，然后接受创建新的记录。如上图下半部分，跟随者的当前最新记录与领导者的前序记录的信息不匹配，这样跟随者会拒绝接受远程调用的请求。

这个一致性检查的过程非常重要。可以将这个过程看作一个归纳的步骤，从而保证前面一致性里所讲的内容。它要求前序每条记录都能满足此条件，所以这意味着如果一个跟随者接受了来自领导者的新记录，它的日志记录也与领导者的日志记录是完全匹配的。

以上就对普通操作的介绍告一段落。接下来介绍领导者变更的情况。

## 领导者变更 ##

![image][image 14]

当领导者发生变更时，新领导者面对的状态不一定是干净的，因为前一领导者可能在它完成复制同步之前就已经崩溃了，当 Raft 处理这个问题时，它在新的领导者被选出之前，不会有任何特别的操作，不会存在一个独立清理过程，清理过程是在普通操作过程中发生的。原因是当新领导者被选出后，某些服务器可能还处于宕机的状态，不可能立刻对它们的日志进行清理，必须能有操作恢复它们，而且在这些机器重新加入集群之前可能会要等待很长一段时间，所以就必须对系统进行设计，要求普通操作最终能让所有的日志达成一致状态。为了达成这个目标，Raft 始终会认为领导者的日志总是正确的，所以对于所有领导者，它们必须时刻的让跟随者的日志与自己保持一致，但同时还是有可能出现在领导者未完成任务就崩溃的情况，所以就会出现一个又一个的新领导者。所以，在极端扭曲的状态下，日志记录会无限堆积并出现混乱的状态，就如上图所示的那样。

为了简单起见，上图中只显示了下标索引位置以及任期号，没有显示具体的命令信息。

当服务器 S4、S5 在任期 2、3、4 时是领导这，但是由于某些原因，它们无法完成对其他服务器（S1、S2、S3）上日志的复制同步，然后它们崩溃了，系统在一段时间内处于分隔状态，服务器 S1、S2、S3 在任期 5、6、7 内成为领导者，但同时也无法与服务器 S4、S5 进行通信，要求它们进行相应的清理操作。这就会出现上图中所示的状态，日志完全是混乱的。这里的关键在于 S1、S2、S3 的索引 1-3 以及 S4、S5 的索引 1-2 区域。这些都是已提交状态的记录，所以我们必须保留它们，但其他的日志记录都是未提交的，所以到底是保留还是丢弃它们并不重要。我们还没有将它们传入状态机，也没有客户端得到了这些命令的执行结果。所以它们都是可以丢弃的。

例如，假设服务器 S4 是任期 7 的领导者，而且它可以与其他所有服务器通信，那么它最终会让集群里其他服务器上的日志与它自己的保持一致，并删除那些与之冲突的记录。在介绍领导者是如何让其他服务器上日志与之保持一致前，首先需要介绍两个概念：正确性（Correctness）和安全性（Safety）。我们是如何知道系统的行为是正确的？如何知道它们没有丢失一些重要信息？因为这里可以看到，为了让集群回到一致的状态，有些日志记录会被丢弃。我们是如何安全地做到这点的？

## 安全性的要求 ##

![image][image 15]

几乎所有的日志复制同步系统都会对安全性有所要求，一旦某个状态机接收了一条日志记录并执行，我们必须保证不存在其他的状态机执行不同的命令。需要保证所有的状态机，以相同的顺序执行相同日志记录的命令。为了达成总体的安全性要求，Raft 实现了一个安全属性，一旦领导者决定某个特定记录已提交，那么 Raft 就需要保证该条记录会出现在它所有未来领导者的日志记录中，并且也处于已提交状态。如果我们可以让 Raft 遵从这个属性，那么它就自然可以保证以上的安全性要求。首先，领导者永远不会覆盖日志记录，它只会追加，正如我们所知，作为领导者时，这些日志记录永远不会被改变，其次，为了到达已提交的状态，记录必须在领导者日志中，这样就不会有其他值会被提交，第三，如果我们知道日志记录必须在发送给状态去执行之前被提交，所以将以上三点放在一起，我们就能使该属性可以满足安全性的要求。

目前为止，我们对 Raft 的描述还不能保证这个属性。下面我会来看看 Raft 是如何解决这个问题的。不过再次之前我们需要再看看，如果某条记录是已提交的，那么它在未来的领导者日志记录中也必须是已提交的。为了满足这个要求，我们会从两个方面对 Raft 算法作出修改。首先，我们会修改选举过程，将日志记录不正确的那些机器排除在选举之外，其次，会对已提交的定义做略微的调整。有时在知道安全之前，我们会延迟一条记录的提交。

下面会先介绍选举相关的问题

## 挑选最好的领导者 ##

![image][image 16]

如何保证选择的领导者有所有已提交的日志记录？首先，这有点微妙，事实上我们无法辨别哪些记录是已提交的，假设有如上图的三台服务器，我们需要选择一个新的领导者，但其中的一台服务器不可用，那么只要在这个过程中，查看可用的服务器，我们此时是无法分辨记录 5 是否已提交，它依赖于不可用服务器上存储的内容。在这个例子中，记录 5 是已提交的，但在其他情况下，可能不是。可以肯定的是我们无法知道哪些记录已被提交了。所以我们能做的就是找到一个候选者，这个候选者很有可能包括所有已提交的记录，我先从直观上尝试解释如何做到的，然后在用精确的方式加以证明，我们是能够挑选到候选者存有所有已提交的记录的。

我们通过比较日志的方式来实现。当一个候选者发起投票请求，它会包括自身的日志记录信息，位置索引 index 以及该记录的任期号 term 。当响应投票的服务器接收到请求，它会将候选者的日志信息与自己的日志信息进行比较，如果投票者的日志更完整，那么它会拒绝投票（lastTerm v > lastTerm c）|| (lastTerm v == lastTerm c) && (lastIndex v > lastTerm c)。结果是赢得选举的服务器可以保证比大多数投票者有更完整的日志记录。

让我们看看实际到底是如何工作的。

## 在当前任期提交记录 ##

最有趣的情况恰好是在领导者决定刚决定日志记录是已提交的时候，会有两种场景：

*  第一种：提交的记录是在当前任期

![image][image 17]

这里任期 2 以及领导者（S1）刚成功调用 AppendEntries 至 S3 ，此时它发现记录已在大多数服务器上存储，随即标记该记录是已提交的，并将其传送给状态机。此时这条记录是安全的，下一任期的领导者必须认定该记录的已提交状态。正如之前介绍的规则，S5 是无法成为下一任期的领导者，S4 也无法成为领导者，所以只有 S1、S2、S3 可能被选举成领导者，实际上，如果 S1 在它们中间，S1 一定可以保证赢得选举，但 S2、S3 也可以通过获得其他服务器（S4、S5）的投票，获胜成为领导者。但在任意一种情况下，下一任期的领导者都必须包含该日志记录。

*  第二种：提交的记录是在前序任期
    
    ![image][image 18]
    
    在这种状态下，领导者在任期 2 只复制了两台服务上的日志记录，随后任期 3 的领导出（S5）于某些原因没有关注到这些记录，在它本地创建了一些记录，然后崩溃了。然后在任期 4 上，领导者（S1）作为试图将其他服务器上的日志内容与它自己的达成一致。所以它让服务器 S3 复制了它自己 Term-2 记录，在这个点上，该记录已被领导者知道存于大多数服务器上，但该记录并没有安全的被提交。因为此时 S1 可能出现崩溃，S5 成为领导者，因为它的前序任期值 3 较大，所以它可以获得来自于 S2、S3、S4 的投票，如果它当选，那么它会试图将自己的日志推到其他的服务器，这也就意味着从 S1 - S4 下标位置索引 3 开始的所有记录都会被删除。所以此时我们还无法认定记录 3 是否已经提交。

## 新提交规则 ##

![image][image 19]  
在这种情况下，新的选举规则并不足以保证安全性（Safety），我们还需要修改提交的规则。到目前为止只要领导者发现记录已存于大多数服务器，那么它就认为该记录已被提交。但是为了保证安全性，我们需要增加另一条规则。除了上述规则，领导者必须能看见至少有一条来自于它本任期内的记录也存于大多数服务器。回到之前的例子，如果领导者完成了记录 3-2 的复制，它此时还无法提交该记录并将其发送给状态机，取而代之的是，它必须等待直到它当前任期内的第一条记录（4-4）提交并存于大多数的服务器。至此，两条记录才能都发送给状态机。这么做的原因在于，在这种状态下，服务器 S5 是不可能被选举为下届领导者的，因为有更多的服务器处于更近的任期（任期 4），服务器 S5 只能从服务器 S4 处得到选票。此时，记录 3 和 4 都是安全的。所以将新选举规则来比较日志与新提交规则相结合，我们就能保证 Raft 的安全属性总是有效的。即一旦领导者决定记录已提交，它就会对未来的所有领导者可见。这里我们展示的例子只说明，已提交的记录对下一任期的领导者可见，但也可以很容易就证明，每个未来的领导者也会有相同的日志记录。

## 日志的不一致 ##

![image][image 20]

现在我们可以保证安全性，也明白了日志是正确的。那么我们如何让所有跟随者的日志都与领导者保持一致呢？首先，让我们来看看日志不一致可以出现怎样的情况。

*  跟随者可能会丢失记录（如 (a)-10、(b)-5、(e)-8）
 *  跟随者可能会有不同的记录（如 (d)-11、(f)-4、(c)-6）

需要做的是剔除所有不同的日志记录，并将所有丢失的记录根据领导者的日志填充完整。

## 修复跟随者的日志 ##

![image][image 21]

要想恢复到一致状态，领导者会为每个跟随者维护一个状态变量，这个变量称为 **nextIndex** ，这个变量存储日志的下一条记录的下标位置索引，服务器会把这个位置发送给跟随者（如上图所示，nextIndex = 11）。当一台服务器成为领导者后，它会将 nextIndex 值设置成当前日志记录的下一位置。所以在上面的例子中，任期 7 的领导者的最后一条记录的索引位置是 10 ，那么它会将 nextIndex 设置成 11 。领导者会根据 AppendEntries 调用发现一致性问题，因为当跟随者接收到 AppendEntries 调用时，都会进行检查。这个检查就可以发现所有的问题。所以当下一次领导者想要与跟随者进行通信时，它都会包括下标位置索引（10）以及任期号（6）作为请求的参数。当选为领导者后，下一次请求也有可能是以心跳检测的方式发送的，心跳检测与 AppendEntries 调用的方式一样，只是没有新值创建，但还是包括一致性检查的。所以当消息到达跟随者（a）后，它会将接收到的下标位置索引与任期与自己的日志信息进行比较，并没有匹配的记录，所以它会拒绝 AppendEntries 请求，当领导者收到拒绝的响应之后，它的响应很简单，它要做的只是将 nextIndex 减 1 ，所以这个值就变成了 10 。如此逐一减少，直到最终 nextIndex 为 5 的时候，领导者再次发送请求的信息会包括下标位置索引（4）以及任期号（4），这时它与跟随者（a）当前的日志记录信息是相匹配的，所以这时跟随者会接受 AppendEntries 请求，并追加记录 5-4 。直到领导者将跟随者的日志记录填充完整。相似的过程也会在跟随者（b）上出现。当 nextIndex 减少到 4 时，领导者会包括下标位置索引（3）以及任期号（1）作为请求的参数，并修正跟随者（b）上的日志记录。

![image][image 22]  
这个过程还需要注意一点，当跟随者接收来自于领导者的替换请求时，它会将后续的日志记录截断并删除后续的所有日志记录，在上述的例子中，如果领导者发送请求（4-4），nextIndex = 4 ，这时跟随者的记录为 4-2 ，是不一致的，这时它不仅会将 4-2 覆盖，同时还会删除剩余的所有记录，因为在不一致的记录后也都是不一致的记录。

现在对领导者发生变更的情况作个小结。总体上需要解决两个问题：一个是需要保证系统的安全性，第二个是一旦新的领导者开始行使权利，它要做的事情就是使所有跟随者上的日志记录与自身保持一致，AppendEntries 的一致性检查会为我们提供所有的信息。

## 平衡旧领导者（Neutralizing Old Leader） ##

![image][image 23]

Raft 协议的第四步也是与领导者更替相关的。旧领导者有可能并不是真的死了。例如出现了网络的隔离，将领导者与集群内其他服务器分隔，那么剩下的服务器会等待选举超时，并选举一个新领导者，那么问题来了，如果旧领导者又重新恢复连接怎么办？这个旧领导者并不知道已经重新进行了选举，也不知道新领导者的存在。所以这时它还会试图以领导者的身份继续运行，它还会与跟随者进行通信，并试图让其他跟随者与自己的日志记录保持一致，我们必须阻止这个事情的发生。

可以使用任期来防止这种情况的出现。因为每个 RPC 请求都包括发送者的任期号，当 RPC 接收时，接受者会将其与自己的任期号相比较，如果不匹配，则会更新那些过期的记录。所以如果发送者的任期比接收者的要老，那么就表示发送者是过时的，这时接收者会立即拒绝 RPC 请求，并将包括了接收者任期信息的响应发送回发送者，这样当发送者接收到响应时就会意识到，它的任期号是过期的，此时它就会停下并作为跟随者继续运行，同时它还会更新自己的任期号，并与其他服务器保持一致。反之，如果接收者的任期号更老，如果这时接收者不是跟随者，那么它也会停下，并作为跟随者，而且更新它自己的任期号。略微不同的是接收者不会拒绝 RPC ，它会接收 RPC 请求。

这里比较有趣的是选举过程会导致任期号的更新，即当候选者请求投票并与大多数服务器发生通信后，它会将自己的任期号随着 RPC 请求发送出去，这样所有的接收者都会更新自己的任期号，并与候选者保持一致，所以当新领导者被选出后，集群里的多数服务器都会更新到这个任期号。这也就意味着，一旦选举完成，被罢免的领导者是无法提交新记录的，因为它需要与至少一台服务器进行通信，这样它就能发现自己的任期号更老，这时它就会停止领导者的行为并作为跟随者继续运行。

还有一些比较典型的场景，这里不作更多的讨论，但可以用任期号来处理所有类似的问题。

## 客户端协议 ##

![image][image 24]

现在让我们看看 Raft 协议的第五部分，即客户端是如何与系统进行交互的。这点并不复杂，客户端将命令发送给领导者，并获得响应，如果客户端不知道哪台服务器是领导者也没关系，它可以与集群的任意一台服务器进行通信，如果这台服务器不是领导者，那么它会告知客户端，并将客户端重定向到领导者，然后客户端会再次发送请求。只有在领导者记录下命令，并已经将其提交，然后发送给状态机执行之后，才会将结果返回给客户端。这里比较微妙的是，如果领导者发生崩溃或请求发生超时该怎么办？如果发生这种情况，客户端会随机挑选另一台服务器并再次发送请求，最终它会将请求发送到新的领导者，新的领导这会执行该命令。这个可以保证命令最终总能被执行。

但这留有一个风险，即命令有可能被执行两次。

![image][image 25]

问题在于领导者会在执行完命令后响应客户端之前发生崩溃，所以命令本身是无法知道自己是否被记录或已被执行。这时客户端就会再次发起请求，这样命令就又被执行了一遍。这是不能被接受的，因为我们要每条命令执行且仅被执行一次。Raft 解决这个问题的办法是让客户端为每条命令生成一个唯一的 ID ，并将其与命令一起发送给领导者，当领导者记录该条命令时，也会包括这个唯一 ID ，但在领导者接受命令之前，它会进行检查，看其他记录中是否已存在相同的 ID ，如果存在相同的，那么它就会知道该条命令请求是多余的，所以它会找到该条记录，并忽略这条新命令，并将老的执行结果返回给客户端。

所以只要客户端不崩溃，结果最多只会被执行一次。这也是我们希望系统应该具备的线性一致性。

接下来要介绍 Raft 协议的第六部分，也是最后一部分。

## 配置变更 ##

![image][image 26]

我们已经有了应对配置发生变更的处理机制。当我们提到配置，指的是集群服务器的信息，包括每台服务器的 ID 、网络地址等。这些信息都非常重要，因为我们需要用它们来决定多数票的具体数量，从而进行领导者选举或用来提交日志记录。我们要支持这些变更的原因在于，比如当服务器出现失败的情况，它们可以被新的机器替换，或者集权管理员希望能更改副本数量，我们希望所有的这些事情都能在安全自动的条件下完成，不要因为配置的变更导致系统出现故障或停机的情况。

![image][image 27]

必须要意识到，我们无法直接从旧配置切换到新配置。我们来看个例子。假设系统集群有三台服务器正在运行，这时我们希望再增加两台服务器，所以最终集群内会有五台服务器。如果我们只是要求每台服务器从旧配置切到新配置，问题是这个切换不能无法同时完成，时间上总会有先有后。而这可能会导致冲突的大多数。因为 S1、S2 可以在某个时候形成旧集群的大多数，并决定领导者。而与此同时，另外三台服务器 S3、S4、S5 已经切至新的配置，它们也形成了该配置状态下的大多数。所以它们也可以决定领导者，确认提交状态。这样就会与 S1、S2 发生冲突。这样，我们就需要使用两段协议（two-phase protocol），无法在一段内达到目的。

这当然也是所有分布式决策的所必须使用的方式。

## 联合共识 ##

![image][image 28]

解决方案是使用两段协议的方式来更改配置信息。

Raft 将第一阶段到中间阶段称为多边共识（joint consensus），在这个阶段中，集群包括所有的服务器上新旧两种配置，但是如选举和提交的决策，需要在新旧两个独立的配置状态下达成一致。

集群配置以 C(old) 开始，然后客户端向领导者发送请求，当接收者收到请求之后，会向日志里新增一条记录，要求记录新配置 C(old+new) ，配置与其他普通的命令记录一样，领导者会用 AppendEntries RPC 请求将其发送给集群的其他服务器，配置变更唯一的不同在于它们会立即生效，一旦服务器将新配置记录到日志中，那么它就立刻生效，并不需要等待该日志记录变为已提交状态。所以此时在领导者上已经认为 C(new) 已生效，那么如果配置C(old+new) 要生效，就要求该配置分别在新旧配置服务器下同时都成为大多数。又过了一会，当记录状态变成已提交后，也还是可能存在决策在 C(old) 与 C(old+new) 决定。例如，如果领导者在记录新配置记录后就发生崩溃，有可能某些其他旧配置的机器仍然处于工作状态，被选举成领导者管理集群。但在某个时间点，C(old+new) 会变为已提交的状态，在此种状态下，任何机器就无法只根据 C(old) 来做出决策。为了让领导者被成功选举，它必须保证所有的记录都已提交，所以一旦 C(old+new) 记录已提交，它就能保证任意选举的领导者都有该记录，也就是说领导者已使用该配置。所以在这个时候，集群是处于联合共识下运行的，一旦联合共识被提交确认，领导者就可以将配置变更 C(new) 写入日志记录，并发送给集群其他服务器。所以在这个时候，集群下服务器配置可能在 C(new) 或 C(old+new) 的状态，因为这时服务器也可能再次出现崩溃，另一服务器会替代成为领导者，并使用联合共识下的 C(old+new) 配置。但最终新配置记录 C(new) 会处于提交状态，一旦出现这种情况，集群所有未来的决策都将基于 C(new) 。所以关键在于，不存在 C(old) 或 C(new) 在不进行相互协调的前提下就能做出决策的情况。C(old) 可以独立做出决策，C(new) 也可以独立做出决策，但是两者不会发生重叠。在这两段时间之间，两个配置需要相互协调，这就能保证，集群不会两个独立的达成共识的群体存在。

在这里，两段协议是一个基础协议。任何共识性算法都需要使用两段协议来对配置进行变更，实际上任何分布式一致都需要两段协议。

![image][image 29]

这个协议还有些需要注意的地方。

在过度期间，有可能服务器来自于任何一种配置都能被选举为集群领导者，这里比较微妙的是如果当前的领导者不在新配置里，那么它最终会停下，并转换为跟随者。在 Raft 里，旧领导者在 C(new) 处于已提交状态后立即停止并转换成跟随者。这时其他的跟随者会超时，并选举新的领导者，这时被选举的领导者所使用的配置一定是 C(new) 。尽管如此，旧的领导者也还是会领导一小段时间。

![image][image 30]

## 参考 ##

参考来源:

2013 Raft lecture, Diego Ongaro

2013 Raft user study

Wiki: Byzantine fault tolerance

## 结束 ##

[image]: http://note.youdao.com/yws/api/personal/file/WEB4908c30bb3ec5b6014af9bcd2e5317e8?method=download&shareKey=6c078c6a5db8445f779a58149fc77bb7
[image 1]: http://note.youdao.com/yws/api/personal/file/WEB2048929c41af94bc88f174ce509d66e3?method=download&shareKey=da1cf0cb9ec5a7eeb0d08ef09c83ccd5
[image 2]: http://note.youdao.com/yws/api/personal/file/WEB1f1804458226047ea2147ad17e2e489c?method=download&shareKey=9a4b4102230a36fd55900cbffab3bc4f
[image 3]: http://note.youdao.com/yws/api/personal/file/WEB8430d433fe86986041b714e15c2646e5?method=download&shareKey=caac5daa3acc13727dae3d94f864d0df
[image 4]: http://note.youdao.com/yws/api/personal/file/WEB3704e43300e55ad1d7352ecb80ce2340?method=download&shareKey=86fe28504d3eefda8bc62901ea1bba1f
[image 5]: http://note.youdao.com/yws/api/personal/file/WEB5cd6c77e86d27004f9744fa0f8e971e3?method=download&shareKey=50f78f51e0537149f2d32c89b627e6da
[image 6]: http://note.youdao.com/yws/api/personal/file/WEB094f6ced9d391dcfcf071529492864e6?method=download&shareKey=60ea9d929e82b4381cef813ff4e23a25
[image 7]: http://note.youdao.com/yws/api/personal/file/WEB5a14b0c2bf57ca5ae3f462d40a170252?method=download&shareKey=9a2d0c5b5a17509e6270f7da1f461552
[image 8]: http://note.youdao.com/yws/api/personal/file/WEB4cfd4d3d8a45d6026bba659631699370?method=download&shareKey=c373400c16661ba529d580563ed51be9
[image 9]: http://note.youdao.com/yws/api/personal/file/WEB1a097a2447b370380f89d83899892ea0?method=download&shareKey=265f92862ac9e556bda12780eaf25ea7
[image 10]: http://note.youdao.com/yws/api/personal/file/WEBf449dca420c264716a8317d577ab2699?method=download&shareKey=4141747693a0b462c3be513a71cbaebb
[image 11]: http://note.youdao.com/yws/api/personal/file/WEB6e3b6d9f96425a4e397017ef9513f3ec?method=download&shareKey=ef560ffc94e658ea225e42eac85a1937
[image 12]: http://note.youdao.com/yws/api/personal/file/WEB95500626185925d2d73fc0fa4ae15fe8?method=download&shareKey=3a74dbc7707ca3ae417f360aa36c9dbf
[image 13]: http://note.youdao.com/yws/api/personal/file/WEB9e6f4a35403b40e74cef3ac4c2b1017f?method=download&shareKey=f3e07c2d55b9546d59bbafe7b0b99eda
[image 14]: http://note.youdao.com/yws/api/personal/file/WEB368bd650b3918a9f99b23619a9a15b75?method=download&shareKey=a9444e03c68a401601bf74bb5273a488
[image 15]: http://note.youdao.com/yws/api/personal/file/WEBe825dec7a5012abee68aaeb456b5ac62?method=download&shareKey=6c1e170e7059fa0ea1416ad8a6c88c2b
[image 16]: http://note.youdao.com/yws/api/personal/file/WEBf6cd846c654d4319ca731a51e907035a?method=download&shareKey=bddbae754a83e77799c089dee1e9ae8d
[image 17]: http://note.youdao.com/yws/api/personal/file/WEB738cfd038bc461dd5db136a6898f28c5?method=download&shareKey=495c865f2fc741e427ba94a013ff215d
[image 18]: http://note.youdao.com/yws/api/personal/file/WEBb1babe59e2b5043e9dde63af8f5cdae4?method=download&shareKey=f9e1f313210daed4c18c63743ef278bd
[image 19]: http://note.youdao.com/yws/api/personal/file/WEB93fb04352e77602c80da8a2c144010f3?method=download&shareKey=094192c22c6f1b75e05e6df2d7614cea
[image 20]: http://note.youdao.com/yws/api/personal/file/WEB5456f5fac7dbdd6d8684e80b19a37ecb?method=download&shareKey=e46e28b4bd2dbb6981b69016860a614d
[image 21]: http://note.youdao.com/yws/api/personal/file/WEB64b4cb331abbbeb678f63d722834b541?method=download&shareKey=48e84c9c5fc1a8845efb3f4180e7dffd
[image 22]: http://note.youdao.com/yws/api/personal/file/WEB20322c23b3eb579b0a93e7c7841c9b8c?method=download&shareKey=eaf381301d52c5a8757f43033e507230
[image 23]: http://note.youdao.com/yws/api/personal/file/WEB22cbef1db8a3f8ebfe548c67fd6c4cbc?method=download&shareKey=a323069b10ffc348d2a02ec01010e37e
[image 24]: http://note.youdao.com/yws/api/personal/file/WEBf25ec75baa03b67f3f9a4e3eb7302950?method=download&shareKey=45e886cc89fb88c4a93d07f7c9f9c4d2
[image 25]: http://note.youdao.com/yws/api/personal/file/WEB8db1935506f03a703bf7c601f631493f?method=download&shareKey=7721aab2f9730a0d50880db4f7a681dd
[image 26]: http://note.youdao.com/yws/api/personal/file/WEBe18108291415a9703ab0ce6a4ad1f411?method=download&shareKey=8076239c91e0187fd7599d7319987061
[image 27]: http://note.youdao.com/yws/api/personal/file/WEB96c19fb00603446556ec222c01233496?method=download&shareKey=5f9c35dad1f998c05987950c9bb908ca
[image 28]: http://note.youdao.com/yws/api/personal/file/WEBedfb195d553100f6bf846a2abd5e38eb?method=download&shareKey=57c25178a5aeb7c3e63dbb9e1dec65b7
[image 29]: http://note.youdao.com/yws/api/personal/file/WEBe2cf3efe794c43df086ca2776227d43c?method=download&shareKey=169664f8bdae1ebb4d141831cdf188b8
[image 30]: http://note.youdao.com/yws/api/personal/file/WEB5a7e373b8b25872667312844e854e149?method=download&shareKey=b6175b91825f4e998f5ac9ce8a4458d4