分布式算法入门之 Paxos 算法
0 前言
Distributed Consensus Algorithm
There is only one consensus protocol, and that's “Paxos” — all other approaches are just broken versions of Paxos
世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本。
—— Mike Burrows，Inventor of Google Chubby
莱斯利-兰伯特（Leslie Lamport）于 1990 年提出的一种基于消息传递的分布式一致性算法 Paxos ，选的论文题目就是“The Part-Time Parliament。该算法具有高度容错特点，是目前公认的解决分布式一致性问题最有效的算法之一。
Lamport 用一个特殊的场景来描述这种一致性算法需要解决的问题，及具体的解决过程：
在古希腊有一个叫做 Paxos 的小岛，岛上采用议会的形式来通过法令，议会中的议员通过信使进行消息的传递。
但问题在于，议员和信使都是兼职的，他们随时都可能会离开会议厅，并且信使可能会重复的传递消息，也可能会一去不复返。因此，议会会议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。
前后写了三篇论文来解释该算法：
Basic-Paxos
Multi Paxos
Fast Paxos
1 一致性问题与共识问题
提高分布式系统，就不得不提到分布式系统领域的核心问题：一致性问题与共识问题。
1.1 什么是一致性问题
举个平常生活中的例子。当一条线路的火车票发售时，大家可以选择在 12306 或者不同售票点购买这条线路上的火车票，而该线路存在多个车站，每个人要购买的起点和终点也不尽相同，怎么能保证在任意车站区间都不会出现超售（即同一个座位卖给两个人）的情况呢？
这个就是一致性，即数据保持一致，可以理解为多个节点中数据的值是一致的。
1.2 那么什么是共识问题呢？
共识描述分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。所以，一致性是结果，共识机制是手段。可以简单举个类似的例子理解一下。假如今晚约定大家在广州塔见面。大家都同时出现在广州塔或者大家都没出现在广州塔这两种情况都是可能的（一致性是结果）；
达到这样的一致结果状态的方法是大家建了一个微信群随时保持联系或者大家互相打电话（共识是手段）。
注意：一致性并不代表正确与否，所有节点都达成失败状态也是一种一致。
1.3 一致性算法的目的
保证多个节点之间的命令按照相同的顺序，保证所有的副本最终得到相同的值。
2 Basic-Paxos
Basic-Paxos 算法提供了一种机制，使分布式系统能够在发生网络分区或服务器故障时以可预测的方式继续工作。只要客户端应用程序可以与分布式系统中的关键角色进行通信，那么分布式存储就可以像线程安全的数据结构一样具有可预测的功能。
2.1 角色介绍
Paxos 定义了几个不同的角色，这些角色必须合作才能达成共识。他们相互合作以集体商定一个提议的值。
这三个角色分别是：
Client（客户端）：请求发起者，是属于系统外部角色
Proposer（提案者）：接收 Client 请求，向集群提出提议。起到冲突调节的作用
Acceptor（接受者）：提出议票和接受者，只有在行程法定人数（Quorum）时，提议才会最终被接受。（仲裁系统）
Learner（学习者： 提议接受者，备份功能，不参与投票，只接受达成共识的值，对集群一致性没有影响
2.2 步骤和阶段
Paxos 是一种算法，它使一组分布式计算机（例如，分布式数据库节点群集）能够通过异步网络达成共识。为了达成协议，一台或多台计算机向 Paxos 提出了一个值。当大多数运行 Paxos 的计算机同意其中一个提议的值时，就实现了共识。
一般而言，Paxos 从建议的一个或多个值中选择一个值，然后将该值广播到所有合作计算机。Paxos 算法运行后，所有计算机（或数据库节点）都同意建议的值，并且群集时钟向前。
Paxos 的四个步骤：
1、Prepare
Proposer 提出一个提案，编号为 N，此 N 大于这个 Proposer 之前提出提案编号，并向接受者进行广播该请求。
2、Promise
这个编号 N 将会跟公认提案者的最高数字进行对比，如果 N 大于此接受者之前接收的任何提案编号则接受，否则拒绝。
3、Accept
如果提案者收到大多数接受者的答复后，提案者会向所有的接受者发出 acceptor 请求，此请求包含提案编号 N 和提案内容
4、Accepted
如果此接受者在此期间没有收到任何大于 N 的提案，则接受此提案的内容，否则忽略
2.3 NoSQL 实现方式
Paxos 通过投票的概念实现了它的许多属性。选票是与每笔交易相关联的有效唯一标识符。例如，在 NoSQL 数据库的情况下，例如，选票是基于 64 位时钟读数，随机位序列和机器 ID 的 128 位 UUID。这使得所有选票都是独一无二的，并按时间顺序排列。Paxos 选票是针对每个分区键独立跟踪的。这既是优势，也是劣势。针对不同分区的事务之间缺乏协调会增加总体吞吐量和可用性，但不会提供任何相互顺序。因此，事务不能跨分区。
选票以及其他协议状态存储在所有副本的本地系统表 system.paxos 中。事务完成后，将修剪掉此状态的大部分内容。但是，如果事务中途失败，则状态将保留预配置的持续时间（默认情况下设置为 10 天）。DBA 应在节点工具过期之前运行节点工具修复。
执行交易的节点（也称为协调器）首先创建一个新的选票，并要求拥有相应令牌范围数据的节点来存储它。如果副本比他们已经知道的选票更旧，则副本拒绝存储选票，而如果副本没有大多数响应，则协调员拒绝继续。此多数规则可确保一次只有一个事务在修改数据，并且协调器在建议新事务之前，会了解最新的更改。
一旦协调器收到接受新值的大多数承诺，它就会评估轻量级事务条件，并向所有副本发送新行。
最后，当大多数副本接受并保留其 system.paxos 表中的新行时，协调器指示它们将更改应用于基表。在任何时候，某些副本都可能失败。即使没有失败，复制品也可能拒绝投票，因为他们已经向不同的协调员做出了承诺。在所有这些情况下，协调员都会进行重新投票，并可能进行新的投票。完成所有步骤后，协调器请求参与者从中间协议状态修剪 system.paxos。修剪作为后台任务执行。
3 算法缺点
领导节点冲突
如果同一时间有两个节点竞争领导节点，各自有自己的提案，可能会导致不断的修改和重复提交。同理，如果两个节点都被选择为提案者，每个节点都提出一个给定数字，但都失败了，然后各自尝试给出更高的数字，然后冲突后失败。这就会导致所有的节点都不能得到一个统一的结果。
活锁
如果来自不同的节点传入的请求高于接受率，每一个请求都会被带有更高数字的新请求所拒绝，这就会导致即使系统启动并运行了，也不会提出任何新的请求，这种情况就是活锁。
实现难，效率低（2 轮 RPC ）
Basic Paxos 只能对单个值形成决议，并且决议的形成至少需要两次网络请求和应答（准备和批准阶段各一次，2 轮 RPC），高并发情况下将产生较大的网络开销。
4 总结
Basic Paxos 的价值在于开拓了分布式共识算法的发展思路，Basic Paxos 是一个学术化的算法，给后续的分布式算法提供了理论基础。实际的应用都是基于 Multi Paxos 和 Fast Paxos 算法的，各大公司都基于该算法实现了自己的 Paxos 工业届实现，如腾讯微信后台团队的PhxPaxos。
推荐阅读：
版权声明: 本文为 InfoQ 作者【宇宙之一粟】的原创文章。
原文链接:【http://xie.infoq.cn/article/9743482bfcf414420981786e4】。文章转载请联系作者。
宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入
🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖，江湖却没有我的影子 热爱技术，专注于后端全栈，轻易不换岗 拒绝内卷，工作于软件工程师，弹性不加班 热衷分享，执着于阅读写作，佛系不水文
评论