Paxos 算法理解

背景

Paxos 发音是[皮克索斯或帕克索斯]
是由莱斯利·兰伯特（Leslie Lamport)，1990年提出的一种基于消息传递的一致性算法。
Leslie Lamport，1941年生，新晋图灵奖得主，一个在计算机领域拥有辉煌成就的大师，他关于时间时钟、面包店算法、拜占庭将军等问题的思考令人乍舌。亲近他的人还会告诉你，他是个年愈古稀仍爱穿旱冰鞋上下班的幽默老头。全球无数人受益于他的成就，却很少听说他的名字。
Lamport.png

1）概要

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。 基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改即拜占庭将军问题。
Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中，如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。
一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。另一个场景是集群中选举Leader。

角色：
Proposer ：提议者
Acceptor：决策者
Client：产生议题者
Learner：最终决策学习者
上面4种角色中，提议者和决策者是很重要的，其他的2个角色在整个算法中应该算做打酱油的，Proposer就像Client的使者，由Proposer使者拿着Client的议题去向Acceptor提议，让Acceptor来决策。这里上面出现了个新名词：最终决策

动作：
promise：Acceptor对proposer承诺，如果没有更大编号的proposal会accept它提交的proposal
accept：Acceptor没有发现有比之前的proposal更大编号的proposal，就批准了该proposal
chosen：当Acceptor的多数派都accept一个proposal时，该proposal就被最终选择，也称为决议

论文结构：
先提出P1的基本需求
对整个结果提出要求（P2）
对Acceptor提出要求（P2a）
对Proposer提出要求（P2b）
对Acceptor与Proposer同时提出要求（P2c）

2）问题描述

假设有一组可以提出提案的进程集合。一个一致性算法需要保证：在这些被提出的提案中，只有一个会被选定；如果，没有提案被提出，那么就不会有被选定的提案；当一个提案被选定后，进程应该可以获取被选定的提案信息。
对于一致性来说，安全性(safety)需求就是这样的：
a.只有被提出的提案才能被选定。
b.只能有一个值被选定(chosen)，同时
c.如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。
• Only a value that has been proposed may be chosen,
• Only a single value is chosen, and
• A process never learns that a value has been chosen unless it actually has been.
整体上来说，目标就是要保证最终有一个提案会被选定，当提案被选定后，进程最终也能获取到被选定的提案。
{!一个分布式算法，有两个最重要的属性：safety 和livness，简单来说safety就是指那些需要保证永远都不会发生的事情，livness是指那些最终一定会发生的事情}。有三种参与角色，我们用Proposers，Acceptors和Learners来表示。在具体的实现中，一个进程可能充当不止一种角色。每个参与者以任意的速度执行，可能会出错而停止，也可能会重启。当一个提案被选定后，所有的参与者都有可能失败或重启，因此除非那些失败或重启的参与者可以记录某些信息，否则是不可能存在一个解的。}
消息在传输中可能花费任意的时间，可能会重复，丢失，但是不会被损坏{!即其内容不会被篡改}。

3）提案选定

选定提案的最简单方式就是只允许一个Accpetor存在，Proposer发送提案给Accpetor，Acceptor会选择它接收到的第一个提案作为被选定的提案。但是显而易见存在单点问题。
用多个Accpetor来避免一个Accpetor时的单点问题。现在，Proposer向一个Acceptor集合发送提案，某个Acceptor可能会通过(Accept)这个提案。当有足够多的Acceptor通过(accept)它的时候，我们就可以认为这个提案被选定了。什么是足够多呢？为了确保只有一个提案被选定，我们可以让这个集合包含Acceptor集合中的多数成员。因为任何两个多数集至少有一个公共成员，如果我们再规定一个Acceptor最多只能通过一个提案，那么就能保证只有一个提案被选定。
---至此，就确定了要用多数派来决定提案选定

在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案来，这就暗示了如下这个需求：
P1.一个Acceptor必须通过第一个他收到的提案。
这个需求产生的问题是：不能选定一个提案。 因为不能形成多数派。比如奇数个接收者中，某个接收者n挂了，导致两个提案的接收者数量相同。或者奇数个通过者都同时收到了提案者的提议。
p1.png

