一致性协议算法

发布于: 2020 年 07 月 14 日

本篇文章总结了三种常用的一致性算法:Raft、ZAB、Paxos

Raft算法

参考文档:

https://zhmin.github.io/2019/09/15/zookeeper-zab/

https://zhuanlan.zhihu.com/p/66441389

选举

一些概念

在介绍选举前先介绍几个概念

  • leader 接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。

  • Follower leader的跟随者,接收并持久化leader同步的日志

  • Candidate Leader选举中的临时角色

  • term 任期,比如新的选举任期,即整个集群初始化时,或者新的Leader选举就会开始一个新的选举任期。

  • 大多数:假设一个集群由N个节点组成,那么大多数就是至少N/2+1。例如:3个节点的集群,大多数就是至少2;5个节点的集群,大多数就是至少3

如何选举

Leader选举需要某个节点发起投票,在确定哪个节点向其他节点发起投票之前,每个节点会分配一个随机的选举超时时间(election timeout)。在这个时间内,节点必须等待,不能成为Candidate状态。现在假设节点a等待168ms , 节点b等待210ms , 节点c等待200ms 。由于a的等待时间最短,所以它会最先成为Candidate,并向另外两个节点发起投票请求,希望它们能选举自己为Leader:

  • a将其当前term+1然后转换为Candidate,它首先会给自己投票,并给集群中的其他节点发送RequestVote RPC

  • a收到了大多数的投票,就会从Candidate变为Leader,接下来分布式系统所有的概念都会先经过节点a

  • 如果a没有赢得多数的投票,则选举失败,等待选举时间超时后发起下一次选举

  • 如果某个时刻,Follower不再收到Leader的消息,它就会变成Candidate。然后请求其他节点给他投票(类似拉票一样)。其他节点就会回复它投票结果,如果它能得到大多数节点的投票,它就能成为新的Leader。

日志复制

一些概念

  • uncommitted 未提交,一条日志提交给Leader后,还没被其他节点接收,状态会初始化uncommitted

  • committed 一旦大多数节点成功写入了这条日志,那么Leader节点的这条日志状态就会更新为commited状态

复制过程

  1. client写入日志,发起请求

  2. 请求首先进入Leader,Leader写入该日志,并将该日志的状态设置为uncommitted

  3. Leader会将此日志通过心跳消息复制给其他的follower

  4. 如果大多数节点成功写入这条日志,那么Leader节点的这条日志就会更新为commited

网络分区

一些概念

  • CAP定义

  • Consistency 每次读取的数据都应该是最近写入的数据或者返回一个错误,等同于所有节点访问同一份最新的数据副本

  • Availability 每次请求都应该得到一个响应,而不是返回一个错误或者丢失后响应,不过这个响应不需要保证数据是最近写入的

  • Partition tolerance 即使因为网络原因,部分服务器节点之间消息丢失或者延迟了,系统依然应该是可以操作的,以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况

  • 网络分区 网络分区指由于网络设备的failure,造成网络分裂为多个独立的组

Raft处理

  • 假设我们的集群由5个节点组成,且节点B是Leader节点

  • 我们假设发生了网络分区:节点A和B在一个网络分区,节点C、D和E在另一个网络分区,且节点B和节点C分别是两个网络分区中的Leader节点

  • 我们假设还有一个客户端,并且往节点B上发送了一个SET 3,由于网络分区的原因,这个值不能被另一个网络分区中的Leader即节点C拿到,它最多只能被两个节点(节点B和C)感知到,所以它的状态是uncomitted(红色)

  • 另一个客户端准备执行SET 8的操作,由于可以被同一个分区下总计三个节点(节点C、D和E)感知到,3个节点已经符合大多数节点的条件。所以,这个值的状态就是committed

  • 接下来,我们假设网络恢复正常,节点B能感知到C节点这个Leader的存在,它就会从Leader状态退回到Follower状态,并且节点A和B会回滚之前没有提交的日志(SET 3产生的uncommitted日志)。同时,节点A和B会从新的Leader节点即C节点获取最新的日志(SET 8产生的日志),从而将它们的值更新为8。如此以来,整个集群的5个节点数据完全一致了

