Paxos

云计算课程补充

概念

一个或者多个进程（节点）均对某个值，事件进行提议后，使得系统中所有进程（节点）对于这个值达成一致的意见

现实问题

在一个分布式系统中，由于节点故障、网络延迟等各种原因，根据CAP理论，我们只能保证一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance） 中的两个。
一致性问题，可以根据是否存在恶意节点分类两类。无恶意节点，是指节点会丢失、重发、不响应消息，但不会篡改消息。而恶意节点可能会篡改消息。有恶意节点的问题称为拜占庭将军问题，不在今天的讨论范围。Paxos很好地解决了无恶意节点的分布式一致性问题

分类

节点角色

  • proposer

  • acceptor

  • learner

所有节点参与协定的情况

  • 领导者选举：

  • 互斥操作

  • 原子广播

  • …

两个阶段

  • 提议阶段

  • 决策阶段

Basic-Paxos算法具体过程

两个注意点

  • acceptor不接受更低的贿赂

    • 不再接受 Proposal ID 小于等于minProposal的 prepare   请求，只接受更大的 prepare 请求

    • 不再接受 Proposal ID 小于minProposal的 proposal 请求。

  • proposer妥协

    • 即便在贿赂中胜出，也要被洗脑，把自己的提议value更改成别人已经 promise 了的value

第一阶段 决策

  • proposer选择一个提案编号n，然后向半数以上的acceptor发送编号为n的 prepare 请求

  • acceptor收到这个编号为n的 prepare 请求，value是N，如果n大于之前见到过的 prepare ，

    • 如果没有接受过其他accept请求 proposal ，那么就 promise 这个消息，并且承诺以后不会接受小于n的proposal ，更新自己本地的minProposal为n

    • 如果acceptor已经收到过一个小于n的编号是m的 proposal ，并且返回了 acceptance 那么 promise 就说自己已经接受过了m的 proposal ，acceptedValue是M，然后更新自己本地的minProposal为n

第二阶段 提议

  • 如果proposer收到半数以上acceptor对其发出的编号为n的prepare的响应 promise ，那么它就会发送一个accept（n，value）请求 proposal 给半数以上的acceptor。

    • 如果收到的 promise 中有其他的acceptedValue，那么就把 promise 中最大的那个 proposal 号所对应的value M来替换自己的value N，表示自己也接受这个M，然后发出新的accept(n,M)请求 proposal （proposer是会妥协的）

    • 如果没有，就把自己的N作为value（自己决定value），进行accept(n,N)请求 proposal 

  • 如果acceptor收到一个针对编号为n的提案的accept请求 proposal ，与本地保存的minProposal进行比较

    • 如果n大于等于minProposal，它就接受该提案（比之前贿赂的低的我都是不可能要的），并且更新自己保存的minProposal和acceptedValue，否则拒绝这个 proposal ，然后返回minProposal

  • 如果一个proposer接受到了半数以上的acceptor对于自己的accept请求 proposal 的 acceptance 回应 ，决议形成，将形成的决议发送给所有 Learners。

    • 如果没有收到半数以上，那么从阶段一开始重新 prepare ，编号n增加

举例1

下面这张图片的阶段一和阶段二与上文所述阶段一，阶段二不同

  • proposerA在最后自己的 proposal 被拒绝，没有形成多数的acceptance，然后编号n增加（上文的第一阶段+第二阶段），然后更改自己的Value的过程（重新返回第一阶段，然后妥协）

  • proposerB更加有钱，用更多的钱在 prepare 阶段贿赂了三个选民（3 1 2），然后在A的 proposal 失败用更多的钱重新贿赂，进行新的 prepare 的时候，抢在A的前面，用 proposal 提前赢得了两个选民的认可，最后迫使A妥协

举例2

https://www.zhihu.com/question/19787937/answer/107750652

活锁

两个proposers交替 Prepare 成功，而 proposal 失败，最后不断提高自己的编号进行尝试的过程

解决方案是在proposer失败之后给一个随机的等待时间，减少同时请求的可能

Multi-Paxos算法流程（没研究完）

原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。

Leader选举

具体参考http://thesecretlivesofdata.com/raft

  • 让有 最高 ID 的服务器作为领导者

  • 可以通过每个服务器定期（每 T ms）向其他服务器 发送心跳消息 的方式来实现。这些消息包含发送服务器的 ID

  • 如果它们没有能收到某一具有高 ID 的服务器的心跳消息，这个间隔（通常是 2T ms）需要设置的足够长，让消息有足够的通信传递时间。所以，如果这些服务器没有能接收到高 ID 的服务器消息，然后它们会自己选举成为领导者。

  • 也就是说，首先它会从客户端接受到请求，其次在 Paxos 协议中，它会 同时扮演 proposer 和 acceptor

  • 如果机器能够接收到来自高 ID 的服务器的心跳消息，它就不会作为 leader，如果它接收到客户端的请求，那么它会 拒绝 这个请求，并告知客户端与 leader 进行通信。

  • 非 leader 服务器不会作为 proposer，只会作为 acceptor

  • 这个机制的优势在于，它不太可能出现两个 leader 同时工作的情况，即使这样，如果出现了两个 leader，Paxos 协议还是能正常工作，只是不是那么高效而已。

  • 应该注意的是，实际上大多数系统都不会采用这种选举方式，它们会采用基于 租约 的方式（lease based approach），这比上述介绍的机制要复杂的多，不过也有其优势。

参考资料

https://zhuanlan.zhihu.com/p/31780743

https://liu-jianhao.github.io/2019/05/paxosmulti-paxos详解/