分布式一致性算法 - raft 图解_raft过程

前言

应用服务架构的发展是一个循序渐进的过程，从最开始的单机架构逐步演化到如今的基于微服务的分布式架构。与此同时，应用服务最底层的数据支撑 – 数据存储服务也逐渐由单节点单副本逐步往多节点多副本的方向演进。

多副本节点通过数据复制技术，可以实现分布式容灾，提高服务的可用性，降低单点故障带来的风险；同时多节点部署，还可以很大程度上提高整个系统的吞吐量，降低访问延迟。但是与此同时，基于 CAP 理论，多副本技术也带来了一致性的问题。

raft 算法的诞生正是为了解决在分布式场景之下的数据一致性问题。本文我们将从 raft 的诞生开始，聊一聊其作为集中式架构的领导者选举以及日志复制的具体流程。

raft 的诞生

raft 算法最早出自于 Diego Ongaro 博士的论文《In search of an Understandable Consensus Algorithm》，但是这篇论文比较短小，只是简单介绍了一下原理，对一些细节部分没有提及。更详细的论文是他的《CONSENSUS: BRIDGING THEORY AND PRACTICE》，在这篇论文里面，作者很详细的谈及了 raft 实现上的一些细节部分，这也成为了很多工程实践上的一个重要参考，比如 etcd raft 的实现就基本上与这篇论文一致。

其实早在 raft 算法之前，paxos 算法是当时业界公认的共识算法，并且也有了一些工程上面的实践（例如 Google 的分布式锁系统 Chubby）。但是由于 paxos 算法本身理论过于复杂，并且在工程实践上难度也比较高，这促使 Diego Ongaro 等人急切想要寻找一个简单易懂，并且实现上也比较简单的新算法。于是，基于 Multi-Paxos 算法的思想，raft 算法就此诞生（可以理解为 raft 算法是 paxos 的简化版）。

After struggling with Paxos ourselves, we set out to
find a new consensus algorithm that could provide a better foundation for system building and education. Our approach was unusual in that our primary goal was understandability: could we define a consensus algorithm for
practical systems and describe it in a way that is signifi-
cantly easier to learn than Paxos?

预备知识

在具体学习 raft 算法之前，我们先了解一些下文会用到的相关词汇。

成员身份

raft 算法是一个典型的集中式架构，既然是集中式架构，那么集群中肯定就会存在不同的成员身份，分别具有不同的职责。既然是中央集权，那么就需要一个集权利于一身的领导者，有了领导者，那肯定也需要有被领导者管理的平民即跟随者，同时因为领导者不可能永远不发生意外，那么相对应的，就需要有下一任领导者的候选人。这么类比下来，我们整个 raft 集群的成员身份也就确定了：

• 领导者（Leader）：集群的“最高领导人”，负责处理客户端请求、管理集群中的日志复制，并且还会定时向其他节点发起心跳请求，告诉大家“我还活着，不要发起领导者选举”。一个集群中最多只能有一个领导者。
• 候选者（Candidate）：如果等待领导者心跳超时，跟随者便可以升级为候选者，进入候选者状态之后，就开始向其他节点发起投票请求，如果在选举过程中获得了大多数选票，那么它便晋升为领导者。
• 跟随者（Follower）：正常的时候就做个普普通通的吃瓜群众，默默处理领导者发过来的日志消息，并随时随刻等待领导者心跳请求。但是一旦等待领导者心跳请求超时，就可以推荐自己当候选者。

raft 集群的每个节点在某时刻必定处于以上三种状态中的一种。三种身份的流转图大致如下：

下文的领导者选举我们会针对上述流程具体讲解。

任期

与现实中的领导人任期的概念类似，raft 算法也具有任期的概念，每次领导者选举的过程都会使任期递增。任期是选举投票以及日志复制的重要依据，充当整个集群的逻辑时钟的作用。

日志

raft 数据的载体是日志，日志是数据存储的最小单位。每条日志项除了包含用户指令之外，还包含产生日志的任期以及日志索引等信息，其中日志索引能够标识日志项所处的位置，是一个连续递增的数字。

领导者选举

接下来，我们以集群刚启动为例具体走一下一次领导者选举的流程。

我们假设集群中共有三个节点，最开始大家都处于跟随者状态：

