使用Basic-Paxos协议的日志同步与恢复
在保证数据安全的基础上，保持服务的持续可用，是核心业务对底层数据存储系统的基本要求。业界常见MySQL/Oracle的1主N备的方案面临的问题是“最大可用（Maximum Availability）”和“最大保护（Maximum Protection）”模式间的艰难抉择，其中“最大可用”模式，表示主机尽力将数据同步到备机之后才返回成功，如果备机宕机或网络中断那么主机则单独提供服务，这意味着主备都宕机情况下可能的数据丢失；“最大保护”模式，表示主机一定要将数据同步到备机后才能返回成功，则意味着在任意备机宕机或网络中断情况下主机不得不停服务等待备机或网络恢复。可见传统主备方式下，如果要求数据不丢，那么基本放弃了服务的持续可用能力。
基于Paxos协议的数据同步与传统主备方式最大的区别在与Paxos只需任意超过半数的副本在线且相互通信正常，就可以保证服务的持续可用，且数据不丢失。本文不再分析Paxos协议本身（参考原始论文，以及这篇比较通俗的分析http://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D ），而是基于Paxos协议，讨论一种在多副本上持久化数据的高可用方案。需要注意的是，本方案不考虑运行性能，只是为了帮助说清协议的工程实现。
我们将数据持久化的需求抽象为：在N个server的机群上，持久化数据库或者文件系统的操作日志，并且为每条日志分配连续递增的logID，我们允许多个客户端并发的向机群内的任意机器发送日志同步请求。对于高可用的需求为：在N个server中只要有超过半数的server（majority）正常服务，并且相互通信正常，那么这个机器就可以持续的提供日志持久化和查询服务。
将每条日志的持久化流程都看作一个“Paxos Instance”，不同的logID代表不同的Paxos Instance形成的“决议（decision）”。即每一个logID标识着一轮完整paxos协议流程的执行，最后形成decision。机群内的每个server同时作为paxos的acceptor和proposer。
获取LogID
Server收到客户端的持久化日志请求后，先要决定这条日志的logID，为了尽量减少后续Paxos协议流程中处理并发冲突造成的回退，要尽量分配与目前已经持久化和正在持久化中的日志不重复的logID，同步也要容忍少于半数的server宕机与网络故障。因此向所有acceptor查询它们本地目前已写盘的最大logID，而只需收集到majority返回的结果，并选择其中最大的logID+1作为本次待持久化日志的logID。从上面的描述可以看出，这里并不能保证并发提交的两条日志一定被分配到不同的logID，而是依靠后续的paxos协议流程来达到对一个logID形成唯一的decision的目的。
产生ProposalID
获取LogID后，server作为proposer开始针对当前logID，执行Paxos Instance，先产生proposalID，根据paxos协议的要求，proposalID要满足全局唯一和递增序，即对同一个server来说后产生的proposalID一定大于之前产生的，这里我们使用server的timestamp联合ip作为proposalID，其中timestamp在高位，ip在低位，只要时钟的误差范围小于server重启的时间，就可以满足“同一个server后产生的proposalID一定大于之前产生的”。
Prepare阶段
Proposer准备好proposalID后，将proposalID作为 “提案（proposal）”发送给所有的acceptor。根据Paxos协议P1b的约束，这个阶段发送的proposal并不需要携带日志内容，而只需要发送proposalID。Acceptor收到proposal后，根据Paxos协议P1b判断是否要“回应（response）”：只有在这个Paxos Instance内（即针对这个logID）没有response过proposalID大于等于当前proposal的，并且也没有“接受（accept）”过proposalID大于当前proposal的，才可以response，并承诺不再accept那些proposalID小于当前proposal的。
如果已经accept过proposal，那么连同proposalID最大的日志内容一同response。为了遵守P1b的约束，在宕机恢复后也能满足，因此在response前，需要将当前proposalID写到本地磁盘。
上述Prepare阶段的处理流程暗示，对于分配到相同logID的不同日志，由于他们的proposalID不同，acceptor在response一个较小proposalID后，是允许继续response后来的较大的proposalID的。
Accept请求阶段
Proposer收集到majority的response后，来决定后续是否将要发出的“accept请求（accept request）”，判断如果majority的response中的日志内容都为空，那么可以向所有acceptor发出accept request并携带上当前日志内容；而如果有任意的response中的日志内容有效，那么说明当前logID已经别其他日志占用，且其他日志可能已经在majority上持久化，因此需要回退，回到第一步“获取logID”重新执行。
Accept处理阶段
Acceptor收到proposer的accept request后，根据上文中“Prepare阶段”的承诺，判断当前logID下，曾经response过的最大proposalID，如果小于等于当前proposal的，则可以继续执行后续的accept处理逻辑；而如果大于当前proposal的，则说明有logID切proposalID更大的proposal在并发执行，当前proposal会被覆盖，因此回复proposer要求回退到第一步“获取logID”重新执行。
然后Accept处理逻辑将当前proposal连同proposalID一起写到本地磁盘，给proposer回复成功。Proposer收集到majority的回复成功后，说明本条日志已经在机群上持久化成功，可以保证后续一定不会被覆盖或丢失，可以给客户端返回了。
上述accept处理阶段的流程暗示，可能会存在针对一个logID，日志只在少于半数的acceptor上写到本地磁盘，而acceptor同时response了proposalID更大的proposal，而使得当前logID下没有任何日志在机群上持久化成功。即一个logID可能没有标识任何有效日志，这种情况是可以接受的。
日志内容读取
已经在机群上持久化成功的日志，需要能够被读取出来，一般的应用模式是按照logID的顺序依次读取并回放日志。读取的时候针对每一条logID，需要执行一轮完整的paxos协议流程，将accept处理阶段成功的日志内容返回。需要注意的是，在accept请求阶段的处理逻辑变化：Proposer收集到majority的response后，判断如果majority的response中的日志内容都为空，那么向所有acceptor发出日志内容为空的accept request；而如果有任意的response中的日志内容有效，则选择proposalID最大的日志内容放入accept request。后续收到majority的accept回复成功后，才可以返回日志内容作为读取结果。
这里的流程暗示，针对一个logID，如果之前已经有日志内容持久化成功，那么这条日志一定会被选为accept request；而如果之前日志内容仅仅在小于半数的server上写到磁盘，那么最终这条logID的内容有可能是有效日志，也有可能内容为空。
为什么读取也需要执行Paxos流程
这是基于一致性的考虑，即针对一条logID，读取出的内容后续应该永远不变。因此如果一条logID在写入过程中，并未在majority上持久化，那么需要在读取返回结果前，将这个结果在机群上持久化成功。
