在接下来的几篇文章中，我将写分布式计算中最基本的概念之一-与理论和实践社区同等重要。该共识的问题是获得一组节点的分布式系统上进行一些同意的问题-这可能是一个值，行动或决策的过程。达成共识允许分布式系统充当单个实体，每个单独的节点都知道并与整个网络的行为保持一致。
例如，共识的一些可能用法是：

• 决定是否将事务提交到数据库
• 通过约定当前时间来同步时钟
• 同意进入分布式算法的下一阶段（这是著名的复制状态机方法）
• 选择一个领导节点以协调一些更高级别的协议

这个听起来很简单的问题已经令人惊讶地成为二十多年来特别是理论分布式系统研究的核心。怎么来的？在我看来，答案是三重的。

首先，事实证明共识是一个足够困难的问题，可以用来表征系统模型不同强度之间的差异。共识是在同步系统solveable，但不是在异步的，如果有任何故障的可能性。因此，问题出在两个模型之间的相位边界上，并且在很大程度上取决于时序假设。
其次，很难达成共识协议。简单的解决方案效果不佳，表现出不良的行为，有时行为不正确。Google Chubby服务的发明者Mike Burrows说：“只有一个共识协议，那就是Paxos。”所有其他方法只是Paxos的残破版本。由莱斯利·兰伯特（Leslie Lamport）构想的Paxos协议以微妙着称，并且有点难以理解（尽管兰伯特（Lamport）不一定通过对希腊议会程序的寓言首次提出该协议来解决该问题）。无论您是否相信这种观点，都很难找到一个好的共识协议。
第三，共识是一个重要问题。分布式数据库依靠它。实际上，大多数分布式系统都基于此。组成员资格系统，容错复制状态机，数据存储-所有典型的分布式系统都在一定程度上能够解决共识。部分原因是，共识与另一个重要问题同构- 原子广播，即原子广播能够可靠地将网络中的消息可靠地以总顺序传送到所有节点。我们将在这些文章的后面看到为什么原子广播和共识是同一问题的两个实例。

正式定义
因此，共识非常重要。对于明显的重要问题，理论家要做的第一件事就是将其形式化，以便更好地进行推理。我将在这里保持理论的亮点，但是我们需要弄清楚什么构成共识问题的解决方案。幸运的是，它仅涉及三个属性。
我们说节点一旦决定就决定是否认为其他所有人都同意这一价值。更正式的定义是，每个节点都有一个输出寄存器，一旦协议终止，该输出寄存器将包含要商定的值。写那个寄存器是决定的行为。
节点提出通过建议他们为在达成一致的价值值。节点建议的值被认为是预先确定的-协议不应强制节点建议任何特定的值（稍后我们将确切地说明原因）。
考虑到这两个定义，并给定了 ñññ 对于分布式系统中的节点，我们将仅在以下情况下认为共识协议正确：

1. 协议 -中的所有节点决定相同的值
2. 有效性 -决定的值必须已经由某个节点提出
3. 终止 -所有节点最终决定

达成共识很容易理解：如果没有达成共识，我们就无法真正达成共识。我们可以考虑弱化这一要求，说只有大多数节点必须达成协议，但这实际上并不能真正改变问题的强度或其所需的解决方案。
有效性不太直观-看起来同时很明显。协议属性的问题在于，无论网络的实际状态如何，它都简单地允许仅指示每个节点确定默认值的协议。例如，无论事务如何，始终投票为“不提交”的数据库提交协议满足协议条件。有效性确保这些协议不会通过召集。
终止也是一个合理的要求，但是需要考虑为什么需要终止-协议仅约束节点如何决定，而不约束节点是否决定。我们需要终止协议，以确保协议确实可以做一些有用的事情，否则，我们将对那些无所作为的简单解决方案持开放态度-满足协议和有效性。
请注意，关于容忍失败，我们还没有说什么。设计一种即使在参与者可能崩溃和失败时仍然有效的协议将变得极为困难，因此稍后我们将重新探讨失败的影响。

