使用Multi-Paxos协议的日志同步与恢复

           本文是Paxos三部曲中的第二篇。在前一篇文章《使用Basic-Paxos协议的日志同步与恢复》（http://oceanbase.org.cn/?p=90）中，我们讨论了基于Basic-Paxos协议的日志同步方案，在这个方案中，所有成员的身份都是平等的，任何成员都可以提出日志持久化的提案，并且尝试在成员组中进行持久化。而在实际的工程应用中，往往需要一个成员在一段时间内保持唯一leader的身份，来服务对数据的增删改操作，产生redolog，并尝试在成员组中进行持久化。本文讨论如何利用Paxos协议选举唯一的leader，以及使用leader将redolog在成员组中进行持久化和恢复的方法。

• Basic-Paxos协议回顾

让我们先来回顾下Basic-Paxos协议的执行流程：为了简化描述，我们假设一个Paxos集群，每个server同时担任proposer和acceptor，任何server都可以发起持久化redolog的请求，首先要向所有的server查询当前最大logID，从多数派的应答结果中选择最大的logID，加1后作为执行本次Paxos Instance的唯一标识；然后进入Paxos的prepare阶段，产生proposalID，并决定出要投票的redolog（即议案）；在accept阶段对prepare阶段产生的议案进行投票，得到多数派确认后返回成功。由此我们可以看出Basic-Paxos协议的执行流程针对每条redolog都至少存在三次网络交互的延迟（1. 产生logID；2. prepare阶段；3. accept阶段）。下面我们逐个分析每个阶段的必要性：

1. 产生logID，由于Basic-Paxos并不假设一段时间内只有唯一的proposer，因此可能由集群内的任意server发起redolog同步，因此不能由单一server维护logID，而是需要进行分布式协商，为不同的redolog分配全局唯一且有序的logID。
2. prepare阶段，上述一阶段的分布式协商logID并不能保证并发多个server分配得到得logID是唯一的，即会出现若干条不同的redolog在同一个Paxos Instance中投票的情况，而这正是Basic-Paxos协议的基本假设，因此需要执行prepare，以决定出这个Paxos Instance内的要进行投票的redolog（即议案）。如果执行prepare决定出的议案与server自己要投票的redolog内容不同，则需要重新产生logID。
3. accept阶段，对prepare阶段决定出的议案进行投票，得到多数派确认后表示redolog同步成功，否则需要重新产生logID。

在这三个阶段中，根据Paxos协议的约束，server应答prepare消息和accept消息前都要持久化本地redolog，以避免重启后的行为与重启前自相矛盾。因此最终可以得到使用Basic-Paxos进行redolog同步的延迟包括了3次网络交互加2次写本地磁盘。并且在高并发的情况下，不同redolog可能被分配到相同的logID，最差可能会在accept阶段才会失败重试。

 

• Multi-Paxos协议概述

在Paxos集群中利用Paxos协议选举唯一的leader，在leader有效期内所有的议案都只能由leader发起，这里强化了协议的假设：即leader有效期内不会有其他server提出的议案。因此对于redolog的同步过程，我们可以简化掉产生logID阶段和prepare阶段，而是由唯一的leader产生logID，然后直接执行accept，得到多数派确认即表示redolog同步成功。

 

• leader的产生

首先，需要明确的是Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志，它允许有多个“自认为是leader的server”来并发生成日志，这样的场景即退化为Basic-Paxos。

Multi-Paxos可以简单的理解为，经过一轮的Basic-Paxos，成功得到多数派accept的proposer即成为leader（这个过程称为leader Elect），之后可以通过lease机制，保持这个leader的身份，使得其他proposer不再发起提案，这样就进入了一个leader任期。在leader任期中，由于没有了并发冲突，这个leader在对后续的日志进行投票时，不必每次都向多数派询问logID，也不必执行prepare阶段，直接执行accept阶段即可。

因此在Multi-Paxos中，我们将leader Elect过程中的prepare操作，视为对leader任期内将要写的所有日志的一次性prepare操作，在leader任期内投票的所有日志将携带有相同的proposalID。需要强调的是，为了遵守Basic-Paxos协议约束，在leader Elect的prepare阶段，acceptor应答prepare成功的消息之前要先将这次prepare请求所携带的proposalID持久化到本地。

对于leader Elect过程，我们并不关心leader Elect提案和决议的具体内容，因为无论执行多少次leader Elect，从Basic-Paxos的角度来看，都是同一个Paxos Instance在对已经形成的决议反复进行投票而已。而执行leader Elect这个过程，我们最关注的是要得到最近一次形成决议的proposer是谁，以及它的proposalID。在leader Elect过程中，得到多数派accept的proposer将成为leader，而它本次所用的proposalID即成为它任期内对所有日志（包括新增日志和后文将提到的重确认日志）进行投票时将要使用的proposalID（称为leader ProposalID）。

这里还需要考虑的一个问题是，由于多个server并发执行leader Elect，可能出现两个server在相近的时间内，先后执行leader Elect都成功，都认为自己是leader的情况。因此，当选leader在开始以leader身份提供服务之前，要使用leader ProposalID写一条日志（称为StartWorking日志），得到多数派确认后，再开始提供服务。这是因为根据Basic-Paxos的约束，可以推断出：先执行leader Elect成功的leader（称为L1），它的proposalID（称为P1）一定会小于后执行leader Elect成功的leader（称为L2）的proposalID（称为P2），而经过了两轮leader Elect，机群内多数派持久化的proposalID一定是P2，而此时L1使用P1执行accept时，由于P1<P2，它将无法得到机群内多数派的accept。

 

