一年一度的春运又到了，据臆度，本年铁路客运量或超 5.1 亿东谈主次，日均 1275 万东谈主次，东谈主们在比拼手速抢票的背后，12306 的计较机系统是怎样快速反应海量的央求的呢？单台做事器由于有限的计较才略无法快速反应成千上万的央求，设想一下线下的购票大厅唯唯独个售票窗口却有一万东谈主列队的场景，东谈主们就怕齐要带上睡袋来列队了。

那怎样加速售票的经过来减少东谈主们的恭候时候呢？领先窗口的责任主谈主员不错加速手速，以极快的速率进行操作，但是单个责任主谈主员的手速再快也有一个上限；另一个办法就是在大厅开设多个窗口，同期进行售票。网罗售票系统亦然相同的，单台做事器处理不外来，就使用多台做事器来进行协同处理，这就需要"漫衍式系统"登场了！

什么是漫衍式系统？

平常地说，漫衍式系统是指，一群计较机共同完成一个任务。这些计较机也可称为节点，它们通过网罗衔接在全部，单干合作，但对用户推崇得像一个合座。不单是是 12306 售票系统，你刷视频时看到的推选、搜索引擎给出的搜索效果、外卖平台的订单分派，背后齐是漫衍式系统在肃静运行。比拟单个做事器，使用漫衍式系统既能提升系统的性能、反应央求的速率，又能提供更好的可靠性，部分节点宕机或者断网了，通盘系统依然能链接提供做事。

漫衍式系统虽有这些平允，但是它带来的复杂性也给计较机系统野心漠视了挑战。这里就触及并发（concurrency）以及数据一致（consistency）的问题。

以售票为例，试想以下场景，东谈主在北京的张三和东谈主在广州的李四在抢并吞张票，张三的抢票央求被分发到了华北地区的某台做事器，而李四的央求被分给了华南地区的某做事器，这俩做事器当今不错同期并行地处理两个东谈主的抢票央求，系统合座的反应速率很快，但是系统怎样妥贴地配合使得票不会被卖重呢？

此外，漫衍式系统的另一大秉性是存在部分失效（partial failure）的可能性，顾名念念义，就是系统部分出现故障，但系统其他部分仍可运行。漫衍式系统由繁密计较机组成，而且通过网罗衔接。理解，岂论是计较机照旧网罗自己齐有可能出现故障，比方某处停电了、网线断了，又或是某台计较机操作系统故障，等等。即使一台机器发生故障的概率很低，可是当计较机的数目多了，对于通盘系统来说，故障会独特平日。

咱们不错作念一个绵薄的计较，假设系统中有 1000 台计较机，每台平均一年只出一次故障（故障可能由任何原因导致），即每天出现故障的概率是 1/365；反之，每天不出现故障概率是 1-1/365，约等于 0.99726。这看起来是一个很大的概率，但是对通盘系统而言，每天扫数机器齐不出故障的概率则是 0.99726 的 1000 次方，约为 0.064。这里还未计划网罗问题，是以对于系统来说，不出故障简直是不成能的。

因此，在漫衍式系统的野心中，如安在部分节点故障或者网罗断开的情况下，依然提供正常的做事是必须计划的问题。

漫衍式系统的基石——共鸣算法（consensus algorithm）

共鸣算法在漫衍式系统中上演着中枢脚色，它使得系统在莫得分享的内存，只可通过发送音问通讯，而且部分节点可能失效的情况下，通盘系统依然大要就某个问题达成共鸣。比方某一个特定的座位到底是卖了照旧没卖，是卖给了张三照旧李四等等，需要系统达成共鸣才能链接扩充。

漫衍式系统前驱、有名图灵奖得主 Leslie Lamport 于 1990 年漠视了当代共鸣算法的基础—— Paxos 算法。

