Paxos,Raft,Zab一致性协议-Raft篇

Raft是一个一致性算法,旨在易于理解。它提供了Paxos的容错和性能。不同之处在于它被分解为相对独立的子问题,它清楚地解决了实际系统所需的所有主要部分。我们希望Raft能够为更广泛的受众提供共识,并且这个更广泛的受众将能够开发出比现在更多的高质量共识系统。

Raft是一个通过管理一个副本日志的一致性算法。它提供了跟(multi-)Paxos一样有效的功能,但是它的架构和Paxos不一样;它比Paxos更加容易理解,并且能用于生产环境中。为了加强理解,raft把一致性的问题分成了三个子问题,例如leader election, log replication, and safety,

Role

Leader,Follower,candidate

在Raft集群中,有且仅有一个Leader,在Leader运行正常的情况下,一个节点服务器要么就是Leader,要么就是Follower。Follower直到Leader故障了,才有可能变成candidate。

Leader负责把client的写请求log复制到follower。它会和follower保持心跳。每个follower都有一个timeout时间(一般为150ms~300ms),在接受到心跳的时候,这个timeout时间会被重置。如果follower没有接收到心跳,这些follower会把他们的状态变为candidate,并且开启新的一轮leader election。

term逻辑时钟

Term相当于paxos中的proposerID,相当于一个国家的朝代。term是一段任意的时间序号。每一任Leader都有一个与之前不同的term。

当Leader选举成功之后,一个节点成为了Leader,就会产生一个新的term,并且直到Leader故障,整个集群都会一直在这个term下执行操作。

如果leader选举失败了,则会再生成出一个term,再开启一轮leader选举。

Quorums:

多数派,意思是超过一半的机器存活,则这个机器可用,这个Quorums指的就是集群可用的指标。例如:集群中的节点数为2N,如果有N+1的机器存活,则代表集群可用,可接受请求,写入log,应用到state machine中去,执行操作。如果少于N+1个机器存活,则代表集群可用,可接受请求,可写入log,但不应用到state machine中去,不执行操作。

Leader Election

只有在下列两种情况下才会进行leader election:

在第一次启动raft集群的时候

在一个已存在的Leader故障的时候

选举流程:

如果以上两种任何一种发生了,所有的Follower无法再和Leader保持心跳,则它们都会等待一个(选举)timeout,如果其中一个Follower的timeout最先到时,则这个Follower变成candidate开始选举,

第一,增加term计数器,

第二,给自己投票并向所有其他的节点服务器请求投自己一票。

如果一个Follower在接受到投票请求时,接受到两个term相同的投票请求时(也就是说,产生了两个candidate),则在多个相同term的投票请求中,这个Follower只能给投给其中一个请求,只能投一票,并且按照先来先服务的原则投票。

如果这个candidate收到另外一个节点服务器的消息,并且这个节点服务器的term序号和当前的term序号一样大,甚至更大的话,则这个candidate选举失败,从而它的状态变成Follower,并且接受新的Leader。

如果一个candidate获得了Quorums选票N+1(2N为集群中节点的数目),则它变成新的leader。

如果多个candidate和多个Follower投完票之后,有多个candidate获得了相同的票数,则会产生split vote,则新的term产生,重新选举。Raft用随机选举timeout迅速地解决split vote问题,这个方法就是对于产生spit vote的candidates各自随机生成一个选举timeout,谁先到时,谁当leader,其他candidate都变为Follower。

当一个leader被选举出来之后,就在Follower timeout到时变为candidate之前,发心跳信息给所有Followers。

Log Replication(Raft协议具体过程)

Leader负责把client的请求日志复制给其他Followers。

Raft协议具体过程就是通过复制状态机的架构实现的,如下:

步骤:

Client发送请求给Leader,其中每个请求都是一条操作指令。

Leader接受到client请求之后,把操作指令(Entry)追加到Leader的操作日志中。紧接着对Follower发起AppendEntries请求、尝试让操作指令(Entry)追加到Followers的操作日志中,即落地。如果有Follower不可用,则一直尝试。

一旦Leader接受到多数(Quorums)Follower的回应,Leader就会进行commit操作,每一台节点服务器会把操作指令交给状态机处理。这样就保证了各节点的状态的一致性。

各服务器状态机处理完成之后,Leader将结果返回给Client。

Saftety

Raft的安全性,体现在如下几个方面:

Election safety:在一个term下,最多只有一个Leader。

Leader Append-Only:一个Leader只能追加新的entries,不能重写和删除entries

Log Matching:集群中各个节点的log都是相同一致的

Leader Completeness:如果一个log entry被committed了,则这个entry一定会出现在Leader的log里。

State Machine Safety:如果一个节点服务器的state machine执行了一个某个log entry命令,则其他节点服务器,也会执行这个log entry命令,不会再执行其他命令

之前四条,在前面都有所提及,而State Machine Safety是在Leader election过程中用到过。

State Machine Safety

一个candidate在选举的时候,它会向其他节点服务器发送包含他的log的消息,获取票数,如果它的log是最新的,则会获取选票,如果它的log不是最新的,其他节点服务器还有更加新的log,则会拒绝给这个candidate投票。这就保证了State Machine Safety。

所以State Machine Safety保证的就是一个candidate必须拥有最新的log,才能获取票数,才有机会赢得Leader选举,才有机会成为Leader。

Follower crashes

如果一个follower故障了,则不会再接受AppendEntriesandvoterequests,并且Leader会不断尝试与这个节点保持心跳。

如果这个节点恢复了,则会接受Leader的最新的log,并且将log应用到state machine中去,执行log中的操作

方格指的是client发出的一条请求。

方格虚线,说明一条log entry写入了log。

方格实线,说明一条log entry应用到state machine中

Leader crashes

则会进行Leader election。

如果碰到Leader故障的情况,集群中所有节点的日志可能不一致。

old leader的一些操作日志没有通过集群完全复制。new leader将通过强制Followers复制自己的log来处理不一致的情况,步骤如下:

对于每个Follower,new leader将其日志与Followers的日志进行比较,找到他们的达成一致的最后一个log entry。

然后删除掉Followers中这个关键entry后面的所有entry,并将其替换为自己的log entry。该机制将恢复日志的一致性。

下面这种情况集群中所有节点的日志可能不一致:

总结

Raft要求具备唯一Leader,并把一致性问题具体化为保持日志副本的一致性,以此实现相较Paxos而言更容易理解、更容易实现的目标。Raft是state machine system,Zab是primary-backup system。

引用

https://en.wikipedia.org/wiki/Raft_(computer_science)

https://raft.github.io/

http://thesecretlivesofdata.com/raft/

https://raft.github.io/raft.pdf

https://www.cnblogs.com/bangerlee/p/5991417.html

https://www.bilibili.com/video/av21667358/

https://en.wikipedia.org/wiki/State_machine_replication

https://github.com/CNiceToUpp/notes/blob/master/paxos%2Craft%2Czab/paper/In%20Search%20of%20an%20Understandable%20Consensus%20Algorithm.pdf

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180703G0J0GE00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券