大螃嗨

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
=====Paxos=====

1990 年由 Leslie Lamport 提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统中，Leslie Lamport 因此获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

Paxos 是第一个被证明的共识算法，其原理基于 两阶段提交 并进行扩展。

作为现在共识算法设计的鼻祖，以最初论文的难懂（算法本身并不复杂）出名。算法中将节点分为三种类型：
  * proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；
  * acceptor：负责对提案进行投票。往往是服务端担任该角色；
  * learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。

并且，算法需要满足 safety 和 liveness 两方面的约束要求（实际上这两个基础属性是大部分分布式算法都该考虑的）：
  * safety：保证决议结果是对的，无歧义的，不会出现错误情况。
    * 决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；
    * 在一次执行实例中，只批准（chosen）一个最终决议，意味着多数接受（accept）的结果能成为决议；
  * liveness：保证决议过程能在有限时间内完成。
    * 决议总会产生，并且 learners 能获得被批准（chosen）的决议。

基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。

Paxos 能保证在超过 1/2 的正常节点存在时，系统能达成共识。

读者可以试着自己设计一套能达成共识的方案，会发现在满足各种约束情况下，算法自然就会那样设计。

====单个提案者+多接收者====

如果系统中限定只有某个特定节点是提案者，那么一致性肯定能达成（只有一个方案，要么达成，要么失败）。提案者只要收到了来自多数接收者的投票，即可认为通过，因为系统中不存在其他的提案。

但一旦提案者故障，则系统无法工作。

====多个提案者+单个接收者====

限定某个节点作为接收者。这种情况下，共识也很容易达成，接收者收到多个提案，选第一个提案作为决议，拒绝掉后续的提案即可。

缺陷也是容易发生单点故障，包括接收者故障或首个提案者节点故障。

以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。

当提案者和接收者都推广到多个的情形，会出现一些挑战。

====多个提案者+多个接收者====

为了解决这个问题，就必须要用到一种多数选择的方法。使用一个Acceptor的集合。然后只有其中的多数批准了一个值，这个值才可以确实是被最终被批准的。为了达到目的也需要一些技巧。
===批准第一个达到的值===
首先规定每个Acceptor必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值

{{:wiki:paxos1.png?nolink&600|}}

但是有一个问题，比如上图，因为没有值被多数批准，无法批准一个最终的值出来。这就需要Acceptor批准了一个值之后还要根据某种规则批准不同的值
===批准每个提议的值===
接下来规定Acceptor批准每个提议的值，但是这也会带来一个问题，可能会批准出多个值

{{:wiki:paxos2.png?nolink&600|}}

如图，S1发出提议，S1，S2，S3批准red为最终批准的值。S5随后发出提议，s3，S4，S5批准，blue又为最终批准的值。此时S1，S2最终批准red，S3，S4，S5最终批准blue，这就违背了我们的一致性原则，最终只有一个值被选择。
===二段提交原则===
要解决这个问题，就要S5在发送自己的提议之前，优先检查有没有已经被批准的值，如果有应该提议已经被批准的值而放弃自己的值，也就是放弃自己的blue改为提议red，这样最终只有一个值被批准就是red。这个就是经典的二段提交原则。

不幸的是，二段提交还是存在另一个问题。

{{:paxos3.png?nolink&600|}}

如图，S1在发送提议之前，检查没有值被批准，因此提议red。但同时在所有Acceptor批准之前，S5也要进行提议，这个时候也检查出没有值被批准，所以它也把自己的blue作为提议发送给acceptor。接下来S5的提议优先到达S3，S4，S5，这些Acceptor先批准了blue，达到多数所以blue最终被批准了。但是随后S1，S2，S3接收到了red进行批准。所以又出现了批准出多个值的问题。

====两阶段的提交====

提案者发出提案之后，收到一些反馈。这个时候得知的一种结果是自己的提案被大多数接受了，一种结果是没被接受。没被接受的话好说，过会再试试。

即便受到来自大多数的接受反馈，也不能认为就最终确认了。因为这些接收者自己并不知道自己刚反馈的提案就恰好是全局的绝大多数。

很自然的，引入了新的一个阶段，即提案者在前一阶段拿到所有的反馈后，判断这个提案是可能被大多数接受的提案，需要对其进行最终确认。

Paxos 里面对这两个阶段分别命名为准备（prepare）和提交（commit）。准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。

准备阶段：
  * 提案者发送自己计划提交的提案的编号到多个接受者，试探是否可以锁定多数接受者的支持。
  * 接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（如果还未接受过任何提案，则为空）给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。
  
提交阶段：
  * 提案者如果收到大多数的回复（表示大部分人听到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功。则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求。
  * 接受者收到接受消息后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。
  
一旦多数接受了共同的提案值，则形成决议，成为最终确认。
====相关链接====
  * [[https://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D|一步一步理解paxos]]