Paxos算法

本篇文章主要主要是对paxos的算法思想的学习，是一片学习笔记，文章内容主要来自于极客时间分布式系统原理与实战课程中关于paxos的相关内容。

Basic Paxos

Basic Paxos 中，有提议者（Proposer）、接受者（Acceptor）、学习者（Learner）

Proposer : 提议一个值，用于投票表决。绝大多数场景中，集群中收到客户端请求的节点，才是提议者. 该角色代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；

Acceptor: 对每个提议的值进行投票，并存储接受的值，比如 A、B、C 三个节点。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；

学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份.学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。

Basic Paxos算法通过一个决议主要分为以下几个阶段：

• 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
• 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
• 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

  

主要流程为：

Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。

当Acceptors收到Prepare的请求之后，承诺当前的Acceptors不再接受Proposal ID小于等于当前请求的Prepare请求。

当Acceptors收到Prepare的请求之后，承诺当前的Acceptors不再接受Proposal ID小于当前请求的Propose请求。

同时当前Acceptors会回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

Propose: Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。

Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。

Learn: Proposer收到多数Acceptors的Accept后，决议形成，将形成的决议发送给所有Learners。

Mutli-Paxos

Basic Paxos 只能就单个值（Value）达成共识，一旦遇到为一系列的值实现共识的时候，它就不管用.

兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。

单纯用多次Basic Paxos实现一系列值的共识，就存在以下几个问题：

• 如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。一个 5 节点的集群，如果 3个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。

• 2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大

  而真正的Mutli-Paxos算法基于Basic Paxos做了两点改进：

• 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。
• 在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过