分布式架构学习(五)-一致性算法Raft

Scroll Down

分布式架构学习(五)-一致性算法Raft

Raft算法

Raft 是一种为了管理复制日志的一致性算法。

Raft实现了和Paxos相同的功能,它将一致性分解为多个子问题:Leader选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等。同时,Raft算法使用了更强的假设来减少了需要考虑的状态,使之变的易于理解和实现。

Raft中的角色

Raft将系统中的角色分为领导者(Leader)、跟从者(Follower)和候选人(Candidate):

  • Leader:接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。
  • Follower:接受并持久化Leader同步的日志,在Leader告之日志可以提交之后,提交日志。
  • Candidate:Leader选举过程中的临时角色。

影响Raft中的角色变化的动作是选举

image-20200701163814680

Raft使用心跳机制来触发选举。当server启动时,初始状态都是follower。每一个server都有一个定时器,超时时
间为election timeout(一般为150-300ms),如果某server没有超时的情况下收到来自领导者或者候选者的任何
消息,定时器重启,如果超时,它就开始一次选举,每次触发选举之后,对应的任期相应+1

动画演示Raft算法全过程:http://thesecretlivesofdata.com/raft/

Raft算法过程

  • 初始状态,各个任期都为1

    image-20200701164021522

  • 某一时刻,其中的一个 follower 由于没有收到 leader 的 heartbeat 率先发生 election timeout 进而发起选举,此时将对应节点任期改为2

    image-20200701164040309

  • 只要集群中超过半数的节点接受投票,candidate 节点将成为即切换 leader 状态,并将其他Follower节点任期改为2。

    image-20200701164230691

  • 成为 leader 节点之后,leader 将定时向 follower 节点同步日志并发送 heartbeat。

    image-20200701164244637

Raft运行过程中出现异常情况处理

集群中各个节点的状态随时都有可能发生变化。从实际的变化上来分类的话,节点的异常大致可以分为四种类型:

  • leader不可用
  • follower不可用
  • 多个candidate或者多个leader
  • 新节点加入集群

leader不可用情况处理

  • 一般情况下,leader 节点定时发送 heartbeat 到 follower 节点。

    image-20200701164804325

  • 由于某些异常导致 leader 不再发送 heartbeat ,或 follower 无法收到 heartbeat 。

image-20200701164841660

  • 此时当某一 follower 率先发生 election timeout 时,其状态变更为 candidate,并向其他 follower 发起投票。

    image-20200701164905868

  • 当超过半数的 follower 接受投票后,这一节点将成为新的 leader,leader 的步进数加 1 并开始向 follower 同
    步日志。

    image-20200701164919499

  • 当一段时间之后,如果之前的 leader 再次加入集群,则两个 leader 比较彼此的任期,任期低的 leader 将切换自己的状态为 follower。

    image-20200701164944694

  • 较早前 leader 中不一致的日志将被清除,并与现有 leader 中的日志保持一致。

image-20200701165022191

follower 节点不可用

follower 节点不可用的情况相对容易解决。因为集群中的日志内容始终是从 leader 节点同步的,只要这一节点再次加入集群时重新从 leader 节点处复制日志即可。

  • 集群中的某个 follower 节点发生异常,不再同步日志以及接收 heartbeat。

    image-20200701165104057

  • 经过一段时间之后,原来的 follower 节点重新加入集群。

image-20200701165117348

  • 这一节点的日志将从当时的 leader 处同步。

    image-20200701165128945

多个 candidate 或多个 leader

在集群中出现多个 candidate 或多个 leader 通常是由于数据传输不畅造成的。出现多个 leader 的情况相对少见,但多个 candidate 比较容易出现在集群节点启动初期尚未选出 leader 的“混沌”时期。

  • 初始状态下集群中的所有节点都处于 follower 状态。

    image-20200701165203761

  • 两个节点同时成为 candidate 发起选举。

image-20200701165216568

  • 两个 candidate 都只得到了少部分 follower 的接受投票,此处两个节点都是一人两票

    image-20200701165240165

  • candidate 继续向其他的 follower 询问。

image-20200701165252395

  • 由于一些 follower 已经投过票了,所以均返回拒绝接受。

    image-20200701165304398

  • candidate 也可能向一个 candidate 询问投票。

image-20200701165317129

  • 在步进数相同的情况下,candidate 将拒绝接受另一个 candidate 的请求。

image-20200701165528032

  • 由于第一次未选出 leader,candidate 将随机选择一个等待间隔(150ms ~ 300ms)再次发起投票。

    image-20200701165551600

  • 如果得到集群中半数以上的 follower 的接受,这一 candidate 将成为 leader。

    image-20200701165602018

  • 稍后另一个 candidate 也将再次发起投票。

    image-20200701165619566

  • 由于集群中已经选出 leader,candidate 将收到拒绝接受的投票。

    image-20200701165632066

  • 在被多数节点拒绝之后,并已知集群中已存在 leader 后,这一 candidate 节点将终止投票请求、切换为
    follower,从 leader 节点同步日志。

    image-20200701165652252

