日常生活中，網(wǎng)絡購物、在線支付、地圖導航等便捷的應用，人們已經(jīng)習以為常，以至于我們幾乎不會關(guān)注其背后的技術(shù)。這自然離不開通信網(wǎng)絡的飛躍發(fā)展，而那些功能的實現(xiàn)則要歸功于分布式系統(tǒng)的進步。本文通過網(wǎng)絡購票的實例，簡要介紹分布式系統(tǒng)的概念，包括其核心的Paxos算法，以及它如何應對網(wǎng)絡斷開的挑戰(zhàn)。

撰文 | 陳清揚

一年一度的春運又到了，據(jù)估計，今年鐵路客運量或超5.1億人次，日均1275萬人次，人們在比拼手速搶票的背后，12306的計算機系統(tǒng)是如何快速響應海量的請求的呢？單臺服務器由于有限的計算能力無法快速響應成千上萬的請求，想象一下線下的購票大廳只有一個售票窗口卻有一萬人排隊的場景，人們恐怕都要帶上睡袋來排隊了。

那如何加速售票的過程來減少人們的等待時間呢？首先窗口的工作人員可以加快手速，以極快的速度進行操作，但是單個工作人員的手速再快也有一個上限；另一個辦法就是在大廳開設(shè)多個窗口，同時進行售票。網(wǎng)絡售票系統(tǒng)也是一樣的，單臺服務器處理不過來，就使用多臺服務器來進行協(xié)同處理，這就需要“分布式系統(tǒng)”登場了！

什么是分布式系統(tǒng)？

通俗地說，分布式系統(tǒng)是指，一群計算機共同完成一個任務。這些計算機也可稱為節(jié)點，它們通過網(wǎng)絡連接在一起，分工合作，但對用戶表現(xiàn)得像一個整體。不僅僅是12306售票系統(tǒng)，你刷視頻時看到的推薦、搜索引擎給出的搜索結(jié)果、外賣平臺的訂單分配，背后都是分布式系統(tǒng)在默默運行。相比單個服務器，使用分布式系統(tǒng)既能提高系統(tǒng)的性能、響應請求的速度，又能提供更好的可靠性，部分節(jié)點宕機或者斷網(wǎng)了，整個系統(tǒng)依然能繼續(xù)提供服務。

分布式系統(tǒng)雖有這些好處，但是它帶來的復雜性也給計算機系統(tǒng)設(shè)計提出了挑戰(zhàn)。這里就涉及并發(fā)（concurrency）以及數(shù)據(jù)一致（consistency）的問題。以售票為例，試想以下場景，人在北京的張三和人在廣州的李四在搶同一張票，張三的搶票請求被分發(fā)到了華北地區(qū)的某臺服務器，而李四的請求被分給了華南地區(qū)的某服務器，這倆服務器現(xiàn)在可以同時并行地處理兩個人的搶票請求，系統(tǒng)整體的響應速度很快，但是系統(tǒng)如何恰當?shù)貐f(xié)作使得票不會被賣重呢？

此外，分布式系統(tǒng)的另一大特點是存在部分失效（partial failure）的可能性，顧名思義，就是系統(tǒng)部分出現(xiàn)故障，但系統(tǒng)其他部分仍可運行。分布式系統(tǒng)由眾多計算機構(gòu)成，而且通過網(wǎng)絡連接。顯然，不管是計算機還是網(wǎng)絡本身都有可能出現(xiàn)故障，譬如某處停電了、網(wǎng)線斷了，又或是某臺計算機操作系統(tǒng)故障，等等。即使一臺機器發(fā)生故障的概率很低，然而當計算機的數(shù)量多了，對于整個系統(tǒng)來說，故障會非常頻繁。

