Paxos

Paxos算法

一致性算法背景

分布式环境中最突出的特点就是其不可靠性，如何在这种环境中解决多个节点并发操作数据并需要保证在读写过程中数据的一致性问题，是一致性算法被提出的初衷。Paxos算法是Lamport提出的一种基于消息传递的分布式强一致性算法，它的目的在于解决分布式环境下一致性的问题。

Mulit-Master多监督节点方式是保证分布式系统可用性(Availability)的一种策略，避免单点故障问题，但是也带来了一致性(Consistency)的问题。保证多节点并发访问分布式数据一致性主要有两种方式，分别是复制与同步和多数派。

复制与同步有三种情况，包括主从异步复制、主从同步复制和主从半同步复制如下表所示：

多数派读/写的基本思想是每次写入操作保证写入大于等于N/2+1个节点，节点之间平等；每次读取保证读写节点个数大于N，从大于等于2N+1个节点读取，容忍最多(N-1)/2个节点损坏。法定集合从理论层面说明了多数派的思想，其定义为将一个超过半数的集合称之为法定集合，比如数字1、2、3、4、5，共5个元素，{1,2,3}有三个元素就是法定集合。法定集合的性质：任意两个法定集合，必定存在一个公共的成员。法定集合的概念有利于加深对Paxos算法的理解，Paxos算法通过多个监督者来增强可靠性，其基本思想是通过监督者们的投票来表决数据的状态变化，并保证所有对数据的访问都遵从这种表决。

Paxos算法

Paxos算法背景

Paxos算法是二段提交原则(2PC)，每个Proposer在发送自己的提案之前，先检查有没有已经提议且被批准的值，如果有则放弃自己的提案，这样最终只有一个值被批准。这就可能存在检查到多个值被批准的情况，例如并发环境中两个申请者(Proposer) P1和P2，P1想提议将实例value的值设置为red，P2想提议将value设置为blue，共有5个决策者(Acceptor) A1~A5。接着，P1在发送提案前，检查后发现自己没有值被批准，因此提议red。同时，在所有Acceptor批准之前，P2也进行提议，它也检查出自己没有值被批准，所以P2也把自己的blue作为提案发送给Acceptor。然后，P2的提案优先到达A1、A2和A3，这些Acceptor先批准了blue ，已经达到多数，所以blue被批准。但是随后A3、A4、A5接收到了red，也予以批准。这就出现了多个值被批准的不一致情况。

考虑上述问题的一种解决方式是，一旦Acceptor批准了某个值，其他有冲突的值都应该被拒绝，即A3对随后到达的red应拒绝。Acceptor采用高优先级优先的策略进行选择与拒绝，使用Proposal唯一ID的方式对Proposal进行优先级排序，Acceptor批准优先级高的值，拒绝低优先级的Proposal 。这样，在Proposer发送Proposal之前，就需要生成一个唯一ID，而且需要比之前已经使用的或生成的都要大。

上述背景就是Paxos算法解决分布式一致性问题的基本思想，即通过二段提交和高优先级选择策略解决分布式系统中的各个进程如何就某个值或提案(Proposal)达成一致的问题。为此，Paxos算法有两个约束条件，(a) 每个Acceptor必须接受他收到的第一个提案；(b) 在一个多数派中，当所有Acceptor都没有批准过编号小于N的任何提案，或者它们批准的提案中编号小于N的最大编号的提案值是C时，Proposer才能提出一个一个编号为N值为C的提案。以此为基础，Paxos算法可以保证在任意时刻，就算存在多个Proposer在询问之后提出了不同值的提案，最终只有其中一个Proposer的提案值会被法定集合接受者接受，即只有一个值会被决定；另外，被决定值会进行传播，即当value的值被决定后，假设被决定为C，之后任意的proposer提出的提案值也是C。

Paxos算法流程

Paxos将一次Paxos算法执行称为一个实例Instance，将有Proposer发起但是没有获得批准的议案称为提案Proposal，将最终被批准通过的议案中的值称为决议Value。另外，Paxos将系统中的角色分为三类，分别是提议者Proposer，决策者Acceptor，和最终决策学习者Learner：

• Proposer：提出提案 (Proposal) ，其中包括提案编号 (Proposal ID) 和提议的值 (Value)

• Acceptor：参与决策，审批Proposers的提案，收到Proposal后对其进行选择，若Proposal获得多数Acceptors的接受，则称该Proposal被批准

• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案和被批准的值(Value) ，在一个Paxos算法实例中，只会批准一个Value

Paxos算法主要分为两个阶段，第一阶段：Prepare阶段，Acceptors接收请求、产生判断、并向对应的Proposer返回承诺，Proposer依据返回的承诺决定是否继续更新数据而进入下一阶段的请求。第二阶段：Accept阶段，Acceptors接受更新请求并完成多副本更新。具体算法流程如下图所示：

