日常生活中，網絡購物、在線支付、地圖導航等便捷的應用，人們已經習以為常，以至于我們幾乎不會關注其背后的技術。這自然離不開通信網絡的飛躍發展，而那些功能的實現則要歸功于分布式系統的進步。本文通過網絡購票的實例，簡要介紹分布式系統的概念，包括其核心的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消息，這時候它就知道，大家已經做好準備接受它的提議了。如果沒有得到多數人的答復，或者收到了一個fail消息，提議者就只能放棄本輪的提議，它可以將自己本地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 過程。
這便是完整的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購票這樣的高負載、高并發場景。本文討論了分布式系統中關于一致性與容錯性的一些基本概念與技術實現。事實上，分布式系統的應用不只是線上網購，在加密領域，分布式系統為區塊鏈技術提供了基礎支持，確保數據的安全性和一致性；在科學計算領域，分布式系統也被用來解決更大規模的問題。這些領域都展示了分布式系統在我們日常生活和技術發展中發揮著不可或缺的作用。最后，春節馬上到了，祝大家：春節快樂，闔家幸福！