我們可以做一個簡單的計算，假設(shè)系統(tǒng)中有1000臺計算機，每臺平均一年只出一次故障（故障可能由任何原因?qū)е拢?，即每天出現(xiàn)故障的概率是1/365；反之，每天不出現(xiàn)故障概率是1-1/365，約等于0.99726。這看起來是一個很大的概率，但是對整個系統(tǒng)而言，每天所有機器都不出故障的概率則是0.99726的1000次方 ，約為0.064。這里還未考慮網(wǎng)絡問題，所以對于系統(tǒng)來說，不出故障幾乎是不可能的。

因此，在分布式系統(tǒng)的設(shè)計中，如何在部分節(jié)點故障或者網(wǎng)絡斷開的情況下，依然提供正常的服務是必須考慮的問題。

分布式系統(tǒng)的基石——共識算法（consensus algorithm）

共識算法在分布式系統(tǒng)中扮演著核心角色，它使得系統(tǒng)在沒有共享的內(nèi)存，只能通過發(fā)送消息通信，并且部分節(jié)點可能失效的情況下，整個系統(tǒng)依然能夠就某個問題達成共識。譬如某一個特定的座位到底是賣了還是沒賣，是賣給了張三還是李四等等，需要系統(tǒng)達成共識才能繼續(xù)執(zhí)行。

分布式系統(tǒng)先驅(qū)、著名圖靈獎得主Leslie Lamport于1990年提出了現(xiàn)代共識算法的基礎(chǔ)——Paxos算法。Lamport用Paxos這個名字的緣由很有意思。Paxos本是希臘伊奧尼亞海有著悠久歷史的小島，Lamport想象，考古學家發(fā)現(xiàn)在遠古時代小島上有一個“業(yè)余議會”（part-time parliament），議員們通過信使傳遞消息對議案進行表決，但是信使不可靠，消息可能傳遞不到或者被延遲，而且議員本身也有不來開會的可能性，在這種情況下，議員們?nèi)绾螌δ匙h案達成一致？在論文中，Lamport使用這個虛構(gòu)在Paxos小島的議會為框架，提出了一個在不可靠通信的情況下實現(xiàn)共識的算法，并給出了嚴格的數(shù)學證明。1990年Lamport將論文提交給ACM Transactions on Computer Systems，審稿人表示論文還算是有趣，但看起來并不很重要，而且關(guān)于Paxos故事的部分建議去掉。Lamport表示，審稿人怎么這么一點幽默感都沒有，并拒絕對論文做任何修改。后來，分布式系統(tǒng)的另一位先驅(qū)Butler Lampson讀懂了論文，并和Nancy Lynch等領(lǐng)域大佬一起發(fā)表了他們自己的證明，此時Lamport再次考慮將論文發(fā)表，最終在一眾同行的推動下，論文于1998年發(fā)表，現(xiàn)在已經(jīng)成為分布式系統(tǒng)的基石。

分布式系統(tǒng)先驅(qū)Leslie Lamport 丨圖片來源：wiki

下面我們以賣票系統(tǒng)為例，簡述一下Paxos算法的思想，以及它如何在節(jié)點失效的情況依然達成共識。為了簡化，假設(shè)系統(tǒng)中只有3臺服務器（節(jié)點；3個節(jié)點是演示Paxos算法所需的最小數(shù)量），并且只賣一張票（賣多張票也可以理解成反復賣一張票的過程）。此外，我們還需要先簡述一下算法的假定。

首先，Paxos算法假定一個節(jié)點如果故障則完全停止響應，而不會繼續(xù)在網(wǎng)絡發(fā)送錯誤的消息以干擾系統(tǒng)，它被修復之后會回到系統(tǒng)中繼續(xù)響應，這種類型的失效被稱為fail-stop（失敗終止），即fail后就stop了。其次，Paxos是一個基于多數(shù)派投票的算法，即需要多數(shù)節(jié)點投票通過才被認為是共識；Paxos需要2m+1個節(jié)點才能容納m個節(jié)點失效。也就是說，要能夠容納1個節(jié)點失效，至少系統(tǒng)需要有3個節(jié)點（另外兩個正常運行）。如果超出半數(shù)的節(jié)點都失效，那Paxos算法將無法正常運轉(zhuǎn)。

