3.7.2　Paxos协议

Paxos协议用于解决多个节点之间的一致性问题。多个节点之间通过操作日志同步数据，如果只有一个节点为主节点，那么，很容易确保多个节点之间操作日志的一致性。考虑到主节点可能出现故障，系统需要选举出新的主节点。Paxos协议正是用来实现这个需求。只要保证了多个节点之间操作日志的一致性，就能够在这些节点上构建高可用的全局服务，例如分布式锁服务，全局命名和配置服务等。

为了实现高可用性，主节点往往将数据以操作日志的形式同步到备节点。如果主节点发生故障，备节点会提议自己成为主节点。这里存在的问题是网络分区的时候，可能会存在多个备节点提议（Proposer，提议者）自己成为主节点。Paxos协议保证，即使同时存在多个proposer，也能够保证所有节点最终达成一致，即选举出唯一的主节点。

大多数情况下，系统只有一个proposer，他的提议也总是会很快地被大多数节点接受。Paxos协议执行步骤如下：

1）批准（accept）：Proposer发送accept消息要求所有其他节点（acceptor，接受者）接受某个提议值，acceptor可以接受或者拒绝。

2）确认（acknowledge）：如果超过一半的acceptor接受，意味着提议值已经生效，proposer发送acknowledge消息通知所有的acceptor提议生效。

当出现网络或者其他异常时，系统中可能存在多个proposer，他们各自发起不同的提议。这里的提议可以是一个修改操作，也可以是提议自己成为主节点。如果proposer第一次发起的accept请求没有被acceptor中的多数派批准（例如与其他proposer的提议冲突），那么，需要完整地执行一轮Paxos协议。过程如下：

1）准备（prepare）：Proposer首先选择一个提议序号n给其他的acceptor节点发送prepare消息。Acceptor收到prepare消息后，如果提议的序号大于他已经回复的所有prepare消息，则acceptor将自己上次接受的提议回复给proposer，并承诺不再回复小于n的提议。

2）批准（accept）：Proposer收到了acceptor中的多数派对prepare的回复后，就进入批准阶段。如果在之前的prepare阶段acceptor回复了上次接受的提议，那么，proposer选择其中序号最大的提议值发给acceptor批准；否则，proposer生成一个新的提议值发给acceptor批准。Acceptor在不违背他之前在prepare阶段的承诺的前提下，接受这个请求。

3）确认（acknowledge）：如果超过一半的acceptor接受，提议值生效。Proposer发送acknowledge消息通知所有的acceptor提议生效。

Paxos协议需要考虑两个问题：正确性，即只有一个提议值会生效；可终止性，即最后总会有一个提议值生效。Paxos协议中要求每个生效的提议被acceptor中的多数派接受，并且每个acceptor不会接受两个不同的提议，因此可以保证正确性。Paxos协议并不能够严格保证可终止性。但是，从Paxos协议的执行过程可以看出，只要超过一个acceptor接受了提议，proposer很快就会发现，并重新提议其中序号最大的提议值。因此，随着协议不断运行，它会往“某个提议值被多数派接受并生效”这一最终目标靠拢。