Paxos选举多次决议的算法实现

在之前的文章中,小秦学习了Paxos的基本算法及单次投票的实现。这篇文章小秦会说下如何进行多次投票。

比如在分布式数据库中,如果采用Paxos做底层的分布式同步算法,那么要被同步的其实是数据库的事物日志。比如在A、B、C三台主机搭建出的数据库中,执行了update tb set a = 5这个操作,那么在Paxos的要求下就需要至少2台主机获取了这个操作的事物日志,这次事物才算成功。

由于Paxos在一次投票结束后,结果是一致性的,所以以后的每次投票(也就是新事物事物日志的记录)都会因为第一次投票的结果而无法记录,那么数据库就无法正常工作了。为了克服这个问题,可以将每个事务日志的记录都放在一次单独的Paxos投票中,这样的话也就是说如果有5个事物日志要被记录,那么会有5个独立的Paxos投票选举5个结果。

由于事物日志是有序的,我们要保证这5个投票的最终事物日志是有序,就需要对每个事物日志加上全局唯一的可以比较的事物id。有两种思路:

第一种思路:我可以从某个数据源获取到全局唯一的可比较的事物id,现在已经有1,2,3,4,5这5个id,内容是将a字段加1,a一开始是0,因此如果某个主机所有的事物日志都拥有,那么该主机上a就是5。那么对于读和写操作:
对于读:任意的请求发到三台主机的一台上,由于该主机不一定拥有1~5的所有日志,假设只有1,3(因为Paxos只要多数主机有就行了),所以该主机发送一个请求给其大多数主机,获取他们目前的比1达的所有事物日志内容,然后在本地重做后,返回结果给请求者
对于写:任意的请求发到三台主机的一台上,该主机从某个数据源获取到全局唯一的下一个id(也就是6),然后用类似读的方式获取当前的所有数据,然后在该id下进行一次paxos协议,得到事物id为6的事物日志,然后更新自己的a为6,将结果返回给请求者。

第二种思路:我可以选举一个leader出来,所有的读、写请求都和leader交互。由于leader是唯一的,所以他可以保证事物日志id的有序和唯一。leader的选举方法可以看小秦的这篇文章。在这种情况下,对于读和写操作:
对于读:leader直接返回结果即可
对于写:leader获取下一个事物id,然后发起一次新的Paxos投票即可。

在第二种思路下,由于leader的存在,leader不需要执行Paxos协议中的第1、2步,因为只有他在进行写入。

现在考虑下leader宕机后的情形,比如本来leader是A,执行了事物1,2,3,4,5,6,B上记录了事物日志1,2,6,C上记录了事物日志1,2,3,4,5。A宕机后,由于没有续约,B和C在PaxosLease的选举下B成为了leader,此时B会发送请求给其它服务器,请求内容是将你事物id大于2的所有事物内容都给我。C会的将3、4、5给B。B在得到大多数服务器的请求后(也就是B和C这两台服务器),其就拥有了当前所有的事物id(从1~6),B在重做事物日志后,即可从下一个事物id为7的基础上对外提供服务。

发表评论

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

*