2PC(两阶段提交)


    • 角色
      • 协调者
      • 参与者
    • 过程
      • 提交请求:协调者发送消息给所有参与者,参与者写入undo/redo日志,并且投票反馈yes/no。
      • 提交/回滚:若所有参与者反馈yes,协调者会发送commit消息;若有参与者反馈no或者由于超时协调未收到响应时,协调者会发送abort消息,参与者收到后会执行回滚。
    • 缺点
      • 两阶段提交协议的最大缺点是它是一种阻塞协议。如果协调者永久失败,则一些参与者将永远不会处理其事务:在参与者向协调者反馈消息后,它将一直阻塞,直到收到提交或回滚。
      • 无法解决这样的场景:协调者在发出commit消息之后宕机,而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者,这条事务的状态也是不确定的,必须等到所有参与者反馈(包含宕机的参与者)。

3PC(三阶段提交)

  • 过程
    • canCommit 协调者询问是否可以提交。参与者写入undo/redo日志,并且投票反馈yes/no,该阶段相当于2PC的第一阶段。
    • preCommit 预提交。若所有参与者反馈yes后,协调者发送preCommit消息。参与者收到后反馈ack;若有参与者反馈no或者由于超时协调者未收到响应时,协调者会发送abort消息,参与者收到abort或超时未收到协调者消息时会执行回滚。该阶段相对于2PC为新增阶段,目的是为了消除参与者已经反馈投票并且等待协调者的commit/abort消息这一段不确定的时期:
      • 若参与者收到preCommit消息,则可以确定所有参与者都已投票确定提交,即使收不到协调者的commit消息,超时后参与者也可以自主提交
      • 若参与未收到preCommit消息,则放弃并且释放锁住的资源
    • doCommit 真正提交。参与者收到所有参与者ack后发送commit消息,参与者收到commit消息或者超时后执行提交。
  • 优点
    • 非阻塞:参与者也引入超时机制,doCommit阶段由于协调者宕机参与者未及时接受到请求时,仍会进行事务提交。
    • 直到所有参与者反馈preCommit消息的ack后协调者才会发送doCommit消息。如果协调者在发送preCommit消息之前失败,则参与者将一致同意操作被中止;若参与者收到了preCommit消息,也可以在很大程度上确认后续可以执行真正的提交(因为此时所有参与者必定全部投票反馈可以提交)。消除了任何参与者在所有参与者意识真正执行提交的决定前完成事务的可能性。
  • 缺点
    • doCommit阶段由于协调者和参与者所在网络出现了网络分区,参与者接受不到协调者的abort请求,仍然会进行提交,导致数据不一致,并且无法恢复
    • 需要至少三次网络往返,即至少3次RTT,对于完成事务是个比较长的延迟。

PAXOS

  • 角色
    • proposer
    • acceptor
    • learner
  • 阶段
    • prepare:proposer生成提案议编号m,向一个多数派acceptor广播prepare请求。acceptor将接收到的编号小于m的提案反馈给proposer,并承诺不会批准小于m的任何提案。
    • accept:若收到半数以上acceptor响应,则proposer向该多数派acceptor广播accept请求包含提议(m,v),v是多数派acceptor反馈的其批准的的最大编号的提案。
    • chosen:proposer接收到半数以上accetor反馈accept请求后,即选定了提案(m,v),从而可以继续执行commit。
  • 要求
    • 活性:值最终被选中
    • 安全性:只有一个值被选中
  • 推导
    • P1.一个Acceptor必须批准它收到的第一个提案
    • P2.如果(m,v)提案被选定了,所有编号比m高,且被选定的提案其值也是v
      • P2a.若(m,v)被选中,则所有的编号为n(n>m)且被Acceptor接受的提案具有值v
      • P2b. 若(m,v)被选中,则所有的proposer提出的编号为n(n>m)的提案具有值v
        由条件(m,v)被选中和编号在 m..(n-1) 之间的提案具有value值 v,可得:存在多数派集合C,C中的每个Acceptor已经通过了 m..(n-1) 之间的某些提案(至少通过m),并且这些提案的值为v
      • P2c. 对于任意的 n 和 v ,如果编号为 n 和value值为 v 的提案被提出,那么肯定存在一 个由半数以上的Acceptor组成的集合 S ,可以满足条件 a 或者 b 中的一个:
        S 中不存在任何的Acceptor通过过编号小于 n 的提案
        v 是 S 中所有Acceptor通过的编号小于 n 的具有最大编号的提案的value值
  • 强归纳法证明

首先假设提案[Mo,Vo]被选定了,设比该提案编号大的提案为[Mn,Vn],我们需要证明的就是在P2c的前提下,对于所有的[Mn,Vn],存在Vn=Vo。当Mn= Mo+1时,如果有这样一个编号为Mn的提案,首先我们知道[Mo,Vo]已经被选定了,那么就一定存在一个Acceptor的子集S,且S中的Acceptor已经批准了小于M的提案,于是,Vn只能是多.      数集S中编号小于M但为最大编号的那个提案的值。而此时因为Mn= Mo+1,因此理论上编号小于Mn但为最大编号的那个提案肯定是[Mo,Vo]同时由于S和通过[Mo,Vo]的Acceptor集合都是多数集,也就是说二者肯定有交集—这样Proposer在确定Vn取值的时候,就一定会选择Vo。

