在正式学习一致性算法之前，先来看一个问题。

基于前面对分布式系统环境下一致性与共识算法的基础理论，在分布式系统中进行节点通信大部分采用基于消息传递通信模型，不可避免的会发生如进程可能会变慢、被杀死或者重启等问题，会对分布式系统中各节点对某一值达成一致性产生问题。

如何解决这一问题，这就要引出今天的主角——Paxos。

关于 Paxos

Paxos 算法是 Leslie Lamport（莱斯利·兰伯特open in new window）在 1990 年提出了一种分布式系统共识算法。这也是第一个被证明完备的共识算法（前提是不存在拜占庭将军问题，也就是没有恶意节点）。

为了介绍 Paxos 算法，兰伯特专门写了一篇幽默风趣的论文。在这篇论文中，他虚拟了一个叫做 Paxos 的希腊城邦来更形象化地介绍 Paxos 算法。

不过，审稿人并不认可这篇论文的幽默。于是，他们就给兰伯特说：“如果你想要成功发表这篇论文的话，必须删除所有 Paxos 相关的故事背景”。兰伯特一听就不开心了：“我凭什么修改啊，你们这些审稿人就是缺乏幽默细胞，发不了就不发了呗！”。

于是乎，提出 Paxos 算法的那篇论文在当时并没有被成功发表。

