分布式共识算法——raft

发表于 | 分类于

一、前言

提到分布式一致性的算法，我们会想到paxos和raft。paxos可以认为是分布式一致性解决措施的一个乌托邦，是一个实验产物，基于强大的理论基础。它理解难度高，实现起来困难且不好解耦，但是它解决了分布式架构下的一致性问题，为后续各类一致性算法提供了理论基础。本文我们主要探讨raft——一个易于理解的分布式共识算法。相比较于paxos而言，除了易于理解，它实现起来更加简单。

二、解决问题

先讲为什么需要分布式系统。在现在复杂的软件架构时代，实现整体系统的稳定性和高可用性一个关键且有效的措施就是冗余存储，也就是单节点存储变为多节点且异地。每个节点拥有整个节点能力，且整个节点网络在其中某个节点宕机或者网络错误等一些错误出现时，能够正确保证输入输出，对整体的系统能力没有损耗。

但是这样也引发了其他问题那就是冗余存储的情况下，如何保证节点间数据的一致性。数据多份存储，在不采取任何一致性的措施下，势必会造成节点间数据冲突、丢失的问题。再讲明确一点就是，如何让多节点针对同一份数据达成共识，都是认可这份数据；也就是本节点存储的数据即为全部数据，和其他节点一样。除了上文提到了晦涩难懂的paxos，raft就是解决这类问题的一致性算法。

本文将通过原则、推论和示例等几个方面，一起探讨raft的一致性原理。

三、raft设计

在一个分布式系统中，假设一个系统模块由五个节点组成,在对外提供服务的时候，假设五个节点同时提供服务,每个节点都对外提供服务，负责响应客户端的读写。这是一个比较初级的分布式系统，即使其中的某几个节点挂了，另外几个几个节点能够正常提供服务。但是存在一个明显的问题，就是数据一致性的问题。每个节点都各自对外提供服务，那么相互之间的数据肯定不一致。有的同学可能会讲，可以使用共享存储。对的，只要使用同一份存储，各个节点之间读取同一份存储，那么问题就解决了。但是这就引发了另外一个问题，你的存储是不是单点？如果你的存储是单点,那么分布式一致性没法讨论；如果存储不是单点,那么就又回到最初的问题，多节点的存储怎么保证一致性？也就是我们本文要论证的分布式共识算法解决方案。

如何保证多节点同时运行且多节点对同一份数据保持一致？raft提供了一个简单地解决方案，那就是只有一个节点真正对外提供服务，其余节点作为backup。当这个提供服务的节点挂了，那就由集群中其他节点接任继续提供服务。raft称这个提供服务的节点为leader，其他节点为follower。leader负责接收客户端的读写请求并将数据同步到follower节点，这样解决了数据一致性问题。因为leader分发数据，follower被动接收数据，如何保证leader和follower的数据一致这就是强leader属性带来的第一个问题。

有了leader节点，我们解决了一致性问题，所有的请求都由leader节点操作并同步，强leader属性保证了数据一致性，但是引发了另外一个问题就是，如果这个leader挂了，是不是整个集群不可用了？follower节点接替leader节点提供服务。那么怎么选举leader？包括集群启动时候的选举，也包括集群leader挂了的时候怎么选举。这就是raft要解决的第二个问题，leader选举机制。

除了上述两个关键点，raft需要保证的另一个属性就是安全性。由于是集群部署，也就是有多个节点，多节点的数据，在某一个数据节点之前肯定要保证一致；同时某个数据节点的数据不能有多个。这就是安全性的保证。这里解释安全性有点模糊，下文提到状态机以及数据一致性时，详细解释安全性概念以及raft通过哪些措施来保证集群的安全性。

来到这里，我们就可以发现，raft将分布式系统中共识拆解成了三个相对独立的子问题：

  1. leader选举
  2. 日志复制
  3. 安全性保证

通过解决这三个子问题来完成整个集群的一致性保证。下面我们就分三个章节来分别讨论每个子问题是如何被解决的。

四、raft名词概念

在讲解raft为解决三个子问题之前，我们先将其中涉及到的名词整理解释一下，方便后续理解。

4.1，角色概念

  • leader：集群中的领导者。负责响应客户端的请求、集群中其他节点的日志同步以及节点心跳检测等。
  • follower：集群中的跟随者。负责接收leader的日志请求、心跳检测以及leader选举投票等。
  • candidate：集群中的候选者。候选者是跟随者在集群中没有leader或者接受不到leader的心跳之后转化成候选者，参与leader的选举。只有candidate才能参与选举，follower负责投票。

整个集群有三种角色，也就是我们提到的leader、follower、candidate。集群刚启动或者leader挂了的时候，follower会转变成candidate，然后获取大多数投票权成为leader。三种角色的转化关系如下：

4.2，日志和状态机