現(xiàn)在我們給這三臺服務器分配一個全局的序號以示區(qū)分：1號節(jié)點、2號節(jié)點和3號節(jié)點。Paxos算法會為每個節(jié)點分配一個角色，這里假設(shè)1號節(jié)點是提議者（proposer）也是接受者（acceptor）；2號和3號節(jié)點是接受者，只接受，不提議?，F(xiàn)在1號節(jié)點收到了來自張三的購票請求，它開始了算法的第一步：PREPARE-PROMISE。

提議者1號節(jié)點首先會為它的提議proposal（即賣票給張三）分配一個唯一的序號（proposal number）。系統(tǒng)中所有的提議都會有一個自己獨特的序號，一種簡單的實現(xiàn)方式是這樣：每個節(jié)點自己維護一個計數(shù)器（counter），初始值為0，每次自己提出新的提議時，計數(shù)器加1；新提議的序號設(shè)定為由計數(shù)器的數(shù)值和該節(jié)點的全局ID所拼接構(gòu)成的小數(shù)，兩者中間用小數(shù)點做間隔，即{counter}.{ID}。比如1號節(jié)點的第一個提議的序號為1.1，第二個提議的序號則是2.1。類似的，2號節(jié)點的第一個提議序號為1.2，它的第二個提議的序號則是2.2，以此類推。按照這種序號的設(shè)計方式，當提議者1號節(jié)點收到張三的請求以后，它首先會發(fā)送一條PREAPRE消息給其他所有節(jié)點，并且附上提議的序號1.1，這里寫作PREPARE(1.1)。

收到提議的接受者們按照以下邏輯進行響應：

1. 查看收到的PREPARE消息所附帶的提議序號。

2. 將收到的提議號與自己本地的max_id進行對比。如果更大，則將本地的max_id更新為這個收到的提議號，并返回一條PROMISE消息，相當于告訴提議者：我收到你的消息了，目前你的提議號是最大的哦，準備提議吧，我承諾將不再接受比你的序號小的提議。

3. 如果收到的提議序號小于它本地的max_id，該接受者就不做回復，或者回復一條fail消息，即告訴提議者：你的提議失敗。

如果提議者（1號節(jié)點）收到了來自大多數(shù)接受者（自己也算一個）返回的PROMISE消息，這時候它就知道，大家已經(jīng)做好準備接受它的提議了。如果沒有得到多數(shù)人的答復，或者收到了一個fail消息，提議者就只能放棄本輪的提議，它可以將自己本地counter加1，然后再次提出新一輪的提議（由于counter加了1，提議號也會加1），重新嘗試。當1號節(jié)點收到了來自多數(shù)節(jié)點的PROMISE消息后，它就進入第二步：PROPOSE-ACCEPT。

在第二步中，1號節(jié)點會發(fā)送一條PROPOSE消息，并且附帶上剛才的提議號，以及具體的值（value），這里的值value就是大家希望達成共識的東西，在本文買票的例子中，它的內(nèi)容就是“張三”，代表票賣給張三。所以1號節(jié)點發(fā)送的消息是這樣：

PROPOSE(1.1, “張三”)

收到消息的接受者們現(xiàn)在要做一個判斷，是否接受這個提議，它們的邏輯是這樣的：

1. 如果PROPOSE消息里附帶的提議號依然是我目前收到的最大的（即和自己的max_id進行對比），那就接受這個提議，并且返回一條ACCEPTED消息；

2. 否則就不返回消息，或者返回fail消息，告訴提議者：提議失敗。

如果提議者收到來自大多數(shù)節(jié)點的ACCEPTED消息，那它就知道共識已經(jīng)達成了。假設(shè)現(xiàn)在2號和3號都正常收到了PROPOSE消息，并正常返回了ACCEPTED消息，則所有節(jié)點就“票賣給張三”這一狀態(tài)達成了一致。

