理解paxos协议

  本文的目的是一步步讲解paxos如何是如何推断和完备的。首先要了解，分布式一致性（consistency）和分布式共识（consensus）并不是一个东西来的，然而网上大部分的人都直接把分布式共识翻译为分布式一致性，导致像paxos，raft这样的算法被误认一致性算法，并拿来跟2pc，3pc做比较，这是不对的。之前我也一直存在疑惑，有次吃饭的时候跟同导师的一个小哥聊天的时候，他一语道破，虽然不属于官方的解释，但是理解起来却格外的清晰：

一致性是要求所有的节点一致，共识算法是只要大部分节点承认

  还是得说明，这个并不是官方解释，在笔者找到更合适的说法前，暂时先用这个代替。分布式共识算法要解决的问题是什么，在分布式的情况下，我们经常会把数据分布到不同的节点上，如何来保证这些数据尽可能达成一致就是paxos要解决的问题了。在论文的一开始，作者就讲明了分布式共识算法要达成的目标。(ps：如果存在理解不正确的地方，欢迎指出，谢谢)

• 达成一致的结果一定是由某个进程或者某个应用提出来的，而不是实现约定的结果。
• 最后要达成一致表明只有一个值能被选中
• 第三点是指，只有已经被选中的值才能被其他不参与决策的人知道，属于learner的功能，不多细讲。

  为了简单的来讲解整个过程，我决定把文中提及的三种觉得拟人化。首先负责提议的称为<font color="#0f88eb">议员(proposal)</font>，负责决策的是<font color="#0f88eb" >选民(acceptor)</font>，负责学习的是<font color="#0f88eb" >群众(learner)</font>。有几个约束，各个角色之间互相通信是利用异步消息队列，可能存在不可达甚至宕机重启的现象，但是没有拜占庭错误（也就是有偷懒睡觉的，但是没有叛徒，不会修改消息内容）。且我们规定提案只有经过大多数人同意才能确定下来（也就是超过半数的人）。首先来看第一条约束

• P1：选民必须接受他收到的第一个提案(An acceptor must accept the first proposal that it receives).

  为什么有这么一条呢？为了达成一致，直观的想法都是，如果接收到了一个消息我就选择accept这个消息，因为我没有合适的拒绝策略。就类似于，每次议员提出一个提案，底下的所有选民就都同意了，除了那些打瞌睡的不知道这件事的除外。之所以有这一条约束，我觉得最主要的原因是目前我们无法给出一个合适的拒绝策略。但是这个选择策略很明显也是有问题的，如果此时有多个议员同时提出提案，然后底下的选民们分别接受到了不同的提案并回复了，但是由于选民分散导致没有一个提案能被大多数的代表选中，这样就导致了选举失败(存在活锁现象)。所谓活锁就是一直在提议却一直无法选择出最终结果。那么如果要满足P1的约束，且要求一定要有大多数的选民都同意一个提案，则催生了另一个条件，选民可以选择多个提案。比如A，B两个议员同时提出了两个提案，作为选民k的你，可以在同意A的提案之后，又同意B的提案。不过这样你肯定又会问，新的选择策略就是全选吗？肯定不行的，于是作者提出，在提案的基础上，我们加入一个全局的编号，这个编号全局有序，谁编号大就选谁，这样最公平（至于提案如何生成这个编号，不在论文的讨论范围，但是我还要啰嗦句，具体实现中，这个编号的生成是很巧妙，不是随意递增就可以的，而且这个编号是后文判断的基础，非常重要）。瞎逼逼了这么多，就是为了说明一点，我们没有合适的拒绝策略/选择策略所以选择第一个达到的提案，但是为了保证一定会有值能选出，则需要可以选民具有选择多个提案的能力(很多情况下并没有一个绝对有效的拒绝策略，那么换种思路就是多样化的选择策略，但是最终只有一个能成功)。
  那么我们如何保证一致性呢？来看看另一个新的约束

• P2：如果一个提案(with value=v，number=n)被选中，那么后续编号大于n的所有被选中的提案必须包含value=v。(If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.)

  P2其实是个很强的约束，如果我们能保证在一次paxos选举中，如果已经有一个能被大多数acceptor接受的结果，那么我们就应该坚定不移的坚持这个结果，自然能获得最终一致性。从前文来看，选举中即使再次发生新提案，如果要通过还是需要acceptor的接受的。那么P2的变种说法就是：