Lamport 用 Paxos 这个名字的起因很特意旨好奇瞻仰。Paxos 本是希腊伊奥尼亚海有着悠久历史的小岛，Lamport 设想，考古学家发当今邃古时期小岛上有一个"业余议会"（part-time parliament），议员们通过信使传递音问对议案进行表决，但是信使不成靠，音问可能传递不到或者被延长，而且议员自己也有不来开会的可能性，在这种情况下，议员们怎样对某议案达成一致？在论文中，Lamport 使用这个诬捏在 Paxos 小岛的议会为框架，漠视了一个在不成靠通讯的情况下完毕共鸣的算法，并给出了严格的数学讲授。

1990 年 Lamport 将论文提交给 ACM Transactions on Computer Systems，审稿东谈主暗意论文还算是好奇瞻仰，但看起来并不很首要，而且对于 Paxos 故事的部分建议去掉。Lamport 暗意，审稿东谈主怎样这样一丝幽默感齐莫得，并拒完全论文作念任何修改。其后，漫衍式系统的另一位前驱 Butler Lampson 读懂了论文，并和 Nancy Lynch 等领域大佬全部发表了他们我方的讲授，此时 Lamport 再次计划将论文发表，最终在一众同业的股东下，论文于 1998 年发表，当今还是成为漫衍式系统的基石。

底下咱们以卖票系统为例，简述一下 Paxos 算法的念念想，以及它如安在节点失效的情况依然达成共鸣。为了简化，假设系统中唯独 3 台做事器（节点；3 个节点是演示 Paxos 算法所需的最少许量），而且只卖一张票（卖多张票也不错意会成反复卖一张票的经过）。此外，咱们还需要先简述一下算法的假设。

领先，Paxos 算法假设一个节点若是故障则完全罢手反应，而不会链接在网罗发送失实的音问以烦嚣系统，它被缔造之后会回到系统中链接反应，这种类型的失效被称为 fail-stop（失败拆开），即 fail 后就 stop 了。其次，Paxos 是一个基于大批派投票的算法，即需要大批节点投票通过才被觉得是共鸣；Paxos 需要 2m+1 个节点才能容纳 m 个节点失效。也就是说，要大要容纳 1 个节点失效，至少系统需要有 3 个节点（另外两个正常运行）。若是超出半数的节点齐失效，那 Paxos 算法将无法正常运转。

当今咱们给这三台做事器分派一个全局的序号以示永别：1 号节点、2 号节点和 3 号节点。Paxos 算法会为每个节点分派一个脚色，这里假设 1 号节点是提议者（proposer）亦然吸收者（acceptor）；2 号和 3 号节点是吸收者，只吸收，不提议。当今 1 号节点收到了来自张三的购票央求，它脱手了算法的第一步：PREPARE-PROMISE。

提议者 1 号节点领先会为它的提议 proposal（即卖票给张三）分派一个唯一的序号（proposal number）。系统中扫数的提议齐会有一个我方私有的序号，一种绵薄的完毕神志是这样：

每个节点我方珍摄一个计数器（counter），启动值为 0，每次我方漠视新的提议时，计数器加 1；新提议的序号设定为由计数器的数值和该节点的全局 ID 所拼接组成的少许，两者中间用少许点作念间隔，即 {counter}.{ID}。比如 1 号节点的第一个提议的序号为 1.1，第二个提议的序号则是 2.1。雷同的，2 号节点的第一个提议序号为 1.2，它的第二个提议的序号则是 2.2，依此类推。按照这种序号的野心神志，当提议者 1 号节点收到张三的央求以后，它领先会发送一条 PREAPRE 音问给其他扫数节点，而且附上提议的序号 1.1，这里写稿 PREPARE ( 1.1 ) 。

收到提议的吸收者们按照以下逻辑进行反应：

1. 稽察收到的 PREPARE 音问所附带的提议序号。

2. 将收到的提议号与我方土产货的 max_id 进行对比。若是更大，则将土产货的 max_id 更新为这个收到的提议号，并复返一条 PROMISE 音问，极端于告诉提议者：我收到你的音问了，刻下你的提议号是最大的哦，准备提议吧，我承诺将不再吸收比你的序号小的提议。

3. 若是收到的提议序号小于它土产货的 max_id，该吸收者就不作念回复，或者回复一条 fail 音问，即告诉提议者：你的提议失败。

