Paxos 算法是第一个被证明完备的分布式系统共识算法。共识算法的作用是让分布式系统中的多个节点之间对某个提案Proposal达成一致的看法。提案的含义在分布式系统中十分宽泛像哪一个节点是 Leader 节点、多个事件发生的顺序等等都可以是一个提案。兰伯特当时提出的 Paxos 算法主要包含 2 个部分:Basic Paxos 算法描述的是多节点之间如何就某个值(提案 Value)达成共识。Multi-Paxos 思想描述的是执行多个 Basic Paxos 实例就一系列值达成共识。Multi-Paxos 说白了就是执行多次 Basic Paxos 核心还是 Basic Paxos 。由于 Paxos 算法在国际上被公认的非常难以理解和实现因此不断有人尝试简化这一算法。到了 2013 年才诞生了一个比 Paxos 算法更易理解和实现的共识算法—Raft 算法 。更具体点来说Raft 是 Multi-Paxos 的一个变种其简化了 Multi-Paxos 的思想变得更容易被理解以及工程实现。针对没有恶意节点的情况除了 Raft 算法之外当前最常用的一些共识算法比如ZAB 协议、Fast Paxos算法都是基于 Paxos 算法改进的。针对存在恶意节点的情况一般使用的是工作量证明POWProof-of-Work、权益证明PoSProof-of-Stake 等共识算法。这类共识算法最典型的应用就是区块链就比如说前段时间以太坊官方宣布其共识机制正在从工作量证明(PoW)转变为权益证明(PoS)。区块链系统使用的共识算法需要解决的核心问题是拜占庭将军问题这和我们日常接触到的 ZooKeeper、Etcd、Consul 等分布式中间件不太一样。下面我们来对 Paxos 算法的定义做一个总结Paxos 算法是兰伯特在1990年提出了一种分布式系统共识算法。兰伯特当时提出的 Paxos 算法主要包含 2 个部分: Basic Paxos 算法和 Multi-Paxos 思想。Raft 算法、ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进而来。Basic Paxos 算法问题假设一个集群包含三个节点 A, B, C提供只读 key-value 存储服务。只读 key-value 的意思是指当一个 key 被创建时它的值就确定下来了且后面不能修改。客户端 1 和客户端 2 同时试图创建一个 K 键。客户端 1 创建值为 baili 的 K 客户端 2 创建值为 百里 的 K 。在这种情况下集群如何达成共识实现各节点上 K 的值一致呢角色Basic Paxos 中存在 3 个重要的角色提议者Proposer也可以叫做协调者coordinator提议者负责接受客户端的请求并发起提案。提案信息通常包括提案编号 (Proposal ID) 和提议的值 (Value)。接受者Acceptor也可以叫做投票员voter负责对提议者的提案进行投票同时需要记住自己的投票历史学习者Learner如果有超过半数接受者就某个提议达成了共识那么学习者就需要接受这个提议并就该提议作出运算然后将运算结果返回给客户端。为了减少实现该算法所需的节点数一个节点可以身兼多个角色即一个节点既可以是提议者也可以是接受者。并且一个提案被选定需要被半数以上的 Acceptor 接受。这样的话Basic Paxos 算法还具备容错性在少于一半的节点出现故障时集群仍能正常工作。算法流程在 Paxos 算法中使用提案表示一个提议提案包括提案编号和提议的值。接下来我们使用 [n, v] 表示一个提案其中 n 是提案编号 v 是提案的值。在 Basic Paxos 中集群中各个节点为了达成共识需要进行 2 个阶段的协商即准备Prepare阶段和接受Accept阶段。Paxos算法包含两个阶段第一阶段Prepare(准备)、第二阶段Accept(接受)。prepare(准备)阶段假设客户端 1 的提案编号是 1客户端 2 的提案编号为 5并假设节点 A, B 先收到来自客户端 1 的准备请求节点 C 先收到来自客户端 2 的准备请求。客户端作为提议者向所有的接受者发送包含提案编号的准备请求。注意在准备阶段请求中不需要指定提议的值只需要包含提案编号即可。接下来节点 AB 接收到客户端 1 的准备请求提案编号为 1节点 C 接收到客户端 2 的准备请求提案编号为 5。
