理工酷

Paxos算法解决分布式一致问题

Paxos中的节点角色

Proposer提案者

Proposer可以有很多个，Proposer提出Value。所谓Value，在工程中可以是任何操作。不同的Proposer可以提出不同的甚至矛盾的Value，例如某个Proposer提议“将变量X设置为1“，另一个Proposer提议“将变量X设置为2“，但是对同一轮Paxos过程，最多只有一个Value被批准。

Acceptor批准者

Acceptor有N个，Proposer提出的Value必须获得超过半数的Acceptor批准后才能通过。并且，Acceptor之间完全对等独立。

Acceptor批准者

Learner学习被批准的Value。所谓学习就是通过读取各个Proposer对Value的选择结果，如果某个Value被超过半数Acceptor通过，则Learner学习到了这个Value。这里类似议会机制，某个Value需要超过半数的Acceptor批准，Learner需要至少读取N/2+1个Acceptor的结果之后，能学习到一个通过的Value。 Paxos描述的就是在一个由多个Proposer和多个Acceptor构成的系统中，如何让多个Acceptor针对Proposer提出的多种提案达成一致的过程，而Learner只是“学习“最终被批准的提案。

Paxos中的约束条件

1.Acceptor必须接受它收到的第一个提案 2.如果一个提案的v值被大多数Acceptor接受过，那后续的所有被接受的提案之中也必须包含v值（v值可以理解为提案的内容，提案由一个或者多个v和提案编号组成） 3.如果某一轮Paxos协议批准了某个Value，则以后的各轮Paxos只能批准这个Value；每轮Paxos协议分为准备阶段和批准阶段，在这两个阶段Proposer和Acceptor有各自的处理流程

Paxos中的两个阶段

准备阶段

Proposer向网络内超过半数的Acceptor发送prepare消息；Acceptor正常情况下回复promise消息

批准阶段

有足够多Acceptor回复promise消息时，Proposer发送accept消息；正常情况下Acceptor回复accepted消息

Paxos中的选举过程

准备阶段

1.Proposer发送prepare请求。Proposer生成全局唯一且递增的ProposalID，向Paxos集群的所有机器发送Prepare 请求，这里不携带Value，只携带ProposalID。 2.Acceptor应答Prepare。收到Prepare请求后，判断：收到的ProposalID是否比之前已相应的所有提案的ProposalID大， 如果是，则： （1）在本地持久化ProposalID，可记为Max_ProposalID。 （2）回复请求，并带上已Accept的提案中ProposalID最大的Value（若此时还没有已Accept的提案，则返回的value是空） （3）做出承诺：不会Accept任何小于Max_ProposalID。的提案。 如果否：则不回复或者回复Error。

选举阶段

1.Proposer 发送Accept经过一段时间后，Proposer 收集一些Prepare回复，有下列几种情况： （1） 回复数量大于一半的Acceptor数量，且所有的回复Value都为空，则Proposer发出accept请求并带上自己指定的value （2） 回复数量大于一半的Acceptor数量，有的回复Value不为空，则proposer发出accept请求，并带上回复中ProposalID最大的value （3） 回复数量小于等于一半的Acceptor数量，则尝试更新生成更大的ProposalID 2. Acceptor应答accept，Acceptor收到Accept请求后判断： （1）收到的N大于等于Max_N（一般情况下是等于）。则回复提交成功，并持久化N和value （2）收到的N小于Max_N，则不回复或者回复提交失败 3. Proposer统计投票。经过一段时间后，Proposer收集到一些Acccept回复提交成功，有几种情况： （1）回复数量大于一半的Acceptor数量，则表示提交value成功。此时，可以发一个广播给所有Proposer、Learner，通知他们已commit的value （2）回复数量小于等于一半的Acceptor数量，则尝试更新生成更大的ProposalID。再转第一步进行 （3）收到一条提交失败的回复，则产生或更新生成更大的ProposalID再转第一步执行。