若是提议者（1 号节点）收到了来怡悦大批吸收者（我方也算一个）复返的 PROMISE 音问，这时候它就知谈，宇宙还是作念好准备吸收它的提议了。若是莫得得到大批东谈主的回答，或者收到了一个 fail 音问，提议者就只可烧毁本轮的提议，它不错将我方土产货 counter 加 1，然后再次漠视新一轮的提议（由于 counter 加了 1，提议号也会加 1），从头尝试。当 1 号节点收到了来怡悦批节点的 PROMISE 音问后，它就干与第二步：PROPOSE-ACCEPT。

在第二步中，1 号节点会发送一条 PROPOSE 音问，而且附带上刚才的提议号，以及具体的值（value），这里的值 value 就是宇宙但愿达成共鸣的东西，在本文买票的例子中，它的内容就是"张三"，代表票卖给张三。是以 1 号节点发送的音问是这样：

PROPOSE ( 1.1，"张三" )

收到音问的吸收者们当今要作念一个判断，是否吸收这个提议，它们的逻辑是这样的：

1. 若是 PROPOSE 音问里附带的提议号依然是我刻下收到的最大的（即和我方的 max_id 进行对比），那就吸收这个提议，而且复返一条 ACCEPTED 音问；

2. 不然就不复返音问，或者复返 fail 音问，告诉提议者：提议失败。

若是提议者收到来怡悦大批节点的 ACCEPTED 音问，那它就知谈共鸣还是达成了。假设当今 2 号和 3 号齐正常收到了 PROPOSE 音问，并正常复返了 ACCEPTED 音问，则扫数节点就"票卖给张三"这一气象达成了一致。

纪念一下，这里达成共鸣一共用了两步。第一步的主见在于取得大批东谈主的承诺，极端于提议者对每个东谈主喊话：我要进行修改数据了啊，你们承诺不承诺？唯独当取得了大批东谈主的承诺之后，才会进行第二步——提议者果然发出要 propose 的值。

试想，若是算法跳过第一步，胜仗发送要 propose 的值，不同的吸收者就可能会收到来自不同提议者的值。而这个时候又因为莫得预先征求大批的承诺，终末吸收者也不知谈我方收到的值是否就代表了大大批的意见，系统中可能会有多个子群体宇宙各自有我方的值，这样全局的共鸣就莫得了。

齐全的 Paxos 算法逻辑

到此戒指，算法的运行一切正常，当今咱们再来望望一些愈加复杂的情况。

假设不光 1 号节点是提议者，2 号节点因收到了李四的央求，也成为了一个提议者（留神扫数节点齐是吸收者），当今系统里就有了两个不同的提议者，它们发送的音问可能以任何的神志交汇在全部。

假设 3 号节点可能先收到了来自 1 号节点的 PREPARE 音问（张三购票），即 PREPARE ( 1.1 ) ，而且复返了 PROMISE。就在这时，它又收到了 2 号节点的 PREPARE 音问（李四购票），即 PREPARE ( 1.2 ) ，因为提议号 1.2 大于 1.1，于是它又会给 2 号节点复返 PROMISE，而且将我方的 max_id 更新为 1.2。留神，1 号节点会进行第二步链接发送 PROPOSE 音问，PROPOSE ( 1.1，"张三" ) ，但此时 3 号节点还是不会再吸收它的提议了，因为当今对它而言，1.2 是更新的提议。唯独当 2 号节点的 PROPOSE 音问发过来时它才会吸收。