根据假设,编号在Mo+1到Mn-1区间内的所有提案的Value值为Vo,需要证明的是编号为Mn的提案的Value值也为Vo。根据P2c,首先同样一定存在一个Acceptor的子集S,且S中的Acceptor已经批准了小子Mn的提案,那么编号为Mn的提案的Value值只能是这个多数集S中编号小于Mn但为最大编号的那个提案的值。如果这个最大编号落在Mo+1到Mn-1区间内,那么Value值肯定是Vo,如果不落在Mo+1到Mn-1区间内,那么它的编号不可能比Mo再小了,肯定就是Mo,因为S也肯定会与批准[Mo,Vo]这个提案的Acceptor集合S有交集,而如果编号是Mo,那么它的Value值也是Vo,由此得证。

  • 优化
    • 选择主proposer解决活性问题
    • 选择主learner(若干)使通信简单化

ZAB

  • 角色
    • leader
    • follower
    • observer
  • 阶段
    • discovery:准leader与quorum通信发现其中的最大epoch,然后epoch+1,发送消息给这些follower,follower更新自己的处理过的的最大事务epoch,follower反馈历史事务集合和当前最大epoch。
    • synchronization:发现阶段获取的最大epoch和最新提议历史去同步quorum,若follower发现自己处理过的最大epoch不等于最大epoch则不执行事务操作,若过半follower正确反馈后,leader向follower发送commit请求broadcast:leader对外提供服务,简化版的二阶段提交,遵循过半原则,收到过半ack后,发送commit消息。
  • java实现
    • Fast Leader Election:选取半数以上同意的(zxid,sid)最大的
    • Recovery Phase:包括discovery和synchronization阶段
    • Broadcast Phase

FAQ

  1. zab 与 paxos的区别?
    • zab为分布式主备系统而设计、paxos为分布式一致性状态机系统而设计
    • 关于状态更新的协议(对于主备系统)需要比客户端请求(针对状态机复制系统)的协议更严格的顺序保证
    • zab leader/follower接受到proposal直接写入事务日志,等待过半follower反馈ack后发送commit消息;paxos master(即proposer)接收到大多数accept反
    • ack选定提案后才写入事务日志,并广播commit消息,acceptor接受commit后才写入事务日志
    • zab存在一个崩溃恢复阶段
  2.  zab为什么同步阶段只需同步quorum就够了?
    事务操作都是类似二阶段提交的过程,遵循多数派原则
  3. zab顺序性如何保证?
    客户端和zk服务器之间采用tcp长连接,利用其FIFO的特性,对于客户端请求先到先执行,leader和follower之间也采用TCP长连接,保证follower接收事务顺序性。
  4. paxos为什么无法保证顺序性?
    proposer提出的第一个提案prepare阶段完成还未被选定(没有commit),接着提出第二个提案覆盖了第一个提案的prepare,被选定进而广播commit消息给acceptor,后面proposer可能还再次提出未达成一致的第一个提案,及时被选中,也无法与提出提案的顺序相一致。要想保证顺序性proposer必须等上一个提议commit后才能发出,但是这样性能极低。
  5. ZK leader选举跟paxos算法什么关系?
    There is a very common misunderstanding that the leader election algorithm in zookeeper is paxos or fast paxos. The leader election algorithm is not paxos or fast paxos, please consider the following facts:
    There is no the concept of proposal number in the leader election in zookeeper. the proposal number is a key concept to paxos. Some one think the epoch is the proposal number, but different followers may produce proposal with the same epoch which is not allowed in paxos.
    Fast paxos requires at least 3t + 1 acceptors, where t is the number of servers which are allowed to fail [3]. This is conflict with the fact that a zookeeper cluster with 3 servers works well even if one server failed.
    The leader election algorithm must make sure P1. However paxos does provide such guarantee.
    In paxos, a leader is also required to achieve progress. There are some similarities between the leader in paxos and the leader in zookeeper. Even if more than one servers believe they are the leader, the consistency is preserved both in zookeeper and in paxos. this is very clearly discussed in [1] and [2].
  6.  zxid设计的作用
    • Fast Leader Election 比较zxid
    • learner与leader数据同步时会进行zxid对比
  7.  zab同步阶段部分follower由于一些原因未正常处理commit请求,如何保证同步结果?
    在leader对外提供服务之前会检查事务日志是否完成数据同步,即是否所有proposal已被过半机器提交

参考

https://en.wikipedia.org/wiki/Three-phase_commit_protocol
https://en.m.wikipedia.org/wiki/Three-phase_commit_protocol
https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.