超时处理

选举超时

为了防止3个节点(假设集群由3个节点组成)同时发起投票,会给每个节点分配一个随机的选举超时时间(Election Timeout),即从Follower状态成为Candidate状态需要等待的时间。在这个时间内,节点必须等待,不能成为Candidate状态。如下图所示,节点C优先成为Candidate,而节点A和B还在等待中:

心跳超时

如下图所示,节点A和C投票给了B,所以节点B是leader节点。节点B会固定间隔时间向两个Follower节点A和C发送心跳消息,这个固定间隔时间被称为heartbeat timeout。Follower节点收到每一条日志信息都需要向Leader节点响应这条日志复制的结果

重新选举

如果Leader节点出现故障,就会触发重新选举。如下图所示,Leader节点B故障(灰色),这时候节点A和C就会等待一个随机时间(选举超时),谁等待的时候更短,谁就先成为Candidate,然后向其他节点发送投票请求,如果节点A能得得到节点C的投票,加上自己的投票,就有大多数选票。那么节点A将成为新的Leader节点,并且Term即任期的值加1更新到2:

需要说明的是,每个选举期只会选出一个Leader。假设同一时间有两个节点成为Candidate(它们随机等待选举超时时间刚好一样),如下图所示,并且假设节点A收到了节点B的投票,而节点C收到了节点D的投票:

这种情况下,就会触发一次新的选举,节点A和节点B又等待一个随机的选举超时时间,直到一方胜出:

我们假设节点A能得到大多数投票,那么接下来节点A就会成为新的Leader节点,并且任期term加1:

ZAB算法

参考文档:

https://zhmin.github.io/2019/09/15/zookeeper-zab/

选举

一些概念

  • leader 主节点,与上面相同

  • follower 从节点,与上面相同

  • observer 可以认为是主的clone copy,不参与投票

  • quorum 集群中超过半数的节点集合

  • zxid Zxid 是一个 64 位的数字,其中低 32 位是一个简单的单调递增的计数器,针对客户端每一个事务请求,计数器加 1;而高 32 位则代表 Leader 周期 epoch 的编号,每个当选产生一个新的 Leader 服务器,就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID,并从中读取 epoch 值,然后加 1,以此作为新的 epoch,并将低 32 位从 0 开始计数。

ZAB 中的节点有三种状态

  • following:当前节点是跟随者,服从 leader 节点的命令

  • leading:当前节点是 leader,负责协调事务

  • election/looking:节点处于选举状态

如何选举