两阶段提交
达成共识问题的简单解决方案似乎显而易见。想一想您将如何解决现实世界中的共识问题-也许是想为三个人的四个人安排一场桥梁游戏。您会依次给所有朋友打电话，建议一个游戏和一个时间。如果那段时间对每个人都有利，那么您就必须环顾四周并确认，但是如果某人无法做到，则需要再次给所有人打电话，告诉他们比赛已经结束。您可能会同时建议新的一天，然后开始另一轮共识。
这是一种非常自然的方法-尽管经过了稍微简化，但省略了一些针对特定人的优化方法-才能达成共识。我们可以确定过程中的两个步骤：

1. 与每个参与者联系，提出价值并收集他们的反馈
2. 如果所有人都同意，请再次与每个参与者联系以告知他们。否则，请与每个参与者联系以中止共识。

该框架描述了可能是最简单，最常用的共识算法，称为两阶段提交或2PC。顾名思义，2PC在两个不同的阶段运行。第一个建议阶段包括向系统中的每个参与者提出一个价值并收集响应。第二个提交或中止阶段将投票结果传达给参与者，并告诉他们继续进行并决定或中止协议。
提出值的过程称为协调器，不必特别选举-如果任何节点愿意，可以充当协调器，因此可以发起一轮2PC。

图1：两阶段提交，无故障执行，第一阶段。
请注意，这里的共识是关于是否接受协调员提出的价值，而不是价值本身。因此，节点未就该值应该达到什么达成共识，而是就是否接受该值达成了共识。这是一个二进制变量：是或否，或者提交或中止。参与者没有机制可以说“实际上，我宁愿我们投票赞成 XXX 比建议的y “-如果要这样做，则必须启动自己的2PC轮。

图2：两阶段提交，无故障执行，第二阶段。
如上所述，2PC是否在不担心故障的情况下解决了共识问题？协议很容易显示：每个节点都决定协调器在第一阶段建议的值，前提是并且只有在第二阶段协调器告知他们这样做的情况下。协调器将相同的决定发送到每个节点，因此如果告知一个节点决定一个值，则它们都是。
有效性也得到满足。2PC不会微不足道地提交或中止-它在每种情况下都会中止，除了每个节点都同意提交的情况外。在所有情况下，决定的最终值已由至少一个节点投票。
如果保证每个节点都能取得进展并最终将其投票权返回给协调器，协调器将最终将其传达给每个节点，那么最终终止将得到保证。请注意，即使是异步模型也可以在不出现故障的情况下保证此属性：最终，每条消息都会得到处理，所有响应都会被发送。2PC规范中没有循环，因此无法永远继续执行。
因此，2PC确实为达成共识提供了解决方案。它具有非常高效的优势-交换的消息数为 3n 对于n节点 很难看到如何可以大大改善。
但是，正如我早先强烈暗示的那样，2PC的软膏存在问题。如果允许节点发生故障-即使单个节点也可能发生故障-那么事情就变得更加复杂。

崩溃和故障
如本博客其他地方所讨论的，节点可能会以多种方式崩溃。最简单地说，它们可能崩溃并且永远无法恢复。这是分布式系统故障的“故障停止”模型。取而代之的是，节点可能崩溃，并可能在以后的某个日期从故障中恢复并继续执行。这就是“故障恢复”模型。最一般地，节点可以以完全任意的方式偏离协议规范。这就是所谓的“拜占庭式失败”，设计应对方案是研究的一个活跃领域，而且相当困难。我们考虑最常用的故障模型，即故障恢复（也可以说这也是最常见的故障模式）。
节点故障如何在2PC的工作中抛出扳手？为了回答这个问题，我们必须查看协议可以采用的每种状态，并考虑如果协调者或参与者之一在该状态下崩溃会发生什么情况。
在第一阶段，在发送任何消息之前，协调器可能会崩溃。这并不会引起我们太多的担心，因为它只是意味着2PC永远不会启动（因此，虚张声势，正常工作）。如果参与者节点在协议启动之前崩溃，那么直到提议消息无法到达崩溃的节点之前，都不会发生任何不良情况，因此我们可以稍后处理该失败。
现在，在发送了一些建议消息之后，而不是全部消息之后，请考虑协议。如果协调器此时崩溃，我们将有一些节点已收到建议并开始2PC回合，还有一些节点不知道发生了什么。如果协调器很长时间没有恢复，则接收提案的节点将被阻塞，等待可能永远无法完成的协议结果。这可能意味着该协议的其他任何实例都无法成功执行，因为参与者在投票“提交”时可能不得不锁定资源。这些节点会将选票发回给协调员-不会意识到它已失败-因此不能简单地使协议超时并中止协议，因为协调员有可能重新唤醒，
因此，该协议在协调器上被阻止，并且无法取得任何进展。我们可以添加一些机制来解决此问题-我们将在下面进行描述-但是这个被困在等待某些参与者完成协议一部分的问题是2PC永远不会忽略的问题。

