泽野弘之 交响音乐会:Paxos算法深入分析

在分布式系统设计领域，Paxos可谓是最重要一致性的算法。连Google的大牛们也在论文Chubby中说到

All working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

可见此算法的地位。网络上讨论此算法的文章多如牛毛，但大多数让人看了之后仍然是一头雾水，就连维基百科中，对此算法的描述亦有含糊和错误之处。但实际上，此算法的核心思想还是比较简单的，只是大多数文章的分析脱离了实际应用，或是陷入大量实现细节以致掩盖了算法的核心。本文将先给出Paxos算法的设计目的，和算法流程，再反过来分析算法的原理。后面我们将看到，正如Paxos made simple中所说

The Paxos algorithm, when presented in plain English, is very simple.

Paxos算法实现的是分布式系统多个结点之上数据的一致性，这个算法有如下特性

1.基于消息传递，允许消息传输的丢失，重复，乱序，但是不允许消息被攥改

2.在结点数少于半数失效的情况下仍然能正常的工作，结点失效可以在任何时候发生而不影响算法正常执行。

以如下场景为例：

Master保存一个状态机，可接收多个Client发来的请求，Master负责把请求序列化并执行请求，执行请求时将修改状态机，同时Master还负责在多个冲突的请求中选出一个请求反馈给Client，如多个Client请求同一个锁的情况。

这个场景实际上就是服务器工作的抽象，如果采用单个Master是很容易做到的，但是，单Master无容错性，不能保证持续提供服务，有人可能会说，我再启用一台备用Master，工作的Master宕机后备用的自动切换上，同时Master执行请求同步到备用结点上，这不就解决了单点故障问题么？这实际上就是双机热备的方法，但是，这种做法在宕机-切换之时无法保证严格的状态一致性，例如：

Master A 接收冲突请求V1 V2 V3 选举出V3，写入本地磁盘，然后传输V3给Master B(备份),但在Master B接收之前Master A宕机，此时Master B接管服务，客户端由于没有接收到回应继续发送请求，而此时可能出现了更多的冲突请求，如V4，也加入选举，Master B只能重新选举，这时选出V4，写入磁盘，不久后Master A 恢复，于是Master A和Master B磁盘状态不再一致。

那么Paxos算法是怎样实现多个Server间的一致性呢，下面是Basic Paxos算法，注意，这个算法只具有在多个冲突请求中选出一个的功能，并不具备序列化多个请求依次执行的功能。

Paxos算法包含三个角色Proposor，Acceptor，Learner。

实现的时候采用一组固定数目Server，每个Server同时担任上述三个角色，多个Client将自己的请求值Value_i随机发给一个Server处理，然后这一组Server经过协商后得出统一的一个值Chosen_Value，这个值必须被每个Server学习到，同时回复给所有发起请求的Client。

具体算法流程如下，为避免歧义，关键字眼Propose,Proposal,Accept,Value,Choose等保留英文原文。

阶段1a---Prepare（预定Proposal序号）

每个Proposor 拿到某个Client的请求Value_i后，在此阶段还不能发起Proposal，只能发送一个Proposal序号N，将序号发送给所有Acceptor（即所有Server包括自己），整个系统中所有Proposal的序号不能重复而且每个Proposor自己用到的序号必须是递增的，通常的做法是，假设K台Server协同运行Paxos算法，那么Server_i（i=0...K-1)用的Proposal序号初始值为i，以后每次要产生新序号时递增K，这样保证了所有Server的Proposal序号不重复。

阶段1b---Respond with Promise

每个Acceptor收到Proposal序号后，先检查之前是否Repond序号更高的Proposal，若没有，那么就给出Response，这个Response带有自己已经Accept的序号最高的Proposal（若还没Accept任何Proposal，回复null），同时，Promise自己不再Accept低于接收序号的Proposal。否则，拒绝Respond。

阶段2a---发起Proposal，请求Accept

Proposal如果得到了来自超过半数的Acceptor的Response，那么就有资格向Acceptor发起Proposal。其中，N是阶段1a中发送的序号，value是收到的Response中序号最大的Proposal的Value，若收到的Response全部是null，那么Value自定义，可直接选一个Client请求的Value_i

