Paxos协议初探

前言

如果世界上只有一种分布式一致性算法，那就是Paxos。Paxos是出了名的晦涩难懂。
Paxos有点类似2PC和3PC，但是它解决了这两种算法存在的问题。
先简要介绍下2PC和3PC的做法和缺陷：

两阶段提交（2PC）

从名字上可以看出两阶段提交分为两个阶段：Propose和Commit。

• Propose阶段：
  • 协调者：发起提议；
  • 投票者：同意或否决提议；
• Commit阶段：
  • 协调者：根据提议发起最终commit；

  • 投票者：进行最终的commit；

    
    两阶段提交

缺点：2PC不能处理fail-stop问题，即当在第二阶段时，如果协调者和其中一个投票者（voter3）crash了，那其他投票者将会一直阻塞等待直到接收到消息为止，这个时候就需要人工手动重启协调者；在这种情况下，其他投票者不能区分第一阶段中voter3是反对了提议还是同意了提议。

三阶段提交（3PC）

3PC解决了上述2PC的问题，把Commit阶段分成了PreCommit和Commit结算，相当于在Commit操作之前加了个屏障，这个屏障相当于告诉所有投票者，所有投票者都收到了propose的结果；当协调者在PreCommit之前crash，则voters可以认为不是所有voters收到propose结果，从而放弃commit或者选择新的协调者；如果协调者在PreCommit之后crash，则每个voter可以放心的Commit，因为已经默认所有voters都收到propose结果了。
缺点：3PC可以处理fail-stop的问题，但是不能处理网络划分和fail-recover问题。
网络划分：当有多个机器处于不同的网络中，并且网络之间不能通信，那协调者crash之后，两个网络会选出不同的新的协调者。
fail-recover：当协调者crash之后，选出新的协调者；当老的协调者重启后，新老协调者对同一个投票者可能发送不同的指令，投票者的状态出现分歧。

Paxos

概念

Paxos is a mechanism for achieving consensus on a single value over unreliable communication channels.

简单的来说就是：Paxos就是在一个不稳定的网络环境中对一个值达成一致。

Paxos解决的问题

Paxos诞生于古希腊Paxos岛上的多个法官在一个大厅对一个议案进行表决，如何达成统一结果的故事。
Paxos解决的问题是如果在一个机器宕机或者网络异常等异常的分布式系统中，快速且正确的再集群内部对某个数据值达成一致，并且保证异常不会破坏整个系统的一致性。（Paxos没办法抵抗恶意行为的节点，比如一个节点故意返回一个相反的结果，Paxos没办法解决这样的问题，因此Paxos没办法解决拜占庭将军问题，除非加上各种校验）。

协议过程

基本角色

Paxos协议有三个角色：

• Proposer：提议发起者；
• Acceptor：提议接受者；
• Learner：提议学习者；

协议推导过程

分布式一致性问题：
假设有一组可以提出value的进程集合；一致性算法需要保证提出的这么多的value中，只有一个value被选定，其他进程都应该能学习到这个被选定的值；这样所有的进程都最终保存相同的值。

分布式一致性基本要求：
安全性：只有被提出的值才能被选定，只有一个value被选定；
活性：值最终会被选择，并且所有进程都会最终学习到这个值；

推导过程：
Proposer是提议的发起者，不能决定最终选择的值，因此我们从Acceptor角色看起；
假设只有一个Acceptor，只要Acceptor接收到第一个提议，该提议就被选定，这样可以保证只有一个value被选定，但是如果机器宕机了，这唯一的Acceptor就不工作了，达不到问题的最终结果；因此必须有多个Acceptor。（paxos协议解决了机器宕机的问题）

如果是多个Acceptor的情况，怎么保证多个Proposer和多个Acceptor下选定一个唯一的value?
假设Acceptor只要接收到第一个提议，就选中；则每个Acceptor都会选中一个唯一的value；但是由于多个Proposer提出的value会有不同，这样根据不同的网络速度，每个Acceptor选中的值不一样，不成立。
因此，Acceptor选择第一个值的约束不成立。这就意味着，Acceptor不能单纯的选择第一个值，那么提议的值必然是要有区分，这样才能区分Acceptor接收的是哪个值。

提议的提案={提议的值+提议的编号}。