正所谓国不可一日无君，由于集群中没有领导者，各个节点很快都会等待领导者心跳超时。如果同时有多个节点由于心跳超时而晋升为领导者，那么很可能会存在一个问题：由于选票被多个节点瓜分，每个候选者都没有获取到大多数选票而发生无效选举（道理很简单，只有一个候选者，那我的选票只能给你；如果有多个，那我就得好好斟酌一下了），然后继续重试，而进入到一个死循环。为了解决由于选票瓜分，导致无效选举概率过高的问题，raft 让每个节点都持有一个随机心跳超时时间，最先到达超时时间的节点最开始发起选举，从而大大减少选票被瓜分的可能，提高选举效率。简而言之，就是先到先得。

假设我们的跟随者A 超时时间最短，那么它会首先晋升为候选者，发起选举。此时跟随者A 会先给自己投一票，然后向其他节点发起投票请求。

其他跟随者在收到投票请求后，会根据以下规则来确定自己是否应该投出自己的选票：

• 自己的任期编号是否小于需要投票的目标任期编号，如果不小于，那么它会拒绝投票；
• 自己在目标任期编号内是否已经投过票，如果已经投过了那么它同样会拒绝投票；
• 如果对方的日志完整性低于自己的本地日志，那么拒绝投票。

当以上情况都满足的时候，它便会投出自己宝贵的一票，并增加自己的任期编号，然后拒绝此任期内的所有其他投票请求。

候选者A 在选举超时时间内获取到大多数选票之后，便可以晋升为领导者。

领导者确定后，它会周期性地向跟随者节点发出心跳请求，证明自己还活着，阻止跟随者节点重新发起选举。

通过以上的选举流程，我们大概可以总结出以下几条选举规则：

1. 自荐：每个节点都有权利推选自己为领导者候选人。
2. 少数服从多数：一次选举中赢得大多数选票的那个节点会成为领导者。
3. 强者优先（领导者日志完整）：日志完整性高的节点不会投票给日志完整性低的节点，这是通过比较节点（已复制）的最新的日志项的索引值来确定的，索引值越大，代表日志完整性越高。同时基于本规则，能够确保领导者的日志完整性（除非领导者和具有最新日志的所有跟随者全部同时宕机，在这种情况下，实际上整个集群已经处于不可用的状态，因为选举过程已经没有办法获取到大多数选票了）。
4. 每人一票，先到先得：一次选举中，一个节点最多只会给一个候选人投票，并且先到先得，当节点收到候选人的投票请求时，它会根据强者优先原则，一旦发现当前候选人满足要求，那么会立即投票给它，并且拒绝投票给后续的所有候选人。
5. 禁止造反：领导者确定之后，它便会周期性的向其他节点发起心跳请求，告诉大家我还活着，不许发起领导者选举。
6. 终身责任制：一个领导者在一个任期内是永远有效的，除非它自身出现问题（比如宕机死掉了，比如产生网络延迟/隔离等），这个时候其它节点便会发起下一轮的领导者选举，产生下一个任期的领导者，周而复始。

日志复制

领导者选举成功之后，整个集群便可以开始接收用户请求。需要明确的是，只有领导者才可以接收用户请求，这里的请求既包括写请求，也包括读请求。当然在一些 raft 的典型实现中，跟随者节点也是可以处理读请求的，比如 etcd raft 实现的 Linearizable Read 机制等。

之所以包括所有读请求，是因为 raft 保证的是强一致性，即用户指令被应用之后，之后的所有请求都应该能读到最新的值，如果读请求读的是跟随者节点，此时跟随者节点数据的准确性的没办法保证的。这与 raft 的日志复制流程息息相关。

上述我们提到，raft 各节点数据副本是以日志的形式存在的，每条日志主要包含以下内容：

• 用户指令：即用户实际要执行的操作
• 任期：创建本条日志时，领导者所处任期
• 索引：本条日志的索引值，用来标识日志项的位置，是一个连续递增的数字

raft 领导者接收到请求之后，会产生一条新的日志项，然后它需要把新的日志项同步到其他节点。接下来，就让我们来具体看一下一次用户请求被复制到整个集群的流程。

日志复制流程

raft 的日志复制过程（共识算法）是基于复制状态机来实现。复制状态机几乎适用于所有的分布式存储架构，例如 mysql 的 HA 架构、redis 的集群架构等等。raft 复制状态机包括三个模块，分别是共识模块、日志模块以及状态机。

抽象出来的日志复制过程大致如下图所示：

1. 接收到客户端请求之后，领导者会根据用户指令和自身任期以及日志索引等信息生成一条新的日志项，并附加到本地日志中。
2. 领导者通过日志复制 RPC，将日志复制到其他跟随者节点。
3. 跟随者将日志附加到本地日志成功之后，便返回 success，此时新的日志项还没有被跟随者 apply。
4. 当领导者接收到大多数（超过集群数量的一半）跟随者节点的 success 响应之后，便将此日志应用到它的状态机中。
5. 领导者将执行的结果返回给客户端。
6. 当跟随者收到下一次领导者的心跳请求或者新的日志复制请求之后，如果发现领导者已经应用了之前的日志，但是它自己还没有之后，那么它便会把这条日志项应用到本地状态机中。