總結(jié)一下，這里達成共識一共用了兩步。第一步的目標在于獲得多數(shù)人的同意，相當于提議者對每個人喊話：我要進行修改數(shù)據(jù)了啊，你們同意不同意？只有當獲得了多數(shù)人的同意之后，才會進行第二步——提議者真正發(fā)出要propose的值。

試想，如果算法跳過第一步，直接發(fā)送要propose的值，不同的接受者就可能會收到來自不同提議者的值。而這個時候又因為沒有事先征求多數(shù)的同意，最后接收者也不知道自己收到的值是否就代表了大多數(shù)的意見，系統(tǒng)中可能會有多個子群體大家各自有自己的值，這樣全局的共識就沒有了。

完整的Paxos算法邏輯

到此為止，算法的運行一切正常，現(xiàn)在我們再來看看一些更加復雜的情況。

假設(shè)不光1號節(jié)點是提議者，2號節(jié)點因收到了李四的請求，也成為了一個提議者（注意所有節(jié)點都是接受者），現(xiàn)在系統(tǒng)里就有了兩個不同的提議者，它們發(fā)送的消息可能以任何的方式交織在一起。

假設(shè)3號節(jié)點可能先收到了來自1號節(jié)點的PREPARE消息（張三購票），即PREPARE(1.1)，并且返回了PROMISE。就在這時，它又收到了2號節(jié)點的PREPARE消息（李四購票），即PREPARE(1.2)，因為提議號1.2大于1.1，于是它又會給2號節(jié)點返回PROMISE，并且將自己的max_id更新為1.2。注意，1號節(jié)點會進行第二步繼續(xù)發(fā)送PROPOSE消息，PROPOSE(1.1, “張三”) ，但此時3號節(jié)點已經(jīng)不會再接受它的提議了，因為現(xiàn)在對它而言，1.2是更新的提議。只有當2號節(jié)點的PROPOSE消息發(fā)過來時它才會接受。

再考慮另一種情況，假設(shè)李四的操作比張三慢了那么一點點，當2號節(jié)點成為提議者，并且發(fā)送PREPARE(1.2)的時候，3號節(jié)點已經(jīng)接受1號節(jié)點的提議了（提議號為1.1），即ACCEPTED消息已經(jīng)發(fā)送。而這時2號節(jié)點因為各種原因還沒有收到1號節(jié)點的PREPARE消息，渾然不知1號和3號已達成共識（票賣給張三）。那么根據(jù)Paxos算法，當3號節(jié)點收到來自2號的PREPARE(1.2) 消息時，由于1.2是3號見過的最大的提議號，所以它的確會向2號返回一個PROMISE消息，但是因為3號又已經(jīng)接受此前的提議1.1了，所以在它返回的PROMISE消息中，會附上之前所接受提議的序號以及值，即PROMISE(1.1, “張三”)，即告訴2號：我收到你的提議號了，它的確是最新的提議，但是我此前已經(jīng)接受過序號為1.1的提議了，它的內(nèi)容是“張三”。2號收到該消息，了解到票已經(jīng)賣出，此時根據(jù)Paxos算法，2號必須將自己要propose的值更改為“張三”，然后繼續(xù)發(fā)送PROPOSE消息，于是所有的節(jié)點依然是達成了共識。

最終客戶端的李四看到的結(jié)果便是：票已售罄。事實上，提議者可能會收到多個帶此前接受值的PROMISE消息，它將會選取這些所有PROMISE里面提議序號最大的那個對應的值，作為自己要propose的值，如果沒有任何PROMISE消息里帶有此前接受的提議信息，提議者則繼續(xù)用自己原本想propose的值。更新后的接受者和提議者的完整邏輯分別如下圖所示。

PREPARE-PROMISE 過程。