再计划另一种情况，假设李四的操作比张三慢了那么一丝点，当 2 号节点成为提议者，而且发送 PREPARE ( 1.2 ) 的时候，3 号节点还是吸收 1 号节点的提议了（提议号为 1.1），即 ACCEPTED 音问还是发送。而这时 2 号节点因为各式原因还莫得收到 1 号节点的 PREPARE 音问，浑然不知 1 号和 3 号已达成共鸣（票卖给张三）。那么把柄 Paxos 算法，当 3 号节点收到来自 2 号的 PREPARE ( 1.2 ) 音问时，由于 1.2 是 3 号见过的最大的提议号，是以它果然会向 2 号复返一个 PROMISE 音问，但是因为 3 号又还是吸收此前的提议 1.1 了，是以在它复返的 PROMISE 音问中，会附上之前所吸收提议的序号以及值，即 PROMISE ( 1.1，"张三" ) ，即告诉 2 号：我收到你的提议号了，它果然是最新的提议，但是我此前还是吸收过序号为 1.1 的提议了，它的内容是"张三"。2 号收到该音问，了解到票还是卖出，此时把柄 Paxos 算法，2 号必须将我方要 propose 的值改变为"张三"，然后链接发送 PROPOSE 音问，于是扫数的节点依然是达成了共鸣。

最终客户端的李四看到的效果等于：票已售罄。事实上，提议者可能会收到多个带此前吸收值的 PROMISE 音问，它将会考中这些扫数 PROMISE 内部提议序号最大的阿谁对应的值，四肢我方要 propose 的值，若是莫得任何 PROMISE 音问里带有此前吸收的提议信息，提议者则链接用我方蓝本想 propose 的值。更新后的吸收者和提议者的齐全逻辑分别如下图所示。

PREPARE-PROMISE 经过。图片起首：https://people.cs.rutgers.edu/~pxk/417/notes/paxos.html

这等于齐全的 Paxos 算法。终末咱们再来绵薄计划下断网或者节点宕机的情况，望望 Paxos 如安在故障情况下依然能正确运行。

网罗或节点失效下的 Paxos

岂论是提议者照旧吸收者齐有宕机的可能性。当吸收者宕机时，试验上对系统运行影响不大，这恰是漫衍式系统的上风：哪怕有一些节点分歧 PREPARE 音问或者 PROPOSE 音问作念任何反应，只须有大批的节点依然在线，系统依然能作念出反应，提议者依然能得到大批东谈主的回复，于是算法运行。而当宕机的节点死而复生后，他们终究也贯通过其他节点发来的带有此前已吸收提议信息的 PROMISE 音问来了解到我方错过的共鸣，在我方土产货也进行更新。

那若是提议者（比方 1 号节点）宕机呢？分为三种情况：

1. 假如它在发送 PREPARE 音问之前宕机，那极端于系统内部什么也莫得发生。其他节点接考取户的需求时会变为新的提议者；

2. 若是提议者在发送 PREPARE 音问之后宕机，还没来得及发送 PROPOSE，如咱们刚所说，它的提议会被之后更新的 PREPARE 所取代（由新的提议者所发出）；

3. 若是提议者还是完成了第一步 PREPARE-PROMISE，干与了第二步，但是在给部分节点发送 PROPOSE 音问后宕机，比方 1 号在给 3 号发送完 PROPOSE 之后宕机，没来得及发给 2 号；那它的提议将会被 3 号吸收，而 2 号最终照旧会了解到 1 号和 3 号达成的共鸣。因为 2 号在某时会成为提议者，它终究会收到 3 号复返的带有此前已吸收提议信息的 PROMISE 音问，并据此来更新我方土产货的信息，于是与 1 号、3 号保捏了一致。

是以终末回到抢票上，当咱们从客户端发出买票央求以后，它会和背后复杂的漫衍式系统进行交互，宇宙若是抢不到票并不一定因为我方手速不够快，还有可能是网罗延长、衔接的做事器宕机，或者和系统算法自己的运作相干。

结语

漫衍式系统四肢当代计较机系统的基石，大要援助 12306 购票这样的高负载、高并发场景。本文征询了漫衍式系统中对于一致性与容错性的一些基本倡导与本领完毕。

事实上，漫衍式系统的讹诈不单是线上网购，在加密领域，漫衍式系统为区块链本领提供了基础援助，确保数据的安全性和一致性；在科学计较领域，漫衍式系统也被用来贬责更大规模的问题。这些领域齐展示了漫衍式系统在咱们日常生涯和本领发展中证据着不成或缺的作用。

终末，春节随即到了，祝宇宙：春节欢乐万博ManBetX下载地址，阖家幸福！