由此可以发现，raft 算法采用了一种类似于二阶段提交的方式来实现节点间的日志同步，只是它把提交阶段给推迟到了下一次请求，这样的设计，大大减少了节点之间的网络请求次数。

日志一致性保证

以上是比较理想的日志复制流程，如果整个集群能一直这么走下去，那么便相安无事。但是实际的生产环境中充满了各种不确定性，例如进程崩溃、服务器宕机等情况都有可能发生，这些问题都有可能导致领导者节点和跟随者节点日志不一致。那么 raft 是如何解决日志一致性问题的呢？

例如，下图所示的领导者和跟随者的日志情况，不妨我们先来考虑一下在什么情况下会发生 index = 5 的日志不一致问题。

需要我们明确的是，raft 算法日志项的比较用的都是已经复制的日志项，而不是本地已经提交的。因此最简单的原因就是集群中的领导者本来是 C，接收到 y <- 5 的指令，复制到 B 之后，领导者 C 还没来的及将日志复制到大多数节点就宕机了，然后集群重新选择出了领导者 A。此时领导者 A 收到了用户指令 x <- 5，由于种种原因没能及时复制给跟随者 B，但是却成功复制给了其他大多数节点，领导者 A 成功应用了 index = 5 的日志项，于是在 这个位置便产生了 和跟随者 B 不一致的日志。

那么领导者节点是如何更新跟随者节点不一致的日志项呢？

其实在日志复制 RPC 的消息体中，除了会携带当前日志项的信息，还会额外带上当前日志项的前一条日志项的任期编号（PrevLogTerm）和索引值（PrevLogIndex），它们是跟随者确定要不要复制当前日志项的重要信息。我们以 index = 6 的日志项为例，来具体走一下日志复制流程：

领导者发起日志复制请求，携带当前日志信息以及 PrevLogTerm 和 PrevLogIndex，跟随者接收到日志复制请求之后，会根据 PrevLogTerm 和 PrevLogIndex 去本地日志查找数据是否存在，如果不存在，返回 fail response：

领导者接收到失败返回值之后，会递减要复制的日志索引，此时 index = 5，跟随者发现找到了 PrevLogTerm 和 PrevLogIndex 对应的日志项，那么会将新的日志项追加到本地，返回 success：

领导者接收到成功返回值之后，继续复制下一条日志（index = 6），直到本地没有更多需要复制的日志项：

基于上述的日志匹配过程，整个集群可以做到一次日志复制过程结束之后，跟随者节点如果能够成功应用当前日志项，那么它之前的所有日志项也都是完全和领导者保持一致的。这是整个集群一致性的重要保证，也是每次重新选举能够实现新的领导者的日志完整性的重要保证。

结语

这篇文章到这里就结束了，讲了很多但是其实也没有多少，只涉及到 raft 领导者选举和日志复制的大致流程等基础知识。其实 raft 算法本身包含的知识远不止这么多，例如集群节点变更，例如读优化等等，这些都可以单独拿出来作为一个章节来讲。但是本文的目的只是为了让大家对 raft 有一个具象的了解，理解它是如何实现强一致性以及高可靠性等能力。想要具体走进 raft 算法的执行流程，建议大家去看一看 etcd 的 raft 模块。

简单总结一下 raft 算法的特点（优点）：

• 强一致性：这是 raft 最本质的东西，虽然在同一时刻 raft 的每个节点的数据并不是完全一样的，但是由于其一切以领导者为准的特性，客户端的所有请求都由领导者完成，因此给客户端的感觉就是强一致性。同时基于领导者日志完整性原则，用户的更新即使在领导者重新选举之后依然能够保存，因此用户的更新操作是持久化的。
• 高可用性：从 raft 的领导者选举和日志复制流程我们可以看出，只要集群中超过一半的节点正常工作即可，可以容忍一小部分的节点故障或者网络不通。
• 高可靠性：raft 算法一切以领导者为准，当用户指令被领导者应用到本地状态机之后，后续的所有操作都可以取到最新的数据。

参考

• 《In search of an Understandable Consensus Algorithm》
• 《CONSENSUS: BRIDGING THEORY AND PRACTICE》
• 分布式协议与算法实战
• raft 动画演示