那么，让我们想象一下。 房间里锁着5只猫，为了叫醒主人，需要它们都同意，因为只有五只猫靠在门上才能打开门。 如果其中一只猫是薛定谔的猫，而其他猫不知道他的决定，就会出现问题：“它们怎么能做到呢？”
在本文中，我将简单地向您介绍分布式系统世界的理论组成部分及其运行原理。 我还将粗略地研究一下 Paxos 的主要思想。
当开发人员使用云基础设施、各种数据库并在大量节点的集群中工作时，他们确信数据将是完整、安全且始终可用的。 但保证在哪里呢？
本质上，我们的保证是供应商的保证。 它们在文档中的描述如下：“这项服务非常可靠，它有给定的 SLA，不用担心，一切都会按照您的预期分布式工作。”
我们倾向于相信最好的，因为来自大公司的聪明人向我们保证一切都会好起来的。 我们不会问这样的问题：事实上，为什么这能行得通？ 此类系统的正确运行是否有任何正式的理由？
我最近去了 并受到这个话题的启发。 学校的讲座更像是微积分课程，而不是与计算机系统相关的课程。 但这正是我们每天使用的最重要的算法在不知不觉中被一次证明的方式。
大多数现代分布式系统都使用 Paxos 共识算法及其各种修改。 最酷的是，只需用笔和纸就可以证明该算法的有效性以及原则上存在的可能性。 在实践中，该算法用于在云中大量节点上运行的大型系统。
接下来讨论的内容的简单说明：两位将军的任务我们先来看一下热身 .
我们有两支军队——红军和白军。 白军驻扎在被围困的城市。 A1、A2将军率领的红军分布在城市两侧。 红发人的任务是进攻白色城市并取得胜利。 然而，每个红将军的军队单独比白军要小。
红方胜利条件：两名将领必须同时进攻，才能对白方取得数量优势。 为此，将军 A1 和 A2 需要彼此达成协议。 如果大家分头攻击的话，红发就会输。
为了达成协议，将军A1和A2可以通过白城境内互相派遣使者。 信使可能会成功到达盟军将军那里，也可能会被敌人拦截。 问题：红发将军之间是否存在这样的通信序列（从A1发送信使到A2，反之亦然从A2发送信使到A1），保证他们同意在X小时发动攻击。这里，保证意味着两位将军都将明确确认盟友（另一位将军）一定会在指定时间 X 发起进攻。
假设A1向A2发送消息：“我们今天午夜进攻吧！” 未经将军 A1 确认，将军 A2 无法攻击。 如果A1的信使已经到达，那么A2将军会发送确认信息：“是的，我们今天杀掉白人。” 但现在A2将军不知道他的使者是否已经到达，他无法保证攻击是否会同时进行。 现在将军A2再次需要确认。
如果我们进一步描述他们的通信，就会发现，无论有多少个消息交换周期，都无法保证两位将军都收到了他们的消息（假设任何一个信使都可以被拦截）。
两将军问题很好地说明了一个非常简单的分布式系统，其中有两个通信不可靠的节点。 这意味着我们不能 100% 保证它们同步。 类似的问题仅在本文后面进行更大规模的讨论。
我们引入分布式系统的概念
分布式系统是一组可以交换消息的计算机（以下我们将其称为节点）。 每个单独的节点都是某种自治实体。 节点可以自行处理任务，但为了与其他节点通信，它需要发送和接收消息。
消息到底是如何实现的，使用什么协议——在这种情况下，我们对此不感兴趣。 分布式系统的节点可以通过发送消息来相互交换数据，这一点很重要。
定义本身看起来并不是很复杂，但是我们必须考虑到分布式系统有许多对我们来说很重要的属性。
分布式系统的属性
- 并发 – 系统中同时或并发事件发生的可能性。 此外，只要我们没有明确的事件发生顺序，我们就会认为两个不同节点上发生的事件可能是并发的。 但是，一般来说，我们没有。
- 没有全局时钟。 由于缺乏全球时钟，我们没有明确的事件顺序。 在普通人的世界里，我们习惯于我们绝对有时钟和时间。 当涉及到分布式系统时，一切都会发生变化。 即使超精密原子钟也会出现漂移，在某些情况下我们可能无法判断两个事件中哪一个先发生。 因此，我们也不能依赖时间。
- 系统节点独立故障。 还有另一个问题：仅仅因为我们的节点不会永远持续下去，就会出现问题。 硬盘驱动器可能会出现故障，云中的虚拟机可能会重新启动，网络可能会闪烁并且消息可能会丢失。 此外，可能存在节点工作但同时对系统不利的情况。 最后一类问题甚至有一个单独的名称：问题 。 存在此问题的分布式系统最流行的例子是区块链。 但今天我们不考虑这一类特殊的问题。 我们会对仅一个或多个节点可能发生故障的情况感兴趣。
- 节点之间的通信模型（消息传递模型）。 我们已经确定节点通过交换消息进行通信。 有两种著名的消息传递模型：同步和异步。
分布式系统中节点之间的通信模型
同步模型 – 我们确信存在一个有限的已知时间增量，在此期间消息可以保证从一个节点到达另一个节点。 如果这个时间过去了并且消息还没有到达，我们可以有把握地说该节点已经失败。 在这个模型中，我们有可预测的等待时间。
异步模型 – 在异步模型中，我们认为等待时间是有限的，但不存在这样的时间增量，在此之后我们可以保证节点发生故障。 那些。 来自节点的消息的等待时间可以是任意长。 这是一个重要的定义，我们将进一步讨论它。
分布式系统中共识的概念
在正式定义共识的概念之前，让我们考虑一个我们需要共识的情况的例子，即： 状态机复制.
我们有一些分布式日志。 我们希望它是一致的，并且在分布式系统的所有节点上包含相同的数据。 当其中一个节点获知要写入日志的新值时，它的任务就是将该值提供给所有其他节点，以便日志在所有节点上更新，并且系统进入新的一致状态。 在这种情况下，节点之间达成一致非常重要：所有节点都同意提议的新值是正确的，所有节点都接受这个值，只有在这种情况下，每个人都可以将新值写入日志。
换句话说：没有一个节点反对它有更多相关信息，并且建议的值不正确。 节点之间的协议以及对单个正确接受值的协议是分布式系统中的共识。 接下来，我们将讨论能够保证分布式系统达成共识的算法。
更正式地说，我们可以将共识算法（或者简称共识算法）定义为将分布式系统从状态A转移到状态B的某种函数。而且，这个状态是所有节点都接受的，并且所有节点都可以确认它。 事实证明，这项任务并不像乍看起来那么微不足道。
共识算法的性质
共识算法必须具备三个属性才能使系统继续存在并在从一个状态转移到另一个状态方面取得一些进展：
- 协议 – 所有正确操作的节点必须采用相同的值（在文章中该属性也称为安全属性）。 当前正在运行的所有节点（未发生故障或与其他节点失去联系）必须达成协议并接受一些最终的共同值。
这里重要的是要理解我们正在考虑的分布式系统中的节点想要达成一致。 也就是说，我们现在谈论的系统中，某些东西可能会简单地失败（例如，某些节点失败），但在这个系统中绝对不存在故意与其他节点作对的节点（拜占庭将军的任务）。 由于此属性，系统保持一致。
- 诚信 — 如果所有正确工作的节点提供相同的值 v，这意味着每个正确运行的节点都必须接受这个值 v.
- 终止合同 – 所有正确运行的节点最终都会呈现一定的值（活性属性），这使得算法能够在系统中取得进展。 每个单独正确运行的节点迟早必须接受最终值并确认它：“对我来说，这个值是真实的，我同意整个系统。”
共识算法如何工作的示例
虽然该算法的属性可能并不完全清楚。 因此，我们将通过一个例子来说明，在具有同步消息传递模型的系统中，最简单的共识算法会经历哪些阶段，其中所有节点都按预期运行，消息不会丢失，也不会中断（这真的会发生吗？）。
- 这一切都始于求婚（Propose）。 假设一个客户端连接到一个名为“Node 1”的节点并启动了一个事务，将一个新值传递给该节点 - O。从现在开始，我们将称为“Node 1” 建议。 作为提议者，“节点 1”现在必须通知整个系统它有新数据，并向所有其他节点发送消息：“看！ 我突然想到了“O”的意思，我想把它写下来！ 请确认您还将在日志中记录“O”。”
- 下一阶段是对提议值进行投票（投票）。 它是做什么用的？ 其他节点可能会收到更新的信息，并且它们拥有同一交易的数据。
当节点“节点 1”发送其提议时，其他节点会检查其日志中是否有有关此事件的数据。 如果没有矛盾，节点宣布：“是的，我没有关于此事件的其他数据。 “O”值是我们应得的最新信息。”在任何其他情况下，节点都可以响应“节点 1”：“听着！ 我有关于这笔交易的最新数据。 不是‘O’，而是更好的东西。”
在投票阶段，节点做出决定：要么全部接受相同的值，要么其中一个节点投反对票，表明他拥有更新的数据。
- 如果一轮投票成功并且每个人都赞成，那么系统将进入一个新阶段——接受该值。 “节点1”收集其他节点的所有响应并报告：“每个人都同意值“O”！ 现在我正式宣布“O”是我们的新含义，对每个人都一样！ 把它记在你的小本子上，不要忘记。 把它记在你的日志里！”
- 其余节点发送确认（已接受），表明它们已写下值“O”；在此期间没有任何新内容到达（一种两阶段提交）。 在这个重大事件之后，我们认为分布式事务已经完成。
因此，简单情况下的共识算法由四个步骤组成：提议、投票（voting）、接受（accept）、确认接受（accepted）。
如果在某个步骤我们无法达成一致，那么算法会再次开始，同时考虑拒绝确认建议值的节点提供的信息。
异步系统中的共识算法
在此之前，一切都很顺利，因为我们谈论的是同步消息传递模型。 但我们知道，在现代世界中，我们习惯于异步完成所有事情。 类似的算法如何在具有异步消息传递模型的系统中工作，在该系统中，我们认为节点响应的等待时间可以是任意长的（顺便说一句，节点故障也可以被认为是当节点可以响应任意长的时间）。
现在我们知道了共识算法的工作原理，对于那些好奇的读者来说，有一个问题是：在具有异步消息模型的 N 个节点的系统中，有多少个节点可以失败，以便系统仍然可以达成共识？
正确答案和理由都在剧透后面。正确的答案是： 0。 异步系统中即使有一个节点发生故障，系统也将无法达成共识。 这一说法在某些圈子里众所周知的 FLP 定理中得到了证明（1985 年，Fischer、Lynch、Paterson，链接到文章末尾的原文）：“如果至少一个节点发生故障，就不可能达成分布式共识”。
伙计们，那么我们有一个问题，我们已经习惯了一切都是异步的。 就是这样。 如何继续生活？
我们只是在谈论理论、数学。 从数学语言翻译成我们的工程语言，“无法达成共识”是什么意思？ 这意味着“不可能总是实现”，即存在无法达成共识的情况。 这是一个什么样的案例呢？
这正是对上述活性属性的违反。 我们没有一个共同的协议，在没有得到所有节点响应的情况下，系统无法取得进展（无法在有限时间内完成）。 因为在异步系统中，我们没有可预测的响应时间，我们无法知道节点是否已崩溃或只是需要很长时间才能响应。
但在实践中我们可以找到解决办法。 让我们的算法在出现故障的情况下能够长时间工作（有可能无限期地工作）。 但在大多数情况下，当大多数节点都正常运行时，我们的系统就会取得进展。
在实践中，我们处理部分同步通信模型。 部分同步的理解是：一般情况下，我们有一个异步模型，但是正式引入了某个时间点的“全局稳定时间”的概念。
这一刻可能不会持续很长时间，但总有一天会到来。 虚拟闹钟将会响起，从那一刻起我们就可以预测消息到达的时间增量。 从这一刻起，系统从异步转为同步。 在实践中，我们处理的正是这样的系统。
Paxos算法解决共识问题
是解决部分同步系统的共识问题的一系列算法，但可能会出现某些节点失败的情况。 Paxos的作者是 。 他于1989年提出了该算法的存在性和正确性的形式证明。
但事实证明这个证明绝非微不足道。 第一份出版物于 1998 年发布（33 页），描述了该算法。 事实证明，这篇文章极其难以理解，2001 年发表了一篇长达 14 页的文章解释。 给出出版物的数量是为了表明事实上共识问题一点也不简单，这些算法的背后隐藏着最聪明的人的大量工作。
有趣的是，莱斯利·兰波特本人在演讲中指出，在第二篇解释性文章中，有一个陈述，一行（他没有具体说明是哪一行），可以有不同的解释。 正因为如此，大量现代 Paxos 实现并不能完全正确工作。
详细分析 Paxos 的工作需要不止一篇文章，因此我将尝试非常简短地传达该算法的主要思想。 在我的文章末尾的链接中，您将找到进一步深入研究该主题的材料。
Paxos 的角色
Paxos算法有一个角色的概念。 让我们考虑三个主要的（有附加角色的修改）：
- 提议者（也可以使用以下术语：领导者或协调员）。 这些人从用户那里了解一些新价值并承担领导者的角色。 他们的任务是发起一轮新值提案并协调节点的进一步行动。 此外，Paxos 允许在某些情况下存在多个领导者。
- 接受者（投票者）。 这些节点投票接受或拒绝特定值。 他们的作用非常重要，因为决策取决于他们：在共识算法的下一阶段之后系统将（或不会）进入什么状态。
- 学习者。 当系统状态发生变化时，节点只接受并写入新的接受值。 他们不做出决定，只是接收数据并将其提供给最终用户。
一个节点可以在不同情况下组合多个角色。
法定人数的概念
我们假设我们有一个系统 N 节点而其中最大的 F 节点可能会失败。 如果 F 个节点失败，那么我们至少必须有 2层+1 受体节点。
这是必要的，这样即使在最坏的情况下，我们也始终拥有大多数正常工作的“好”节点。 那是 F+1 同意的“好”节点，最终值将被接受。 否则，可能会出现我们不同的地方群体具有不同的含义并且彼此之间无法达成一致的情况。 因此，我们需要绝对多数才能赢得投票。
Paxos共识算法如何工作的总体思路
Paxos算法涉及两个大阶段，每个阶段又分为两个步骤：
- 第 1a 阶段：准备。 在准备阶段，领导者（提议者）通知所有节点：“我们正在开始一个新的投票阶段。 我们有新一轮。 本轮次数为n。 现在我们将开始投票。” 目前，它只是报告新周期的开始，但不报告新值。 该阶段的任务是发起新一轮并告知每个人其唯一编号。 轮数很重要，它必须大于所有先前领导者的所有投票数。 因为正是通过这个轮数，系统中的其他节点才能了解领导者数据的最新程度。 其他节点很可能已经有了后来几轮的投票结果，并且只会告诉领导者他落后于时代。
- 第 1b 阶段：承诺。 当接受节点收到新投票阶段的编号时，可能有两种结果：
- 新投票的数量 n 大于接受者之前参与的任何投票的数量。 然后acceptor向leader发送承诺，不再参与数量低于n的投票。 如果接受者已经对某件事进行了投票（也就是说，它已经在第二阶段接受了某些值），那么它将接受的值和它参与的投票数附加到它的承诺中。
- 否则，如果接受者已经知道较高编号的投票，它可以简单地忽略准备步骤并且不响应领导者。
- 第 2a 阶段：接受。 领导者需要等待法定人数（系统中的大多数节点）的响应，如果收到所需数量的响应，那么他有两种事件发展选择：
- 一些接受者发送了他们已经投票赞成的值。 在这种情况下，领导者从投票中选择数量最多的值。 我们将此值称为 x，它会向所有节点发送一条消息，例如：“Accept (n, x)”，其中第一个值是其自己的 Propose 步骤中的投票数，第二个值是每个人收集的值， IE。 我们实际投票的价值。
- 如果没有一个接受者发送任何值，但他们只是承诺在这一轮中投票，则领导者可以邀请他们为他们的值投票，即他首先成为领导者的值。 我们称其为 y。 它向所有节点发送一条消息，例如：“Accept (n, y)”，与之前的结果类似。
- 第 2b 阶段：已接受。 此外，接受者节点在收到来自领导者的“Accept(...)”消息后，只有在没有承诺某些（其他）的情况下才同意该消息（向所有节点发送他们同意新值的确认）领导者以轮数参与投票 n' > n，否则他们会忽略确认请求。
如果大多数节点对领导者做出了响应，并且所有节点都确认了新值，则认为新值被接受。 万岁！ 如果未达到多数或有节点拒绝接受新值，则一切重新开始。
这就是 Paxos 算法的工作原理。 每个阶段都有很多微妙之处，我们实际上没有考虑各种类型的故障、多个领导者的问题等等，但本文的目的只是向读者介绍高层次的分布式计算世界。
另外值得注意的是，Paxos 并不是唯一的一种，还有其他算法，例如， ，但这是另一篇文章的主题。
进一步研究材料的链接
初学者级：
- ，Preethi Kasireddy，Medium 上的博客文章
- ，Adi Kancherla，Medium 上的博客文章
- ，伊泰·亚伯拉罕，博客
- ，Ittai Abraham，博客文章
莱斯利·兰波特等级：
- ，Fischer、Lynch 和 Paterson，研究论文，1985 年
- ，莱斯利·兰波特，研究论文，1998
- ，莱斯利·兰波特，研究论文，2001
来源： habr.com