這便是完整的Paxos算法。最后我們再來簡單考慮下斷網(wǎng)或者節(jié)點宕機的情況，看看Paxos如何在故障情況下依然能正確運行。

網(wǎng)絡或節(jié)點失效下的Paxos

不管是提議者還是接受者都有宕機的可能性。當接收者宕機時，實際上對系統(tǒng)運行影響不大，這正是分布式系統(tǒng)的優(yōu)勢：哪怕有一些節(jié)點不對PREPARE消息或者PROPOSE消息做任何反應，只要有多數(shù)的節(jié)點依然在線，系統(tǒng)依然能做出反應，提議者依然能得到多數(shù)人的回復，于是算法運行。而當宕機的節(jié)點死而復生后，他們終究也會通過其他節(jié)點發(fā)來的帶有此前已接受提議信息的PROMISE消息來了解到自己錯過的共識，在自己本地也進行更新。

那如果提議者（譬如1號節(jié)點）宕機呢？分為三種情況：

1. 假如它在發(fā)送PREPARE消息之前宕機，那相當于系統(tǒng)里面什么也沒有發(fā)生。其他節(jié)點接收用戶的需求時會變?yōu)樾碌奶嶙h者；

2. 如果提議者在發(fā)送PREPARE消息之后宕機，還沒來得及發(fā)送PROPOSE，如我們剛所說，它的提議會被之后更新的PREPARE所取代（由新的提議者所發(fā)出）；

3. 如果提議者已經(jīng)完成了第一步PREPARE-PROMISE，進入了第二步，但是在給部分節(jié)點發(fā)送PROPOSE消息后宕機，譬如1號在給3號發(fā)送完P(guān)ROPOSE之后宕機，沒來得及發(fā)給2號；那它的提議將會被3號接受，而2號最終還是會了解到1號和3號達成的共識。因為2號在某時會成為提議者，它終究會收到3號返回的帶有此前已接受提議信息的PROMISE消息，并據(jù)此來更新自己本地的信息，于是與1號、3號保持了一致。

所以最后回到搶票上，當我們從客戶端發(fā)出買票請求以后，它會和背后復雜的分布式系統(tǒng)進行交互，大家如果搶不到票并不一定因為自己手速不夠快，還有可能是網(wǎng)絡延遲、連接的服務器宕機，或者和系統(tǒng)算法本身的運作有關(guān)。

結(jié)語

分布式系統(tǒng)作為現(xiàn)代計算機系統(tǒng)的基石，能夠支持12306購票這樣的高負載、高并發(fā)場景。本文討論了分布式系統(tǒng)中關(guān)于一致性與容錯性的一些基本概念與技術(shù)實現(xiàn)。事實上，分布式系統(tǒng)的應用不只是線上網(wǎng)購，在加密領(lǐng)域，分布式系統(tǒng)為區(qū)塊鏈技術(shù)提供了基礎(chǔ)支持，確保數(shù)據(jù)的安全性和一致性；在科學計算領(lǐng)域，分布式系統(tǒng)也被用來解決更大規(guī)模的問題。這些領(lǐng)域都展示了分布式系統(tǒng)在我們?nèi)粘Ｉ詈图夹g(shù)發(fā)展中發(fā)揮著不可或缺的作用。最后，春節(jié)馬上到了，祝大家：春節(jié)快樂，闔家幸福！

注：本文封面圖片來自版權(quán)圖庫，轉(zhuǎn)載使用可能引發(fā)版權(quán)糾紛。

特 別 提 示

1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閱不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關(guān)注公眾號，回復四位數(shù)組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。

版權(quán)說明：歡迎個人轉(zhuǎn)發(fā)，任何形式的媒體或機構(gòu)未經(jīng)授權(quán)，不得轉(zhuǎn)載和摘編。轉(zhuǎn)載授權(quán)請在「返樸」微信公眾號內(nèi)聯(lián)系后臺。