Paxos算法是分布式一致性的代名词，可以说是最难理解的算法。 本文试图用通俗易懂的语言解释 Paxos 算法。
Paxos 算法是由 Grandmaster Lamport 提出的一种基于消息的分布式共识算法，该算法获得了 2013 年图灵奖。
Paxos 于 1998 年由 Lamport 首次发表在 The Part-Time Parliament** 上，最初的描述以希腊的 Paxos 岛为隐喻来描述在 Paxos 岛上通过决议的过程，并以此命名算法，但描述难以理解。 后来，在 2001 年，Lamport 觉得他的同龄人无法理解他的幽默感，于是他重新发布了一个严肃的算法描述版本 Paxos Made **
Paxos 自成立以来就垄断了分布式共识算法，Paxos 一词几乎是分布式一致性的代名词。 Google 的许多大型分布式系统都使用 PaxOS 算法来解决分布式一致性问题，例如 Chubby、MegaStore 和 Spanner。 开源 ZooKeeper 和 MySQL 5为取代传统主从复制而推出的MySQL Group Replication，采用了PaxOS算法来解决分布式一致性问题。
然而，PaxOS最大的特点是难，不仅难理解，而且难实现。
PaxOS算法解决的问题恰恰是分布式一致性问题，即分布式系统中的进程如何就某个值（分辨率）达成一致。
PaxOS 算法在异步系统中运行，该系统允许停机，不需要可靠的消息传递，并且可以容忍消息丢失、延迟、乱序和重复。 它利用多数机制来确保 2f+1 容错，即 2f+1 系统允许多达 f 个节点同时发生故障。
一个或多个提案者可以发起提案，Paxos算法可以在所有流程中就所有提案中的一个达成一致。 系统中的大多数人同时同意该提案，即同意该提案。 至多应就一项已确定的提案达成一致意见。
Paxos 将系统中的角色分为提议者、接受者和学习者
proposer：提出建议。 提案信息包括提案 ID 和提案的值。 acceptor：参与决策，回应提案人的建议。 提案收到后即可被接受，如果提案被多数接受者接受，则称该提案获得批准。 learner：不参与决策，向投标人、接受者了解最新商定的提案价值。 在多副本状态机中，每个副本同时具有三个角色：提议者、接受者和学习者。
Paxos 算法中的角色。
PaxOS 算法通过分辨率将 Paxos 算法分为两个阶段（分辨率在学习阶段之前形成）：
第 1 阶段：准备阶段。 提议人向受理人提出准备请求，接受人对收到的准备请求作出承诺。 第 2 阶段：接受阶段。 提议人收到大多数接受人的承诺后，向接受人发送提议请求，接受人接受收到的提议请求。 第 3 阶段：学习阶段。 提案人收到大多数接受者的接受后，标志着接受成功，并形成决议，并将形成的决议发送给所有学习者。 
Paxos 算法流程。
PaxOS 算法流程中的每条消息描述如下：
prepare：提议者生成一个全局唯一且递增的提议 ID（您可以使用时间戳和服务器 ID）向所有接受者发送准备请求。 promise：接受者收到准备请求后，做出“两个承诺，一个回答”。 两个承诺：
准备提案 ID 小于或等于（注意：此处为 <= 此处）的请求，不再接受当前请求。 提案 ID 小于（注意：此处<）的提案请求将不再被接受。 一个答案：
在不违反先前承诺的情况下，回复已接受提案中提案 ID 最大的提案的值和提案 ID，如果没有，则返回 null 值。
propose：提议者收到大多数接受者的承诺响应后，从回复中选择提案 ID 最大的提案值作为要发起的提案。 如果所有响应的提案值为空，则可以随意决定提案值。 然后携带当前提案 ID，并向所有接受者发送提案请求。 accept：接受方收到提案请求后，在不违反其先前承诺的情况下接受并保留当前提案 ID 和提案值。 learn：提案人获得大多数接受者的接受后，形成决议，并将形成的决议发送给所有学习者。 Paxos 算法伪**描述如下：
Paxos 算法伪**。
获取提案ID n，为了保证提案ID唯一，可以通过时间戳+服务器ID生成; 提议者向所有接受者广播准备（n）请求; 接受者比较 n 和 minproposal，如果 n>minproposal， minproposal=n，则返回 acceptedproposal 和 acceptedvalue; 在收到超过一半的回复后，如果提议者发现返回了 acceptedValue，则所有回复中 AcceptedProposal 最大的 AcceptedValue 将作为提案的值，否则可以任意确定提案的值。 从这里可以进入第二阶段，向所有节点广播接受（n，value）; 接受者比较 n 和 minproposal，如果 n>=minproposal，则 acceptedproposal=minproposal=n，acceptedvalue=value，局部持久化后返回; 否则，将返回 minproposal。 在收到一半以上的请求后，如果提议者发现结果>n的返回值，则表示有更新的提案，跳转到1;否则，该值是商定的。 以下是一些示例，示例 1 如下所示：
Paxos 算法示例 1
在图中，p 表示准备阶段，a 表示接受阶段。 3.1 表示提案 ID 为 31，其中 3 是时间戳，1 是服务器 ID。 x 和 y 表示建议值。
第 3 页中的示例 11 获得多数，其值 （x） 被接受，然后 p 45 学习 value（x） 并接受。
Paxos 算法示例 2
实例 2 中的第 3 页1 不被多数人接受（只有 S3 接受），但 P 45 学习，第 4 页5 将其值替换为 y 和 x， accept（x）。
Paxos 算法示例 3
第 3 页中的实例 31 不被多数人接受（只有 S1 接受），也不被 P 4 接受5 学会了。 由于第 4 页5 提出，如果没有返回值，则 p 45 可以接受自己的值 （y）。 后续工作 p 3接受 1 的 （x） 将失败，已经接受的 s1 将被覆盖。
PaxOS 算法可以形成永无止境的活锁，如以下示例所示：
PaxOS 算法形成一个活锁。
回顾这两个承诺之一，接受方不再回答提案 ID 小于或等于当前请求的准备请求。 表示如果提案 ID 大于当前请求，则需要应答 Prepare 请求。
两个提议者交替准备成功和接受失败，形成一个活锁。
基本的Paxos算法只能在一个值上形成一个解析，而解析的形成至少需要两次网络往返，在高并发的情况下，可能需要更多的网络往返，在极端情况下，甚至可能形成活锁。 如果要确定连续的多个值，Basic PaxOS 将无法解决问题。 因此，Basic PaxOS 几乎完全用于理论研究，而不是直接应用于实际工程。
在实践中，几乎总是需要连续确定多个值，并且希望提高效率。 Multi-Paxos 就是为了解决这个问题而设计的。 Multi-PaxOS 基于 Basic PaxOS，并进行了两项改进：
对于要确定的每个值，运行 Paxos 算法的实例以形成分辨率。 每个 PaxOS 实例都使用唯一的实例 ID 进行标识。 在所有提案者中选出一名领导者，领导者将提案唯一地提交给接受者进行投票。 这消除了提议者的竞争，解决了活锁问题。 如果系统中只有一个领导者提交一个值，则可以跳过准备阶段，从而将两个阶段变成一个阶段并提高效率。 
Multi-Paxos 进程。
Multi-PaxOS 首先需要选出一个领导者，而一个领导者的确定也是决策的形成，所以可以执行一个基本的 Paxos 实例来选举领导者。 领导当选后，只有领导才能提交提案，领导下台后服务暂时不可用，需要连任才能继续服务。 如果系统中只有一位领导者提交提案，则可以跳过准备阶段。
Multi-PaxOS 将准备阶段的范围改为后续 leader 提交的所有实例，让 leader 的后续提交只需要执行一次准备阶段，后续阶段只需要执行接受阶段，将两个阶段变成一个阶段，提高效率。 为了区分连续提交的多个实例，每个实例都由一个实例 ID 标识，该 ID 由领导者在本地递增。
Multi-PaxOS 允许多个自认为领导者的节点在不影响其安全性的情况下同时提交提案，这是对 Basic PaxOS 的降级。
Chubby 和 Boxwood 都使用 Multi-Paxos。 ZooKeeper 使用的 zab 也是 multi-paxos 的变体。
PaxOS算法的设计过程从正确性开始，对于分布式一致性问题，很多进程提出（提出）不同的值，共识算法保证最后只选择一个值，安全性表示如下：
只能选择建议的值。 只一选择值。 该过程将仅被告知已确认选择的值。 Paxos 的设计就以这些约束为出发点，只要算法最终满足这些约束，就不需要证明正确性。 PaxOS 算法中有三种类型的参与者：提议者、接受者和学习者，实现中的每个过程通常同时扮演所有三个角色。
投标人向承兑人提出建议，以保证最多只有一提案必须被半数以上的接受者接受，每个接受者只能接受一个值。
为了正常运行（必须接受一个值），Paxos 算法：
p1：接受者必须接受它收到的第一个提案。
先到先得，价格合理。 但这就产生了一个问题，如果一个以上的提案人同时提出，很可能不会达成一致，因为没有一个提议被超过一半的接受者接受，因此，接受者必须能够接受多个提案，不同的提案用不同的数字来区分，当一个提案被超过一半的接受者接受时， 这个提案被选中了。
由于接受者被允许接受多个提案，因此最终可能会选择多个不同的值，这违反了安全要求
P2：如果选择了值为 V 的提案，则任何具有较高数字的选定提案也必须具有 V 值。
只要算法同时满足p1跟p2，安全有保障。 p2这是一个宽泛的约定，根本没有算法细节，我们将进一步扩展它：
P2A：如果选择值为 V 的提案，那么对于所有接受者来说，他们接受的任何具有较高数字的提案也必须具有 V 值。
如果满意p2a那么你一定满意p2，显然，因为只有先被接受才有可能最终被选中。 但p2a它仍然很难实现，因为接受者很可能不知道之前选择的提案（恰好在接受它的大多数人之外），所以它走得更远：
P2B：如果选择值为 V 的提案，那么对于所有提案者来说，任何具有更高数字的提案也必须具有 V 值。
再往前走：
P2C：为了提出一个值为 v 且数量为 n 的提案，必须有一组包含一半以上接受者的 s，满足 （1） s 中没有一个接受者接受过数量小于 n 的提案，或 （2） v 并且 s 中的接受者接受了数量少于 n 的提案数量最多。
满意p2c即满意p2b即满意p2a即满意p2。至此，Paxos 提出了 Proposer 的执行流程，以满足：p2c
提议者选择一个新的数字 n 并向超过一半的接受者发送请求信息，接受者回复：（a） 承诺不接受数量小于 n 的提案，以及 （b） 它接受的人数小于 n 的最大提案（如果有的话）。 该请求称为准备请求。 如果提议者收到半数以上接受者的答复，则可以提出一个提案价值的提案，该提案的价值是收到的答复中编号最多的，如果没有这样的价值，它可以自由提出任何价值。 向收到回复的接受者发送接受请求，要求他们接受提议的提案。 仔细看看 Proposer 的执行过程，它非常适合p2c，但你可能也注意到了，当多个提议者同时运行时，可能会出现无法成功接受提案的情况（第一步是随着数量的增加交替完成），这就是 Paxos 算法的活体问题，或者说是“livelock”，建议通过向提议者介绍主算法来选择杰出的提议者，以提出解决这个问题的提案， 但即使在多个提议者同时提出的情况下，Paxos 算法也可以保证安全。
让我们来看看接受者的执行过程，以及我们对此的处理p2做和我们一样的事情p1进行扩展：
p1a：当且仅当接受者没有回复具有较大数字的准备消息时，接受者才能接受编号为 n 的提案。
容易看到，p1a是的p1，对于接受者：
当收到准备请求时，如果其编号 n 大于先前收到的准备消息，则会回复该请求。 当收到接受请求时，它接受提案，并且仅当它没有回复具有较大数字的准备消息时才进行回复。 以上涵盖了满意度p1a跟p2b一整套一致性算法。