图3：两阶段提交，其中协调器失败，第一阶段。
但是，我们可以采取措施解决这一漏洞，是当我们意识到协调员崩溃时，要让另一位参与者接管协调员的工作。当某个节点发生超时时，我们可以强制该节点完成协调器启动的协议。就像在第一阶段的消息中一样，该节点可以联系所有其他参与者，并找出他们投票的方式。这要求所有节点将所有2PC执行的结果保持在持久性存储中，直到他们知道其他所有节点都已提交或中止为止；否则，如果所有节点忘记了给定执行所执行的操作，则恢复节点将接替合作伙伴-coordinator将无法恢复事务状态。

图4：两阶段提交，协调器失败，第二阶段。
但是，如果另一个参与者节点在恢复节点可以完成协议之前崩溃了，则协议的状态将无法恢复。恢复节点无法区分所有已经投票决定提交的节点和失败的参与者已经提交的情况（在这种情况下，默认情况下中止是无效的）和所有节点，除了失败的节点已经投票决定要提交和失败的节点已经投票给中止（在这种情况下，默认情况下提交无效）。
在第二阶段中，已经广泛使用了相同类型的论点。如果协调器在提交给所有参与者的提交消息之前崩溃了，我们需要一个恢复节点来接管并安全地指导该协议的缔结。
最坏的情况是协调员本身是参与者，并且对协议的结果进行投票。然后，协调员的崩溃使它和一个参与者都崩溃了，从而保证了该协议将保持阻塞，并且仅由于一个失败而导致。
协调器通常会将任何成功协议的结果记录在持久性存储中，以便在其恢复时可以回答有关事务是否已提交的查询。这允许在参与者节点上定期对日志进行垃圾回收：协调器可以告诉节点，没有人会尝试恢复相互提交的事务，并且他们可以从其日志中清除其存在（也就是说，日志可能保持崩溃状态，以便能够在崩溃后恢复节点的状态）。

结论
2PC仍然是一种非常流行的共识协议，因为它具有较低的消息复杂度（尽管在故障情况下，如果每个节点都决定是恢复节点，则复杂度可以达到 N的平方。与协调员交谈的客户可以在3个消息延迟时间内得到答复。这种低延迟对于某些应用程序非常有吸引力。
但是，2PC可能阻止协调器故障这一事实是一个严重影响可用性的重大问题。如果可以在任何时间回滚事务，那么协议可以在节点超时时恢复，但是如果协议必须将任何提交决策视为永久的，则错误的失败会使整个事情陷入僵局。
就是说，仍然有一些包含2PC的前沿研究项目。最近最重要的是Sinfonia（PDF），它在SOSP 2007上获得了最佳论文奖。它们在2PC之上构建了一种分布式内存，但是使协调器崩溃可以通过以下方式恢复（通过超时和恢复干预）节点）。内存节点崩溃被认为是“游戏过度”的情况（但是内存节点本身可能被高度复制）。这是一篇很好的论文，我建议阅读。
下次，我将介绍3PC，它以额外的消息延迟为代价消除了2PC的阻塞问题。在博客中留下评论或问题，或直接给我发邮件。