我们把客户端的请求以及集群处理的数据统一称之为日志。客户端请求设置x=3，集群leader接收到本次请求，将本次请求保存到本地，并复制给集群中的大多数。我们将这种请求以及处理称之为日志和应用状态机。这么讲还是比较模糊，其实本质可以这么简单理解：客户端将集群认为是一个可靠存储，需要集群保存一个数据或者某个状态；集群简单认为不管让它存储什么都是一个日志；然后每次日志的存储，都是集群中leader和大多数都保存到自身存储里面，而这个自身存储我们叫他状态机。按序请求并且持续存储，也就是应用状态机迁移。

这里可以发现，状态机是基于日志的，而集群中日志是由leader复制到大多数机器节点的，所以日志复制和状态机应用是比较关键的两个步骤，我们后续会分阶段解释两个步骤是怎么处理的。

4.3，数据术语

除了上述我们提到的角色、日志和状态机，在集群中通信以及数据存储的一些数据术语，我们也简单介绍一下。

  • term：任期。集群将整个生命划分为一个一个的时间片段，一个时间片段称之为一个任期。每个任期有唯一一个集群leader（或者没有选举出leader）来负责整个任期中响应客户端请求、日志复制以及心跳检测的工作。
  • RPC：通信方式。这个指的是集群之间节点（leader和follower以及candidate和follower）通信方式是通过RPC交互。包括领导人选举、日志复制和心跳检测等等。

4.3.1，在集群机器中永久存在的

术语 释义
currentTerm 服务器最后一次知道的任期号
votedFor 当前获得选票的候选人ID
log[] 服务器日志条目集合；每个日志条目包含了用户执行的状态机指令和当时的任期号

4.3.2，服务器上经常变更的

术语 释义
commitIndex 已知的最大的已经被提交的日志条目的索引值
lastApplied 最后被应用到状态机的日志条目索引值（初始化为 0，持续递增）

4.3.3，领导人经常变更的

术语 释义
nextIndex[] 对于每一个服务器，需要发送给他的下一个日志条目的索引值（初始化为领导人最后索引值加一）
matchIndex[] 对于每一个服务器，已经复制给他的日志的最高索引值

4.3.4，附加日志RPC（心跳检测）

术语 释义
term 领导人的任期号
leaderId 领导人的 Id，以便于跟随者重定向请求
prevLogIndex 新的日志条目紧随之前的索引值
prevLogTerm prevLogIndex 条目的任期号
entries[] 准备存储的日志条目（表示心跳时为空；一次性发送多个是为了提高效率）
leaderCommit 领导人已经提交的日志的索引值
返回值 释义
term 当前的任期号，用于领导人去更新自己
success 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

follower需要做的是

  1. 如果 term < currentTerm 就返回 false
  2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false （5.3 节）
  3. 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的
  4. 附加日志中尚未存在的任何新条目
  5. 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个

4.3.5，请求投票 RPC

请求参数 释义
term 候选人的任期号
candidateId 请求选票的候选人的 Id
lastLogIndex 候选人的最后日志条目的索引值
lastLogTerm 候选人最后日志条目的任期号
返回值 释义
term 当前任期号，以便于候选人去更新自己的任期号
voteGranted 候选人赢得了此张选票时为真

接收者实现：

  1. 如果term < currentTerm返回 false
  2. 如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他

五、raft约束和特性

5.1，所有服务器

  • 如果commitIndex > lastApplied，那么就 lastApplied 加一，并把log[lastApplied]应用到状态机中
  • 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者

5.2，follower

  • 响应来自候选人和领导者的请求
  • 如果在超过选举超时时间的情况之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，或者是给某个候选人投了票，就自己变成候选人

5.3，candidate

  • 在转变成候选人后就立即开始选举过程
    • 自增当前的任期号（currentTerm）
    • 给自己投票
    • 重置选举超时计时器
    • 发送请求投票的 RPC 给其他所有服务器
  • 如果接收到大多数服务器的选票，那么就变成领导人
  • 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
  • 如果选举过程超时，再次发起一轮选举

5.4，leader

  • 一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时
  • 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端
  • 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：
    • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
    • 如果因为日志不一致而失败，减少 nextIndex 重试
  • 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex 等于这个 N

5.5，特性

  1. 选举安全特性：对于一个给定的任期号，最多只会有一个领导人被选举出来
  2. 领导人只附加原则：领导人绝对不会删除或者覆盖自己的日志，只会增加
  3. 日志匹配原则：如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同
  4. 领导人完全特性：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
  5. 状态机安全特性：如果一个领导人已经将给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会应用一个不同的日志

六、raft推导

6.1，raft基础

上文我们阐述了raft协议的一些名词概念、约束限制以及特性，下面我们按照流程，逐渐梳理raft是如何在集群多节点、网络分区等情况下保证一致性的。

我们一般推荐集群由五个节点（奇数个节点）组成，这样即使挂掉两个节点，集群还是可以正常提供服务。任何一个时刻，集群中的节点都是处于三种角色中的一个：leader、follower、candidate。leader负责接收客户端的指令，follower被动接受leader的同步指令（客户端的请求，follower会重定向给leader），同时在leader挂掉之后成为candidate选举自己成为leader。

