Paxos一致性算法

1. 概述

Paxos协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下，剩余的多数节点仍然能够达成一致。

Paxos协议是一个两阶段协议，分为Prepare阶段和Accept阶段，涉及三个参与者角色：Proposers、Acceptors和Learners。Proposers提出提案，提案信息包括提案编号和提议的 value；Acceptors 收到提案后可以接受（accept）提案，若提案获得多数 acceptors 的接受，则称该提案被批准（chosen）；Learners 只能“学习”被批准的提案。

2. Prepare阶段

• Prepare阶段1：Proposer发送Prepare请求

Proposer生成全局唯一且递增的提案ID，并向Paxos集群的所有机器发送请求，这里只需携带提案ID即可，无需携带提案内容（暂且把提案ID叫做Pn）。

• Prepare阶段2：Acceptor应答Prepare请求

Acceptor收到Prepare请求后，做出以下约定：

1. 不再应答 <=Pn 的Prepare请求
2. 对于 < Pn 的Accept请求也不处理

Acceptor对于Prepare请求，做以下处理：

1. 应答前要在本地持久化当前提案ID（Pn）
2. 如果现在请求的提案ID（Pn）大于此前存放的proposalID，则做以下逻辑：

if Pn > proposalID then proposalID = Pn

如果该Acceptor Accept过提案，则返回提案中proposalID最大的那个提案的内容，否则返回空值。

3. Accept阶段

• Accept阶段1：Proposer发送Accept请求

Proposer收集到多数派应答（多数派是指超过 n/2 + 1，n是集群数）Prepare阶段的返回值后，从中选择proposalID最大的提案内容，作为要发起Accept的提案，如果这个提案为空值，则可以自己随意决定提案内容。然后携带上当前proposalID，想Paxos集群的所有机器发送Accept请求。

• Accept阶段2：Acceptor应答Accept请求

Acceptor收到Accept请求后，检查不违背约定（上述约定①、②）的情况下，持久化当前proposalID和提案内容，最后Proposer收集到多数派应答的Accept回复后，形成决议。

4. 思考

Prepare阶段与Accept阶段是并行（即不同提案的Prepare和Accept请求并行执行）、持续的（在最终决议产生前，流程不会终止）：

比方说ProposerA生成一个提案P0，发送Prepare请求到所有的Acceptor，Acceptor在本地持久化当前提案ID，并向ProposerA应答，此时Acceptor处理的提案为P0。（如果同时有多个提案发送到Acceptor且先接收到提案Pn，则后续接收到的小于Pn的提案会被忽略。若P0提案的Prepare请求应答没有达到多数派，则P0提案作废，流程继续）

ProposerA如果接收到多数派的对提案P0的Prepare请求应答，则向Acceptor发送Accept请求并带上PO对应的ID，如果多数派Acceptor应答了该Accept请求，则形成决议。（如果Acceptor在应答PO提案的Prepare请求后，在应答P0提案的Accept请求之前继续应答其他大于P0的提案，则忽略对P0提案的Accept请求的应答。若提案P0的Accept请求应答没达到多数派，则P0提案作废，流程继续）