Raft日志同步

Leader选出后,就开始接收客户端的请求。Leader把请求作为日志条目(Log entries)加入到它的日志中,然后并行的向其他服务器发起 AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上,Leader将这条日志应用到它的状态机并向客户端返回执行结果

image-20200701173456813

4 个步骤:

  • 客户端的每一个请求都包含被复制状态机执行的指令。

  • leader把这个指令作为一条新的日志条目添加到日志中,然后并行发起 RPC 给其他的服务器,让他们复制这
    条信息。

  • 跟随者响应ACK,如果 follower 宕机或者运行缓慢或者丢包,leader会不断的重试,直到所有的 follower 最终
    都复制了所有的日志条目。

  • 通知所有的Follower提交日志,同时领导人提交这条日志到自己的状态机中,并返回给客户端。

    可以看到,直到第四步骤,整个事务才会达成。中间任何一个步骤发生故障,都不会影响日志一致性。

日志由有序编号(log index)的日志条目组成。每个日志条目包含它被创建时的任期号(term),和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上,就被认为可以提交(commit)了。

v2-ee29a89e4eb63468e142bb6103dbe4de_720w

Raft日志同步保证如下两点:

  • 如果不同日志中的两个条目有着相同的索引和任期号,则它们所存储的命令是相同的。
  • 如果不同日志中的两个条目有着相同的索引和任期号,则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目,同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时,Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志,它就会拒绝新的日志条目。

一般情况下,Leader和Followers的日志保持一致,因此 AppendEntries 一致性检查通常不会失败。然而,Leader崩溃可能会导致日志不一致:旧的Leader可能没有完全复制完日志中的所有条目。

v2-d36c587901391cae50788061f568d24f_720w

上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目,也有可能包含一些Leader没有的条目,也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

Leader通过强制Followers复制它的日志来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。

Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。

Leader会从后往前试,每次AppendEntries失败后尝试前一个日志条目,直到成功找到每个Follower的日志一致位点,然后向后逐条覆盖Followers在该位置之后的条目。

Raft的安全性

Raft增加了如下两条限制以保证安全性:

  • 拥有最新的已提交的log entry的Follower才有资格成为Leader。

这个保证是在RequestVote RPC中做的,Candidate在发送RequestVote RPC时,要带上自己的最后一条日志的term和log index,其他节点收到消息时,如果发现自己的日志比请求中携带的更新,则拒绝投票。日志比较的原则是,如果本地的最后一条log entry的term更大,则term大的更新,如果term一样大,则log index更大的更新。

  • Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志,旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。

之所以要这样,是因为可能会出现已提交的日志又被覆盖的情况:

v2-12a5ebab63781f9ec49e14e331775537_720w

在阶段a,term为2,S1是Leader,且S1写入日志(term, index)为(2, 2),并且日志被同步写入了S2;

在阶段b,S1离线,触发一次新的选主,此时S5被选为新的Leader,此时系统term为3,且写入了日志(term, index)为(3, 2);

S5尚未将日志推送到Followers就离线了,进而触发了一次新的选主,而之前离线的S1经过重新上线后被选中变成Leader,此时系统term为4,此时S1会将自己的日志同步到Followers,按照上图就是将日志(2, 2)同步到了S3,而此时由于该日志已经被同步到了多数节点(S1, S2, S3),因此,此时日志(2,2)可以被提交了。;

在阶段d,S1又下线了,触发一次选主,而S5有可能被选为新的Leader(这是因为S5可以满足作为主的一切条件:1. term = 5 > 4,2. 最新的日志为(3,2),比大多数节点(如S2/S3/S4的日志都新),然后S5会将自己的日志更新到Followers,于是S2、S3中已经被提交的日志(2,2)被截断了。

增加上述限制后,即使日志(2,2)已经被大多数节点(S1、S2、S3)确认了,但是它不能被提交,因为它是来自之前term(2)的日志,直到S1在当前term(4)产生的日志(4, 4)被大多数Followers确认,S1方可提交日志(4,4)这条日志,当然,根据Raft定义,(4,4)之前的所有日志也会被提交。此时即使S1再下线,重新选主时S5不可能成为Leader,因为它没有包含大多数节点已经拥有的日志(4,4)。

Raft与Multi-Paxos的异同

Raft与Multi-Paxos中相似的概念:

v2-a932cb62a02604d5ec57dc0a046a1414_720w

Raft与Multi-Paxos的不同:

v2-7679d235c0ac8056552ba88b677e73a2_720w

参考

Raft算法详解

动画演示Raft算法全过程

寻找一种易于理解的一致性算法

The Raft Consensus Algorithm