P1 and the requirement that a value is chosen only when it is accepted by a majority of acceptors imply that an acceptor must be allowed to accept more than one proposal.
【P1再加上一个提案被选定需要由半数以上的Acceptor通过】的需求，暗示着一个Acceptor必须能够通过(accept)不止一个提案。为每个提案设定一个编号来记录一个Acceptor通过的那些提案。为了避免混淆，需要保证不同的提案具有不同的编号。如何实现这种保证取决于实现，假设已经提供了这种保证。当一个具有某value值的提案被半数以上的Acceptor通过后，我们就认为该value被选定了。即认为该提案被选定了。
{!此时的提案已经跟value变成了不同的东西，提案是由编号+value组成的}
We can allow multiple proposals to be chosen, but we must guarantee that all chosen proposals have the same value.By induction on the proposal number, it suffices to guarantee:
P2. If a proposal with value v is chosen, then every higher-numbered proposalthat is chosen has value v.
P2.如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被选定的提案的value值也必须是v。
因为编号是全序的，条件P2就保证了只有一个value值被选定的这一关键安全性属性。
被选定的提案，首先必须被至少一个acceptor通过，因此我们可以通过满足如下条件来满足P2：
P2a.If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.
P2a.如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被acceptor通过的提案的value值也必须是v。
我们仍然需要P1来保证提案会被选定。但是因为通信是异步的，一个提案可能会在某个Acceptor c还未收到任何提案时就被选定了。假设一个新的proposer苏醒了，然后产生了一个具有另一个value值的更高编号的提案，根据P1，就需要c通过这个提案，但是这与P2a矛盾。
p2.png

因此如果要同时满足P1和P2a，需要对P2a进行强化：
P2b.If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.
P2b.如果具有value值v的提案被选定，那么所有比它编号更高的被proposer提出的提案的value值也必须是v。
一个提案被acceptor通过之前肯定要由某个proposer提出，因此P2b就隐含了P2a，进而隐含了P2为了发现如何保证P2b，我们来看看如何证明它成立。我们假设某个具有编号m和value值v的提案被选定了，需要证明具有编号n(n>m)的提案都具有value值v。我们可以通过对n使用归纳法来简化证明，这样我们就可以在额外的假设下—即编号在m…(n-1)之间的提案具有value值v，来证明编号为n的提案具有value值v。因为编号为m的提案已经被选定了，这意味着肯定存在一个由半数以上的acceptor组成的集合C，C中的每个acceptor都通过了这个提案。再结合归纳假设，m被选定意味着：
C中的每个acceptor都通过了一个编号在m…n-1之间的提案，每个编号在m…n-1之间的被acceptor通过的提案都具有value值v。
因为任何包含半数以上的acceptor的集合S都至少包含C中的一个成员，我们可以通过维护如下不变性就可以保证编号为n的提案具有value v：
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.
P2c.对于任意的n和v，如果编号为n和value值为v的提案被提出，那么肯定存在一个由半数以上的acceptor组成的集合S，可以满足条件a)或者b)中的一个：
a)S中不存在任何的acceptor通过过编号小于n的提案
b)v是S中所有acceptor通过的编号小于n的具有最大编号的提案的value值
通过维护P2c我们就可以保证P2b了。
{可以看到上面是对一系列条件的逐步加强，如果需要证明它们可以保证一致性，则需要反过来，P2c->P2b->P2a->P2 + p1 =>保证了一致性。
我们再看P2c，实际上P2c规定了每个Proposer 如何产生一个提案，对于产生的每个提案(n,v)需要满足这个条件:
“存在一个由超过半数的Acceptor 组成的集合S：要么S中没有人批准(accept)过编号小于 n 的任何提案，要么S的任何acceptor批准的所有议案（编号小于n）中，v是编号最大的议案的决议”。
当Proposer遵守这个规则产生提案时，就可以保证满足P2b。
论文中，作者是从如何产生提案进而可以保证P2b来思考，才得到P2c的。下面我们反过来看，证明P2c可以保证P2b。如论文中一样，采用数学归纳法证明。
首先假设提案(m,v)被选定了，设比该提案编号大的提案为(n,v’),我们需要证明的就是在P2c的前提下，对于所有的(n,v’)，有v’=v。
(1)n=m+1时，如果有这样编号的提案，首先我们知道(m,v)被选定了，这样就不可能存在一个S且S中没有人批准过小于n的提案[S与批准(m,v)的Acceptor集合肯定有交集]，那v’只能是多数集S中编号小于n的最大编号的那个提案的值了，此时n=m+1，理论上小于n的最大的编号肯定是m，同时由于S和通过(m,v)的acceptor集合都是多数集，就保证了二者肯定有交集，这样Proposer在确定v’取值时，肯定选到就是v。
上面实际上就是数学归纳法的第一步，确切的说是使用的是第二数学归纳法。上面是第一步，验证了某个初始值成立。下面，需要假设编号在[m+1,k-1]区间内成立，并在此基础上推出n=k上也成立。
(2)根据假设编号在[m+1,k-1]区间内的所有提案都具有值v，需要证明的是编号为k的提案也具有值v。根据P2c，首先同样的不可能存在一个S且S中没有人批准过小于n的提案，那么编号为k的value值，只能是一个多数集S中编号小于n的最大编号的那个提案的值，如果这个最大编号落在[m+1,k-1]区间内的，那么值肯定是v，如果不是落在[m+1,k-1]区间，那么它的编号肯定就是m了，不可能比m再小了，因为S也肯定会与批准(m,v)的Acceptor集合肯定有交集，那么它的编号值就不会比m小，而编号如果是m那么它的值也是v。由此得证。
p3.png
}

