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

一年一度的春运又到了，据估计，今年铁路客运量或超 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 号节点）收到了来自大多数接受者（自己也算一个）返回的 PROMISE 消息，这时候它就知道，大家已经做好准备接受它的提议了。如果没有得到多数人的答复，或者收到了一个 fail 消息，提议者就只能放弃本轮的提议，它可以将自己本地 counter 加 1，然后再次提出新一轮的提议（由于 counter 加了 1，提议号也会加 1），重新尝试。当 1 号节点收到了来自多数节点的 PROMISE 消息后，它就进入第二步：PROPOSE-ACCEPT。

在第二步中，1 号节点会发送一条 PROPOSE 消息，并且附带上刚才的提议号，以及具体的值（value），这里的值 value 就是大家希望达成共识的东西，在本文买票的例子中，它的内容就是“张三”，代表票卖给张三。所以1号节点发送的消息是这样：

PROPOSE(1.1, “张三”)

收到消息的接受者们现在要做一个判断，是否接受这个提议，它们的逻辑是这样的：

如果提议者收到来自大多数节点的 ACCEPTED 消息，那它就知道共识已经达成了。假设现在 2 号和 3 号都正常收到了 PROPOSE 消息，并正常返回了 ACCEPTED 消息，则所有节点就“票卖给张三”这一状态达成了一致。

总结一下，这里达成共识一共用了两步。第一步的目标在于获得多数人的同意，相当于提议者对每个人喊话：我要进行修改数据了啊，你们同意不同意？只有当获得了多数人的同意之后，才会进行第二步——提议者真正发出要 propose 的值。

试想，如果算法跳过第一步，直接发送要 propose 的值，不同的接受者就可能会收到来自不同提议者的值。而这个时候又因为没有事先征求多数的同意，最后接收者也不知道自己收到的值是否就代表了大多数的意见，系统中可能会有多个子群体大家各自有自己的值，这样全局的共识就没有了。

到此为止，算法的运行一切正常，现在我们再来看看一些更加复杂的情况。

假设不光 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 的值。更新后的接受者和提议者的完整逻辑分别如下图所示。

这便是完整的 Paxos 算法。最后我们再来简单考虑下断网或者节点宕机的情况，看看 Paxos 如何在故障情况下依然能正确运行。

不管是提议者还是接受者都有宕机的可能性。当接收者宕机时，实际上对系统运行影响不大，这正是分布式系统的优势：哪怕有一些节点不对 PREPARE 消息或者 PROPOSE 消息做任何反应，只要有多数的节点依然在线，系统依然能做出反应，提议者依然能得到多数人的回复，于是算法运行。而当宕机的节点死而复生后，他们终究也会通过其他节点发来的带有此前已接受提议信息的 PROMISE 消息来了解到自己错过的共识，在自己本地也进行更新。

那如果提议者（譬如 1 号节点）宕机呢？分为三种情况：

所以最后回到抢票上，当我们从客户端发出买票请求以后，它会和背后复杂的分布式系统进行交互，大家如果抢不到票并不一定因为自己手速不够快，还有可能是网络延迟、连接的服务器宕机，或者和系统算法本身的运作有关。

结语

分布式系统作为现代计算机系统的基石，能够支持 12306 购票这样的高负载、高并发场景。本文讨论了分布式系统中关于一致性与容错性的一些基本概念与技术实现。

事实上，分布式系统的应用不只是线上网购，在加密领域，分布式系统为区块链技术提供了基础支持，确保数据的安全性和一致性；在科学计算领域，分布式系统也被用来解决更大规模的问题。这些领域都展示了分布式系统在我们日常生活和技术发展中发挥着不可或缺的作用。

最后，春节马上到了，祝大家：春节快乐，阖家幸福！

策划制作

来源丨返朴（ID：fanpu2019）

作者丨陈清扬

责编丨钟艳平

审校丨徐来 林林

相关推荐

1.它被国外评为最具营养活力的蔬菜，但我打赌 90% 的人没吃过

2.长得像姜但比鸡腿还好吃！这个小众食材突然爆火，谢谢广东人！

3.越来越多人查出甲状腺问题，是熬夜、压力大导致的？

4.最不该玩手机的时间，其实不是睡前

5.一种咖啡因含量比咖啡还高的饮品，很多人喝了就失眠

本文封面图片及文内图片来自版权图库

转载使用可能引发版权纠纷
原创图文转载请后台回复“转载”

点亮“在看”

一起涨知识！