撰文 | 陳清揚
一年一度的春運又到了，據估計，今年鐵路客運量或超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的值，不同的接受者就可能會收到來自不同提議者的值。而這個時候又因為沒有事先徵求多數的同意，最後接收者也不知道自己收到的值是否就代表了大多數的意見，系統中可能會有多個子群體大家各自有自己的值，這樣全域性的共識就沒有了。
到此為止，演算法的執行一切正常，現在我們再來看看一些更加複雜的情況。
假設不光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如何在故障情況下依然能正確執行。
不管是提議者還是接受者都有宕機的可能性。當接收者宕機時，實際上對系統執行影響不大，這正是分散式系統的優勢：哪怕有一些節點不對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購票這樣的高負載、高併發場景。本文討論了分散式系統中關於一致性與容錯性的一些基本概念與技術實現。事實上，分散式系統的應用不只是線上網購，在加密領域，分散式系統為區塊鏈技術提供了基礎支援，確保資料的安全性和一致性；在科學計算領域，分散式系統也被用來解決更大規模的問題。這些領域都展示了分散式系統在我們日常生活和技術發展中發揮著不可或缺的作用。最後，祝大家：春節快樂，闔家幸福！
>End
>>>
本文轉載自“返樸”，原標題《春運搶票，原來售票系統背後的技術這麼精妙！》。
為分享前沿資訊及有價值的觀點，太空與網路微信公眾號轉載此文，並經過編輯。
>>>
充滿激情的新時代，
充滿挑戰的新疆域，
與踔厲奮發的引領者，
卓爾不群的企業家，
一起開拓，
一起體驗，
一起感悟，
共同打造更真品質，
共同實現更高價值，
共同見證商業航天更大的跨越！
——《太空與網路》，觀察，記錄，傳播，引領。
>>>
·《衛星與網路》編輯委員會
高階顧問：王國玉、劉程、童旭東、相振華、王志義、楊烈
· 《衛星與網路》創始人：劉雨菲
·《衛星與網路》副社長：王俊峰
雜誌訂閱，請加微信：
wangxiaoyu9960
