Paxos协议理解

Paxos协议要点

  • Paxos协议*有三种角色:Proposer、Acceptor、Learner,具体实现中一个进程可担当多个角色。

  • Paxos协议的目的:针对同一主题,每个Proposer都可提出若干提案,所有的Acceptor和Learner必须从这些提案中一致选定某个提案。

  • 某个提案被选定成功的定义:此提案被超过半数Acceptor 批准

  • Paxos的第一个Prepare阶段的目的是确定Proposer如何生成提案。这实际上涉及到Paxos协议的推导,可参考《从Paxos到Zookeeper 分布式一致性原理与实践》。即Prepare阶段是提案生成阶段

    提案生成算法如下,此算法保证了如果某个提案[M0, V0]被选定后,之后Proposer提出的任何编号大于M0的提案,其值一定是V0。
    Paxos协议理解

  • Paxos的第二个Accept阶段的目的是将生成的提案发送给所有Acceptor批准,如果超过半数Acceptor都批准了,则此提案被选定成功。即Accept阶段是提案选定阶段

  • 一个提案已经被超过半数Acceptor批准,但是Proposer可能并不知道提案已经被选定成功,因为Accept阶段,大多数Acceptor返回的响应可能在网络中丢失。但是所幸的是Prepare阶段的提案生成算法保证了Proposer新的提案的值一定为已经选定的提案的值。

  • Acceptor对于Prepare和Accept请求的响应原则:Acceptor可以成功响应编号大于当前Acceptor记录过最大编号的提案请求(Prepare和Accept请求)。响应过程可参考以下流程图。

Paxos算法陈述

Paxos协议理解
Paxos协议理解

Paxos算法流程图

  • K为提案编号
  • MaxN为Acceptor所记录的最大提案编号
  • AcceptN为Acceptor所批准的提案编号
  • AcceptV为Acceptor所批准的提案的值。
    Paxos协议理解

Paxos协议缺陷

多个Proposer竞相提案,陷入死循环:
Paxos协议理解
解决方法:选举主Proposer,只有主Proposer才能进行提案,即Multi-Paxos、Raft等协议。

上一篇:paxos算法及加锁的思考


下一篇:一致性协议(2PC,3PC,Paxos,Raft, ZAB)