日常生计中，网罗购物、在线支付、舆图导航等方便的愚弄，东谈主们如故习以为常，以致于咱们险些不会关心其背后的期间。这当然离不绽开讯网罗的飞跃发展，而那些功能的终了则要归功于分散式系统的超越。本文通过网罗购票的实例，简要先容分散式系统的宗旨，包括其中枢的Paxos算法，以及它如何应酬网罗断开的挑战。

撰文 | 陈清扬

一年一度的春运又到了，据意想，本年铁路客运量或超5.1亿东谈主次，日均1275万东谈主次，东谈主们在比拼手速抢票的背后，12306的策动机系统是如何快速反馈海量的恳求的呢？单台劳动器由于有限的策动才略无法快速反馈千千万万的恳求，联想一下线下的购票大厅只须一个售票窗口却有一万东谈主列队的场景，东谈主们或许都要带上睡袋来列队了。

那如何加速售票的历程来减少东谈主们的恭候时刻呢？最初窗口的使命主谈主员不错加速手速，以极快的速率进行操作，然则单个使命主谈主员的手速再快也有一个上限；另一个办法就是在大厅开设多个窗口，同期进行售票。网罗售票系统亦然相似的，单台劳动器处理不外来，就使用多台劳动器来进行协同处理，这就需要“分散式系统”登场了！

什么是分散式系统？

泛泛地说，分散式系统是指，一群策动机共同完成一个任务。这些策动机也可称为节点，它们通过网罗贯穿在一齐，单干合作，但对用户发达得像一个举座。不单是是12306售票系统，你刷视频时看到的推选、搜索引擎给出的搜索效果、外卖平台的订单分拨，背后都是分散式系统在沉默运行。比较单个劳动器，使用分散式系统既能进步系统的性能、反馈恳求的速率，又能提供更好的可靠性，部分节点宕机或者断网了，通盘系统依然能接续提供劳动。

分散式系统虽有这些公正，然则它带来的复杂性也给策动机系统蓄意建议了挑战。这里就波及并发 （concurrency）以及数据一致 （consistency）的问题。以售票为例，试想以下场景，东谈主在北京的张三和东谈主在广州的李四在抢兼并张票，张三的抢票恳求被分发到了华北地区的某台劳动器，而李四的恳求被分给了华南地区的某劳动器，这俩劳动器当今不错同期并行地处理两个东谈主的抢票恳求，系统举座的反馈速率很快，然则系统如何允洽地配合使得票不会被卖重呢？

此外，分散式系统的另一大特质是存在部分失效 （partial failure）的可能性，顾名念念义，就是系统部分出现故障，但系统其他部分仍可运行。分散式系统由稠密策动机组成，而且通过网罗贯穿。显豁，岂论是策动机照旧网罗自身都有可能出现故障，比喻某处停电了、网线断了，又或是某台策动机操作系统故障，等等。即使一台机器发生故障的概率很低，关联词当策动机的数目多了，对于通盘系统来说，故障会相等泛泛。

咱们不错作念一个浅近的策动，假设系统中有1000台策动机，每台平均一年只出一次故障 （故障可能由任何原因导致），即每天出现故障的概率是1/365；反之，每天不出现故障概率是1-1/365，约等于0.99726。这看起来是一个很大的概率，然则对通盘系统而言，每天 统统机器都不出故障的概率则是0.99726的1000次方 ，约为0.064。这里还未探究网罗问题，是以对于系统来说，不出故障险些是不能能的。

因此，在分散式系统的蓄意中，如安在部分节点故障或者网罗断开的情况下，依然提供正常的劳动是必须探究的问题。

分散式系统的基石

——共鸣算法

共鸣算法在分散式系统中饰演着中枢扮装，它使得系统在莫得分享的内存，只可通过发送音尘通讯，况且部分节点可能失效的情况下，通盘系统依然大致就某个问题达成共鸣。比喻某一个特定的座位到底是卖了照旧没卖，是卖给了张三照旧李四等等，需要系统达成共鸣能力接续现实。

分散式系统前驱、著名图灵奖得主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年发表，当今如故成为分散式系统的基石。

分散式系统前驱Leslie Lamport 丨图片起首：wiki

底下咱们以卖票系统为例，简述一下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音尘，这时候它就知谈，各人如故作念好准备收受它的提议了。如若莫得得到无数东谈主的恢复，，提议者就只可烧毁本轮的提议，它不错将我方腹地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购票这样的高负载、高并发场景。本文商酌了分散式系统中对于一致性与容错性的一些基本宗旨与期间终了。事实上，分散式系统的愚弄不单是线上网购，在加密界限，分散式系统为区块链期间提供了基础撑抓，确保数据的安全性和一致性；在科学策动界限，分散式系统也被用来措置更大限度的问题。这些界限都展示了分散式系统在咱们日常生计和期间发展中阐扬着不能或缺的作用。临了，祝各人：春节快活开云体育(中国)官方网站，阖家幸福！