阶段2b--Accept Proposal

检查收到的Proposal的序号是否违反阶段1b的Promise，若不违反，则Accept收到的Proposal。

所有Acceptor Accept的Proposal要不断通知所有Learner，或者Learner主动去查询，一旦Learner确认Proposal已经被超过半数的Acceptor Accept，那么表示这个Proposal 的Value 被 Chosen，Learner就可以学习这个Proposal的Value，同时在自己Server上就可以不再受理Proposor的请求。

这个算法能达到什么效果呢，只要保证超过半数的Server维持正常工作，同时连接工作Server的网络正常（网络允许消息丢失，重复，乱序），就一定能保证，

P2a: 在将来某一时刻，自从某个Proposal被超过半数的Acceptor Accept后，之后Accept的Proposal Value一定和这个Proposal Value相同。

这就是整个算法的关键，保证了这一点，剩下的Learn Value过程就简单了，无需再为消息丢失，Server宕机而担心，例如，假设5台Server编号0~4，Server0，Server1，Server2已经Accept Proposal 100，然后Server0,Server1学习到Proposal 100，刚学习完成Server0,Server1就都宕机了，但这时候，Server2 Server3和Server4由于没有学习到Chosen value，因此还要继续提出Proposal，然后呢，根据这个神奇的算法，最后能使得Server3 Server4将来Accept的值一定是之前选出来过的Proposal 100的Value。

看到这里，大家应该能够隐隐猜到，在这个过程中，Server2之前Accept Proposal 100的Value起了关键作用，下面，我们就来严格证明上述红色字体表示的算法关键点：

首先回顾前边两阶段协议的几个关键点：

1.发起Proposal前要先获得超半数Acceptor中Accept过的序号最大的Proposal Value。若Value为null才能采用自己的Value。

2.阶段1b Promise自己不再Accept低于接收序号的Proposal。

3.Propsal被超半数的Acceptor Accept才能被认定为Chosen Value从而被Learner学习。

这几个约束条件共同作用，达到了上述P2a要求的效果，Paxos算法提出者Leslie Lamport是怎么构造出来的呢，事实上很简单：

首先，把P2a加强为如下条件：

P2b:自从某个Proposal被超过半数的Acceptor Accept后，之后Proposor提出的Proposal Value一定和这个Proposal Value相同。

显而易见，由P2b可以推出P2a，那么怎么满足P2b呢，实际上，只要满足如下条件：

P2c:发起的Proposal的Value为任意一个超半数Acceptor集合中Accept过的序号最大的Proposal Value。若这个Acceptor集合中没有Accept过Proposal才能采用自己的Value。

如何从P2c推出P2b呢，利用数学归纳法可以轻易做出证明：假设在某一时刻一个超半数Acceptor集合C共同Accept了某个Proposal K，由于集合C和任意一个超半数Acceptor集合S必有一个共同成员，那么，在这个时刻之后，任意一个超半数Acceptor集合S 中Accept过的最大序号的Proposal只可能是Proposal K或序号比Proposal K更大的Proposal，假设为Proposal K2。同理，Proposal K2的Value等于Proposal K或Proposal K3的Value，而K

我们可以看到，P2c条件基本就是上述两阶段协议的关键点1，但是还有一个问题，这个P2c条件要求找出这个“最大序号Value”和提出Proposal必须是一个原子操作，这实际上是难以实现的，所以，上述两阶段协议用了一个巧妙的方法避开了这个问题，这就是上述关键点2 Promise所起的作用了。在Acceptor respond“最大序号Value”的时候，Promise不再Accept低于收到序号的Proposal，这样“找出这个‘最大序号Value’”和“提出Proposal”之间就不可能插入新的被Accept的序号，从而避免P2c条件被破坏。

到这里为止，基本的Paxos算法就已经透彻分析完了，但是，现在这个算法是使用多个Proposal，会造成活锁问题，需要引入leader来优化，而且，这个算法还只能实现在多个冲突Value中选举一个Value的功能，至于序列化多个Value实现状态机，就需要multi-paxos算法。这些问题，就留到下一篇博文来详细讲解。