PAXOS算法理解

在之前的一偏文章中,小秦我学习了下PAXOS的大致算法思想。这里,在《The Part-Time Parliament》的基础上(主要是看了中文的一个翻译版本,感谢翻译人),趁着春节的假期再次学习下PAXOS算法的数学基础、协议流程,以及尝试了解下作者是如何解决一些我在思考分布式问题时遇到问题的一些解决思路。

PAXOS可以用来解决分布式环境下,选举(或设置)某一个值的问题(比如更新数据库中某个user的age是多少)。比如下面的情况:
有三个服务器进程A,B,C运行在三台主机上提供数据库服务,当一个client连接到任何一台服务器上的时候,都能通过该服务器进行read和update的操作。

首先先看一个A、B、C不那么均等的方法:
A、B、C选举主机名最大的服务器为master提供服务,所有的read、update操作都发生在它上面,其余的两台服务器只是slave(后者,在这里类似proxy),当client是连接在master的服务器的时候,其直接和master交互,就类似于单机的场景。当client时连接在slave的时候,所有的请求被转移到了master上进行操作,然后再结果返回给client。如果master挂了,那么剩余两台主机在检测到master挂的情况后,再根据主机名最大的方法选举master。

上面的算法有一个问题,它让A、B、C不那么均等了,A、B、C存在角色之分,且在某个时候master挂机后,需要立刻选举出新的master提供服务。同时,这个算法还要求各个服务器之间保持心跳。而PAXOS算法则不同,PAXOS提供了一种将A、B、C等价的方式提供上面的操作,并保证数据的正确性。在某台主机宕机后,只要总数一半以上的服务器还存活,则整个集群依然能对外提供服务,甚至不需要心跳。

来看下论文吧。论文的前半部分提到在Paxos岛上通过某种协议进行法令的选举,一轮选举要求满足下面的条件:
假设存在下面四个要素:
B-dec:一条法令(被投票的那条 decree)
B-qrm:一个牧师的非空集合(表决的法定人数集 quorum)
B-vot:一个牧师的集合(所有对法令作出投票(赞成)的牧师)
B-bal:这轮表决的编号
只有B-qrm属于B-vot集合的时候,某一次表决B才是成功的。
再此基础上,为了保证这种选举可以选举出一致性的法令,有下面的限制条件:
B1:所有表决中的每一轮表决,都有一个唯一的编号
B2:所有表决中的任意两轮表决的法定人数集中,至少有一个公共的牧师成员
B3:对于所有中的每一轮表决B,如果B的法定人数集中的任何一个牧师在所有表决中的一个更小轮的表决中投过(赞成)票,那么B的法令与所有这些更小轮表决中的最大的那次表决的法令相同

通过B1、B2、B3可以证明该协议可以得到一致性的法令,同时该协议是可以持续进行的,但是不保证一定能选举出法令。具体的数学证明方法可以看论文,简单的说(严重不规范的思考,详细的证明务必参见论文):
a.如果B1、B2、B3都满足,那么假设B2表明需要一半以上的人员参与表决或投票,那么当某个法令已经发布后,必然有一半以上的人员其当前最大的一次表决结果是该法令。由于B2和B3的存在,下一次有人来请求的时候,必然当前选出的一半以上的人员会给出其最大的表决结果,也就是已经表决出的那个结果,所以一致性是可以保证的
b.可行性是可以保证的,B1、B2要满足是很简单的,对于B3,如果还没有任何表决,则让大家选举任意法令,否则按要求选取之前最大的即可

到这里为止,作者提出了Paxos的数学基础。从这里开始,作者的方向变成构造一种实际的可操作、可编程的协议来满足该数学思想(或者可以称之为数学模型)。这里开始是小秦很佩服的地方,能将数学理论与实际的流程想互通,这种能力是我需要学习的。

对于B1,在实际操作中是容易实现的。对于B1,按照之前小秦的文章提到的那样即可实现(比如在我们上面举得例子里,每个服务器在启动的时候都写明自己的id为1、2、3。由于知道自己的id以及总服务器个数3,因此每次得到法令编号的时候,用自己当前的编号加上3的n倍即可)。

我们来看B2和B3,这是从理论到实际的一个难点。B3要求当一次投票请求来到的时候,我们的三台服务器(其实是任意两台,也就是B2)需要知道大家之前所有投票中编号最大的那次的投票的值,来判断是否和投票请求的值相同,如果相同则同意(或者不投票),否则则不投票。这就需要我们的服务器之间存在交流,这种交流在实现的时候是复杂的,需要考虑延迟、丢包、重复等问题。那么能不能绕过去呢?作者在这里换了思路(赞!),如果我client去询问B2要求的大多数服务器,让大多数服务器和我client做交流,得到满足B3条件的值(如果得不到那么这次就算了,歇会再发起投票即可),然后由于服务器在投票的时候只有赞成是投同意的,其余情况(比如不赞成、不做评价、服务器繁忙不响应、没有收到投票请求)这类都是不投票的,那么我收到B2中大部分服务器回应的时候,只要我的需要的被投票的值就是大家返回的值,那么大家在这个时候肯定是都同意的,所以我只要发个信息让大家投票同意即可。如果这个信息在发送过程中丢失了,或者由于其它投票的发生,这次投票无效了,那么服务器什么都不做即可。也就是说,当client收到大部分服务器的回应并得到此时(或这一轮)肯定能通过的决议后,当前的这一轮(这一轮可以用B1要求的序号表示)就是一次满足B1、B2、B3的投票。client可以将结果发送给各个服务器,让他们在类似于论文中提到的法律本中记录,或者说发送的时候消息丢失,类似于服务器即便同意但是也不想投票。所有的这一切都不会影响到B1、B2、B3,因此所有的这一切都能保证最终结果的一致性以及可进展性。只要某一次投票中,client得到大多数服务器的B3得到的值后将该值发送给大多数服务器,并且大多数服务器都投了赞成票,那么结果就最终确定了。这样,一个建立在数学基础上的分布式算法就有了一个实际的可实现的流程。

这里再来看一个实现这个过程的很重要的一点,在上面小秦提过:“当client收到大部分服务器的回应并得到此时(或这一轮)肯定能通过的决议后”,这里的这一轮内在要求了B1,同时也要求每个编号都是可以比较的。小秦在看论文前思考这个算法如果是自己怎么设计的时候,总会被各种异常情况(比如A发了请求,传递给B和C的时候B延迟很久这类)所困惑。如果在思考分布式这类问题的时候,有一个全局唯一的编号,并且编号是可比较的,那么就能得到任何一轮的时候的情况,并且这些情况不会因为各种变化(如新的投票)而变化,新的投票只是让序列进入到编号更大的轮次而已,对于某一时间的某轮只要是定了则永远定了。通过这个方法,可以让混乱的分布式变的一定程度的有序。

如果有人在这里还是对Paxos的实现流程有疑问的话,建议多看下论文中的那个示例表格,跳跃的编号、不赞成或赞成时的不投票,这张表格代表了Paxos的完整的投票过程。而表格的每一行则是一次次的B3的结果。

论文的接下来讨论了对于上面提到的初级协议的改进,比如如何让协议更容易快速得到结果等。但算法的核心就是上面提到的B1、B2、B3的数学基础及建立在该数学模型上的一种实现。另外论文还讨论了如何处理多次(甚至无限次)投票,对于这一点小秦会在下一篇文章中写明具体的过程。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*