分布式共识算法之Raft
前言
之前我们的文章讲过了分布式共识算法(Distributed Consensus Algorithm)Paxos。在Paxos算法里,把每一个要写入的操作,称为提案(Proposal)。接受外部请求,尝试写入数据的服务器节点,称为提案者(Proposer)。比如说,一个集群中有5个节点,我们可以让这些节点作为5个提案者,接受外部客户端请求。
前面说到,每个节点都可以作为提案者进行提案。从文字描述看,好像也没什么复杂度。但是,一个好的分布式系统一定需要满足可靠性、可维护性的。比如,集群中某个节点出现网络分区故障、当有客户端请求时需要满足数据能正常写入,当故障恢复后必须保障集群中个节点数据一致。在这种情况下,Paxos每个节点都能处理提案,无疑增加了技术实现复杂度。
为什么需要Raft
维基百科上是这么解释raft算法:Raft是一种用于替代Paxos的共识算法。相比于Paxos,Raft的目标是提供更清晰的逻辑分工使得算法本身能被更好地理解,同时它安全性更高,并能提供一些额外的特性。[1][2]:1Raft能为在计算机集群之间部署有限状态机提供一种通用方法,并确保集群内的任意节点在某种状态转换上保持一致。Raft算法的开源实现众多,在Go、C++、Java以及 Scala中都有完整的代码实现。Raft这一名字来源于"Reliable, Replicated, Redundant, And Fault-Tolerant"(“可靠、可复制、可冗余、可容错”)的首字母缩写。
那么Raft相比Paxos是如何做到更清晰逻辑分工的呢?
-
首先,Paxos算法提出时,它的出发点注意是为了达成分布式共识。而Raft算法,则直接从具体如何达成分布式共识这个问题出发。它更关注具体实现
-
其次,Paxos算法可以通过任意一个节点发起数据写入,我们需要考虑各种数据写入情况下的时序情况下的共识问题。而Raft算法则把问题拆解成一个独立的子问题,比如Leader选举、日志复制、安全及成员变化等问题。
-
最后,Raft定义了一个领导者,从本质上说,Raft算法所有写入都以领导者为准,进而实现一系列的共识和各节点数据的一致性。
Raft基本概念
这里,我们先了解Raft基本概念。首先,Raft系统有多台服务器。这些服务器,会分成三个角色:
- **跟随者(Follower):**接受和处理来着领导者消息,当领导者心跳超时时,会主动发起投票请求推荐自己当候选人
- **候选人(Condidate):**候选人向其他节点发送请求投票(RequestVote)消息。各个节点接受到请求投票消息后,进行投票,如果赢得大多数选票,就修改自己状态为领导者
- **领导者(Leader):**接受外部客户端数据写入,并向
Follower
同步客户端写入的数据。同一时间,整个Raft集群,只会存在一个Leader
在深入了解Raft之前,让我们看看Raft算法具体是怎样实现的:
- 首先Raft集群始终存在一个
Leader
,来自客户端所有写入数据都是发送给Leader
。leader
接受到客户端写入后,会在本地存储数据。同时,Leader
会把写入数据复制到其他Follower
节点上。 - 因为
Leader
所在节点可能会出现异常。那么就需要Raft集群尽快选举一个新的Leader
。所以我们需要解决一个子问题,也就是Leader选举问题 Leader
在复制数据到其他节点时,需要确保所有Follower
节点数据一致性。这里就涉及到分布式共识问题,也就是数据复制问题- 在Leader节点出现故障,切换新Leader过程中。存在一个挑战,新Leader可能没有同步到最新写入的数据。这就涉及到**“安全性”问题**
接下来,让我们深入Raft算法实现具体问题
Leader选举
选举过程
在初始状态下,集群所有节点都是
Follower
,任期编号都为0
。每个节点会随机初始一个超时时间(和领导者进行心跳检测时间)
-
节点A在指定超时时间内,没有接受到来自
Leader
心跳消息。节点A会认为当前没有领导者。那么节点A会发起选举,会做两个动作。第一个,是先给自己投一票;第二个,是向所有其他的Follower
发起一个RequestVote
请求,也就是要求那些Follower
为自己投票。这个时候,Follower
的角色,就转变成了Candidate
。- 在每一个 RequestVote 的请求里,除了有发起投票的服务器信息之外,还有一个任期(Term)字段。
- 每个 Follower,在本地都会保留当前 Leader 是哪一个任期的。当它要发起投票的时候,会把任期自增 1,和请求一起发出去。
-
其他
Follower
节点B、C在接收到RequestVote
请求的时候,会去对比请求里的任期和本地的任期。如果请求的任期更大,那么它会投票给这个Candidate
。不然,这个请求会被拒绝掉 -
通过
Quorum
机制,选举节点A成为新的Leader
-
节点 A 当选领导者后,他将周期性地发送心跳消息,通知其他服务器我是领导者,阻止跟随者发起新的选举
在一个任期里,一台服务器最多给一个
Candidate
投票,所以投票过程是先到先得,两个服务器都发起了 RequestVote,我们的Follower
也只能投给一台
讲到这,大家对Leader选举有了大致了解,整个选举过程遵循多数人原则。当然,里面还存在一些细节需要大家注意:
-
节点间如何通讯?
-
什么是任期
-
选择有哪些规则
-
为什么要有随机超时
节点间如何通讯?
服务器节点间通讯采用远程过程调用(RPC),在领导者选举过程会存在2类RPC
-
请求投票(RequestVote)RPC,由候选人在选举期间发起,通知各节点投票
-
日志复制(AppendEntries)RPC,由领导者发起,用来复制客户端写入数据
-
心跳检测(SendHeartbeats)RPC,通知其他服务器我是领导者,阻止其他节点发起投票
什么是任期?
Raft算法中,每个Leader
都是有任期的,每个任期由单调递增标识,也就是任期编号。比如:
- 跟随者在等待领导者心跳信息超时后,推举自己为候选人时,会增加自己的任期号,比如节点 A 的当前任期编号为 0,那么在推举自己为候选人时,会将自己的任期编号增加为 1
- 如果一个服务器及节点,发现自己任期编号小于其他节点,那么它会更新自己的编号到较大编号。比如节点 B 的任期编号是 0,当收到来自节点 A 的请求投票 RPC 消息时,因为消息中包含了节点 A 的任期编号,且编号为 1,那么节点 B 将把自己的任期编号更新为 1。
选举有哪么规则?
多数人投票(Quorum)规则:
-
获取超过半数服务器投票(公式:
n / 2 - 1
),候选人会赢得选举变成Leader,同时开启一个新的任期。比如:集群包含3个节点,必须获得2个节点投票通过才能成功选择为Leader
基于任期编号规则:
-
如果一个候选人或者领导者,发现自己的任期编号比其他节点小,那么它会立即恢复成跟随者状态。比如出现网络分区错误恢复后,任期编号为 3 的领导者节点 B,收到来自新领导者的,包含任期编号为 4 的心跳消息,那么节点 B 将立即恢复成跟随者状态。
-
如果一个节点接受到比自己记录任期编号值小的请求,那么它会直接拒绝。比如节点 C 的任期编号为 4,收到包含任期编号为 3 的请求投票 RPC 消息,那么它将拒绝这个消息。
-
在一次选举中,每一个服务器节点最多会对一个任期编号投出一张选票,并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3,先收到了 1 个包含任期编号为 4 的投票请求(来自节点 A),然后又收到了 1 个包含任期编号为 4 的投票请求(来自节点 B)。那么节点 C 将会把唯一一张选票投给节点 A,当再收到节点 B 的投票请求 RPC 消息时,对于编号为 4 的任期,已没有选票可投了。
-
经过一轮投票,无人获胜。那么Raft算法会对任期自增+1,再发起新一轮投票
日志完整性规则:
-
日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。比如节点 B 的任期编号为 3,节点 C 的任期编号是 4,节点 B 的最后一条日志项对应的任期编号为 3,而节点 C 为 2,那么当节点 C 请求节点 B 投票给自己时,节点 B 将拒绝投票。
-
已经有一个Condidate赢得了选举,这时其他候选人还不知道自己输了。过了一会,新的Leader发起心跳请求,里面包含任期编号、索引值等信息。这时候,其他候选人发现Leader日子完整性更高,那么他们就知道自己已经在投票中输了,然后变更自己状态为跟随者(
Follower
)
日志复制
Leader
选出来后,客户端就可以向Leader
发送写入数据请求了,写入数据请求其实就是一条操作日志追加写。在Raft中,主要通过**AppendEntries
的RPC**调用实现。
整个数据写入,其实是一个两阶段提交过程,和Paxos
的提案分准备阶段和提交阶段类似,准备阶段提交只需要“半数”通过,如果中途出现部分阶段故障,需要无限重试。
日志格式
接下来我们看看追加日志操作。首先,我们要了解日志的形式。日志是一种数据格式,它主要包括:
- 索引值(Log index): 随着数据写入不断自增的值
- 任期编号(Term): 每次日志写入来自Leader哪个任期,每次选举都产生一个新的任期编号
- 指令(Command): 客户端指定需要写入的数据
从图中可以看到,一个领导者任期,往往可以写入多条日志。而每个日志写入,索引值是一个单调递增+1的值。
日志复制
我们在追加写入日志的时候,不只是单单追加最新的一条日志,还需要做一个校验,确保对应的 Follower
的数据和 Leader
是一致的:
- 首先,在发起追加写入日志请求时,
Leader
的AppendEntries
的RPC里,不仅会有最新的一条日志,还会有上一条日志数据对象中日志索引和任期编号数据 Follower
会拿Leader
发过来的上一条日志索引和任期编号,和自己的日志进行对比- 如果没找到,说明它的日志和领导者日志不一致。那么,
Follower
会拒绝追加新日志,并返回消息给Leader
。Leader
会向前递减要复制的日志索引,发送新的日志索引和任期编号 - 如果找到了,
Leader
会知道Follower
和自己位置相同的索引值。Leader
会通知Follower
复制或者覆盖该索引之后的日志,也就是Follower
会把这个位置之后的日志删除,然后追加新日志
- 如果没找到,说明它的日志和领导者日志不一致。那么,
- Leader会不断重复这个过程,最终实现集群各节点日志的一致性
本质上,Raft 的复制操作,是让 Leader
为每一个 Follower
都从 Leader
的尾部往头部循环,找到 Follower
最新同步到哪里的日志。然后不断重复把日志复制到Follower
。
下面通过一个例子来解释这个复制过程。
从图中你可以看到:
- 我们的 Leader,此时此刻已经到了第 10 条日志;
- 服务器 a 和 b 里,日志还没有及时复制到最新的日志;
- 服务器 c 和 d 里,包含了没有提交的“脏日志”;
- 服务器e和 f里,不仅没有复制到最新的日志,也包含很多旧的脏日志。
Tip: 这里的脏日志,指服务器在担任 Leader 的时候,可能已经在本地写入了日志,然后挂掉了,所以日志没有能够完成提交。
我们拿服务器f为例,任期编号Term、索引为LogIndex
-
Leader通过RPC消息发送心跳消息,发送上一条日志数据
Object(term=6,LogIndex=10)
-
服务器f查看日志找不到
Object(term=6,LogIndex=10)
,服务器d拒绝更新,并返回失败信息给领导者 -
Leader再向前找一条日志数据
Object(term=6,LogIndex=9)
,服务器d检查日志不存在,Leader继续向前查找直到找到日志数据Object(term=1,LogIndex=3)
-
Leader知道服务器f在
Object(term=1,LogIndex=3)
位置,数据和自己保存一致 -
Leader通过日志复制PRC,依次覆盖
Object(term=2,LogIndex=4)
为Object(term=4,LogIndex=4)
、Object(term=2,LogIndex=5)
为Object(term=4,LogIndex=5)
…
安全性
前面日志复制例子中,由很多没有提交的“脏数据”,为什么会出现“脏数据”?这要我们具体来分析Raft机制。
在Raft里,每一个服务器写入日志,分为两种状态:
- 未提交
- 已提交
如果我们要确保Leader日志是最新的(只包含已提交日志),只需要在选举时,让拥有最新日志的Leader被选中。那么Raft又是如何实现?
- 在
RequestVote
请求里,除里预期下一个任期外,还要带上Condidate已提交日志的最新索引和任期编号 - 每一个Follower,会拿Condidate请求数据和本地已提交日志的最新索引和任期编号进行比较
- 如果Follower本地数据更新,那么它会拒绝投票
- 如果Condidate数据更新,Follower会按照规则进行投票。一旦投票通过,意味Candidate 的已提交的日志,至少和一半的 Follower 一样新或者更新。而 Raft 本身写入数据,就需要至少一半成功,才会提交成功。
通过上面日志更新机制,我们按照大多数原则的共识,让最新数据的服务器有机会选上Leader。
内容小结
到了这里,关于Raft算法原理,我们已经讲完了算法主干。总体来说,Raft算法实际是一个分布式共识算法。为了达成共识,算法通过领导者选举、日志复制、节点变更、安全性保障等一系列子问题,来使得算法更易于理解。
在 Leader 选举上,Raft 采用的是典型的心跳检测 Leader 存活,以及随机超时时间投票,确保不会死循环,来确保我们可以快速选出 Leader。
在日志复制层面,Raft 采用的是一个典型的两阶段提交。在日志复制过程中,强制 Follower 和 Leader 同步,来解决删除未提交的脏日志的办法。
在安全性上,Raft 在 Leader 选举的时候,带上了日志索引和任期编号。来解决,无论 Leader 如何通过选举切换,都需要包含最新已提交的日志。