直到 1998 年，系统研究中心 (Systems Research Center，SRC）的两个技术研究员需要找一些合适的分布式算法来服务他们正在构建的分布式系统，Paxos 算法刚好可以解决他们的部分需求。因此，兰伯特就把论文发给了他们。在看了论文之后，这俩大佬觉得论文还是挺不错的。于是，兰伯特在 1998 年重新发表论文《The Part-Time Parliament》open in new window

论文发表之后，各路学者直呼看不懂，言语中还略显调侃之意。这谁忍得了，在 2001 年的时候，兰伯特专门又写了一篇《Paxos Made Simple》open in new window 的论文来简化对 Paxos 的介绍，主要讲述两阶段共识协议部分，顺便还不忘嘲讽一下这群学者。

《Paxos Made Simple》这篇论文就 14 页，相比于《The Part-Time Parliament》的 33 页精简了不少。最关键的是这篇论文的摘要就一句话：

The Paxos algorithm, when presented in plain English, is very simple.

翻译过来的意思大概就是：当我用无修饰的英文来描述时，Paxos 算法真心简单！

有没有感觉到来自兰伯特大佬满满地嘲讽的味道？

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性。

Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。

但是它也有两个明显的缺点：

难以理解
在工程是实现上比较复杂。

回到上面的问题，在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序还有网络分区）等情况。

Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

这里的某个数据并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令。根据场景的不同，某个数据的值有不同的含义。

Paxos 中的角色

在 Paxos 算法中，有三种角色：

Proposer (提案者)
Acceptor (人大代表)
Learners (广大群众)

需要注意的是，在具体的算法实现中，并不是一个进程只能担任一种角色，它有可能会同时充当多个。比如一个进程既是Proposer又是Acceptor还是Learner。

还有一个很重要的概念叫提案（Proposal），最终要达成一致的 value 就在提案里。

这个提案到底是什么？是仅仅包含一个信息数值吗？目前咱们先认为仅仅是一个普普通通的 value。

Paxos 算法过程和我国的立法过程是极其相似的（法律案的提出、法律案的审议、法律案的表决、法律的公布四个阶段），所谓的提案就是新颁布法律。

Proposer (提案者)可以提出（propose）提案；Accoptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被选定了。

回到刚刚说的『对某个数据的值达成一致』，指的是Proposer、Acceptor、Learner都认为同一个value被选定（chosen）。那么，Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢？

Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。
Acceptor：只要Acceptor接受了某个提案，Acceptor就认为该提案里的value被选定了。
Learner：作为一个学习者，Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。

问题产生

假设有一组可以提出（propose）value的进程集合（提案者团队），一个一致性算法需要保证提出的这么多value中，仅仅只有一个相同的value被选定（chosen）。也就是说要么没有value被提出，只要提出了value并且被选定，那么大家最终学习到的value必须是一致的。对于一致性算法，安全性（safaty）要求如下：

只有被提出的value才能被选定。
只有一个value被选定。
如果某个进程认为某个value被选定了，那么这个value必须是真的被选定的那个。

“Paxos的目标：保证最终有一个value会被选定，当value被选定后，进程最终也能获取到被选定的value。

如果假设不同角色之间可以通过发送消息来进行通信，那么：

每个角色以各自任意的速度进行通信执行，在这个过程中可能会因为各种原因出错而导致执行停止或重启。当一个value被选定之后，因为故障原因才恢复正常的角色因为失去了某些重要的信息，导致它们无法确定被选定的值。
消息在传递过程中可能出现任意时长的延迟，可能会重复，也可能丢失。但是消息不会被损坏，即消息内容不会被篡改（拜占庭将军问题）。

以上都是可能会遇到的问题，要怎么解决？？？

算法推导

最简单的方案——只有一个 Acceptor

假设只有一个 Acceptor（可以有多个 Proposer），只要 Acceptor 接受它收到的第一提案，则该提案被选定，该提案中的 value 就是被选定的 value。这样就保证只有一个 value 会被选定。

但是，如果唯一的 Acceptor 宕机了，那么整个系统就无法工作了！

因此，一个 Acceptor 是不可行的，必须要有多个 Acceptor！

多个 Acceptor

当有多个 Acceptor 的时候，如何保证在多个 Proposal 和多个 Acceptor 的情况下选定一个 value。

首先，我们的目标是无论有多少个 Proposal 提出天，有且仅有一个 value 被选定？

那么，我们可以先定义一个约束：

“P1：一个 Acceptor 必须接受它受到的第一个提案。”

但是，这样又会出现其他的问题：如果每个 Proposal 所提出的提案 value 是不同的，并且将提案发送给不同的 Acceptor。根据 P1 约束，每个 Acceptor 都接受它收到的第一个提案，就会出现不同的 value 被选定的情况不一样，出现了不一致。

为了解决新出现的问题，我们加入一个新的规定：

“规定：一个提案被选定需要半数以上的 Acceptor 接受”

一个提案被半数以上接受，说明『一个 Acceptor 必须能够接受不止一个提案！』，不然可能导致最终没有 value 被选定。比如上图的情况。v1、v2、v3都没有被选定，因为它们都只被一个 Acceptor 的接受，并没有被超过半数以上的 Acceptor 接受。

最开始将【提案 = value】已经无法满足现在的需求，因为当一个 Proposer 发送多个提案到一个 Acceptor 的时候，需要使用一个编号来区分被提出的顺序。现在【提案=提案编号+value】。

虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同的 value 值，否则又会出现不一致。

“P2：如果某个 value 为 v 的提案被选定了，那么每个编号更高的被选定提案的 value 必须也是 v”

一个提案只有被Acceptor接受才可能被选定，因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。

“P2a：如果某个 value 为 v 的提案被选定了，那么每个编号更高的被 Acceptor 接受的提案的 value 必须也是 v。”

只要满足了P2a，就能满足P2。

但是，考虑如下的情况：以立法过程为背景，假设总的有5个人大代表（Acceptor）。

人民法院（Proposer2）提出[M1,V1]的提案，人大代表2-5号（半数以上）均接受了该提案，于是对于人大代表2-5号和人民法院来讲，它们都认为V1提案是被选定的。此时，人大代表1在办完其它事务之后也参与到其中（之前人大代表1没有收到过任何提案），此时最高人民检察院（另一个提案者Proposer1）向人大代表1发送了[M2,V2]的提案（V2≠V1且M2>M1），对于人大代表1来讲，这是它收到的第一个提案。根据P1（一个Acceptor必须接受它收到的第一个提案。）,人大代表1必须接受该提案！同时人大代表1认为V2被选定。这就出现了两个问题：

人大代表1认为V2被选定，人大代表2-5和人民法院认为V1被选定。出现了不一致。
V1被选定了，但是编号更高的被人大代表1接受的提案[M2,V2]的value为V2，且V2≠V1。这就跟P2a（如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v）矛盾了。

所以，我们要对 P2a 约束进行加强。

P2a 是对 Acceptor 接受的提案约束，但其实提案是 Proposer 提出来的，所有我们可以对 Proposer 提出的提案进行约束。得到 P2b：

P2b：如果某个 value 为 v 的提案被选定了，那么之后任何 Proposer 提出的编号更高的提案的 value 必须也是 v。”

那么，如何确保在某个value为v的提案被选定后，Proposer提出的编号更高的提案的value都是v呢？

只要满足P2c即可：

“P2c：对于任意的 N 和 V，如果提案[N, V]被提出，那么存在一个半数以上的 Acceptor 组成的集合S，满足以下两个条件中的任意一个：

S中每个 Acceptor 都没有接受过编号小于 N 的提案。
S中 Acceptor 接受过的最大编号的提案的 value 为 V。”

Proposal 生成提案

为了满足 P2b，这里有个比较重要的思想：Proposal 生成提案之前，应该先去『学习』已经被选定或者可能被选定的 value，然后以该 value 作为自己提出的提案的 value。如果没有 value 被选定，Proposal 才可以自己决定 value 的值。这样才能达成一致。这个学习的阶段是通过一个『Prepare请求』实现的。

于是我们得到了如下的提案生成算法：

Proposal 选择一个新的提案编号 N，然后向某个 Acceptor 集合（半数以上）发送请求，要求该集合中的每一个 Acceptor 做出以下响应（response）。
- 向 Proposal 承诺保证不再接受任何编号小于 N 的提案。
- 如果 Acceptor 已经接受过提案，那么就向 Proposer 响应已经接受过的编号小于 N 的最大编号的提案。

我们将该请求成为编号 N 的 Prepare 请求。

如果 Proposer 收到半数以上的 Acceptor 的响应，那么它就可以生成编号为 N， Value 为 V 的提案[N, V]。
这里的 V 是所有的响应中编号最大的提案的 value。
如果所有的响应中都没有提案，那么此时 V 就可以由 Proposer 自己选择(一般为当前提案)。
生成提案后，Proposer 将该提案发送给半数以上的 Acceptor 集合，并期望这些 Acceptor 能接受该提案。我们称该请求为Accept请求。（注意：此时接受 Accept 请求的 Acceptor 集合不一定是之前响应 Prepare 请求的 Acceptor 集合）。

Acceptor 接受提案

Acceptor可以忽略任何请求（包括Prepare请求和Accept请求）而不用担心破坏算法的安全性。因此，我们这里要讨论的是什么时候Acceptor可以响应一个请求。

我们对Acceptor接受提案给出如下约束：

“P1a：一个Acceptor只要尚未响应过任何编号大于N的Prepare请求，那么他就可以接受这个编号为N的提案。”

如果Acceptor收到一个编号为N的Prepare请求，在此之前它已经响应过编号大于N的Prepare请求。根据P1a，该Acceptor不可能接受编号为N的提案。因此，该Acceptor可以忽略编号为N的Prepare请求。当然，也可以回复一个error，让Proposer尽早知道自己的提案不会被接受。

因此，一个Acceptor只需记住：

已接受的编号最大的提案
已响应的请求的最大编号。

算法描述

经过上面的推导，我们总结下Paxos算法的流程。

Paxos算法分为两个阶段。具体如下：

阶段一：

Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话） 作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

阶段二：

如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor（和之前的Acceptor不一定相同）。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

算法实现流程

提议者发出提案，发起一次投票，发现者接收到投票请求，讲提案发给参与者；
参与者接收到投票请求后，会对提案进行投票，投票正确时发送投票确认消息；
发起者收到参与者发回的投票确认消息，如果收到确认消息超过半数，则发起者发出 accept 消息，将提案接受；
参与者接收到 accept 消息后，如果投票正确，则发送 accept 确认消息；
发起者收到 accept 确认消息后，如果收到的 accept 确认消息超过半数，则发起者发出 commit 消息，将提案接受，并执行操作；
参与者接收到 commit 消息后，如果投票正确，则发送 commit 确认消息；
发起者收到 commit 确认消息后，如果收到的 commit 确认消息超过半数，则发起者发出 ack 消息，将提案接受，并将操作结果返回给发起者；
参与者接收到 ack 消息后，如果投票正确，则发送 ack 确认消息；
发起者收到 ack 确认消息后，如果收到的 ack 确认消息超过半数，则发起者发出完成消息，将提案接受，并将操作结果返回给发起者，完成 Paxos 算法。

一些问题

Learner 如何学习被选定的 value？

Learner学习（获取）被选定的value有如下三种方案：

方案一：

Acceptor接受到一个提案，就将该提案发送给所有 Learners.

优点：Learner 能够快速获取被选定的 value
缺点：通信次数为M*N（M为提案数，N为 Learner数）

方案二：

Acceptor接受一个提案，就将提案发送给主Learner，主 Learner 再通知其它 Learner

优点：通信次数减少（M+N-1）（M为提案数，N为Learner数，M个提案发送给主Learner，然后主Learner通知N-1个Learner）
缺点：单点故障问题（主Learner可能出现故障）

方案三：

Acceptor接受一个提案，就将提案发送给Learner**团**,Learner团再通知其它Learner

优点：解决了方案二单点故障问题，可靠性好
缺点：实现复杂，网络通信复杂度高

如何保证 Paxos 算法的活性？

通过选取主Proposer，就可以保证Paxos算法的活性。通过选取主Proposer，并规定只有主Proposer才能提出议案。这样一来只要主Proposer和过半的Acceptor能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准，这样通过选择一个主Proposer，整套Paxos算法就能够保持活性。至此，我们得到一个既能保证安全性，又能保证活性的分布式一致性算法——Paxos算法。

总结

Paxos算法十分重要，现在很多一致性算法都是由其演变过来的，在互联网时代分布式环境应用非常广泛。但在查询资料时发现学习难度还是比较大的，主要是因为大家的文章写得都不太一样，加上大多都是抽象的描述，理解起来需要一点时间。

最近更新的频率明显变低了很多，其实是在转过头来学之前学过的东西，之前都是囫囵吞枣，重新看一遍会有很大的收获。

字节面试进三面了，这几天还是要好好把项目和基础知识搞明白，加油加油加油，祝我面试顺利！！！