简单理解Paxos算法（译）

本文翻译自Quora上的一个回答

我认为在了解Paxos前，可以先谈谈其他解决共识问题的方法，在这个基础上再理解Paxos会简单些。

结婚誓言是一种达成共识的直观方式。

“你愿意（若干省略）？”“我愿意！”“我愿意！”
“现在我宣布你们（若干省略）”

两阶段提交

现在假设这场婚姻不是发生在两个人之间，而是一个男人和多个女人之间。这个男人要么娶所有人，要么一个也不能娶。那么，结婚誓言也要相应地改成下面的样子：

“你愿意（若干省略）？”“我愿意！”“我愿意！”“我愿意！”......
“现在我宣布你们（若干省略）”

如果其中一个女人没有回应“我愿意！”，那么婚礼将无法进行。

计算机科学家称之为两阶段提交。

两阶段提交（2PC）过程如下：

表决阶段。一个协调者向所有节点发布一个值并且收集它们的返回（接受或者不接受）。在我们的场景中，一个事务协调者询问所有的资源管理器RM（数据库服务器实例）是否可以提交一个事务，RM回答是或者不是。
提交阶段。如果所有人都同意，协调者将告诉所有节点这个值被确定下来了；如果有哪怕一个节点不同意，协调者将告诉所有节点这个值没有被确定下来。在我们的场景中，协调者要求RM提交事务或者终止事务。

注意表决仅仅针对本次提出的值，节点可以回应是或者不是，而不能提出一个替代值。如果一个节点想要提出一个值，它应该开始自己的2PC。显然，这个算法是管用的，一个节点提出的值要由所有节点同意；同时，这个算法的效率较低下，对于一个拥有N个节点的集群，完成共识需要传输3N条信息。

如果某个节点挂掉了呢？比如，在阶段1中，协调者向部分节点（不是全部节点）发送提议后挂掉。

现在部分节点开始第二阶段，而其他的节点还不知道。那些开始第二阶段的节点将会阻塞。
在我们的场景中，表决过的RM可能不得不锁住一些资源，并且不能启用超时机制，因为协调者可能会恢复，然后继续第二阶段。

在第二阶段，如果协调者向部分节点发送提交的消息后挂掉，类似的问题一样会存在。通过另外一个协调者在监测到timeout时接管可以解决部分问题；这个节点和其他的节点保持通信来发现其他节点的表决（需要节点持久化表决结果）从而结束事务。但是这个流程也有可能发生失败从而导致事务可能无法恢复。结语：在发生节点失败的情况下2PC并不可靠。

三阶段提交

2PC的关键问题在于，当协调者挂掉时，没有其他的角色能够完成协议。这可以通过添加一个额外的步骤来完成：

第一阶段。和2PC一样，协调者向所有节点提出一个值。
第二阶段。如果在第一阶段所有节点返回“是”，协调者发送一个“准备提交”的信息，让节点执行可以撤销但是无法回复的操作。每个节点向协调者确认已经收到“准备提交”的信息。
第三阶段。和2PC的阶段一样，如果协调者接收到所有节点的确认，那么向所有节点发送第一步协调的值，让节点提交。如果协调者没有接到所有节点的确认，那么协调者取消本次事物。

假如协调者在上面的任何一个步骤挂掉，其他的任意参与者都可以接管这个角色，查询其他节点的状态。

如果有任意RM向新协调者报告没有收到“准备提交”信息，新的协调者会知道没有节点提交了该事务。新的协调者可以取消这个事物或者重新执行一遍流程。
如果已经提交了事务的RM挂掉，我们会知道其他的RM都已经收到并且确认了“准备提交”信息，不然协调者不会进行到提交阶段。所以协调者可以从最后得到阶段开始。

从上面可以看出，3PC可以很好地处理节点失败的情况。代价是多了一个步骤，导致了系统更高的延迟。

在发生网络分区的情况下，3PC也处理的不够好。假设所有接收到“准备提交”的RM都在分区1，其他的RM在分区2。这个会导致每个分区都会选举出各自的恢复节点，恢复节点要么提交事务，要么取消事务。万一网络分区消失，系统就会处于不一致的状态。

Paxos

首先问一个问题，有比3PC更好的算法吗？3PC面临的唯一问题是网络分区，对吧？要想回答这个问题，让我们假设网络分区是唯一的问题（实际并不是，后面会提到）。由网络分区导致的一致性问题值得解决吗？

首先，随着云计算的兴起，为了服务的可扩展性，可能会将服务部署在不同的大陆上；这种情况下，的确需要一个容忍网络分区的算法。

第二，网络分区并不是3PC面临的唯一问题。处理节点临时故障，最常见的情况是故障-恢复-继续上次执行。这种fail-recover模式也可以用来描述一个异步的网络模型，在这个模型中，无法规定节点用于响应消息的时间上限，因为永远不能假定一个节点已经挂了--它们可能会很慢，或者网络可能会很慢。不能对这个模型采用超时机制。