成为 leader 的条件

  1. epoch最大的

  2. epoch相等,选 zxid 最大的

  3. epochzxid都相等,选择server id最大的(就是我们配置zoo.cfg中的myid

选举过程(fast paxos)

节点在选举开始都默认投票给自己,当接收其他节点的选票时,会根据上面的条件更改自己的选票并重新发送选票给其他节点,当有一个节点的得票超过半数,该节点会设置自己的状态为 leading,其他节点会设置自己的状态为 following。

  • 每个进入looking状态的节点,最开始投票给自己,然后把投票消息发给其它机器。内容为<第几轮投票,被投节点的zxid,被投节点的编号>

  • 其他looking状态的节点收到后,首先判断票是否有效,是否有效的方法为看票的投票轮数和本地记载的投票轮数是否相等。

  • 如果比本地投票轮数的小,丢弃

  • 如果比本地投票轮数的大,证明自己投票过期了,清空本地投票信息,更新投票轮数和结果为收到的内容。通知其他所有节点新的投票方案。

  • 如果和本地投票轮数相等,按照投票的优先级比较收到的选票和自己投出去的选票

  • 如果收到的优先级大,更新自己的投票为对方发过来投票方案,把投票发出去。

  • 如果收到的优先级小,则忽略该投票。

  • 如果收到的优先级相等,则更新对应节点的投票。

  • 每收集到一个投票后,查看已经收到的投票结果记录列表,看是否有节点能够达到一半以上的投票数。如果有达到,则终止投票,宣布选举结束,更新自身状态。然后进行发现和同步阶段。

  • 否则继续收集投票。

选举过程(basic paxos)

  • 每个looking节点先发出请求,询问其他节点的投票。

  • 其他节点返回自己的投票 < zk的id,zxid >。第一次都投自己。

  • 收到结果后,如果收到的投票比自己投票的zxid大,更新自己的投票。

  •  当收到所有节点返回后,统计投票,有一个节点的选举达到一半以上,则选举成功。否则继续开始下一轮询问,直到选择出leader结束。

消息复制

ZAB 协议的消息广播过程使用的是一个原子广播协议,类似一个 二阶段提交过程。对于客户端发送的写请求,全部由 Leader 接收,Leader 将请求封装成一个事务 Proposal,将其发送给所有 Follwer ,然后,根据所有 Follwer 的反馈,如果超过半数成功响应,则执行 commit 操作(先提交自己,再发送 commit 给所有 Follwer)。

  • 将数据都复制到 Follwer 中

  • 等待 Follwer 回应 Ack,最低超过半数即成功

  • 当超过半数成功回应,则执行 commit ,同时提交自己

一些细节

  1. Leader 在收到客户端请求之后,会将这个请求封装成一个事务,并给这个事务分配一个全局递增的唯一 ID,称为事务ID(ZXID),ZAB 兮协议需要保证事务的顺序,因此必须将每一个事务按照 ZXID 进行先后排序然后处理。

  2. 在 Leader 和 Follwer 之间还有一个消息队列,用来解耦他们之间的耦合,解除同步阻塞。

  3. zookeeper集群中为保证任何所有进程能够有序的顺序执行,只能是 Leader 服务器接受写请求,即使是 Follower 服务器接受到客户端的请求,也会转发到 Leader 服务器进行处理。

  4. 实际上,这是一种简化版本的 2PC,不能解决单点问题。

灾难场景

Leader 崩溃

崩溃即:Leader 失去与过半 Follwer 的联系

ZAB保证:能够确保提交已经被 Leader 提交的事务,同时丢弃已经被跳过的事务。

  • ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。

  • ZAB 协议确保丢弃那些只在 Leader 提出/复制,但没有提交的事务。

针对这个要求,如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号(即 ZXID 最大)的事务,那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。而且这么做有一个好处是:可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

数据同步

当成为 follower 节点后,需要向 leader 节点同步数据,因为 follower 节点的数据可能落后于leader。当同步过程完成后,集群就可以对外提供读写服务了。

  • 当 Follower 连接上 Leader 之后,Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对,比对结果要么回滚,要么和 Leader 同步

  • 当所有的 Follwer 服务器都成功同步之后,Leader 会将这些服务器加入到可用服务器列表中

  • 这里只有当准Leader将多数节点数据同步到一致状态之后,才会发送NewLeader给多数节点,多数节点才更新其本地的currentEpoch

ZAB中Leader会根据Follower数据情况使用多种同步策略:

  • SNAP:如果Follower数据太老,Leader将发送快照SNAP指令给Follower同步数据

  • DIFF:Leader发送从Follower.lastZxid到Leader.lastZxid之间的提案DIFF数据给Follower同步数据

  • TRUNC:当Follower.lastZxid比Leader.lastZxid大时,Leader发送从Leader.lastZxid到Follower.lastZxid的TRUNC指令让Follower丢弃该段数据SNAP和DIFF用于保证集群中Follower节点上已经Committed的数据的一致性,TRUNC用于抛弃已经被处理但是还没有Committed的数据。Follower接收SNAP/DIFF/TRUNC指令同步数据与ZXID,同步成功之后向Leader发送ACK-LD,Leader才会将其加入到可用Follower列表。

Paxos算法

参考文档:

https://zhuanlan.zhihu.com/p/31780743

https://www.cnblogs.com/linbingdong/p/6253479.html

背景

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法,使其获得2013年图灵奖。

Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开,最初的描述使用希腊的一个小岛Paxos作为比喻,描述了Paxos小岛中通过决议的流程,并以此命名这个算法,但是这个描述理解起来比较有挑战性。后来在2001年,Lamport觉得同行不能理解他的幽默感,于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

自Paxos问世以来就持续垄断了分布式一致性算法,Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题,如Chubby、Megastore以及Spanner等。开源的ZooKeeper,以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。

然而,Paxos的最大特点就是难,不仅难以理解,更难以实现。

Basic Paxos

一些概念

  • Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

  • Acceptor:参与决策,回应Proposers的提案。收到Proposal后可以接受提案,若Proposal获得多数Acceptors的接受,则称该Proposal被批准。

  • Learner:不参与决策,从Proposers/Acceptors学习最新达成一致的提案(Value)。

在具体的实现中,一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner

算法过程

Paxos算法通过一个决议分为两个阶段(Learn阶段之前决议已经形成):

  1. 第一阶段:Prepare阶段。Proposer向Acceptors发出Prepare请求,Acceptors针对收到的Prepare请求进行Promise承诺。

  2. 第二阶段:Accept阶段。Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理。

  3. 第三阶段:Learn阶段。Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有Learners。

Paxos算法流程中的每条消息描述如下:

  • Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID),向所有Acceptors发送Prepare请求,这里无需携带提案内容,只携带Proposal ID即可。

  • Promise: Acceptors收到Prepare请求后,做出“两个承诺,一个应答”。

