Paxos 算法是 Leslie Lamport莱斯利·兰伯特在 1990 年提出了一种分布式系统 共识 算法。这也是第一个被证明完备的共识算法（前提是不存在拜占庭将军问题，也就是没有恶意节点）。
为了介绍 Paxos 算法，兰伯特专门写了一篇幽默风趣的论文。在这篇论文中，他虚拟了一个叫做 Paxos 的希腊城邦来更形象化地介绍 Paxos 算法。
不过，审稿人并不认可这篇论文的幽默。于是，他们就给兰伯特说：“如果你想要成功发表这篇论文的话，必须删除所有 Paxos 相关的故事背景”。兰伯特一听就不开心了：“我凭什么修改啊，你们这些审稿人就是缺乏幽默细胞，发不了就不发了呗！”。
于是乎，提出 Paxos 算法的那篇论文在当时并没有被成功发表。
直到 1998 年，系统研究中心 (Systems Research Center，SRC）的两个技术研究员需要找一些合适的分布式算法来服务他们正在构建的分布式系统，Paxos 算法刚好可以解决他们的部分需求。因此，兰伯特就把论文发给了他们。在看了论文之后，这俩大佬觉得论文还是挺不错的。于是，兰伯特在 1998 年重新发表论文 《The Part-Time Parliament》。
论文发表之后，各路学者直呼看不懂，言语中还略显调侃之意。这谁忍得了，在 2001 年的时候，兰伯特专门又写了一篇 《Paxos Made Simple》 的论文来简化对 Paxos 的介绍，主要讲述两阶段共识协议部分，顺便还不忘嘲讽一下这群学者。
《Paxos Made Simple》这篇论文就 14 页，相比于 《The Part-Time Parliament》的 33 页精简了不少。最关键的是这篇论文的摘要就一句话：The Paxos algorithm, when presented in plain English, is very simple.
翻译过来的意思大概就是：当我用无修饰的英文来描述时，Paxos 算法真心简单！
有没有感觉到来自兰伯特大佬满满地嘲讽的味道？
Paxos 算法是第一个被证明完备的分布式系统共识算法。共识算法的作用是让分布式系统中的多个节点之间对某个提案（Proposal）达成一致的看法。提案的含义在分布式系统中十分宽泛，像哪一个节点是 Leader 节点、多个事件发生的顺序等等都可以是一个提案。
兰伯特当时提出的 Paxos 算法主要包含 2 个部分:
由于 Paxos 算法在国际上被公认的非常难以理解和实现，因此不断有人尝试简化这一算法。到了 2013 年才诞生了一个比 Paxos 算法更易理解和实现的共识算法—Raft 算法 。更具体点来说，Raft 是 Multi-Paxos 的一个变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现。
针对没有恶意节点的情况，除了 Raft 算法之外，当前最常用的一些共识算法比如 ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进的。
针对存在恶意节点的情况，一般使用的是 工作量证明（POW，Proof-of-Work）、 权益证明（PoS，Proof-of-Stake ） 等共识算法。这类共识算法最典型的应用就是区块链，就比如说前段时间以太坊官方宣布其共识机制正在从工作量证明(PoW)转变为权益证明(PoS)。
区块链系统使用的共识算法需要解决的核心问题是 拜占庭将军问题 ，这和我们日常接触到的 ZooKeeper、Etcd、Consul 等分布式中间件不太一样。
下面我们来对 Paxos 算法的定义做一个总结：
假设一个集群包含三个节点 A, B, C，提供只读< key-value 存储服务。只读 key-value 的意思是指，当一个 key 被创建时，它的值就确定下来了，且后面不能修改。
客户端 1 和客户端 2 同时试图创建一个 K 键。客户端 1 创建值为 "baili" 的 K ，客户端 2 创建值为 "百里" 的 K 。在这种情况下，集群如何达成共识，实现各节点上 K 的值一致呢？
Basic Paxos 中存在 3 个重要的角色：
为了减少实现该算法所需的节点数，一个节点可以身兼多个角色，即一个节点，既可以是提议者，也可以是接受者。并且，一个提案被选定需要被半数以上的 Acceptor 接受。这样的话，Basic Paxos 算法还具备容错性，在少于一半的节点出现故障时，集群仍能正常工作。
在 Paxos 算法中，使用提案表示一个提议，提案包括提案编号和提议的值。接下来，我们使用 [n, v] 表示一个提案，其中， n 是提案编号， v 是提案的值。
在 Basic Paxos 中，集群中各个节点为了达成共识，需要进行 2 个阶段的协商，即准备（Prepare）阶段和接受（Accept）阶段。
Paxos算法包含两个阶段，第一阶段Prepare(准备)、第二阶段Accept(接受)。
假设客户端 1 的提案编号是 1，客户端 2 的提案编号为 5，并假设节点 A, B 先收到来自客户端 1 的准备请求，节点 C 先收到来自客户端 2 的准备请求。
客户端作为提议者，向所有的接受者发送包含提案编号的准备请求。注意在准备阶段，请求中不需要指定提议的值，只需要包含提案编号即可。
接下来，节点 A，B 接收到客户端 1 的准备请求（提案编号为 1），节点 C 接收到客户端 2 的准备请求（提案编号为 5）。
集群中各个节点在接收到第一个准备请求的处理：
接下来，当节点 A，B 接收到提案编号为 5 的准备请求，节点 C 接收到提案编号为 1 的准备请求：
总结一下：
接受者在收到提案后，会给与提议者两个承诺与一个应答：
当客户端 1，2 在收到大多数节点的准备响应之后会开始发送接受请求。
当节点 A, B, C 接收到客户端 1, 2 的接受请求时，对接受请求进行处理：
如果集群中还有学习者，当接受者通过一个提案，就通知学习者，当学习者发现大多数接受者都通过了某个提案，那么学习者也通过该提案，接受提案的值。
总结一下：
当提议者收到了多数接受者的接受应答后，协商结束，共识决议形成，将形成的决议发送给所有学习节点进行学习。
所以Paxos算法的整体详细流程如下：
上面例子中，准备阶段和接受阶段均不存在接受者已经通过提案的情况。这里继续使用上面的例子，不过假设节点 A, B 已通过提案 [5, "百里"]，节点 C 未通过任何提案。 增加一个新的提议者客户端 3，客户端 3 的提案为 [8，""] 。
接下来，客户端 3 执行准备阶段和接受阶段。
客户端 3 向节点 A, B, C 发送提案编号为 8 的准备请求：
节点 A, B 接收到客户端 3 的准备请求，由于节点 A, B 已通过提案 [5, "百里"]，故在准备响应中，包含此提案信息。
节点 C 接收到客户端 3 的准备请求，由于节点 C 未通过任何提案，故节点 C 将返回“尚无提案”的准备响应。
客户端 3 接收到节点 A, B, C 的准备响应后，向节点 A, B, C 发送接受请求。这里需要特点指出，客户端 3 会根据响应中的提案编号最大的提案的值，设置接受请求的值。由于在准备响应中，已包含提案 [5, "百里"]，故客户端 3 将接受请求的提案编号设置为 8，提案值设置为 "百里" 即接受请求的提案为 [8, "百里"]：
节点 A, B, C 接收到客户端 3 的接受请求，由于提案编号 8 不小于三个节点承诺可以通过的最小提案编号，故均通过提案 [8, 百里]。
概括来说，Basic Paxos 具有以下特点：
Paxos算法有什么缺点吗？怎么优化？
Basic Paxos 算法只能对单个值达成共识，对于多个值的情形，Basic Paxos 算法就不管用了。因此，Basic Paxos 算法几乎只是用来理论研究，并不直接应用在实际工作中。
Lamport 提出的 Multi Paxos 是一种思想，并不是算法。
Multi Paxos 算法则是一个统称，是指基于 Multi Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（例如 Raft 算法等）。
如果直接通过多次执行 Basic Paxos 实例方式，来实现一系列值的共识，存在以下问题：
为了解决以上问题，Multi Paxos 引入了领导者（Leader）和优化了 Basic Paxos 的执行过程。
上面的问题一存在多个提议者同时提交准备请求的情况，如果引入了领导者，由领导者作为唯一的提议者，就可以解决问题一中的冲突的问题。
Lamport 没有说明如何选举领导者，需要在实现 Multi Paxos 算法的时候自行实现。这里我们略去如何选举领导者的算法，假设已经选举出领导者。
准备阶段的意义，是发现接受者节点上已通过的提案的值。引入领导者后，只有领导者才可发送提议，因此，领导者的提案就已经是最新的了，不再需要通过准备阶段来发现之前被大多数节点通过的提案，领导者可以独立指定提议的值。
这样一来，准备阶段存在就没有意义了，领导者可以直接跳过准备阶段，直接进行接受阶段，减少了 RPC 通讯次数。
Google 分布式锁 Chubby 实现了 Multi Paxos 算法。Chubby 的 Multi Paxos 算法主要包括：
注意：Multi-Paxos 只是一种思想，这种思想的核心就是通过多个 Basic Paxos 实例就一系列值达成共识。也就是说，Basic Paxos 是 Multi-Paxos 思想的核心，Multi-Paxos 就是多执行几次 Basic Paxos。
由于兰伯特提到的 Multi-Paxos 思想缺少代码实现的必要细节(比如怎么选举领导者)，所以在理解和实现上比较困难。因此，Multi Paxos 的算法实现，是建立在一个未经证明的基础之上。实现 Multi Paxos 算法，最大的挑战是如何证明它是正确的。
不过，也不需要担心，并不需要自己实现基于 Multi-Paxos 思想的共识算法，业界已经有了比较出名的实现。像 Raft 算法就是 Multi-Paxos 的一个变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现，实际项目中可以优先考虑 Raft 算法。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。