4）这就导致了如下的提案生成算法：

  1. proposer选择一个新的提案编号n，然后向某个acceptors集合的成员发送请求，要求acceptor做出如下回应：
    (a).保证不再通过任何编号小于n的提案
    (b).当前它已经通过的编号小于n的最大编号的提案，如果存在的话
    我们把这样的一个请求称为编号为n的prepare请求。
  2. 如果proposer收到了来自半数以上的acceptor的响应结果，那么它就可以产生编号为n，value值为v的提案，这里v是所有响应中编号最大的提案的value值，如果响应中不包含任何的提案那么这个值就可以由proposer任意选择。
    Proposer通过向某个acceptors集合发送需要被通过的提案请求来产生一个提案(此时的acceptors集合不一定是响应prepare阶段请求的那个acceptors集合)。我们称此请求为accept请求。
    p4.png

消息流图解

paxos-6.png

这4类消息对应于paxos算法的两个阶段4个过程： 

phase 1
    a) proposer向网络内超过半数的acceptor发送prepare消息
    b) acceptor正常情况下回复promise消息
phase 2
    a) 在有足够多acceptor回复promise消息时，proposer发送accept消息
    b) 正常情况下acceptor回复accepted消息

个人理解

从论文结构从P1->P2->P2a->P2b->P2c这个推演过程是比较清晰的，作者从正面解释了推演过程。其中P2c是形成算法的核心。
P2c可以这样理解，在一个可能发生各种异常的集群中，提议者先询问它能感知的一个多数派接受者的批准的值，然后它与这个多数派的V值统一后，再提议。这样多过几轮后，整个集群的V值在收敛，而S集合在接近整个集群的真值S‘，这样最终一定能形成决议。

P1.一个Acceptor必须通过第一个他收到的提案。 P2.如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被选定的提案的value值也必须是v。 P2a.如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被acceptor通过的提案的value值也必须是v。 P2b.如果具有value值v的提案被选定，那么所有比它编号更高的被proposer提出的提案的value值也必须是v。 P2c.对于任意的n和v，如果编号为n和value值为v的提案被提出，那么肯定存在一个由半数以上的acceptor组成的集合S，可以满足条件a)或者b)中的一个： a)S中不存在任何的acceptor通过过编号小于n的提案 b)v是S中所有acceptor通过的编号小于n的具有最大编号的提案的value值