Paxos算法详解

问题描述

Paxos算法的目的是解决分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成最终一致。当多个进程提出（Propose）不同的值，算法保证最终只有其中一个值被选定，即需要满足：

只有被提出（Propose）的值才可能被最终选定（Chosen）。
有且只有一个值会被最终选定（Chosen）。
进程只会获知到已经确认被选定（Chosen）的值。

三种角色

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner)。每个进程可能充当不止一种角色。

Paxos允许这三种角色在相互的通信中存在消息丢失、延迟、乱序以及重复的故障，但假设消息不会被篡改。它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。

两个阶段

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors对收到的Prepare请求进行Promise承诺。
第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
第三阶段：Learn阶段。Proposer在多数的Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

算法的推导

为了保证必须有值被接受，所以Paxos算法中：

P1：Acceptor必须接受（Accept）它所收到的第一个Proposal。

因为我们需要只有一个提案被提出的情况下，仍然能选出一个决议。但这样产生一个问题，如果多个Proposers同时提出Proposal，可能会导致没有任何一个提案被多数Acceptor批准。在P1的基础上，加上一个提案需要半数以上的Acceptor批准才能选定，因此需要Acceptor能够批准多个提案。

这里我们使用一个全局的编号来唯一标识每一个被Acceptor批准的提案（假设当前已经具备这样的外部组件能够生成全局唯一的，编号本文不详细讨论）。此时，提案变成了一个由编号和值组成的组合体。为了保证只有一个值会被最终选定，Paxos进一步提出：

P2：如果值为v的Proposal被选定（Chosen），则任何被选定（Chosen）的具有更高编号的Proposal值也一定为v。

P1和P2，就保证了有且只有一个值会被最终选定。但P2难以实现为具体的算法。我们提出p2的充分条件P2a：

P2a：如果值为v的Proposal被选定（Chosen），则任何被Acceptor批准的的具有更高编号的Proposal值也一定为v。

因为只有首先被批准才有可能被最终选定。但是P2a依然难以实现，因为acceptor很有可能并不知道之前已经被选定的提案的信息（该acceptor恰好不在接受它的多数派中），因此进一步提出P2a的充分条件P2b：

P2b：如果值为v的Proposal被选定（Chosen），则对所有的Proposer，它们提出的的任何具有更高编号的Proposal值也一定为v。

因为只有提案被提出才可能被批准。更进一步，提出充分条件P2c：

P2c：如果编号为n，值为v的提案被提出，必须存在一个由半数以上的Acceptor组成的集合S，满足以下条件中的任意一个：

S中没有任何Acceptor曾经批准过编号比n小的提案
S中的Acceptors所接受过的编号最大且小于n的提案的值也是v

我们再对P1进行延伸，提出p1的充分条件P1a：

P1a：一个Acceptor只要尚未响应过任何编号大于n的请求，它就可以接受这个编号为n的提案

自此可以引出如下的提案生成算法：

Proposer生成提案

1. Proposer选择一个新的编号n，向超过一半的Acceptors发送请求消息。Acceptor回复信息:

承诺不会批准编号比n小的proposal
如果它已经批准过编号比n小的提案，它会返回已经批准的编号最大且小于n的提案的值。

该请求称为Prepare请求。

2. 如果Proposer收到超过一半Acceptors的回复，它就可以提出编号n，值为v的提案。其中v是收到的回复中编号最大的提案的值，如果没有这样的值 (半数以上的Acceptor都没有批准过任何提案)，则可以自由提出任何值。然后，向超过一半的Acceptors发出请求（和前一阶段的Acceptors集合不要求相同，两个集合因为都超过一半，必定存在至少一个公共的Acceptor），请求对方接受提出的提案

该请求称为Accept请求。

Acceptor批准提案

1. 当收到Prepare请求时，如果其编号n大于之前所收到的Prepare消息，则回复。

因为，若一个Acceptor收到一个编号为n的请求，但该Acceptor已经对编号大于n的Prepare请求做出了响应，它肯定不会批准编号为n的提案，因此Acceptor没有必要对这个Prepare请求做出响应

2. 当收到Accept请求时，仅当它没有回复过一个具有更大编号的提案，批准该提案并回复。

算法陈述

阶段一：

Proposer选择一个提案编号n，向Acceptor的某个超过半数的子集成员发送编号为n的Prepare请求
如果一个Acceptor收到一个编号为n的Prepare请求，且编号n大于该Acceptor已经响应的所有Prepare请求的编号，那么它会将它已经批准过的最大编号的提案（如果有）的值作为响应反馈给Proposer，同时Acceptor会承诺不会再批准任何编号小于n的提案

阶段二：

如果Proposer收到来自半数以上的Acceptor对于其发出的编号为n的Prepare请求的响应，那么它就会发送一个针对提案（编号n，值v）的Accept请求给Acceptor。注：其中v是收到的回复中编号最大的提案的值，如果没有这样的值 (半数以上的Acceptor都没有批准过任何提案)，则可以自由提出任何值。
如果Acceptor收到这个编号n，值v的Accept请求，只要该Acceptor尚未对编号大于n的Prepare请求做出响应，它就会通过这个提案。

提案的获取

如果一个提案已经被半数以上的Acceptor批准，代表这个提案已经被选定。Leaner获取提案获取这个被选定的提案有如下几种方式：

一旦Acceptor批准了一个提案，就将提案发送过所有的Learner。缺点是每个Acceptor需要与所有的Leaner进行通信，通信次数为二者的乘积。

所有Acceptor将它们对提案的批准情况发送给一个主Learner。当主Learner被通知一个提案已经被选定时，它会负责通知其他的Learner。缺点是主Learner带来单点故障问题。

将方法2的主Learner扩大为一个特定的Learner集合。

一些例子

paxos1.jpg

图中P代表Prepare阶段，A代表Accept阶段。3.1代表从server s1发出的编号为3的proposal。X和Y代表proposal值。
例1中P 4.5的Prepare阶段前，P 3.1已达成多数派，其值X被Accept，然后P 4.5学习到值X。X被最终选定

paxos2.jpg

例2中在P 4.5的Prepare阶段前，P 3.1与s3的accept阶段率先完成，与s1和s2 accept阶段有一定延迟。但P 4.5将学习到X，并将自己的值由Y替换为X。X被最终选定。

paxos3.jpg

例3中在P 4.5的Prepare阶段前，P 3.1与s2和s3的accept阶段尚未完成。当P 4.5提出Prepare请求，s3由于未批准任何提案，将不会返回任何提案值，并承诺不会再批准任何编号小于4的提案。接着，s3收到P 3.1 Accept请求，这个提案不会得到批准。P 4.5的提案在得到s3, s4和s5批准后，Y被最终选定。

paxos4.jpg

例4中两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。
一个解决活锁的方法是Multi-Paxos算法。

下一节：Multi-paxos算法