Paxos小议
问题
最近我们在做一个项目的时候有这样一个需求：我们有多台服务器资源，希望彼此协作完成一项工作。这项工作可以被划分为N个小的模块，但由于这项工作会依赖于持续不断的输入(在线业务)，因此我们无法使用人工指定的方式将此工作分发到不同服务器进行。目前我们想到一个方法，将这项工作划分出的小模块放到一个稳定可靠的地方，例如mola存储系统，然后每台服务器去存储系统上取得一定数量的模块进行工作，完成后再将处理的结果输出到前述的存储系统上。这些小的模块虽然可以被不同的服务器运行，然后重复运行却是不可接受的(例如我们的计费日志，重复计费是绝对不允许的)。因此，当任意一台机器取得一些模块并准备运行时，一定要通知到其他所有机器：这些模块已经由我运行，确认其他所有机器不会挑选到重复的模块。这个问题难住了我们，究竟应当如何使一个分布式系统(例如我们的服务器资源)有效快速的达成一致？[1]
Paxos是什么[2]
Paxos也许是分布式系统中最有名的一致性协议了。Chubby论文[3]中提到：目前已有的所有一致性协议的精髓其实只有一个，那就是paxos。而paxos本身的发表过程也被传为经典：Lamport于1990年提出此算法，并以一个虚构的希腊城邦paxos为例对此算法进行了详细的介绍与分析；然而算法本身过于复杂，几个编辑建议Lamport将其论文更改为数学语言重新进行描述。大牛Lamport认为他们没有幽默感，拒绝更改。直到1998年，paxos算法才被发表在ACM Transactions on Computer Systems。2001年，Lamport觉得同行无法接受他的幽默感，于是改用平实的方式重新发表了论文，即 Paxos made simple。后来，google的chubby系统使用了Paxos作为其一致性协议，从此 Paxos协议终于得登大雅之堂
Paxos的完整过程
Paxos本身的推导过程十分复杂，要跟上作者的思维实属不易，对其推导及原因感兴趣的读者可以仔细研究下Paxos相关的几篇论文，在此不作翻译了J。我会直接告诉大家Paxos的做法，以及这种做法如何能保证一致性的证明。请注意我描述的是basic paxos，对于优化的考虑并不在此进行
Paxos将系统角色分为三类：Proposer，Acceptor，Learner[4]。其中Proposer即前文问题中取得模块并希望运行的机器，它提出：第N个模块希望由我取得并运行；Acceptor角色即所有的服务器，它们会对Porposer提出的方案进行裁决，以确认是否同意Porposer的请求，并视情况对Proposer进行回复，Acceptor的一次回复被称为一次投票；Learner可以是任意希望获取模块处理情况的机器，它通过向Acceptor发送学习请求而获知所有模块的分配情况(当然，当Acceptor同意Porposer请求的时候也可以主动的通知Learner，这两种方式的区别并不是本文的重点)。很明显，我们的服务器实际上至少同时兼任了两个角色：Proposer及Acceptor，在需要知道当前分配情况的时候还需要扮演Learner。
另外，Paxos还引入议案的概念，议案内容为<序列号，方案>。序列号是Porposer自行产生的单调递增的数字，并且所有的Porposer提出的序列号不能一样。如何使所有Porposer产生不同的序列号不在本文讨论范围；举个简单例子，每个Porposer都保持一个序列号集合{Porposer id+Porposer数量*N，N=1,2,3……}即可。
Paxos有一个很重要的概念，多数派。Paxos中的多数派意义为：对于参加本次投票的Acceptor集合，如果它和之前任意一次成功投票的Acceptor集合的交集都不为空，则称本次投票的Acceptor集合达到多数派条件，并且本次投票也是一个成功的投票。这个说法过于晦涩，在不考虑权重的情况下，我们可以简单理解为：所有Acceptor机器数量为N，则多数派指的是参与投票的Acceptor数量达到或超过⌈ (N+1)/2⌉。只有满足多数派条件的投票才是一次成功的投票
下面描述Paxos算法的详细过程。
Proposer过程：
1.每当Porposer希望提出方案V1，首先发出prepare请求至Acceptor。Prepare请求内容为<序列号SN1>
2.经过一段时间，收到一些Acceptor回复，回复可分为以下几种
a) 回复数量满足多数派，并且所有的回复都是<OK>，则Porposer发出accept请求，请求内容为议案<SN1，V1>
b) 回复数量满足多数派，但有的回复为：<SN2，V2>，<SN3，V3>……则Porposer找到所有回复中序列号最大的那个，假设为<SNx，Vx>发出accept请求，请求内容为议案<SN1，Vx>
c) 回复数量不满足多数派，Proposer尝试增加序列号为SN1+，转1继续执行
3.经过一段时间，收到一些Acceptor回复，回复可分为以下几种
a) 回复数量满足多数派，则确认V1被接受
b) 回复数量不满足多数派，V1未被接受，Proposer增加序列号为SN1+，转1继续执行
上文中步骤(3)与(2)的区别在于(3)仅判断了回复的数量，而对回复内容未进行判断。因为对于accept请求，如果Acceptor回复就表示接受了
Acceptor过程：
1.当Acceptor接收到prepare请求<SN1>时，检查自身上次回复过的prepare请求<SN2>
a) 如果SN2>SN1，则忽略此请求，直接结束本次批准过程
b) 否则检查上次批准的accept请求<SNx，Vx>，并且回复<SNx，Vx>；如果之前没有进行过批准，则简单回复<OK>
1.当Acceptor接收到Accept请求<SN1，V1>时，检查自身上次回复过的prepare请求<SN2>(注意Acceptor可能在没有收到prepare请求的情况下接收到accept请求，因为Porposer并不保证只将accept请求发送给那些回复它prepare请求的Acceptor；同理，Acceptor回复prepare请求后也并不保证一定能收到accept请求。此处的SN2与步骤(1)中的SN2可能不一致)[5]
a) 如果SN2>SN1，则忽略此请求，直接结束本次批准过程
b) 否则直接批准此Accept请求
如果我们需要学习到当前的方案，则我们可以扮演一个Learner的角色。Learner向所有的Acceptor发出学习请求，Acceptor收到此请求时回复自身上次批准的<SNx，Vx>，当Learner学习到一个经多数派Acceptor批准的<SNx，Vx>时，则说明Vx得到最终的通过，此时称为Vx这个方案被选择了
Paxos协议里面有几点需要特别注意，也请大家思考：
1.一个Acceptor是否可能批准不同的方案？
2.Acceptor本身是否知道一个方案被选择了？
3.在Proposer的阶段(2c)中，如果此时有其他的Porposer在提交方案引起冲突，是否会引起震荡的提交？
4.一个方案已经被选择了，之后是否可以重复提出此方案进行提交？
5.Acceptor是否可能重复批准相同的方案？
6.是否可能出现一个方案被选择后，Learner学习不到的情况？即，一个方案被选择了，但Proposer，Acceptor，Learner都不清楚是否有方案被选择，哪个方案被选择？如果会，那么Paxos协议如何保证进展及一致性？
不严谨的证明
对上述过程进行归纳总结，采用文字描述的Paxos协议整个过程如下：[6]
将一个议案的选择过程分为两个阶段：
prepare 阶段：
Porposer 选择一个序列号SN 并将 prepare 请求发送给 Acceptors 中的一个多数派；
Acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 Acceptor 将自己上次的批准回复给 Porposer，并承诺不再批准序列号小于SN的提案，同时不再响应序列号小于SN的prepare消息；
批准阶段：
当一个 Proposer 收到了多数 Acceptors 对 prepare 的回复后，就进入批准阶段。它要向一个多数派 Acceptor 发送 accept 请求，包括编号 SN 和根据前述条件确定的value。
在不违背自己向其他 Porposer 的承诺的前提下，Acceptor 收到 accept 请求后即批准这个请求。
这个过程在任何时候中断都可以保证正确性(即在任何情况下算法都可以保证一致性)。在其过程中并不保证任意一次请求一定能得到响应，在任一步骤中发生Proposer或Acceptor失效都不会影响算法的正确性。
对于算法的正确性，Paxos论文中本身已有严谨证明，虽然严谨却难于理解。我尝试给出不那么严谨的证明方式如下：
两个条件：
1.多数派批准，被称为value被选择
2.Prepare消息回复中，要么：所有的回复中没有批准value，要么本次提交所有回复中最大SN号的那个value
Paxos认为满足上述条件就能保证一致性。那么：
1.如果所有prepare回复中没有批准value，那么随意提交一个value不会造成不一致，这是显然的，因为多数派Acceptor并没有批准任意一个议案
2.假设在第K次有方案v被选择(即多数派Acceptor对议案<K，v>进行了批准，此时Learner已经可以学习到方案v)，如果上述算法不能满足一致性，则必然存在第K+m次有方案v1被选择，且v1!=v，且第K+1，K+2,……K+m-1次中都没有任何方案被选择。根据上述条件(2)，第K+1，K+2，……K+m-1次所提出的方案都是v1，则：第K+m次的prepare请求中，没有收到<Kx，v>这样的回复。存在一个多数派，其在第K，K+1，K+2，……K+m-1次中均没有进行过方案v的批准，而这与方案v在第K次被通过冲突，因此，假设不成立，上述算法一定能满足一致性要求，Paxos算法的正确性得到证明
问题解决
我们将上述达成一致的过程称为一次Paxos运行实例。显然，单实例的Paxos没有任何意义，我们并不需要一个只能达成一个值并且从此不变的协议。为此，我们扩充到multi-paxos。在prepare请求和accept请求中都加入实例号N，所谓一致性仅在一个实例内部有意义。以锁操作为例，我们希望：首先加锁，然后解锁，这就是两个paxos实例，这两个实例的实例号可以使用锁的序列号来表示。则对于任一客户端，加锁解锁的过程变为：Learner首先取得当前已完成的锁序列号Lx，如果当前最新序列号中锁的状态是解锁，则提出议案<Lx，SNx，加锁服务器id>，如果加锁失败(即本地Learner未收到多数派加锁成功消息，或者加锁成功消息中的方案与本机提出的不一致)，则从头开始重新进行
最终，我们成功使用Paxos解决了前面提出的问题。任务分解出来的模块进行顺序编号，每个模块都有自身的惟一编号，以这个号做为Paxos的实例号。服务器每当获取一个模块N(此时作为Proposer)时，会发出议案<N，SN，服务器id>，然后服务器开始等待学习议案<N>；当学习到<N，SN，服务器M>时，认为模块N已经被服务器M所运行，之后的判断，比如M是否是自身，不是的话后续如何处理等，交由用户逻辑处理[7]
参考文档
[1] The Part-Time Parliament，Lamport，1998，ACM Transactions on Computer Systems
[2] Paxos Made Simple，Lamport，2001年
[3] http://libpaxos.sourceforge.net/ ，paxos的开源实现
[4] http://zh.wikipedia.org/zh-cn/Paxos算法 ，wikipedia上的中文说明
[5] http://en.wikipedia.org/wiki/Paxos_algorithm ，wikipedia上的英文说明
[6] http://labs.google.com/papers/chubby-osdi06.pdf ，chubby论文，关于paxos的使用
[1]为避免读者误会，我虚构了上述场景及其解决方案。我所描述的解决方案显然不是最优的，但这不是重点，重点是paxos确实可以解决我们碰到的这个问题
[2] 之所以要写Paxos，是因为网上流传的一些关于Paxos的描述不尽准确，并且大家抄来抄去，当你读到1千篇文章的描述都一样时，很可能会把错的也当成对的。另外，st的此次活动是促使动笔的直接因素，在此表示感谢
[3] 可以认为chubby论文的发表将对Paxos的研究推向热潮，chubby文章可以参考附件
[4] 对于这三者的概念，可以参考《Paxos made simple》，比起原始的论文《The Part-Time Parliament》要简单许多
[5] 对于accept请求的发送，wiki中文及《Paxos made simple》中提到，需要发送给回复prepare请求的多数派Acceptor，但《The Part-Time Parliment》中没有此要求，可以随意发送给一个多数派集群即可。另外参考了开源的libpaxos做法，其所有的请求都是采用直接广播的方式进行。此处采用发送给任一多数派的说法，因为我认为这样做并不会引起不一致，并且在实现上更加简单，只需要按照libpaxos，每次都将accept请求往Acceptor集群进行广播即可
[6] 此处的描述引用了wiki中文关于Paxos的相关条目，但有所更改，因为我认为wiki中文中对于Paxos的描述主要参考的是Paxos made simple，并且做了一些优化，而对于basic paxos的描述有些地方并不准确。详情见http://zh.wikipedia.org/zh-cn/Paxos算法
[7] 同前述，本例子只是虚构的，用来引出Paxos算法。请不要太认真的对待这个例子的解决方式
原文来源：http://stblog.baidu-tech.com/?p=1196