分布式协议与算法——Paxos算法

Paxos算法

Paxos论文 Paxos Made Simple 、author：Leslie Lamport（兰伯特）

Paxos算法是一种共识算法，一些常用的共识算法都是基于它改进的，如Fast Paxos算法、Cheep Paxos算法、Raft算法等。Paxos算法包含2个部分：

1. Basic Paxos算法，描述的是多节点之间如何就某个值（提案 value）达成共识。
2. Multi-Paxos算法，描述的是执行多个Basic Paxos实例，就一系列值达成共识。

Basic Paxos算法

实现一个分布式集群，这个集群由多个组成。现有多个客户端（客户端1、客户端2）访问这个集群，试图创建同一个只读变量（如X），客户端1试图创建值为3的X，客户端2试图创建值为7的X。那如何达成共识，实现各节点上X值的一致呢？使用Paxos算法。

Paxos算法中有一些独有而且比较重要的概念：提案、准备请求、接受请求、角色等。其中角色是对Basix Paxos中最核心三个功能的抽象。

三种角色

在Basic Paxos中，有提议者（Proposer）、接受者（Acceptor）、学习者（Learner）三种角色。

• 提议者：提议一个值，用于投票表决。在绝大多数场景下，集群中收到客户端的请求的节点是提议者（而不是客户端作为提议者），这样做的好处是对业务代码没有入侵性（不需要在业务代码中实现算法逻辑）。
• 接受者：对每个提议的值进行投票、并存储接受的值。一般来说，集群中所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。
• 学习者：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份的节点，被动地接受数据，容灾备份。

一个节点可以身兼多种角色。例如一个3节点的集群，1个节点收到了客户端的请求，那么该节点将作为提议者发起二阶段提交，然后这个节点和另外两个节点一起作为接受者进行共识协商。

这三种角色，本质上代表的是三种功能：

• 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商。
• 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存。
• 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。

如何达成共识（协商过程）

在Basic Paxos中，使用提案代表一个提议。在提案中，除了提案编号，还包含了提议值。如[n,v]表示一个提案，其中n为提案编号，v为提议值。

假设客户端1的提案编号为1，客户端2的提案编号为5；节点A、B先收到来自客户端1的准备请求，节点C先收到来自客户端2的准备请求。

提议者 一般由收到客户端请求的节点担任，这里为了便于理解，将客户端作为了提议者。你可以这样理解：每个客户端对应一个节点，其所对应的节点即担任提议者又担任接受者。所以下述的客户端1、2可以看成节点A、C。

准备（Prepare）阶段

第一个阶段是准备阶段。首先客户端1、2作为提议者，分别向所有接受者发送包含提案编号的准备请求。

在准备请求的时候不需要指定提议的值，只需要携带提案编号。

随后，节点A、B收到提案编号为1的准备请求，节点C收到提案编号为5的准备请求，进行以下处理。

• 由于之前没有通过任何提案，所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者，我之前没有通过任何提案呢，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。
• 节点 C 也是如此，它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。
  

随后，当节点A、B收到提案编号为5的准备请求，节点C收到提案编号为1的准备请求的时候，进行以下处理。

• 当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。
• 当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。