raft把时间划分成为任意长度的任期，用连续的整数表示，在raft中作为逻辑时钟。每个任期至多有一个leader，也就是说某个任期内可能不存在leader。比如一个任期内有两个candidate获得了相同的票数，都不满足大多数投票，那么就会再次发起一轮leader选举。有了任期这个逻辑时钟的存在，每个节点可以和全局时钟做一个校验。也就是每个节点本地都会存储一个任期号——term，这个任期号是单调递增的。节点之间的通信会交换任期号，如果消息中的任期号小于自己的任期号，则会拒绝消息：比如消息是投票则会拒绝；如果任期号大于自己，则会更新自己的任期号为最新。如果candidate或者leader发现自己的任期号过期了，那么就会切换自己的角色为follower。

服务器节点之间通过rpc通信。整个过程其实只需要两种类型的rpc：一种是选举期间由candidate发起的请求投票rpc；一种是服务运行期间由leader发起的日志复制的rpc，这种除了用来附加日志，也用来进行心跳检测。节点之间还通过并行rpc来提供通信效率。

6.2，领导人选举

raft使用心跳检测来触发leader选举。当服务器启动时，他们都是follower状态。由于一定时间内没有收到leader的心跳检测，会有节点转化为candidate发起leader选举。follower如果收到leader选举请求或者leader的心跳检测、日志附加请求，都会保持自己的follower角色。当有一个服务节点被集群中大多数节点投票承认为leader时，它会定时的发送心跳检测来维持自己的权威性。

首先只有candidate才能发起选举。也就是如果follower想要发起选举，必须转变角色为candidate。要做这个转变就是一定时间内没有接收到任何信息，可能是集群初始化，可能是leader节点挂掉，也可能是发生网络分区、网络超时等问题。candidate发起投票的时候，会把自己的任期term加1，表明逻辑时钟到了下一个任期，然后发起rpcs请求其他节点为自己投票。它会一致保持candidate的状态直到几个情况发生：1，自己成为leader；2，其他服务器成为leader；3，没有节点成为leader。

情况1比较简单纯粹，也就是集群中的大多数节点都承认它的leader属性，也就是大多数节点的任期小于等于本次请求投票的任期号且日志有效。leader选举过程中，follower只能进行一次投票且按照先到先得的顺序。一旦candidate获得选举，它就从candidate角色转变成leader，并且向集群中的所有节点发送心跳来证明自己的权威性。

情况2可以理解为，candidate发起投票期间，收到了leader的附加日志的心跳rpc，而且任期号不小于自己的任期号。那么此时candidate会转变成为follower，承认leader的权威并且接收附加日志请求。如果任期号比自己的小那么将会拒绝此次rpc请求，继续保持candidate状态。

情况3可能的结果是候选人既没有赢得选举也没有输：如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。当这种情况发生的时候，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举。然而，没有其他机制的话，选票可能会被无限的重复瓜分。

raft采用随机选举超时时间来避免选票被无限瓜分的情况，选举超时时间从一个区间（150ms-300ms）之间进行随机选择，那么多个candidate会被分散到不同的时间节点，总有一个超时时间比较短比较快的发起重试。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。

6.3，日志复制

一旦一个leader被选举出来，它就负责提供服务接收客户端的请求。客户端的请求一般是一个状态机指令，leader将这条指令作为日志附加到日志条目中，并通过附加日志rpc发送给集群中的所有机器节点；各个follower机器节点收到附加日志rpc后，做完响应的check然后记录到自己的日志记录中并返回成功；在集群中大多数的节点响应成功后，leader会将本次状态机指令附加到状态机中（可以理解为commit）并响应客户端成功。在后续的心跳请求中，leader会将应用到状态机的日志索引告诉follower节点，follower应用自己的状态机。

通过上述的简单描述，我们可以大致将日志复制分为两个阶段，也就是常常听到的两阶段提交。第一阶段是集群中的大多数节点承认请求有效，第二阶段是针对这个请求的提交。但是和两阶段提交不同的是，不需要所有节点应用状态机，leader在收到集群中大多数节点第一阶段响应成功后就可以自身提交然后响应成功。

再详细介绍下日志复制的整个过程（正常流程）：

1，leader接收到客户端的状态机指令，假设指令为设置x的值为2，即：x=2

2，leader记录自己的日志为log[index++] = “x=2”

3，并行地向集群中的其他节点发送附加日志”x=2”的请求，同时为了保证数据的完整性和安全性，会携带当前的任期号term、上一个日志的索引和其对应的任期号

4，follower收到leader发来的附加日志的rpc，首先会校验当前日志条目中上一个日志的索引和任期号，如果匹配则将本次请求的日志条目附加，并返回成功；否则则返回失败

5，leader收到大多数节点成功附加的响应后，会将”x=2”附加到自己的状态机中，并响应客户端为成功

正常流程比较简单，在异常流程中，也就是可能会出现case比如某些follower日志记录和leader不匹配，那么处理方式就是leader强制follower复制自己的日志来解决；也有可能是某些follower只有前几条日志记录匹配，后面有缺失，那么leader就会不断缩小对应follower节点的index去匹配直到匹配成功并将后续所有的日志批量发送。

坚持原创分享