两个承诺:

1. 不再接受Proposal ID小于等于(注意:这里是<= )当前请求的Prepare请求。

2. 不再接受Proposal ID小于(注意:这里是< )当前请求的Propose请求。

一个应答:

不违背以前作出的承诺下,回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID,没有则返回空值。

  • Propose: Proposer 收到多数Acceptors的Promise应答后,从应答中选择Proposal ID最大的提案的Value,作为本次要发起的提案。如果所有应答的提案Value均为空值,则可以自己随意决定提案Value。然后携带当前Proposal ID,向所有Acceptors发送Propose请求。

  • Accept: Acceptor收到Propose请求后,在不违背自己之前作出的承诺下,接受并持久化当前Proposal ID和提案Value。

  • Learn: Proposer收到多数Acceptors的Accept后,决议形成,将形成的决议发送给所有Learners。

问题

Paxos算法可能形成活锁而永远不会结束,如下图实例所示:

Paxos算法形成活锁

回顾两个承诺之一,Acceptor不再应答Proposal ID小于等于当前请求的Prepare请求。意味着需要应答Proposal ID大于当前请求的Prepare请求。

两个Proposers交替Prepare成功,而Accept失败,形成活锁(Livelock)。

Multi-Paxos算法

原始的Paxos算法(Basic Paxos)只能对一个值形成决议,决议的形成至少需要两次网络来回,在高并发情况下可能需要更多的网络来回,极端情况下甚至可能形成活锁。如果想连续确定多个值,Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究,并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值,而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了两点改进:

  1. 针对每一个要确定的值,运行一次Paxos算法实例(Instance),形成决议。每一个Paxos实例使用唯一的Instance ID标识。

  2. 在所有Proposers中选举一个Leader,由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争,解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下,Prepare阶段就可以跳过,从而将两阶段变为一阶段,提高效率。

Multi-Paxos首先需要选举Leader,Leader的确定也是一次决议的形成,所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal,在Leader宕机之后服务临时不可用,需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下,Prepare阶段可以跳过。

Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例,从而使得Leader的连续提交只需要执行一次Prepare阶段,后续只需要执行Accept阶段,将两阶段变为一阶段,提高了效率。为了区分连续提交的多个实例,每个实例使用一个Instance ID标识,Instance ID由Leader本地递增生成即可。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性,这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。

用户头像

张瑞浩

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论

发布
暂无评论
一致性协议算法