Paxos协议

现如今网站中，涉及到一定规模的都会引入分布式的部署和实现。说到分布式系统，那就要提到它所使用的信息交换方式，不外乎两种，一种为通过共享内存共享数据，另外一种是通过传递消息来完成。

 

但是使用消息传递的方式会引入很多问题，比如网络问题、进程意外被kill掉、宕机以及进程被阻塞，在这些情况下，就会造成消息重复、消息不可达或者超时处理等现象。在这里引入Paxos协议来解决分布式系统中的一致性问题。

 

但是使用Paxos协议的前提是通信环境要可靠，也就是说信息是准确而且保证没有被篡改过，也就是不存在拜占庭将军提及的问题(关于拜占庭将军问题(Byzantine Generals Problem)，可以参考维基百科拜占庭将军)。

 

Paxos算法是通过一个故事的形式来描述的。首先虚拟了一个名为Paxos的希腊城邦，以议会中讨论议案的步骤流程作为算法的呈现。

 

其中前提是议员的角色分成三类：Proposers(提议案) Aceeptors(接受议案进行判断) Learners(议案观察员)。除了角色之外，还有两个定义如下：

Proposal：议案

Value：决议，议案的内容。由{编号，协议}的形式组成。

 

现在定义一些前提：

1.对协议能做出的操作必须是：首先被提出议案的议员提出后，才能被批准。

2.算法的执行过程中，一次只能批准一个协议。

3.Learners议案观察员角色只能获取被批准以后的Value(决议)。

 

同时，每个议员都会使用结实的本子和不可能被篡改的墨水来书写议案，但是议员会把表决信息写在本子的背面，正面书写的议案永远都不能改变，但是背面的可以被擦掉。同时本子背面只能记下如下内容：

LastTried[p]：表示议员p试图发起的最后一个议案的编号，如果没有提出过议案，则记成负的无穷大。

PreviousVote[p]：表示在议员p的的所有表决中，编号最大的表决对应的投票，与上面一样，如果没有投过票则记为负无穷大。

NextBallot[p]：表示在议员p发出的所有LastVote(b,v)消息中，表决编号b的最大值。

 

下面是协议表决的基本完整流程：

 

1.议员p选择一个比LastTried[p]大的表决编号b，然后设置LastTried[p]的值为b，最后将NextBallot(b)消息发送给某些议员；

2.从议员p收到一个b大于NextBallot[q]的NextBallot(b)消息后，议员q将NextBallot[q]设置为b，然后发送一个LastVote(b,v)消息给p，其中v等于PreviousVote[q](b<=NextBallot[q]的NextBallot(b)消息被忽略)；

3.在某个多数集合Q中的每个成员都收到一个LastVote(b,v)消息后，议员p发起一个编号为b、法定人数集合为Q、议案为d的新表决。然后给Q中的每一个成员发送一个BeginBallot(b,d)的消息；

4.当收到一个b=NextBallot[q]的BeginBallot(b,d)的消息后，议员q在编号为b 的表决中投上自己的一票，然后设置PreviousVote[p]为这一票，最后向p发送Voted(b,q)消息；

5.议员p在收到Q集合中每一个q的Voted(b,q)消息后，将d(此轮需要表决的法令)记录到他的本子上，然后发送一条Success(d)消息给Q中每一个q成员；

6.最后当议员收到Success(d)消息后，会将决议d记录在他的本子上。

 

其中重要的原则其实很简单，就是少数服从多数罢了。

 

在这其中，如果同一时间有多余一人的议员提出议案，则会出现碰撞，这种情况下双方都要增加议案的编号并且再次提交。但是再次提交可能仍会有此问题存在，这种情况下就会出现活锁了。

 

这种情况也不难解决，就是在整个集群之中增加一个领导也就是大家说的议长或者某一政党的党首的角色，所有的议案都通过他们来提出就会避免掉上面所述的冲突了。但是这样也有问题，就是如果党首或者议长因为去接孩子或者生病重感冒来不了的情况下怎么办啊，其实也难不倒，可以选举一个备份的人选出来代替他们来行使职责，比如副议长以及第二党首，哈哈，否则除非议会中只要有众人在，就不会再出现问题。

 

   上面只是一些简单介绍了Paxos算法，如果想更加深入的窥视算法的细节，可以阅读下Paxos相关的论文，或者维基百科上的相关资料。