Basic paxos协议更新日志

我们将数据持久化的需求抽象为：在N个server的机群上，持久化数据库或者文件系统的操作日志，并且为每条日志分配连续递增的logID，我们允许多个客户端并发的向机群内的任意机器发送日志同步请求。

将每条日志的持久化流程都看作一个“Paxos Instance”，不同的logID代表不同的Paxos Instance形成的“决议（decision）”。即每一个logID标识着一轮完整paxos协议流程的执行，最后形成decision。机群内的每个server同时作为paxos的acceptor和proposer。

获取LogID

Server收到客户端的持久化日志请求后，因此向所有acceptor查询它们本地目前已写盘的最大logID，而只需收集到majority返回的结果，并选择其中最大的logID+1作为本次待持久化日志的logID。

从上面的描述可以看出，这里并不能保证并发提交的两条日志一定被分配到不同的logID，而是依靠后续的paxos协议流程来达到对一个logID形成唯一的decision的目的。

产生ProposalID

这里我们使用server的timestamp联合ip作为proposalID，其中timestamp在高位，ip在低位。(为了唯一卫衣proposalID，只要要求时钟的误差范围小于server重启的时间)

Prepare阶段

只有在这个Paxos Instance内（即针对这个logID）没有response过proposalID大于等于当前proposal的，并且也没有“接受（accept）”过proposalID大于当前proposal的，才可以response，并承诺不再accept那些proposalID小于当前proposal的。

上面Prepare阶段的处理流程暗示，对于分配到相同logID的不同日志，由于他们的proposalID不同，acceptor在response一个较小proposalID后，是允许继续response后来的较大的proposalID的。

Accept请求阶段

如果majority的response中的日志内容都为空，那么可以向所有acceptor发出accept request并携带上当前日志内容；而如果有任意的response中的日志内容有效，那么说明当前logID已经别其他日志占用，因此需要回退，回到第一步“获取logID”重新执行。

Accept执行阶段

而如果ProposalID小于当前最大minProposal的，则说明有logID切proposalID更大的proposal在并发执行，当前proposal会被覆盖，因此回复proposer要求回退到第一步“获取logID”重新执行。

这里的流程暗示，针对一个logID，如果之前已经有日志内容持久化成功，那么这条日志一定会被选为accept request；而如果之前日志内容仅仅在小于半数的server上写到磁盘，那么最终这条logID的内容有可能是有效日志，也有可能内容为空。(本例中可能两个提议者竞争一个logID，然后本例中为了加快收敛，其中一个自动放弃，选择更大的logID)

日志内容读取

在读取的时候也需要回放一遍paxos协议，防止读到未提交的日志(相当于raft的提交阶段？)。

为什么需要comfirm日志

假设有a, b, c 3个节点, 刚开始的时候, 3个节点的值是一致的, 都是v1. 这时候一个proposer发起一轮paxos请求, 希望将值设置成v2. 那么可能出现两种情况, 一种是paxos成功了, a, b, c的多数派中value设置成了v2, 也就是说v2被批准了(假设a, b, c的值分别是v1, v2, v2). 另外一种是失败了, a, b, c的多数派中value仍然是v1, 也就是说v2没有被批准, 但是a, b, c中可能存在少数派节点的值是v2(假设a, b, c的值分别是v1, v1, v2). 按照p2a的流程, 选取proposal的原则是选取多数派中, proposal号最大的作为期望被批准的value. 在上述两种情况下, 当reader读取数据时, 按照p2a的逻辑, 既可能读到v1, 也可能读到v2, 那这样的话, 如果有一个acceptor故障了, 其实reader就无法准确知道之前被批准的value了吧? 我看paxos made simple的论文中也提到, 如果有一个acceptor故障了, 也不可能找出被批准的value了, 唯一的办法就是issue a proposal, 然后运行一轮新的paxos算法了。这是不是说, 不管reader读到的是v1还是v2, 仍然发起一轮paxos协议, 保证一致性就ok了

简而言之，就是只有leader某条日志才知道某条日志复制到大多数，而参与者并不知道。所以在提交的时候，要么再跑一次paxos，要么写一条comfirm日志

Multi-paxos更新日志

Leader的产生

通过Multi-paxos，我们可以简化掉产生logID阶段和prepare阶段，而是由唯一的leader产生logID，然后直接执行accept，得到多数派确认即表示redolog同步成功。

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

Leader产生并不是走完一个完整的basic paxos流程，而是只走了proposal prepare阶段，所以可能同时产生多个leader。因此，我们需要先写一条StartWorking日志，成功写下这条日志升级为唯一leader

confirm日志优化

因为在读取日志的时候，需要再进行一次basic paxos协议。因此引入confirm日志，针对刚刚提交的日志写入一条confirm日志。出于性能考虑，实际操作中，批量发送confirm日志，因此，读到未确认的日志，还是需要走一遍paxos协议

新任leader对日志的重确认

新任leader可能保存的日志落后于前任leader，因此需要对小于当前集群中max log id的日志都进行，只要大多数回复max log id即可。这样的结果可能超越了前任已经accept的日志记录，称为最大commit原则。

“幽灵复现”日志的处理

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

x	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

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

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

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

其中，log1和log6分别是第一轮和第二轮的start working log。

本质上是通过在发生leader权抢占的时候，ProposalID的递增性质保证了不会回放以前的logID。

multi-paxos和raft对比

以下是我自己的观点，不保证正确性

raft logID递增，multi_paxos并不需要
multi_paxos为了保证读到的日志已经提交，需要再走一边paxos确认日志；raft每次获得多数派的认可后，也需要向参与者发送提交命令(相当于读取命令)。
因为multi-paxos的logID不连续，在leader权抢占的时候，所以有了最大commit原则，最大commit原则可能产生幽灵日志，如果epochID小于上一条，就不回放，所以有了不回放上一个任期的日志。

幽灵日志解释很清晰