• Confirm日志的优化

在Paxos协议中，对于决议的读取也是需要执行一轮Paxos过程的，在实际工程中做数据恢复时，对每条日志都执行一轮Paxos的代价过大，因此引入需要引入一种被成为confirm的机制，即leader持久化一条日志，得到多数派的accept后，就再写一条针对这条日志的confirm日志，表示这条日志已经确认形成了多数派备份，在回放日志时，判断如果一条日志有对应的confirm日志，则可以直接读取本地内容，而不需要再执行一轮Paxos。confirm日志只要写本地即可，不需要同步到备机，但是出于提示备机及时回放收到日志的考虑（备机收到一条日志后并不能立即回放，需要确认这条日志已经形成多数派备份才能回放），leader也会批量的给备机同步confirm日志。出于性能的考虑，confirm日志往往是延迟的成批写出去，因此仍然会出现部分日志已经形成多数派备份，但是没有对应的confirm日志的情况，对于这些日志，需要在恢复过程中进行重确认。

在实际的工程实践中，可以使用基于logID的滑动窗口机制来限制confirm日志与对应的原始日志的距离，以简化日志回放与查询逻辑。

 

• 新任leader对日志的重确认

如上一节所述，在恢复过程中，拥有对应confirm日志的原始日志，可以被直接回放。而没有对应confirm日志的原始日志，则需要执行一轮Paxos，这个过程被成为重确认。

此外日志中的“空洞”，也需要进行重确认，因为当前leader再上一任leader的任期内可能错过了一些日志的同步，而这些日志在其他机器上形成多了多数派。由于logID连续递增，被错过的日志就成了连续logID连续递增序列中的“空洞”，需要通过重确认来补全这些“空洞”位置的日志。

新任leader在开始执行重确认前，需要先知道重确认的结束位置，因为leader本地相对于集群内多数派可能已经落后很多日志，所以需要想集群内其他server发送请求，查询每个server本地的最大logID，并从多数派的应答中选择最大的logID作为重确认的结束位置。也即开始提供服务后写日志的起始logID。

对于每条日志的重确认，需要执行一轮完整的Paxos过程，可能有些日志在恢复前确实未形成多数派备份，需要通过重新执行Paxos来把这些日志重新持久化才能回放。这种不管日志是否曾经形成多数派备份，都重新尝试持久化的原则，我们称之为“最大commit原则”。之所以要遵守“最大commit原则”，是因为我们无法区分出来未形成多数派备份的日志，而这些日志在上一任leader任期内，也必然是“未决”状态，尚未应答客户端，所以无论如何都重新持久化都是安全的。比如A/B/C三个server，一条日志在A/B上持久化成功，已经形成多数派，然后B宕机；另一种情况，A/B/C三个server，一条日志只在A上持久化成功，超时未形成多数派，然后B宕机。上述两种情况，最终的状态都是A上有一条日志，C上没有，在恢复时无法区分这条日志是否曾经形成过多数派，因此干脆按照“最大commit原则”将这条日志尝试重新在A/C上持久化后再回放。

需要注意的是，重确认日志时，要使用当前的leader ProposalID作为Paxos协议中的proposalID来对日志执行Paxos过程。因此在回放日志时，对于logID相同的多条日志，要以proposalID最大的为准。

 

• “幽灵复现”日志的处理

使用Paxos协议处理日志的备份与恢复，可以保证确认形成多数派的日志不丢失，但是无法避免一种被称为“幽灵复现”的现象，如下图所示：

	Leader	A	B	C
第一轮	A	1-10	1-5	1-5
第二轮	B	宕机	1-6,20	1-6,20
第三轮	A	1-20	1-20	1-20

1. 第一轮中A被选为Leader，写下了1-10号日志，其中1-5号日志形成了多数派，并且已给客户端应答，而对于6-10号日志，客户端超时未能得到应答。
2. 第二轮，A宕机，B被选为Leader，由于B和C的最大的logID都是5，因此B不会去重确认6-10号日志，而是从6开始写新的日志，此时如果客户端来查询的话，是查询不到6-10号日志内容的，此后第二轮又写入了6-20号日志，但是只有6号和20号日志在多数派上持久化成功。
3. 第三轮，A又被选为Leader，从多数派中可以得到最大logID为20，因此要将7-20号日志执行重确认，其中就包括了A上的7-10号日志，之后客户端再来查询的话，会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。

对于将Paxos协议应用在数据库日志同步场景的情况，“幽灵复现”问题是不可接受，一个简单的例子就是转账场景，用户转账时如果返回结果超时，那么往往会查询一下转账是否成功，来决定是否重试一下。如果第一次查询转账结果时，发现未生效而重试，而转账事务日志作为幽灵复现日志重新出现的话，就造成了用户重复转账。

           为了处理“幽灵复现”问题，我们在每条日志的内容中保存一个generateID，leader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时，因为leader在开始服务之前一定会写一条StartWorking日志，所以如果出现generateID相对前一条日志变小的情况，说明这是一条“幽灵复现”日志（它的generateID会小于StartWorking日志），要忽略掉这条日志。

 

• 总结

本文介绍了在Basic-Paxos协议基础之上构建Multi-Paxos协议的几个要点：通过使用Paxos选举leader来避免对每条日志都执行Paxos的三阶段交互，而是将绝大多数场景简化为一阶段交互，并且讨论了基于Paxos协议的“最大commit原则”；通过引入confirm日志来简化回放处理；通过引入Start Working日志和generateID来处理“幽灵复现”问题。