由于Acceptor不单纯选择第一条提案，那么Acceptor就是可以接收多条提案，并从中选择一条作为最终值，如果有N个节点的Acceptor，要保证N个节点选定的是同一个值，这样的概率非常低，因此有了另一个约定：

Acceptor可以接收多个提案，但是不需要全部都是同一个值，而是半数以上是同一个值，就最终确定这个值，就是典型的少数服从多数的原则。

有了少数服从多数的原则，我们就可以标记多数选择的值为最终的一致值；但是少数服从多数还会带来一个问题：如果有三个节点选择了提案1；三个节点选择了提案2；其余都是小众；那就出现了平票的场景。这样的场景最终该选择哪个提案？
这个就需要决定提案1和提案2的优先级；因此提议的编号我们设置成自增。这样就诞生了一个约定：

如果一个编号的提议值V被选择，那么每个编号更高（编号是自增的）的被Acceptor接受的提案的值必须是V。

协议描述

基于上述的约定，Paxos算法大致如下，和两阶段有点类似：

• 第一阶段：
• Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求；
• 如果一个Acceptor接收到提案编号N，并且这个N大于该Acceptor已经响应过的所有编号；那么它就会将已经响应的最大编号的值返回给Proposer；同时该Acceptor承诺不再接收比N小的提案；
• 第二阶段：
• 如果Proposer收到半数以上的Acceptor对其发出的编号为N的Prepare请求响应，那么它就会发送一个[N,V]的Accept请求给半数以上的Acceptor。其中V就是响应编号中最大的提案的那个值。如果没有提案，则Proposer自行决定。
• 如果Acceptor收到一个针对编号为N的提案的Accept的请求，只要该Acceptor没有对比N大的Prepare请求做过响应，它就接收该提案。

Paxos过程

Learner角色

如果计算机网络中节点非常多的话，广播一次所有节点将消耗大量的性能；因此我们可以只适用一部分的节点应用Paxos协议；然后当Acceptor接受最终提案后，就将最终的提案大宋给Learner；Learner的做法有好几种：

• 提案发给所有Learner；
• 提案发给一个主Learner，然后主Learner再发给其余Learner；
• 提案发给一个Learner集合；然后集合再发给其他Learner；
  几种做法各有优缺点，这里不详细讨论。

主Proposer

上述的协议保证了基本要求中的安全性；但是还存在活性的问题：
如果两个Proposer先后提出了顺序递增的提案，那么整个过程将陷入一个死循环中；
比如Proposer1提出了N=1的提案完成了第一阶段；这个时候Proposer2提出了N=2的提案也继续完成了第一阶段；那么这个时候Proposer1进行第二阶段会失败，它会再次发起N=3的提案；Proposer2进行第二阶段也失败，它会进行N=4的提案；这样就会不停的死循环下去。
因此，Proposer也需要进行一个主次的分别。

协议证明

Paxos协议最终解决了当一个提议被多数接受后，这个提议的值被选定；那么这个值就是分布式一致的；后续所有进程选择的都是同一个值。
其实，Paxos就是一个数学问题，我们来看下数学证明：

原命题

如果一个提议{N0,V0}被多数Acceptor接受，那么不会存在提议{N1,V1}被大多数Acceptor接受，其中N0<N1，并且V0!=V1；

证明

不妨用反证法：
假设存在{N1,V1}符合条件，并且N1是满足条件最小的提议编号。
那么提议N0，N0+1，N0+2 。。。。N1-1编号对应的值都为V0；
由于存在{N1,V1}，说明N1被半数以上的Acceptor接受，并承诺不会接受比N1小的编号；
又因为存在{N0,V0}，说明N0也被半数以上的Acceptor接受，并承诺不会接受比N0小的编号；
所以，存在一个Acceptor即接受了N1，又接受了N0；
由Paxos协议得知，这个Acceptor一定是先接受了N0，再接受了N1；
所以在发出{N1,V1}这个提议的Proposer在发出{N1,V1}之前，有一个共识；必然存在一个N>=N0，并且值为V0的提议被接受；这个时候这个Proposer会从所有的Acceptor返回值中选择一个编号最大的作为发送的请求；因此会选择一个N>=N0,并且值为编号最大的值V0；
因此，就有V0==V1；矛盾，所以不存在该{N1,V1};

参考文档

[1] Paxos made simple论文
[2] The Part-Time Parliament论文