春运抢票，原来售票体系背后的技能这么精妙！

一样平常生存中，网络购物、在线支付、舆图导航等便捷的应用，人们已经习以为常，以至于我们险些不会关注其背后的技能。这自然离不开通讯网络的飞跃发展，而那些功能的实现则要归功于分布式体系的进步。本文通过网络购票的实例，扼要先容分布式体系的概念，包罗其焦点的Paxos算法，以及它怎样应对网络断开的寻衅。

撰文 | 陈清扬

一年一度的春运又到了，据估计，本年铁路客运量或超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年发表，如今已经成为分布式体系的基石。

分布式体系先驱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购票这样的高负载、高并发场景。本文讨论了分布式体系中关于划一性与容错性的一些根本概念与技能实现。毕竟上，分布式体系的应用不但是线上网购，在加密范畴，分布式体系为区块链技能提供了底子支持，确保数据的安全性和划一性；在科学盘算范畴，分布式体系也被用来办理更大规模的题目。这些范畴都展示了分布式体系在我们一样平常生存和技能发展中发挥着不可或缺的作用。最后，春节立刻到了，祝各人：春节快乐，阖家幸福！

注：本文封面图片来自版权图库，转载使用大概引发版权纠纷。