• P2a：(If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.)

  P2a和P2的区别就是在提案那里加了一个定语，所以其实两种说法是相同的，因为提案要想被接受，必然需要有大多数的acceptor去接受这个提案。但是存在一种场景，假设一个proposer宕机了，然后重启后，发布了一个提案(高编号，但是值不同)，此时刚好存在一些好死不死的acceptor，也是没有收到任何的提案，然后这两个一拍即合的就选择了这个新提案(根据P1)。但是根据P2，这些acceptor不应该接受这样的提案，也就冲突了。其实就是缺少对于proposer的限制。所以需要增强下P2，对实现对proposer的限制(也避免P1和P2之间的冲突)：

• P2b：If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

  跟P2a很相似，也是针对提案加了定语，但是这里的issue却是一个非常重要的过程，论文后面才会讲到，先按下不表。先来说说，这个跟上一个有什么不同。首先，issue是发生在accept前面的，accept的提案一定是issue过了，但是issue的提案就不一定能被accept了(issue的提案只是在第一阶段被选中，但是为了最终一致性可能会舍弃)。P2b->P2a是没有问题的，而且看起来P2b的限制更强了。那么提案在issue的时候，就必须要求带有已经被选中的value这一点，使得压力不用放在acceptor那里(因为这里发送出去的时候，就表明是个已经被大多数acceptor接受的结果，acceptor只要对比本地的结果就可以最终确认了)。
  那么如何去保证P2b呢，只要在一次paxos提案中，如果已经有一个value被大多数的acceptor接受，那么后续更高编号的proposal就必须带有value = v。这个要求每个在提出新的proposal的proposer，都要收集本次提案中，是否已经有被大多数acceptor接受的提案，有的话，就做个顺水人情，帮他完成掉这个提案。那么就催生了一个新的条件：

• P3c：For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

  简单来说，那就是，之所以有大多数集的acceptor接受了这个提案，这些acceptor的组成是，(a).从来没有接受过比n小的提案，这样都会接受，就说明这是P1导致的结果，因为从来没有接受过提案，那么n作为第一个到来的提案，自然可以接受了。(b).v是编号小于n的提案里面，被接受的编号最大的那个提案的值，这是为了满足P2，做个顺水人情嘛。到这里，基本整个算法的流程就算是差不多了。但是到这里，读者可能会疑问，好像不知道编号有什么大的作用的，虽然说选大的编号，但是仅仅是上述的说法，不带编号好像可以，来看看算法的基本流程就明白了。

• prepare阶段：一个proposer选择一个新的编号，然后发送一个prepare请求给所有的acceptors，要求他们回应

1. 承诺不再接受编号小于n的提案。

2. 如果有存在已经接受的提案，请把提案和编号发给我

   • accept阶段：如果一个proposer接收到了大多数acceptors的回应说可以。那么proposer就要issue这个提案（with number n，value v），这里v的选择就根据P2c来，如果prepare阶段没有返回任何的已经接受的提案的话，那么就有proposer随机选择。如果有返回，那就在里面选择编号最大的一个的提案中的值来作为v。然后将这个提案封装后发送给acceptors

  这个就是算法的过程，仔细来看，每个proposer可以发起两次请求，而每个acceptors可以接收两次请求，做出两次回应。首先对于acceptors来说，acceptor首先可以无视任何一次请求(也就是超时或者宕机)都不会造成任何安全性的影响。那么在响应的时候呢，acceptor可以响应所有的prepare请求(不管是拒绝也好，接受也好)。但是对于accept请求的话，如果已经承诺过不接受的话，那么就不能相应自己要接受这个请求。也就是说：

• P1a：An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

  一个acceptor只有在没有接受过其他编号大于n的prepare请求的情况下，才能接受一个编号为n的请求。这个约束是可以推倒出P1的，因为，如果他没有接受过任何请求，那么就可以接受任何请求了。到这里，P1，P2两个约束其实是相互扶持的P1决定第一次该怎么做，P2决定后续该怎么做。
  算法到这里就算是全部结束了，但是这只是理论上的实现，实际编码则需要做相应的优化，比如编号的产生，比如acceptor在相应的时候反馈一些有用的信息使得proposer能停止自己过时的操作等。但是，这个算法是存在活锁的问题的。假如现在有两个proposers，A，B，A先发起了prepare阶段并获得了大多数的支持，然后紧接着B带着更高编号的来了知道A已经获得支持，但是由于B编号更大可以获得大多数的支持。紧接着A进入accept阶段，发现，大家都接受了更高编号，尴尬了，于是马上发起新一轮的prepare阶段，换了更大编号的。同样B在进入accept阶段的时候也发现了这个问题，于是两个proposers相互更新编号，即使协议已经达成一致却一直无法更新。这就是活锁问题，论文后续提出，为了解决活锁问题，最好引入一个leader proposer，由这个leader来发起提议。但是leader选举本身也是一个paxos问题。

内容参考：Paxos Made Simple，paxos算法 - 维基百科，csdn的一篇博客