Paxos的推演和直观理解

Paxos在分布式系统中的重要性无需多言。我们能在网络上找到非常多解析Paxos原理的文章,这些文章大部分只讲协议的过程,有些深入的文章还会讲协议的证明,我总感觉缺少对Paxos协议“生动直观”的理解。最终我认为最直观解释Paxos的文章是作者Lamport在2001年发表的《Paxos Made Simple》。作者写这篇文档的目的是因为1998年发表的paxos原文《The part-time parliament》被很多人吐槽晦涩难懂。在《Paxos Made Simple》文中作者对Paxos协议做了一次从简单场景到完整协议的推演。我写这篇文章没有什么新奇的地方,仅仅写我对《Paxos Made Simple》的推演过程的消化理解。

Paxos协议要解决的问题:

在一个不可靠的分布式环境中,各个实体达成一个一致的状态。

如果系统中只有一个proposal,那么这个proposal的提议在大多数acceptor存活时,必须要被接受。因此

P1.  An acceptor must accept the first proposal that it receives.

如果有多个proposal,每个acceptor只接受第一个proposal而拒绝后续所有的proposal的话。那么就可能会导致每个proposal都不能被大多数acceptor接受,导致协议无法收敛。因此:

每个acceptor接受的proposal不止一个,当然,只有被大多数acceptor接收的proposal才会被chosen

因此,我们允许多个proposal被选中,但是必须保证:这些被选中的proposal都有同样的value。也就是说:

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

如何来保证只要一个value为v的proposal被chosen,后续的proposal的值都为v呢?

P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

简单啊,只要保证后面的被acceptor的proposal的值都为v就好了。那么如何保证后面的被accept的prososal都是v呢?

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

简单啊,只要后面proposer发出的proposal都为v就好了。(这不废话吗)

那么,如何保证一旦一个proposal被chosen,后续的proposal都跟之前的proposal有相同的value呢?

P2c. For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

意思是我们要把好proposal的出口这一关,就是说proposal不能瞎jb提,这样才能保证“达成一致”的这个过程最快速的收敛。P2c翻译一下的意思就是:对于任何一个proposal(n,v)(n是提案编号,v是提案值),如果要提出这个proposal,必须要满足一下的两个条件之一:

1. 大多数的acceptor都没有accept小于n的proposal; 或者

2. 大多数的acceptor accept的提案都小于n,这其中序号最大的一个提案的值就是v

怎么理解这两个条件呢?直观一点讲就是,如果你想提案,要么1)大多数acceptor没有接受过任何提案;要么2)你的提案跟之前最大编号的提案一样。

好,其实paxos本质上就是通过约束每个proposer要提出的proposal来达到快速达成一致的目的(收敛)。

那么如何来约束proposor提出的proposal呢?根据之前提出了两个条件,因此proposer在提出proposal之前,必须先“学习”,学习当前(大多数acceptor)最大提案的值。这个学习的过程叫做"Prepare":

Prepare阶段

一个Proposer要想提案,它首先得知道当前要么大部分acceptor没有接受过任何提案,要么找到一个在大部分acceptor组成的集合中最大的提案值。因此Proposer首先获取一个新的提案编号,然后使用这个编号N向大部分acceptor发送prepare请求。这些acceptor给proposer响应

1)要么大多数acceptor从来没有接受过任何提案

2)要么有部分acceptor告诉proposer当前最大的提案编号和提案值

    2.1 有部分Acceptor的接受的最新的提案大于等于N,不可能。因为Acceptor只返回小于N的最大编号和提案值。一个acceptor不会响应一个小于它当前提案编号的proposal。

    2.2 所有的提案编号都小于N。

3)有返回的acceptor没有达到大多数(proposal无法继续)

我们再看Acceptor在Prepare阶段的逻辑:

1)如果Acceptor没有承诺/接受过任何提案,那么向Proposal直接返回承诺,也就是后续不会接收小于N的proposal

2)如果Acceptor 承诺过一个小于N的提案,那么Aceeptor可以直接向Proposal再次承诺N,也就是之前的小于N的Proposal将永远不会被自己Accept

3)如果Acceptor接受过一个小于N的提案,那么返回这个提案编号和提案值

4)如果Acceptor承诺过一个大于N的提案,那么忽略当前为N的提案(承诺也没用,因为就算承诺了N,也不可能接受N)

5)如果Acceptor接受过一个大于N的提案,那么忽略当前为N的提案

一旦Acceptor给出了Prepare阶段的响应,意味着这个Acceptor将不会接受小于N的提案。什么意思呢?只要一个Proposal通过了Prepare阶段,也就意味着任何一个小于N的Proposal如果还没有Prepare,他将不能通过Prepare阶段,如果通过了Prepare,它也不会被大多数acceptor接受。相当于对整个acceptor集群做了一个锁定操作,即锁定不会有一个小于N的proposal被chosen。

但是也会出现这个问题,当为N的proposal在通过prepare阶段之后但是还没有还没有发送acceptor请求之前,另一个proposer发起了一个编号为N+1的proposal,这个时候N+1也可以通过Prepare阶段,接着另一个Proposor可能再发起一个N+2的proposal,这样整个协议过程将无法收敛。

Accept阶段

Proposer在Acceptor阶段的逻辑:当第一阶段学习(Prepare)完成后,Proposal收到了大部分Acceptor的响应。

1. 如果有一个最大的Proposal被接受,也就以为着当前没有任何一个大于N的proposal被chosen。那么Proposer将会用自己选用的Proposal编号和学习到的当前最大Proposal的值作为新提案发起Accept请求。 (是否意味着有可能已经有小于N的proposal被chosen?有可能。是否意味着有可能有多个小于N的proposal被chosen?有可能。但是没关系,因为这些已经被chosen的提案值和当前将要发出的提案值都一样)。

2. 如果大部分的Acceptor没有接受过任何Proposal,那么Proposer可以自己指定任何提案值发起Accept请求。

Acceptor在Accept阶段的逻辑:

P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

也就是,如果Acceptor没有承诺过大于N的proposal,那它就可以accept N。(如果他Accept过小于N的proposal呢?)。一个Acceptor需要记住两样东西:

1. 已经承诺过的最大提案编号,用来忽略大于此编号的prepare和accept请求

2. 已经接受过的最大提案编号和提案值,用来约束后续的提案值(通过后续提案的prepare请求)

到此为止,这个协议的逻辑算讲完了。

推荐阅读更多精彩内容