Multiple-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 的基础上对外提供服务。

Reference