3PC能处理fail-stop，但不能处理fail-recover。不幸的是，现实情况需要处理fail-recover，因此，我们需要一个更通用的方案。Paxos就是这样的方案。

工作过程

Paxos的工作过程和2PC很像：

选择一个节点成为leader/proposer。
leader选择一个值，发送到所有的节点（Paxos中称之为acceptor），这个消息被称为“接受请求”消息。acceptor可以回应接受或拒绝。
一旦节点中的大多数回应接受，共识就能达成，协调者将“提交”消息发送到所有节点。

和2PC不同的关键在于，2PC需要所有节点同意，Paxos只需要大多数节点同意。这个想法很有意思，因为在两个不同的大多数节点集合中，至少会有一个节点同时在这两个集合中。这就可以保证，如果大多数节点都同意某个值，随后任何想做出提议的节点都能从其他节点发现这个值并同意。这意味着，即使一半的急诶单无法回复，Paxos算法也能进行下去。

当然，leader本身可能也会挂掉。为此，Paxos不会在给定的时间点授予当个节点leader职责。算法允许任意节点成为leader，并且协调事务。这自然意味着在给定的时间点，可能存在多个认为自己是leader的节点。在这种情况下，两个leader也许会提出不同的值。那么，如何在这种情况下达到共识呢？Paxos为此设计了两种机制：

为leader分配顺序。这样每个节点就能区分现有的leader和从失败中恢复过来的leader，从而防止旧的leader阻碍共识的达成。
对leader提出的值进行限制。一旦在某个值上达成了共识，Paxos强迫后面的leader也选择这个值来保证共识的延续。让acceptor发送其最近确认的值和发送该值leader的序列号，来实现这一点。新的leader可以选择一个从acceptor接收的值；如果没有值被发送，leader可以选择自己提出的值。

协议过程

准备阶段

一个节点选择成为leader，选择一个序列号x和值v来创建一个提议P1(x, v)。leader将这个提议发送给acceptor，等待大多数节点的返回。
acceptor在收到提议P1(x, v)后，判断：
- 如果提议是该acceptor要接受的第一个提议，回复“同意”，承诺leader该acceptor未来不会接受小于x的请求。
- 如果该acceptor之前有接受过提议：
  - 比较x和之间和之前接受的最高序列号的提议，比如P2(y,v2)
  - 如果x<y，回复拒绝和y值
  - 如果x>y，回复同意和P2(y, v2)

接受阶段

如果大多数的acceptor回复“拒绝”或者没有回复，leader取消本次提议。
如果大多数的acceptor回复“同意”，leader也能知道acceptor已经接受的提议。leader从这些值中任选一个值（如果没有值被接受，选择自己的值），发送“接受请求”消息，带着提议的序列号和值(x, v)。
当acceptor收到“接受请求”消息，如果满足下面的两个条件，就发送“接受”，否则返回“拒绝”。
- v和之前接受的某个值相同
- x是该acceptor所接受提议中序列号的最大值
如果leader没有从大多数节点中收到“接受”消息，leader取消这次提议然后重新开始；如果leader从大多数节点中收到了“接受”消息，本次协商就结束了。作为优化，leader可以发送“提交”消息给其他的节点。

Paxos失败处理

在Paxos算法中，如果我们指定集群中同一时间只能有一个leader，并且要求所有节点都要投票呢？是的，我们就得到了2PC。2PC是Paxos的一个特例。

如上所述，Paxos比2PC更能容忍失败：

leader挂掉。其他的leader可以提出自己的提议来继续协议。
挂掉的leader恢复。由于节点只会同意具有最大序列值的提议，并且只提交之前接受的值，所以两个节点能够同时共存。

Paxos也比3PC更能容忍失败，尤其是在网络分区的情况下。在3PC中，如果两个分区分别同意一个值，那么当分区消失时，系统会处于不一致的状态。在Paxos中，这个问题不会存在，因为同意一个值需要大多数的节点参与。除非一个分区里面的节点占大多数，否则共识不能达成。如果占有多数节点的分区达成共识，这个共识需要另外一个分区的节点接受。

Paxos可能出现的问题是，当两个leader由于节点不能获知彼此的存在时，不停地提出比原来提议序列号高的提议，这会导致Paxos不能终止。最终两个leader获知了彼此的存在，其中一个做出让步。

这是一个一致性和实时性之间的妥协。Paxos保证了一致性，一旦共识达成，值就不会被修改。但是，Paxos不保证可用，在某些极端情况下可能无法达成共识。事实上，一个异步算法不能保证既安全又实时。这被称之为FLP不可能结果。