你的数据是如何存储的，或者说，想象中的希腊人的法则
你的数据是如何存储的，或者说，想象中的希腊人的法则
如果你不从事计算机工作，你可能没有花太多时间去思考数据是如何存储在计算机或云中的。我说的不是硬盘或内存芯片工作的物理方式，而是一些比你想象的更复杂、更容易理解的东西:如果你有一份很多人想立刻阅读和编辑的数据，比如一个共享的文本文件、一家银行的记录或一个多人游戏中的世界，每个人如何就文档中的内容达成一致，并确保没有人覆盖其他人的工作？这就是“分布式共识”的问题，为了讨论这个问题，我们必须讨论难吃的墨西哥卷饼、羊霸和古希腊虚构的岛屿。
“的假想岛屿是什么？，“你问？
原来，关于用来解决这个问题的最重要方法之一的原始科学论文是以冗长的讨论形式写成的，讨论的内容是虚构的古希腊帕克斯岛的兼职议会是如何设法通过法律的，尽管从来没有人可靠地出现在立法机构工作。这是一个很好的比喻，说明了一群人如何能够就向一个文件中写入什么达成一致，即使他们可能暂时无法联系或相距遥远——这篇论文既是有史以来发表的最有趣的严肃研究论文之一，也是我见过的对复杂算法的最佳解释之一。因为这个比喻很好地解释了这个问题的一部分，而且因为它比谈论文件系统有趣得多，所以我将用它来解释所有的问题。
Note that I am a computer scientist, not an illustrator. This represents the upper bound of my artistic skills.
这个比喻如此奏效的原因是，对于文件和法律，我们有一些数据，许多人希望更改，许多人希望阅读，但这些人都不想永远这样做。同时阅读一本法律书籍会受到一次能看到书的人数的限制，就像阅读一个文件会受到磁盘上数据的速度的限制一样；同时写要求每个人都以某种方式同意不重写对方，但在继续之前不必进行冗长的辩论。除了让世界上的每一个人轮流，一次一个人拿着书，我们如何解决这个问题？
因此，与其谈论文件系统和数据库事务，不如让我们把自己带到虚构的爱琴海的岛屿上，在那里，每个人都痴迷于颁布法令和制定法律:他们只需要确保每个人都可以在需要时阅读法律。我们将经历一些曲折的段落，当我们完成时，你将会像专业的计算机科学家那样理解分布式共识。只是有更多的羊。
(顺便说一句，将会有一堆岛屿，它们的名字完全是杜撰的，除了引发这个故事的那一个，稍后会有更多的介绍。)
隐士和墨西哥食物
我们从所有这些岛屿中最简单的一个开始我们的故事，Pseudemoxos，一个隐士写法律和法令供自己使用的家。起初，她用了一个非常简单和明显的方法:一个笔记本和一支铅笔。她可以随心所欲地添加法律、修改法律、重组法律，只要在她喜欢的地方擦掉或写下新的东西。(从本质上讲，这就是你电脑中的磁盘在 20 世纪 90 年代末之前的工作方式)
这种方法似乎工作得相当好，除了过度擦除的纸张磨损变薄的趋势。然而，当有一天一箱可疑的玉米煎饼被冲上海岸时，隐士开始可怕地意识到她设计中的缺陷。在修改法律的过程中——已经删除了文本并开始写东西——她经历了我们在计算机科学中委婉地称为“生产紧急情况”的情况。当我们的隐士回到她那有些破旧的法律书上时，她发现她不仅忘记了她将要写的内容，而且在法律书中间有一个空白的地方，既没有旧的也没有新的法律，而是写得如此匆忙以至于连她都看不懂！
(当然，这个比喻是指当计算机或程序在写入过程中突然失败时会发生什么——磁盘上的数据可能会无可救药地损坏。这个比喻也延伸到了隐士更严重的失败，像头部撞击这样的事件不仅会对所写的文字造成损害，而且会在整页纸上留下令人不快的永久痕迹。)
这两个问题都可以通过所谓的日志来解决。规则是永远不要删除任何东西——就像人们保存日志或实验笔记本一样。现在，我们的隐士保存了一摞纸。当她希望修改法律时，她会在日记中添加一条注释:
6 月 4 日 10:32——食品安全法附录:禁止食用未确定时间的墨西哥卷饼。
每一次编辑，无论是插入、修改还是删除，都用笔记录在日志的末尾。隐士在紧急情况下得到保护，因为没有东西会被抹去；在最坏的情况下，有一个不完整或损坏的日志条目(丢失，也许是它的最后一期)，这是写作尝试失败的标志，人们可以简单地忽略它。日记账还有一个额外的好处，就是可以作为所有变化的记录；例如，要看一年前的法律是什么样子，我们的隐士可以简单地阅读日志并在那一天停下来。
该杂志的一个明显缺陷是，阅读它比阅读笔记本更困难:要了解当前的食品安全法，必须从杂志的最开头开始，从头到尾阅读，同时跟踪食品安全法的所有变化，随着时间的推移和杂志的变长，这个过程变得越来越繁琐。
为了简化这一点，我们的隐士在手边放了一堆空的法律书籍。每当日志变得太长时，她就留出一些时间来对法律做一个摘要:她从头到尾阅读日志，如果需要的话在废纸上做笔记，形成对所有法律的当前状态的描述，然后将当前状态写入法律书籍。在这本法律书籍的封面上，她写道:“这是[某个日期]的法律状态。”法律的进一步阅读只要求她阅读摘要，以及在摘要日期之后所做的变化的日志。如果偶尔需要摘要之前的变更历史记录，或者干脆扔掉，可以保留比这更早的日志。
如果我们的隐士忙于起草新的立法而没有时间定期做一个摘要，她可以简单地雇佣一个抄写员(也就是说，与第一个程序并行运行的第二个计算机程序)来帮助她。抄写员将简单地阅读日志，直到某个商定的时间，写一个摘要，并在他完成时通知我们的隐士，以便她可以开始使用新的摘要。为了完成他的工作，抄写员不需要和任何人说话，所以隐士可以继续她的工作，她的沉默没有被打破。
这种方法还有更多好处。我们的隐士因她的智慧而广为人知(例如，她关于避免海上墨西哥烹饪的课程)，许多人可能希望阅读她的法律。只要这些读者满足于知道最近的法律摘要，他们可以简单地制作他们自己的摘要副本，自由阅读而不需要打扰圣人的工作。只有需要对法律有绝对最新看法的读者才需要直接打扰她。
(日志在个人电脑上的使用始于 20 世纪 90 年代末，并在 21 世纪中期变得普遍。您今天的电脑可能会这样做。)
福塔斯岛上的混乱
靠近 Pseudemoxos 的是稍大一些的 Fotas 岛。这个岛上人烟稀少，但有足够多的人，福坦人都同意他们需要一个共同的法律体系来管理他们的生活。然而，佛昙派以其强烈的独立性而闻名:他们不愿意让任何其他佛昙派或佛昙派团体拥有对他们的权力，因此决定任何和每一个佛昙派都应该拥有独立制定法律的权力，只需在一张纸上写下他们希望制定的法律，连同日期和时间以及他们的名字，并通过信使将其发送到佛昙派图书馆，在那里抄写员会将其附加到法律期刊上。
(如果不清楚的话，这表示许多人试图同时编写一个文件，而没有试图在他们这样做之前就文件内容达成一致。毫无疑问，要做到这一点并不困难，但是只要有一点小聪明——以及对人们如何学习变化的一些限制——这实际上是可能的！)
为了了解这种情况可能会出现的一些问题，让我们从 Agnes 开始，她住在岛的一边，非常关心祭祀仪式的纯洁性。她颁布了一项法律:
6 月 1 日中午——关于出售绵羊的法律 32.1.2 修改为:禁止出售或购买羊毛不是纯白的绵羊，违者处以死刑。签名了，艾格尼丝。
在岛的另一边，巴兹尔，他最近生了一些害群之马，他很难出售，制定了自己的法律:
6 月 1 日中午——关于出售绵羊的法律 32.1.2 被修改为:任何人不得因绵羊毛的颜色而拒绝买卖绵羊。签名，巴兹尔。
那天晚些时候，抄写员发现自己有了两条新的法律，甚至有了相同的时间戳。他要做什么？当巴兹尔下一次来到镇上要把一只黑羊卖给加拉太亚，而她拒绝买一只非白羊时，他们去读法律书，他们应该遵守哪条法律？当抄写员试图写下一个法律摘要时会发生什么——法律 32.1.2 会说什么？(用计算机术语来说，有两个人尝试过一次把不同的数据写到同一个文件的同一个部分；结果可能是任何事情。阿格尼斯定律可能会赢，巴兹尔定律可能会赢，我们可能会以每一个定律中的每一个字母结束，或者其他任何东西)
为了说明一种更微妙的问题，想象 Agnes 想要执行法律的“读-修改-写”——也就是说，她查看当前的法律，决定做出更改，然后编写更改。但是就在她这么做的时候，巴兹尔对法律做了一个矛盾的修改。例如，在 10:00，Agnes 读法律
第 32.1.3 节。任何出售山羊的人都必须向图书馆总基金缴纳一 obol 的税。
她想了想，在 10 点 02 分写下了:
6 月 1 日 10:02 —应修改法律 32.1.3，将“一个 obol”改为“两个 obol”签名了，艾格尼丝。
不幸的是，在 10:01，Basil(他对山羊税没什么耐心)发布了:
6 月 1 日 10:01 —法律 32.1.3 应替换为“2 月 15 日是国家橄榄日”就这样。签名，巴兹尔。
我们的书记员，试图按顺序协调法律，将会非常困惑:当他看到 Agnes 的条目时，法律 32.1.3 正在谈论国家橄榄日，并没有在任何地方提到“一个 obol”。他要做什么？(如果你认为这个例子显而易见，想象一下如果巴兹尔定律用“巴兹尔！”代替了“图书馆总基金！”抄写员无法知道 Agnes 在编辑之前是否知道这一变化。)
每当多位作家竞相编辑同一部法律书籍时，就会出现这种情况。有许多解决方案，每一个都有不同的利弊。这些解决方案分为两个基本类别。一个是“最终一致性”(或“弱一致性”)，其中一些关于写作如何工作的规则将允许每个人同时写作，而无需彼此交谈。这样做的代价是，没有人能在这一瞬间知道法律的确切状态；他们只能知道不久前的情况。另一个是“强一致性”，所有类型的写作都是可能的，每个人都可以知道法律的当前状态，但代价是每次写作都需要一个建立共识的过程。
这两者都证明是有用的。有时候，你的信息有点陈旧是正常的；例如，当 Fotas 的居民正在制作他们的年度年鉴，并交换彼此的个人资料照片时，没有迫切的需要获得最新的照片，因此更简单的最终一致的协议会做得很好。另一方面，对于实际的法律，强一致性将被证明是更有用的，尽管它的成本。(计算机也是如此。例如，你上传到谷歌的图片是用一个最终一致的系统存储的，而访问控制列表(定义谁可以查看哪些内容)是用一个强一致的系统存储的
让我们回到福塔斯岛。
最终，这一切都说得通了
我们可以很容易地解决两个问题中的第一个——在相同的时间戳上有矛盾的法律——只需简单地同意一个打破平局的规则，这样就不会有两个时间戳匹配。例如，我们可以按照作者的名字，按字母顺序，在时间戳中打破束缚，这样在比赛的情况下，Agnes 的变化将总是发生在 Basil 的变化之前。(或者，如果名称匹配，我们可以提前给每个 Fotan 分配一个唯一的编号)一旦时间戳不再匹配，就不会有混淆:后来者总是取代先来者，所以当加拉太亚来到镇上时，巴兹尔定律就是书本上的那个。
如果这种相互覆盖是一个问题，可以通过事先约定谁可以写什么来避免。例如，在一周内，Agnes 可能只被允许编辑偶数编号的法律，而 Basil 奇数编号的法律，下一周可以切换。(在计算机中，文件的空间通常是分开的，因此两个作者根本不会试图写同一个文件，更不用说同时写了。例如，每个新上传的照片可能会被自动分配一个唯一的名称，以便只有其上传者需要写入该文件)
为了解决第二个问题，我们简单地宣布它不存在:我们改变杂志的规则，禁止任何“编辑”声明，只允许替换、添加或删除。这意味着杂志上的任何陈述都不能依赖法律的现状来解释。阿格尼丝将不得不在表格中写下她的法律
6 月 1 日 10:02 —法律 32.1.3 应替换为“任何出售山羊的人必须向参议院缴纳两先令的税款。”艾格尼丝。
而且，由于她写作有一个较晚的时间戳，她的版本将毫无疑问地战胜巴兹尔的版本。
这样一个制定法律的系统具有快速和简单的优点:任何人都可以在任何时候制定法律，而不需要和任何人商量。然而，阅读法律变得出奇的棘手。假设你想知道现行的山羊销售税，于是你去图书馆要求阅读法律 32.1.3。10:05 到达，你读了文摘和日志，发现上面写着:“任何人卖山羊都必须向元老院缴纳 obol 的税。”
你看，阿格尼斯按她的时间在 10:02 修改了法律——但是她的信使还没有到达！你所能知道的是，在最后一次写日记的时候，法律是这么说的。
为了让事情变得稍微好一点，信使可以在图书馆登记:每当信使从给定的 Fotan 到达，在他们传递他们的信息之后，他们在板上写一个便条，表明所有给定的 Fotan 的信息已经在某个时间传递了。然后，访客可以查看该板。如果 Agnes 的最后一条消息是在那天早上 9 点，Basil 的最后一条消息是在前一天晚上 7 点，以此类推，那么你至少知道，你正在阅读的法律是前一天晚上 7 点的准确时间，也就是黑板上显示的最早的时间，因为在那之前的所有编辑肯定已经到达。(这个时间被称为“低水位标志”)
当然，如果某个特定的 Fotan 不太爱打官司，他们的更新可能会很少，所以每个人都会想知道他们是否最近做了一些改变，只是还没有到达图书馆，或者他们是否只是几周没有任何事情要报告。为了避免这个问题，每个 Fotan 必须定期向库发送一个信使，不管他们是否有任何更新要做，以便板保持新鲜。
现在，佛坦人是一个有创造力的民族，所以他们很快意识到这种稳定的信使流可以进一步简化他们的生活。他们不必自己长途跋涉去图书馆，只需维护自己的法律文摘和法律期刊就可以了。他们的信使每次都简单地回来，带着自从他们最后一次派信使到图书馆以来对法律期刊所做的所有修改，以及当时在黑板上的日期的副本。他们只需更新自己的法律期刊，根据需要进行消化，现在可以尽可能轻松地查阅自己的法律期刊和中央参考资料。
然而，随着 Fotan 人口的增长，图书馆的交通成为一个问题，所有的信使来回奔跑，抄写员复制日志和摘要，简单地制定一项法律来改变山羊税的任务变得异常缓慢。幸运的是，福坦人意识到他们已经解决了自己的问题:有了自己的法律副本，他们不再需要一个中央图书馆了！
相反，开设了几个分馆。信使可以在最近的分馆简单地传递和接收更新，其他信使可以在每对分馆之间穿梭，将所有更新的副本传送到期刊。最终，一个“树形图”被建立起来:一个连接每个分支和每个 Fotan 到一个分支库的图表。更新只沿着树中显示的路线传递，但是由于每个 Fotan 或库都与其他 Fotan 或库相连，最终，任何 Fotan 所做的任何更改都会到达其他 Fotan。因为每个人最终都会有相同的日志在手，他们的法律书籍最终会一致！
这有许多好的优点:例如，当必须通过一条困难或昂贵的道路时，如危险的收费公路，这是从中央岛到其东部山区的唯一通道，只有一个信使需要穿越这条路径；他将简单地从西方向东方传递更新，反之亦然，道路两端的图书馆分馆将信息传播到岛的另一端。
(您可能注意到，在这一点上，单个 Fotan 和分支库之间不再有任何有意义的区别——这是完全正确的！每个人都有一份副本，只要他们继续沿着适当的路线派遣信使，每个人都可以简单地通过在自己的日记中写作来改变法律，并相信他们的信使会将信息传播到其他地方)
因此，这种方法非常有效，但有三个明显的缺点。首先，任何人都不可能确切地知道法律的现状。不像写自己的日记，像一个伪摩西隐士，一个人不再有保证，在完成一个变化后，任何人在未来阅读会看到这个变化；只是任何在未来足够远的地方阅读的人都会看到这种变化。(这被称为缺乏“写后读”一致性)
第二，不可能执行读-修改-写。这意味着，如果有两个 Fotan 试图改变同一法律，后果是不可预测的:在他们发布改变的那一刻，Fotan 都不能肯定地知道另一个改变是否已经开始，以及另一个改变是否会在他们之前或之后发生，这意味着在所有改变到达他们两个家之后，哪个改变会在他们的法律日志中结束。为了规避这一点，Fotan 必须找到一些方法来保证他是唯一一个试图改变给定法律的Fotan，并且他在改变法律之前已经阅读了最新版本的法律。
第三，这种方法容易受到网络故障的影响:想象一下，通往一个偏远家庭的道路被一次泥石流切断了。没有更新可以从他那里到达外面的世界，所以没有人可以假设他们有比从这个 Fotan 到道路安全一侧的最后消息更近的任何时间的所有更新。但是他们也不能假设他从那时起就没有传播过任何东西；据他们所知，幸运的是，他没有意识到岩石滑坡，并继续写他自己的日记，等待一个永远不会来的信使。整个系统因此停止，没有人的低水位标记前进，因此没有人能够形成一个新的摘要，这一切都是因为一个单一的道路失败！
在计算实践中，这样的问题是真实而严重的。每当单个节点(一台计算机，或者一个数据中心)断开连接时，生产工程师需要立即评估情况，并确定是否可以快速修复和重新连接。如果不这样做，所有其他服务器将无法形成摘要，因此他们的日志将继续增长，给读者带来问题，而孤立的作者变得越来越不同步。如果问题不能很快解决，孤立的节点通常会被完全关闭，并使用其他方法将希望连接到它们的人路由到其他地方的其他计算机——通常通过一个慢得多的外部网络，但希望是一个没有被破坏的网络。但是，其他节点将继续等待。如果很明显，一个修补程序不会很快出现，只有一个选择:从网络中完全删除丢失的节点，告诉其他节点假装它们不再存在，并且不会有来自它们的更新。其他节点会继续，但被隔离节点在隔离后执行的任何写入操作(除非可以通过其他方式复制并传输到主网络)将永久丢失。
Fotas 的客户，一致性强
因此，我们在上面看到的是一个合理的解决方案，对于像 Fotans 这样极端独立的岛民来说，他们希望能够快速写作，而不是完全关心是否能够阅读最新版本的内容。但是在这种情况下会发生什么呢？法律实际上是一个很好的例子——如果你在 10 点犯罪，那么针对它的法律是在 9 点还是 11 点通过的就很重要了。了解最新的法律很重要。
当 Fotas 进入法律书籍行业时，问题变得更加严重。你看，Fotas 被许多更小的岛屿所包围，每个岛屿都有自己的产业，因此需要自己的法律。作为小岛，他们没有资源来维持密集的佛天抄写员和信使系统；即使他们做到了，他们也永远无法训练那些抄写员和信使像佛坦人那样快速有效地工作，佛坦人(必须承认)对此有点着迷。因此，这些小岛多年来继续使用最简单和最野蛮的解决办法:每个岛都有自己的隐士，有一本法律期刊，以伪摩西的风格，每个想阅读或修改法律的人都简单地排队，一个一个地与隐士打交道。它缓慢而低效，如果他们的隐士碰巧生病了，或者被海啸卷走了，愿不朽的神灵保护他们。但是缺乏像福塔斯这样的资源，他们只是继续他们的方式。
因此，佛坦人嗅到了向他们的邻居提供法律书籍作为服务的机会；这些客户岛屿可以简单地从佛天法律书籍的一部分中读取和写入他们的信息，每个岛屿都有自己的专用章节，其他人无法编写。
起初，邻居们很兴奋:因为每个人都不再需要排队和一个隐士说话，这个过程变得更快了，甚至考虑到去 Fotas 的旅行时间。(事实上，Fotan 通过在 Fotan 网络的各个岛屿上建立大使馆来改善旅行时间)它也更加可靠，因为当海啸摧毁了几个岛屿并严重损坏 Fotas 本身时，每个人都会被提醒。因为每一个佛昙都有全部律法的复制品，所以很容易复原。(佛坦人后来改进了系统，让每个章节只由一些佛坦人维护，遍布全岛；这给了他们相同的总体可靠性，而不需要花费复制每个客户岛的法律到 Fotas 上的绝对每个点，并且由于 Fotas 靠近如此多的岛屿，这些岛屿甚至可以开始使用 Fotian 系统作为一种可靠地相互发送消息的方式。
但是我们上面看到的两个问题变得更加明显。例如，在 Parafoitas 岛(客户岛屿之一)，Andros 的葡萄酒公司一直使用 Fotian storage 来跟踪其订单。一天，安德罗斯为一个当地政客的婚礼订购了 100 瓶葡萄酒，并把它登记在了订单簿上。第二天，他的一名员工检查了订单簿——但该员工派往 Fotas 的信使碰巧去了一个与 Andros 不同的港口，由于道路泥泞，该港口尚未收到前一天的更新。员工因此不知道订单的事，酒直到婚礼后的第二天才做出来！(Andros 考虑在他的办公室里放一块板子，列出每个订单输入的时间，每个人都会在提交或执行订单之前检查，但当他意识到他刚刚制作了自己的隐士板时，他停止了，在这种情况下，他到底为什么要支付这些 Fotans？)
在西拉诺斯岛上，情况也好不到哪里去。在那里，他们试图解决读-修改-写的问题，方法是让鲍西斯在星期一负责偶数编号的法律，让盖伦负责奇数编号的法律，在星期二换班，等等，这样一次只有一个人可以试图影响一个法律。但事实上，盖伦很不耐烦地想改变某个偶数定律，所以他尽可能快地在周二午夜时分改变了它。不幸的是，Baucis 在前一天晚上 11:58 对同一个定律进行了修改，当 Galen 进行自己的修改时，她的修改还没有被他看到——因此 Galen 发布了一个修改，认为他是唯一这样做的人，并且无意中覆盖了 Baucis 的工作。
另一方面，一些邻近的岛屿很满意；例如，Epifoitas 一直使用 Fotian 存储来保存他们的诗歌档案。一旦一首诗被提交到档案馆，它将永远不会被改变，只有阅读，新的诗歌可能会增加作为回应；因此，从来没有人担心一首诗会被改写。对他们来说，福田系统既可靠又便宜。但总的来说，有足够多的岛屿想要定期阅读和书写他们的文本，佛天法的不足之处变得很明显。
Paxos 的兼职议会
所以现在我们来到了帕克斯岛。这是莱斯利·兰波特发明的最初想象的爱琴海岛屿，它导致了整个隐喻，事实上他描述的方法因此被普遍称为“帕克斯算法”。(本文中所有其他岛屿的名称都是我自己发明的)
关于这个算法的好消息是，它并不比我们刚才讨论的更复杂，他的论文也是以同样的风格讨论的；如果你对阅读这篇文章感到舒服，你现在可以简单地拿起兰波特的论文“兼职议会”，毫无困难地阅读它。坏消息是，我想不出任何比 Lamport 的解释更短的方式来解释它，这将使这个已经很长的故事长得惊人，所以我将把细节留给他的仁慈。但是我可以给你一个想法的总结:
帕克森人关心的是记录他们自己的法律，因此非常关心写后读的一致性，这样每个人都可以知道这片土地上的现行法律。他们还希望有读-修改-写的一致性，因为否则他们可能会意外地通过冲突的法律。总的来说，这种一致性通常被称为强一致性，而佛天系统的较弱属性被称为最终(或弱)一致性。
帕克森问题的细节(如果你阅读这篇文章，你会了解更多)略有不同:他们的法律只由他们的议会通过，议会在一个房子里开会，所以他们不必担心成员由于泥石流或海啸突然变得无法联系。但相反，他们有一个兼职议会:立法者可以随心所欲地来来去去，变得遥不可及不是因为自然灾害，而是因为一瓶特别好的葡萄酒。由于大厅的音响效果不好，演讲是不可能的，立法者必须通过信使相互交流，就像佛坦人一样。因此，尽管存在表面上的差异，Paxos 的兼职议会带来了与 Fotas 的分散议会相同的后勤复杂性。
Paxos 解决方案的核心理念很简单:为了改变法律，你可以让大多数 Pax OS 做出同样的改变。在这一点上，如果有人试图做一个矛盾的改变，当他们试图建立自己的多数时，保证至少有一个人知道另一个改变，谁能阻止他们并说“等等！我们已经在为不同的东西投票了！”(因为如果你有两组 Paxons，每组都比一半大，那么它们之间至少有一个人是共同的！)同样，当你希望阅读法律，你问大多数 Paxons 法律的最新版本；再说一遍，如果发生了什么变化，他们中至少有一个人一定听说过。这些细节相当于一种跟踪当前正在进行的投票的方法，这是基于每个 Paxon 都有自己的法律日志和笔记本，他们可以在其中跟踪自己的投票和他们收到的消息。
Lamport 的方法提供了几个重要的保证:它具有写后读的一致性，因为一旦一个被提议的法律出现了一致的条件，它保证了将来每一次阅读该法律的尝试都将看到这种一致；它使得读-修改-写成为可能，因为一旦对给定规则的改变开始，要么该改变将以不允许介入写操作而结束，要么(如果中途发现介入写操作已经开始)该改变将明确失败，并且每个人都知道要再试一次；它进一步满足了“进步条件”，即“如果大多数立法者在众议院，并且没有人进入或离开众议院很长一段时间，那么立法者在众议院提出的任何法令都将被通过，并且每个通过的法令都将出现在众议院每个立法者的账本上。”
然而，这是有代价的。通过一项法律——即写入系统——需要在大多数成员之间建立共识。如果一些成员远离发起者，那么这可能是一个非常慢的过程；你不能再通过简单地把它写在你自己的日志里来增加一条法律。阅读法律也变成了一个缓慢的过程，因为这个过程现在需要询问一定数量的帕克森人对法律的看法。
为了缓和这种情况，Paxon 系统实际上提供了两种读取方法:“最新读取”，它执行如上所述的定额读取，以及“最近读取”，它包括简单地检查您自己的日志。最近的读取缺乏 Paxos 系统的一致性保证，但它们很快，并且在实践中许多系统只在某些时候需要这些强保证。(例如，Agnes 和 Basil 可能希望在解决他们关于卖羊的纠纷时阅读最新消息，但是在平常的一天，当他们中的一个去市场时，他们会在离开家之前阅读最新消息)
尽管如此，这意味着 Paxos 方法总是有不小的速度成本，并且随着参与人数的增加，这种成本会迅速增加。(即使没有很长的传输时间，单个 Paxons 的回答时间的简单随机变化也会产生影响，因为每个操作都需要等待超过一半的人回答，所以你最终会等待较慢的人)
复合系统和主选举:回到 Siranos
这些系统的一个有趣的特性是它们可以组合。例如，在 Fotas 和 Paxos 系统中，每个立法者都有一本法律期刊和自己的笔记本。这些系统的设计仅仅依赖于这样一个事实，即立法者可以在他们的自己的书里写，并保证强一致性。在普通笔记本的情况下，只有一个立法者写和读，这是很容易实现的。
但是没有理由说这只能通过笔记本来实现，这让我们可以解决更多的问题。想象一个由岛屿组成的网络，每个岛屿都很小，但是被大海分隔开，就像在太平洋中一样。(或者用计算机术语来说，想象一个数据中心网络，每个数据中心都在一栋建筑内，但分布在整个世界)使用 Paxos 在这样的距离上提供一个高度一致的存储是非常不切实际的，因为每次读取或写入都需要一个法定人数，这需要多次岛间旅行。但是，每个岛都可以使用上述任何方法维护自己的强一致性商店，然后一个单独的岛间组织可以使用任何方法维护自己的法律，只需用单岛商店替换单个笔记本。局限于单个岛的客户只能处理他们自己的岛的系统，而做岛间业务的客户可以使用不同的系统，但可以获得在他们的岛上有多个单点联系的所有健壮性优势。
这种可能性导致西拉诺人重新考虑他们自己的系统。请记住，这个岛屿曾试图通过按天划分他们的法律来实现强一致性，这样一来，鲍西斯可以在星期一写偶数法律，而盖伦在星期二写偶数法律，反之亦然。尽管这个简单的系统遇到了问题，但它揭示了一个重要的事实:周一对卖羊法律感兴趣的人很可能在周二仍然对它感兴趣，而且兴趣的变化相对较少；同样，导致人们消失的事故——没有人去处理关于羊的法律——也相对较少。即使许多非常一致的方法很慢，如果你必须在很少的情况下做一些慢的事情，如果你的日常生活很快，这也是可以的。
这导致西拉诺人问自己，对于任何主题，他们是否可以简单地选举一个暴君来负责与该主题相关的所有法律。只要每个人都可以很容易地找到任何特定主题的暴君，而暴君本人也不会变得请求过多，这将实现一种更简单的强一致性形式:任何希望改变该主题的法律或了解该主题的最新法律的人都可以简单地与暴君交流，这是一种伪现代隐士的风格；然而，任何希望简单地了解最新情况的人都会阅读他们自己的普通法律书籍，以 Fotan 风格复制给他们。
基本原理很简单。比方说，鲍西斯想知道羊法。鲍西斯询问中央暴君登记处，“谁是现在的羊暴君？”如果登记处说菲利蒙是，那么鲍西斯立即知道去哪里。如果注册处说没有人是，那么她简单地向这个注册处提出一个法律，“鲍西斯应该是羊的暴君。”如果这项法律通过，那么鲍西斯现在是羊暴君，可以完全靠她自己；如果这项法律失败了，那么在此期间一定会有另一项法律通过，所以她只是重复她的疑问。
正如你可能已经猜到的，暴君的中央注册表只不过是另一个强一致性存储。对于非常小的群体，单个隐士可能是可行的，但是出于规模和可靠性的原因，通常最好使用 Paxos 方法来构建中央暴君注册中心。虽然岛间的 Paxos 可能非常慢，但你只需要在很少的情况下访问它，当你想找出(或成为)某个特定主题的暴君时；关于这个主题的普通交流是一对一的。
这种方法有一些很好的优点。如果只有一个人对一个给定的主题感兴趣(一种常见的情况，尤其是如果主题相当狭窄)，那么这个人可以成为该主题的暴君，而根本不需要与任何邻居打交道；他们可以像一个隐士一样继续工作，阅读和写作他们自己的书，确信没有人被允许改变关于他们主题的法律。如果许多人有共同的兴趣，那么所有这些人都必须排队与一个暴君说话，但暴君可以立即给他们一个答案，而不必等待信息被带到整个岛屿。
然而，还是有一些问题。首先是死霸。鲍西斯统治羊群多年后，有一天心脏病发作。然而，没有人知道这件事，所以每个关心羊的人都在她家门口排队，永远等着她出现，所有的养羊法都停止了几天，直到最后门被打破，发现她死了，西拉诺人通过了一项法律，废除了她的暴政。在这种情况发生一次后，西拉诺人以一种简单的方式正式确定了解决方案，即任期条款:鲍西斯不会通过“鲍西斯应该是羊的暴君”，而是提出“鲍西斯应该是羊的暴君，直到星期四中午。”如果她还活着，并且对绵羊感兴趣，那么在周四早上的某个时候，她可以提出另一项投票措施来延长她的统治。
第二个问题是超载的暴君。在爱琴海小岛上做羊的暴君是一回事；成为新西兰的羊之王完全是另一回事，那里的羊比人多 7:1。暴君门外的队伍会变得令人难以忍受！
幸运的是，在这个系统中没有任何东西要求暴君是个人——简单地说，暴君必须提供他们的主题的强一致的表示，并使用一些健壮的方法将更新传输到所有其他法律期刊。因此，在新西兰，不是一个人被选为羊的暴君，而是一群感兴趣的牧场主联合起来组成了几维羊暴政联盟。作为一个由相对可靠的人组成的相对较小的小组，他们可以使用 Paxos(或任何其他系统)以合理的轻松和速度维护一个共享的法律手册。如果他们发现自己经常超负荷工作，他们可以简单地在组织中增加新成员，这样就有更多的人可以满足客户的要求。
更有用的是，他们可以不断改进他们的方法。当 KSTC 很小的时候，他们可能会使用每个人都可以立刻阅读的大型印刷期刊，而内部只是轮流阅读；或者他们可以在他们之间划分主题，如果有人暂时不在，就临时由其他人来处理；或者他们可能使用 Paxos 或者最终，随着 KSTC 的发展，他们甚至可能以自己的方式细分绵羊法，并进行内部主选举，以确定奥塔哥地区剪羊毛的次暴君。这样做的好处是，他们的客户永远不需要理解，甚至不需要知道他们如何在内部存储信息的细节；只要 KSTC 提供保证，任何上门的人都将受到绵羊法则的强烈一致的代表，方法可以反复改变。
这个主选举协议的经典版本叫做 小胖 。
总之
如果您已经做到了这一步，那么您已经了解了分布式计算中一些最具挑战性的主题。几乎数据中心或全球规模的计算中的每个问题都可以归结为这些问题:如何让一群通常彼此相距很远、通过不可靠的链接连接并且容易在不可预测的时间间隔停机的计算机就它们存储的信息达成一致？
在实践中，有四种常用的方法:
- 单一数据存储(Pseudemoxian 隐士)，其中一台计算机保存自己的副本，希望使用它的每个人都必须轮流使用，系统容易受到单一灾难的影响；然而，这个系统非常一致，非常简单，所有其他系统都建立在它的基础上。
- 最终一致复制(Fotan 系统)，其中每个参与者都有他们自己的(强一致)存储，每个人都修改和读取他们自己的副本，随后向他们所有的同伴分发和接收更新。这具有快速和简单的优势，以及对多种灾难的鲁棒性，但缺乏强一致性的保证，即一旦你写了，所有未来的读者都会知道它。这种系统在不需要这种保证的情况下非常有用，例如分发在写入后永远不会改变的图像(或其他大数据)的副本，以及不真正需要新鲜度的情况。
- 法定人数决策(Paxon 系统——与其他示例不同，在正常的 CS 对话中，该系统实际上被称为“Paxos ”),其中读取和写入涉及获得大多数参与者的同意。这提供了很强的一致性和健壮性，但可能会非常慢，尤其是当分布在一个很宽的区域时。
- 主选举(Siranon 系统)，其中使用一个昂贵的、强一致性的存储来决定谁在一段时间内负责任何主题，然后该负责方使用他们自己的、较小的、强一致性的存储来维护关于该主题的法律。
因此，系统的选择以及如何组合是一个实际问题。例如，如果希望维护一个系统，在该系统中，许多用户可以几乎实时地同时看到一个共享数据(可能是一个共享文档或一个计算机游戏)的变化，那么由尽可能小的组来管理该单个共享数据是有帮助的。在这种情况下，主节点选举运行良好，单个主节点经过优化，可以快速处理单个数据。延迟来自从客户端到主服务器的消息传输时间，以及主服务器的排队延迟；后者可以通过把 master 本身做大(甚至把它变成一个小集群本身)来解决，而前者只是一个问题。
另一方面，如果一个人希望为用户上传的数十亿张图像(倾向于庞大的数据)提供服务，那么除了对上传用户而言，强一致性没有什么好处。然后，您可以通过让单个服务器与用户通信来处理上载过程本身，直到数据完全上载；因为我们知道，在上传完成之前，这个用户是唯一查看图片的人，所以默认情况下，这个服务器是数据的“主人”,没有额外的欺骗。一旦上传完成，最终的一致性就足够了。(这带来了更有趣的问题，比如“部分复制”的可能性:“只有一些网站有每张图片的副本，但如果需要，任何网站都可以访问另一个网站的图片。我自己的工作，几年前，是在那个领域)
这些系统最好的一点是，从客户的角度来看，它们不是由方法定义的，而是由它们提供的保证定义的。如果您告诉您的客户，这里有一个非常一致的系统，他们可以通过使用这个 Greek 来执行写入、读取当前和读取最新，那么可以说，您可以随着客户需求的增长和变化而不断改变您使用的方法(从单个数据文件到主选举，主选举选择本身使用 Paxos 或其他什么的集群),而不需要他们之间达成任何共识或协议。
就这样，我现在离开你。你已经漫游了一系列关于想象中的岛屿、羊霸、泥石流之类的荒谬故事；但你刚刚学到的根本不是婴儿版的计算机科学，而是实际的真实的东西，专业人士每天花时间做的事情。所以我希望，即使你自己不是计算机科学家，也不打算成为，你现在对现代计算有了更好的理解——或者至少，对涉及羊的部分有了更好的理解。
黑客中午是黑客如何开始他们的下午。我们是 @AMI 家庭的一员。我们现在接受投稿并乐意讨论广告&赞助机会。
要了解更多信息，请阅读我们的“关于”页面、在脸书上给我们点赞/发消息，或者简单地说， tweet/DM @HackerNoon。