【Paxos算法】是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一,其解决的问题就是在分布式系统中如何就某个值(决议)达成一致。
Paxos算法的前提假设是不存在拜占庭将军问题,即:信道是安全的(信道可靠),发出的信号不会被篡改。
只有被提出的value才能被选定。
*
只有一个value被选定。
*
如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个。
Paxos算法类似于两阶段提提交,其算法执行过程分为两个阶段。具体如下
proposer提出一个编号为N的proposal,发送给半数以上的acceptor。
acceptor收到编号为N的prepare请求后:
如果小于它已经响应过的请求,则拒绝回复或者回复error;
如果N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过(已经经过第二阶段accept的提案)的编号最大的提案(如果有的话,如果还没有的accept提案的话返回{pok,null,null})作为响应反馈给Proposer,同时存储更新本地对应的提案编号,并且该Acceptor承诺不再接受任何编号小于N的提案。
分为两种情况:
如果acceptor已经接受过提案,返回接受提案的最大value;
如果还没有接受过提案,就返回{pok,null,null})
如果proposer收到半数以上的acceptor回复的编号为N的提案的prepare响应,那么会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。
注意:V就是收到的响应中编号最大的提案的value。
如果响应中不包含任何提案,那么V就由Proposer自己决定,可以是任意值。
*
如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。
*
如果N小于Acceptor以及响应的prepare请求,则拒绝,不回应或回复error(当proposer没有收到过半的回应,那么他会重新进入第一阶段,递增提案号,重新提出prepare请求)。
具体如下图所示:
过半的acceptor都接受提案后,learner会自动感知到,并开始学习提案。(同一个进程可以同时扮演多个角色)
本节点Proposer的某个提案被选中(chosen)时,通过(MsgType_PaxosLearner_ProposerSendSuccess)消息通知到各个节点。
*
正常情况下,所有节点处于online状态,共同参与paxos选举。因此为了避免instance id冲突,paxos建议只由主节点的proposer发起提案,这样保证接受提案和习得提案编号一致。
*
此时,Learn习得的提案值实际上就是本节点Accept的数据,因此learner只更新内存状态即可,无需再次落盘(acceptor已落盘)。
*
最后,如果存在follower节点,数据同步到follower(follower节点不参与paxos算法,相当于某个paxos节点的同步备)。
一旦节点处于落后状态,它无法再参与到paxos提案选举中来。这时需要由learner发起主动学习完成追赶。
*
Paxos启动时,启动learner定时器,定时发送learn请求到各个节点,发送请求携带本节点的Instance ID、Node ID信息。各节点收到该请求后,回复数据自主完成学习过程。
假设有K台Server运行paxos算法,那么他们初始编号为0…k-1。以后编号每次增加k,从而保证全局唯一递增。
*
正式提案被半数以上Acceptor接受后,就可以确定最终被接受的提案就是该观点。
*
两个半数以上的集合的一定存在交集。
介绍了Paxos的算法逻辑,但在算法运行过程中,可能还会存在一种极端情况,当有两个proposer依次提出一系列编号递增的议案,那么会陷入死循环,无法完成第二阶段,也就是无法选定一个提案。如下图:
Zookeeper 采用的 ZAB协议也是基于 Paxos 算法实现的,不过 ZAB 对 Paxos 进行了很多改进与优化,两者的设计目标也存在差异——ZAB 协议主要用于构建一个高可用的分布式数据主备系统,而 Paxos 算法则是用于构建一个分布式的一致性状态机系统。
ZAB协议全称就是ZooKeeper Atomic Broadcast protocol,是ZooKeeper用来实现一致性的算法,分成如下3个阶段:
fast leader election:快速选举阶段
recovery:恢复阶段
Discovery;
Synchrozation
broadcasting:广播阶段
选举过程关注两个要点:刚启动时进行leader选举和选举完leader后,刚启动的server怎么感知到leader,投票过程有两个比较重要的数据:
从快照日志和事务日志中加载数据,得到本机器的内存树数据,以及lastProcessedZxid。投票内容为:
proposedLeader:server自身的myid值,初始为本机器的id
proposedZxid:最大事务zxid,初始为本机器的lastProcessedZxid
proposedEpoch:peerEpoch值,由上述的lastProcessedZxid的高32得到
然后向所有的服务器发送投票。
server接收到投票通知后,进行PK。
根据server的状态来判定leader
如果当前发来的投票的server的状态是LOOKING状态,则只需要判断本机器的投票是否在recvset中过半了,如果过半了则说明leader选举就算成功了,如果当前server的id等于上述过半投票的proposedLeader,则说明自己将成为了leader,否则自己将成为了follower。
*
如果当前发来的投票的server的状态是FOLLOWING、LEADING状态,则说明leader选举过程已经完成了,则发过来的投票就是leader的信息,这里就需要判断发过来的投票是否在recvset或者outofelection中过半了,同时还要检查leader是否给自己发送过投票信息,从投票信息中确认该leader是不是LEADING状态。
一旦leader选举完成,就开始进入恢复阶段,就是follower要同步leader上的数据信息。
通信初始化
leader会创建一个ServerSocket,接收follower的连接,leader会为每一个连接会用一个LearnerHandler线程来进行服务;
重新为peerEpoch选举出一个新的peerEpoch
follower会向leader发送一个Leader,FOLLOWERINFO信息,包含自己的peerEpoch信息。
*
leader的LearnerHandler会获取到上述peerEpoch信息,从中选出一个最大的peerEpoch,然后加1作为新的peerEpoch。
*
然后leader的所有LearnerHandler会向各自的follower发送一个Leader.LEADERINFO信息,包含上述新的peerEpoch;
*
follower会使用上述peerEpoch来更新自己的peerEpoch,同时将自己的lastProcessedZxid发给leader,leader的根据这个lastProcessedZxid和leader的lastProcessedZxid之间的差异进行同步。
*
已经处理的事务议案的同步
判断LearnerHandler中的lastProcessedZxid是否在minCommittedLog和maxCommittedLog之间
*
LearnerHandler中的lastProcessedZxid和leader的lastProcessedZxid一致,则说明已经保持同步了
*
如果lastProcessedZxid在minCommittedLog和maxCommittedLog之间,从lastProcessedZxid开始到maxCommittedLog结束的这部分议案,重新发送给该LearnerHandler对应的follower,同时发送对应议案的commit命令。
上述可能存在一个问题:即lastProcessedZxid虽然在他们之间,但是并没有找到lastProcessedZxid对应的议案,即这个zxid是leader所没有的,此时的策略就是完全按照leader来同步,删除该follower这一部分的事务日志,然后重新发送这一部分的议案,并提交这些议案。
如果lastProcessedZxid大于maxCommittedLog,则删除该follower大于部分的事务日志
*
如果lastProcessedZxid小于minCommittedLog,则直接采用快照的方式来恢复。
未处理的事务议案的同步
LearnerHandler还会从leader的toBeApplied数据中将大于该LearnerHandler中的lastProcessedZxid的议案进行发送和提交(toBeApplied是已经被确认为提交的)
*
LearnerHandler还会从leader的outstandingProposals中大于该LearnerHandler中的lastProcessedZxid的议案进行发送,但是不提交(outstandingProposals是还没被被确认为提交的)
*
将LearnerHandler加入到正式follower列表中
*
LearnerHandler发送Leader.NEWLEADER以及Leader.UPTODATE命令。
事务持久化分为:broadcasting持久化和leader shutdown过程的持久化。
leader针对每次事务请求都会生成一个议案,然后向所有的follower发送该议案。follower收到提案后,将该议案记录到事务日志中,每当记满100000个(默认),则事务日志执行flush操作,同时开启一个新的文件来记录事务日志
同时会执行内存树的快照,snapshot.[lastProcessedZxid]作为文件名创建一个新文件,快照内容保存到该文件中
一旦leader过半的心跳检测失败,则执行shutdown方法,在该shutdown中会对事务日志进行flush操作
在分布式系统中,一致性算法至关重要。在所有一致性算法中,Paxos 最负盛名,它由莱斯利·兰伯特(Leslie Lamport)于 1990 年提出,是一种基于消息传递的一致性算法,被认为是类似算法中最有效的。
Paxos算法虽然很有效,但复杂的原理使它实现起来非常困难,截止目前,实现 Paxos 算法的开源软件很少,比较出名的有 Chubby、LibPaxos。
由于Paxos算法过于复杂、实现困难,极大地制约了其应用,而分布式系统领域又亟需一种高效而易于实现的分布式一致性算法,在此背景下,Raft 算法应运而生。
*
Raft是一个共识算法(consensus algorithm),所谓共识,就是多个节点对某个事情达成一致的看法,即使是在部分节点故障、网络延时、网络分割的情况下。
*
共识算法的实现一般是基于复制状态机(Replicated state machines),何为复制状态机:简单来说:相同的初识状态 + 相同的输入 = 相同的结束状态。
一个Raft集群包含若干个节点,这些节点分为三种状态:Leader、 Follower、Candidate,每种状态负责的任务也是不一样的。正常情况下,集群中的节点只存在 Leader与Follower两种状态。
为简化逻辑和实现,Raft 将一致性问题分解成了三个相对独立的子问题。
如果follower在election timeout内没有收到来自leader的心跳,则会主动发起选举。
Raft 集群在刚启动(或 Leader 宕机)时,所有节点的状态都是 Follower,初始 Term(任期)为 0。同时启动选举定时器,每个节点的选举定时器超时时间都在 100~500 毫秒之间且并不一致。
没有leader后,followers状态自动转为candidate,并向集群中所有节点发送投票请求并且重置选举定时器。
增加节点本地的current term ,切换到candidate状态
投自己一票,并行给其他节点发送 RequestVote RPCs
等待其他节点的回复,可能出现三种结果:
收到majority的投票(含自己的一票),则赢得选举,成为leader
被告知别人已当选,那么自行切换到follower
一段时间内没有收到majority投票,则保持candidate状态,重新发出选举
当leader选举成功后,客户端所有的请求都交给了leader,leader调度请求的顺序性和followers的状态一致性。
*
在集群中,所有的节点都可能变为leader,为了保证后续leader节点变化后依然能够使集群对外保持一致,需要通过Log Replication机制来解决如下两个问题:
*
Follower与Leader节点相同的顺序依次执行每个成功提案;
*
每个成功提交的提案必须有足够多的成功副本,来保证后续的访问一致
Leader 在收到client请求提案后,会将它作为日志条目(Entry)写入本地log中。需要注意的是,此时该 Entry 的状态是未提交(Uncommitted),Leader 并不会更新本地数据,因此它是不可读的。
Leader 与 Floolwers 之间保持着心跳联系,随心跳 Leader 将追加的 Entry(AppendEntries)并行地发送给其它的 Follower,并让它们复制这条日志条目,这一过程称为复制(Replicate)。
*
为什么 Leader 向 Follower 发送的 Entry 是 AppendEntries,因为 Leader 与 Follower 的心跳是周期性的,而一个周期间 Leader 可能接收到多条客户端的请求,因此,随心跳向 Followers 发送的大概率是多个 Entry,即 AppendEntries。
*
Leader 向 Followers 发送的不仅仅是追加的 Entry(AppendEntries)在发送追加日志条目的时候,Leader 会把新的日志条目紧接着之前条目的索引位置(prevLogIndex), Leader 任期号(Term)也包含在其中。如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目,那么它就会拒绝接收新的日志条目,因为出现这种情况说明 Follower 和 Leader 不一致。
*
如何解决 Leader 与 Follower 不一致的问题,正常情况下,Leader 和 Follower 的日志保持一致。然而,Leader 和 Follower 一系列崩溃的情况会使它们的日志处于不一致状态。
Followers 接收到 Leader 发来的复制请求后,有两种可能的回应:
写入本地日志中,返回 Success;
*
一致性检查失败,拒绝写入,返回 False,原因和解决办法上面已做了详细说明。
*
当 Leader 收到大多数 Followers 的回应后,会将第一阶段写入的 Entry 标记为提交状态(Committed),并把这条日志条目应用到它的状态机中。
完成前三个阶段后,Leader会向客户端回应 OK,表示写操作成功。
Leader 回应客户端后,将随着下一个心跳通知 Followers,Followers 收到通知后也会将 Entry 标记为提交状态。至此,Raft 集群超过半数节点已经达到一致状态,可以确保强一致性。
1) election safety: 在一个term内,至多有一个leader被选举出来。raft算法通过
一个节点某一任期内最多只能投一票;
只有获得majority投票的节点才会成为leader。
2)log matching:说如果两个节点上的某个log entry的log index相同且term相同,那么在该index之前的所有log entry应该都是相同的。leader在某一term的任一位置只会创建一个log entry,且log entry是append-only。
3)consistency check。leader在AppendEntries中包含最新log entry之前的一个log 的term和index,如果follower在对应的term index找不到日志,那么就会告知leader不一致。当出现了leader与follower不一致的情况,leader强制follower复制自己的log。
3)leader completeness :如果一个log entry在某个任期被提交(committed),那么这条日志一定会出现在所有更高term的leader的日志里面。
一个日志被复制到majority节点才算committed
一个节点得到majority的投票才能成为leader,而节点A给节点B投票的其中一个前提是,B的日志不能比A的日志旧。
4)stale leader: 落后的leader,但在网络分割(network partition)的情况下,可能会出现两个leader,但两个leader所处的任期是不同的。而在raft的一些实现或者raft-like协议中,leader如果收不到majority节点的消息,那么可以自己step down,自行转换到follower状态。
5)leader crash:新的节点成为Leader,为了不让数据丢失,希望新Leader包含所有已经Commit的Entry。为了避免数据从Follower到Leader的反向流动带来的复杂性,Raft限制新Leader一定是当前Log最新的节点,即其拥有最多最大term的Log Entry。
6)State Machine Safety
某个leader选举成功之后,不会直接提交前任leader时期的日志,而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了,具体的实现是:如果leader被选举后没有收到客户端的请求呢,论文中有提到,在任期开始的时候发立即尝试复制、提交一条空的log。
总结:raft将共识问题分解成两个相对独立的问题,leader election,log replication。流程是先选举出leader,然后leader负责复制、提交log(log中包含command)
一个log被复制到大多数节点,就是committed,保证不会回滚
leader一定包含最新的committed log,因此leader只会追加日志,不会删除覆盖日志
不同节点,某个位置上日志相同,那么这个位置之前的所有日志一定是相同的
Raft never commits log entries from previous terms by counting replicas.
极限就是为了超越而存在的
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://www.cnblogs.com/liboware/p/15229621.html
内容来源于网络,如有侵权,请联系作者删除!