Prepare 阶段 Proposer生成一个全局唯一且递增的提案编号N，并将 Prepare 请求发送给Acceptors中的一个多数派；Acceptor收到 Prepare 消息后，如果提案编号小于它已经回复的编号，则拒绝该Prepare消息；如果提案的编号大于它已经回复的所有Prepare消息，则Acceptor将自己上次接受的提案回复给Proposer，并做出两个承诺 (Promise)，一个应答 (Response) ：承诺不再接受提案编号小于等于 N 的Prepare请求，承诺不再接受小于 N 的Propose请求，应答已经接受过的提案中ID编号最大提案的Value和Proposal ID，没有则返回空值。这一阶段有两个目的，一是Proposer检查询问自己是否有被批准的值，如果有就改用被批准的值；Acceptor如果有在此之前的提案没有被批准，则根据提案编号阻塞掉他们，从而不让它们与其自身发生竞争。

Accept阶段当一个Proposer收到了多数Acceptors对Prepare请求的回复后，就进入Accept批准阶段。它要向回复Prepare请求的Acceptors发送Accept请求，包括编号N和根据Prepare阶段决定的Value，Proposer也会收到其他Accept上一阶段给出的承诺。在不违背自己向其他 Proposer的承诺的前提下，Acceptor收到 Accept 请求后即接受并持久化当前Proposal ID和提案Value。如果Acceptor收到一个编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。如果N小于Acceptor已经响应的prepare请求，则拒绝，不回应或回复Error。当Proposer没有收到多数Acceptors的回应，就会递增提案ID重新进入Prepare阶段，并重新提出prepare请求。

最后 Proposer 收到多数Acceptors的Accept之后，决议形成，将形成的决议发送给所有Learners。

从系统角色的角度理解上述Paxos算法流程

Proposer在询问和预提案阶段都是向法定集合进程发送消息并获取回复，收到询问和预提案回复后再进行选值，所以，可以把询问和预提议阶段合并，预提案附带询问功能，即为Prepare阶段。对应的Acceptor在处理询问时，要在根据规则接受预提案后，将询问结果和预提案接受结构在一个消息中回复给Proposer，称这个消息为诺言，诺言中包含了Acceptor记录的value值。可以看出无论是提案还是预提案，Acceptor只接受提案ID编号比它自身记录的ID编号更大的消息。

Paxos算法分析

总体说来，Paxos算法就是通过两个阶段确定一个决议，Prepare阶段：通过询问和回复确定谁的编号最高，只有编号最高者才有权利提交Proposal，会阻塞低编号的预提案；Accept姐u但：编号最高者提交Proposal，如果没有其他节点提出更高编号的Proposal，则该提案会被顺利通过；否则，整个过程就会重来。

Paxos算法中决议的传播

区别于一般选举逻辑，Paxos算法中每个Proposer不是执着于让自己的提议通过，而是要让提议尽快达成一致意见。例如，存在两个提议者PA和PB，如果PA在询问时发现某个Acceptor已经接受过先于其进行询问的PB的提议，即PA询问得到的是Acceptor对PB的诺言，这时PA会把自己的提议改为PB的提议。

基于上述示例可能存在一种情况是，PA收到了其发出提议的法定集合中多个Acceptor的返回意见，且这些返回意见中存在多个接受者对于其他提议者的诺言。这时，PA需要处理接受与拒绝的问题，要在它们之间做出选择，当PA收到接受者的诺言是，一般接受者会告知已承诺的提案和该被接受提案的ID编号两项信息，PA基于此选择ID编号较大的诺言作为自己的提案。

Paxos算法中的Proposal编号

整个Paxos算法基本上就是围绕着Proposal编号在进行，Proposer要不断选择更大的编号提交Proposal；Acceptor需要不断比较收到的Proposal编号是否最大，当编号确定了，就可以确定所对应的Value值。

所以Proposal编号对Paxos算法至关重要，但是在分布式环境中，编号的产生就是一个棘手的问题，当多个Proposer并发地进行提案提交，怎么保证编号的唯一性在分布式环境中是一个比较复杂的问题。Chubby提出了一种Paxos提案ID编号的生成算法，假设N个Proposer的节点编号为 ir 取值大于等于0小于N，则Proposal的ID编号 S 的取值应该大于该Proposer已知的最大值，并且满足公式\(S \ $\% N = ir\)，其中Proposer已知的最大值来自Proposer对编号自增后的值和接收到Acceptor的拒绝后所得到的值两部分。

Paxos算法的活锁问题

Proposal编号除了在产生过程中存在问题，在其更新过程中也有需要解决的冲突。当某Proposer提交的Proposal被拒绝时，可能存在因为Acceptor承诺返回了更大编号的Proposal，该Proposer提高Proposal编号继续提交的情况。一旦出现这种情况，两个Proposer都发现自己的编号过低转而提出更高编号的Proposal，显而易见。这会导致死循环，该现象被称为活锁。用一句通俗的话来描述活锁现象：你编号高，我再比你更高，反复如此，算法永远无法结束。

Paxos算法中给出的解决活锁的办法是选举出一个Proposer作Leader，所有的Proposal都通过Leader来提交，当Leader宕机时马上再选举其他的Leader。通过Leader选举相当于把一个分布式问题转化为一个单点问题，而单点的正确性和健壮性由选举机制保证。Leader通过控制提交的进度来解决活锁现象：如果之前的Proposal还没有结果，之后的Proposal就稍微等待，而不是急于提高编号再次提交。

 

Reference

Paxos Made Simple

Paxos算法详解