常生活中，網(wǎng)絡(luò)購(gòu)物、在線支付、地圖導(dǎo)航等便捷的應(yīng)用，人們已經(jīng)習(xí)以為常，以至于我們幾乎不會(huì)關(guān)注其背后的技術(shù)。這自然離不開(kāi)通信網(wǎng)絡(luò)的飛躍發(fā)展，而那些功能的實(shí)現(xiàn)則要?dú)w功于分布式系統(tǒng)的進(jìn)步。本文通過(guò)網(wǎng)絡(luò)購(gòu)票的實(shí)例，簡(jiǎn)要介紹分布式系統(tǒng)的概念，包括其核心的Paxos算法，以及它如何應(yīng)對(duì)網(wǎng)絡(luò)斷開(kāi)的挑戰(zhàn)。
一年一度的春運(yùn)又到了，據(jù)估計(jì)，今年鐵路客運(yùn)量或超5.1億人次，日均1275萬(wàn)人次，人們?cè)诒绕词炙贀屍钡谋澈螅?2306的計(jì)算機(jī)系統(tǒng)是如何快速響應(yīng)海量的請(qǐng)求的呢？單臺(tái)服務(wù)器由于有限的計(jì)算能力無(wú)法快速響應(yīng)成千上萬(wàn)的請(qǐng)求，想象一下線下的購(gòu)票大廳只有一個(gè)售票窗口卻有一萬(wàn)人排隊(duì)的場(chǎng)景，人們恐怕都要帶上睡袋來(lái)排隊(duì)了。
那如何加速售票的過(guò)程來(lái)減少人們的等待時(shí)間呢？首先窗口的工作人員可以加快手速，以極快的速度進(jìn)行操作，但是單個(gè)工作人員的手速再快也有一個(gè)上限；另一個(gè)辦法就是在大廳開(kāi)設(shè)多個(gè)窗口，同時(shí)進(jìn)行售票。網(wǎng)絡(luò)售票系統(tǒng)也是一樣的，單臺(tái)服務(wù)器處理不過(guò)來(lái)，就使用多臺(tái)服務(wù)器來(lái)進(jìn)行協(xié)同處理，這就需要“分布式系統(tǒng)”登場(chǎng)了！
什么是分布式系統(tǒng)？
通俗地說(shuō)，分布式系統(tǒng)是指，一群計(jì)算機(jī)共同完成一個(gè)任務(wù)。這些計(jì)算機(jī)也可稱為節(jié)點(diǎn)，它們通過(guò)網(wǎng)絡(luò)連接在一起，分工合作，但對(duì)用戶表現(xiàn)得像一個(gè)整體。不僅僅是12306售票系統(tǒng)，你刷視頻時(shí)看到的推薦、搜索引擎給出的搜索結(jié)果、外賣平臺(tái)的訂單分配，背后都是分布式系統(tǒng)在默默運(yùn)行。相比單個(gè)服務(wù)器，使用分布式系統(tǒng)既能提高系統(tǒng)的性能、響應(yīng)請(qǐng)求的速度，又能提供更好的可靠性，部分節(jié)點(diǎn)宕機(jī)或者斷網(wǎng)了，整個(gè)系統(tǒng)依然能繼續(xù)提供服務(wù)。
分布式系統(tǒng)雖有這些好處，但是它帶來(lái)的復(fù)雜性也給計(jì)算機(jī)系統(tǒng)設(shè)計(jì)提出了挑戰(zhàn)。這里就涉及并發(fā)（concurrency）以及數(shù)據(jù)一致（consistency）的問(wèn)題。
以售票為例，試想以下場(chǎng)景，人在北京的張三和人在廣州的李四在搶同一張票，張三的搶票請(qǐng)求被分發(fā)到了華北地區(qū)的某臺(tái)服務(wù)器，而李四的請(qǐng)求被分給了華南地區(qū)的某服務(wù)器，這倆服務(wù)器現(xiàn)在可以同時(shí)并行地處理兩個(gè)人的搶票請(qǐng)求，系統(tǒng)整體的響應(yīng)速度很快，但是系統(tǒng)如何恰當(dāng)?shù)貐f(xié)作使得票不會(huì)被賣重呢？
此外，分布式系統(tǒng)的另一大特點(diǎn)是存在部分失效（partial failure）的可能性，顧名思義，就是系統(tǒng)部分出現(xiàn)故障，但系統(tǒng)其他部分仍可運(yùn)行。分布式系統(tǒng)由眾多計(jì)算機(jī)構(gòu)成，而且通過(guò)網(wǎng)絡(luò)連接。顯然，不管是計(jì)算機(jī)還是網(wǎng)絡(luò)本身都有可能出現(xiàn)故障，譬如某處停電了、網(wǎng)線斷了，又或是某臺(tái)計(jì)算機(jī)操作系統(tǒng)故障，等等。即使一臺(tái)機(jī)器發(fā)生故障的概率很低，然而當(dāng)計(jì)算機(jī)的數(shù)量多了，對(duì)于整個(gè)系統(tǒng)來(lái)說(shuō)，故障會(huì)非常頻繁。
我們可以做一個(gè)簡(jiǎn)單的計(jì)算，假設(shè)系統(tǒng)中有1000臺(tái)計(jì)算機(jī)，每臺(tái)平均一年只出一次故障（故障可能由任何原因?qū)е拢疵刻斐霈F(xiàn)故障的概率是1/365；反之，每天不出現(xiàn)故障概率是1-1/365，約等于0.99726。這看起來(lái)是一個(gè)很大的概率，但是對(duì)整個(gè)系統(tǒng)而言，每天所有機(jī)器都不出故障的概率則是0.99726的1000次方，約為0.064。這里還未考慮網(wǎng)絡(luò)問(wèn)題，所以對(duì)于系統(tǒng)來(lái)說(shuō)，不出故障幾乎是不可能的。
因此，在分布式系統(tǒng)的設(shè)計(jì)中，如何在部分節(jié)點(diǎn)故障或者網(wǎng)絡(luò)斷開(kāi)的情況下，依然提供正常的服務(wù)是必須考慮的問(wèn)題。
分布式系統(tǒng)的基石——共識(shí)算法（consensus algorithm）
共識(shí)算法在分布式系統(tǒng)中扮演著核心角色，它使得系統(tǒng)在沒(méi)有共享的內(nèi)存，只能通過(guò)發(fā)送消息通信，并且部分節(jié)點(diǎn)可能失效的情況下，整個(gè)系統(tǒng)依然能夠就某個(gè)問(wèn)題達(dá)成共識(shí)。譬如某一個(gè)特定的座位到底是賣了還是沒(méi)賣，是賣給了張三還是李四等等，需要系統(tǒng)達(dá)成共識(shí)才能繼續(xù)執(zhí)行。
分布式系統(tǒng)先驅(qū)、著名圖靈獎(jiǎng)得主Leslie Lamport于1990年提出了現(xiàn)代共識(shí)算法的基礎(chǔ)——Paxos算法。
Lamport用Paxos這個(gè)名字的緣由很有意思。Paxos本是希臘伊奧尼亞海有著悠久歷史的小島，Lamport想象，考古學(xué)家發(fā)現(xiàn)在遠(yuǎn)古時(shí)代小島上有一個(gè)“業(yè)余議會(huì)”（part-time parliament），議員們通過(guò)信使傳遞消息對(duì)議案進(jìn)行表決，但是信使不可靠，消息可能傳遞不到或者被延遲，而且議員本身也有不來(lái)開(kāi)會(huì)的可能性，在這種情況下，議員們?nèi)绾螌?duì)某議案達(dá)成一致？在論文中，Lamport使用這個(gè)虛構(gòu)在Paxos小島的議會(huì)為框架，提出了一個(gè)在不可靠通信的情況下實(shí)現(xiàn)共識(shí)的算法，并給出了嚴(yán)格的數(shù)學(xué)證明。
1990年Lamport將論文提交給ACM Transactions on Computer Systems，審稿人表示論文還算是有趣，但看起來(lái)并不很重要，而且關(guān)于Paxos故事的部分建議去掉。Lamport表示，審稿人怎么這么一點(diǎn)幽默感都沒(méi)有，并拒絕對(duì)論文做任何修改。后來(lái)，分布式系統(tǒng)的另一位先驅(qū)Butler Lampson讀懂了論文，并和Nancy Lynch等領(lǐng)域大佬一起發(fā)表了他們自己的證明，此時(shí)Lamport再次考慮將論文發(fā)表，最終在一眾同行的推動(dòng)下，論文于1998年發(fā)表，現(xiàn)在已經(jīng)成為分布式系統(tǒng)的基石。
下面我們以賣票系統(tǒng)為例，簡(jiǎn)述一下Paxos算法的思想，以及它如何在節(jié)點(diǎn)失效的情況依然達(dá)成共識(shí)。為了簡(jiǎn)化，假設(shè)系統(tǒng)中只有3臺(tái)服務(wù)器（節(jié)點(diǎn)；3個(gè)節(jié)點(diǎn)是演示Paxos算法所需的最小數(shù)量），并且只賣一張票（賣多張票也可以理解成反復(fù)賣一張票的過(guò)程）。此外，我們還需要先簡(jiǎn)述一下算法的假定。
首先，Paxos算法假定一個(gè)節(jié)點(diǎn)如果故障則完全停止響應(yīng)，而不會(huì)繼續(xù)在網(wǎng)絡(luò)發(fā)送錯(cuò)誤的消息以干擾系統(tǒng)，它被修復(fù)之后會(huì)回到系統(tǒng)中繼續(xù)響應(yīng)，這種類型的失效被稱為fail-stop（失敗終止），即fail后就stop了。其次，Paxos是一個(gè)基于多數(shù)派投票的算法，即需要多數(shù)節(jié)點(diǎn)投票通過(guò)才被認(rèn)為是共識(shí)；Paxos需要2m+1個(gè)節(jié)點(diǎn)才能容納m個(gè)節(jié)點(diǎn)失效。也就是說(shuō)，要能夠容納1個(gè)節(jié)點(diǎn)失效，至少系統(tǒng)需要有3個(gè)節(jié)點(diǎn)（另外兩個(gè)正常運(yùn)行）。如果超出半數(shù)的節(jié)點(diǎn)都失效，那Paxos算法將無(wú)法正常運(yùn)轉(zhuǎn)。
現(xiàn)在我們給這三臺(tái)服務(wù)器分配一個(gè)全局的序號(hào)以示區(qū)分：1號(hào)節(jié)點(diǎn)、2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)。Paxos算法會(huì)為每個(gè)節(jié)點(diǎn)分配一個(gè)角色，這里假設(shè)1號(hào)節(jié)點(diǎn)是提議者（proposer）也是接受者（acceptor）；2號(hào)和3號(hào)節(jié)點(diǎn)是接受者，只接受，不提議?，F(xiàn)在1號(hào)節(jié)點(diǎn)收到了來(lái)自張三的購(gòu)票請(qǐng)求，它開(kāi)始了算法的第一步：PREPARE-PROMISE。
提議者1號(hào)節(jié)點(diǎn)首先會(huì)為它的提議proposal（即賣票給張三）分配一個(gè)唯一的序號(hào)（proposal number）。系統(tǒng)中所有的提議都會(huì)有一個(gè)自己獨(dú)特的序號(hào)，一種簡(jiǎn)單的實(shí)現(xiàn)方式是這樣：
每個(gè)節(jié)點(diǎn)自己維護(hù)一個(gè)計(jì)數(shù)器（counter），初始值為0，每次自己提出新的提議時(shí)，計(jì)數(shù)器加1；新提議的序號(hào)設(shè)定為由計(jì)數(shù)器的數(shù)值和該節(jié)點(diǎn)的全局ID所拼接構(gòu)成的小數(shù)，兩者中間用小數(shù)點(diǎn)做間隔，即{counter}.{ID}。比如1號(hào)節(jié)點(diǎn)的第一個(gè)提議的序號(hào)為1.1，第二個(gè)提議的序號(hào)則是2.1。類似的，2號(hào)節(jié)點(diǎn)的第一個(gè)提議序號(hào)為1.2，它的第二個(gè)提議的序號(hào)則是2.2，以此類推。按照這種序號(hào)的設(shè)計(jì)方式，當(dāng)提議者1號(hào)節(jié)點(diǎn)收到張三的請(qǐng)求以后，它首先會(huì)發(fā)送一條PREAPRE消息給其他所有節(jié)點(diǎn)，并且附上提議的序號(hào)1.1，這里寫(xiě)作PREPARE(1.1)。
收到提議的接受者們按照以下邏輯進(jìn)行響應(yīng)：
1.查看收到的PREPARE消息所附帶的提議序號(hào)。
2.將收到的提議號(hào)與自己本地的max_id進(jìn)行對(duì)比。如果更大，則將本地的max_id更新為這個(gè)收到的提議號(hào)，并返回一條PROMISE消息，相當(dāng)于告訴提議者：我收到你的消息了，目前你的提議號(hào)是最大的哦，準(zhǔn)備提議吧，我承諾將不再接受比你的序號(hào)小的提議。
3.如果收到的提議序號(hào)小于它本地的max_id，該接受者就不做回復(fù)，或者回復(fù)一條fail消息，即告訴提議者：你的提議失敗。
如果提議者（1號(hào)節(jié)點(diǎn)）收到了來(lái)自大多數(shù)接受者（自己也算一個(gè)）返回的PROMISE消息，這時(shí)候它就知道，大家已經(jīng)做好準(zhǔn)備接受它的提議了。如果沒(méi)有得到多數(shù)人的答復(fù)，或者收到了一個(gè)fail消息，提議者就只能放棄本輪的提議，它可以將自己本地counter加1，然后再次提出新一輪的提議（由于counter加了1，提議號(hào)也會(huì)加1），重新嘗試。當(dāng)1號(hào)節(jié)點(diǎn)收到了來(lái)自多數(shù)節(jié)點(diǎn)的PROMISE消息后，它就進(jìn)入第二步：PROPOSE-ACCEPT。
在第二步中，1號(hào)節(jié)點(diǎn)會(huì)發(fā)送一條PROPOSE消息，并且附帶上剛才的提議號(hào)，以及具體的值（value），這里的值value就是大家希望達(dá)成共識(shí)的東西，在本文買票的例子中，它的內(nèi)容就是“張三”，代表票賣給張三。所以1號(hào)節(jié)點(diǎn)發(fā)送的消息是這樣：
PROPOSE(1.1，“張三”)
收到消息的接受者們現(xiàn)在要做一個(gè)判斷，是否接受這個(gè)提議，它們的邏輯是這樣的：
1.如果PROPOSE消息里附帶的提議號(hào)依然是我目前收到的最大的（即和自己的max_id進(jìn)行對(duì)比），那就接受這個(gè)提議，并且返回一條ACCEPTED消息；
2.否則就不返回消息，或者返回fail消息，告訴提議者：提議失敗。
如果提議者收到來(lái)自大多數(shù)節(jié)點(diǎn)的ACCEPTED消息，那它就知道共識(shí)已經(jīng)達(dá)成了。假設(shè)現(xiàn)在2號(hào)和3號(hào)都正常收到了PROPOSE消息，并正常返回了ACCEPTED消息，則所有節(jié)點(diǎn)就“票賣給張三”這一狀態(tài)達(dá)成了一致。
總結(jié)一下，這里達(dá)成共識(shí)一共用了兩步。第一步的目標(biāo)在于獲得多數(shù)人的同意，相當(dāng)于提議者對(duì)每個(gè)人喊話：我要進(jìn)行修改數(shù)據(jù)了啊，你們同意不同意？只有當(dāng)獲得了多數(shù)人的同意之后，才會(huì)進(jìn)行第二步——提議者真正發(fā)出要propose的值。
試想，如果算法跳過(guò)第一步，直接發(fā)送要propose的值，不同的接受者就可能會(huì)收到來(lái)自不同提議者的值。而這個(gè)時(shí)候又因?yàn)闆](méi)有事先征求多數(shù)的同意，最后接收者也不知道自己收到的值是否就代表了大多數(shù)的意見(jiàn)，系統(tǒng)中可能會(huì)有多個(gè)子群體大家各自有自己的值，這樣全局的共識(shí)就沒(méi)有了。
完整的Paxos算法邏輯
到此為止，算法的運(yùn)行一切正常，現(xiàn)在我們?cè)賮?lái)看看一些更加復(fù)雜的情況。
假設(shè)不光1號(hào)節(jié)點(diǎn)是提議者，2號(hào)節(jié)點(diǎn)因收到了李四的請(qǐng)求，也成為了一個(gè)提議者（注意所有節(jié)點(diǎn)都是接受者），現(xiàn)在系統(tǒng)里就有了兩個(gè)不同的提議者，它們發(fā)送的消息可能以任何的方式交織在一起。
假設(shè)3號(hào)節(jié)點(diǎn)可能先收到了來(lái)自1號(hào)節(jié)點(diǎn)的PREPARE消息（張三購(gòu)票），即PREPARE(1.1)，并且返回了PROMISE。就在這時(shí)，它又收到了2號(hào)節(jié)點(diǎn)的PREPARE消息（李四購(gòu)票），即PREPARE(1.2)，因?yàn)樘嶙h號(hào)1.2大于1.1，于是它又會(huì)給2號(hào)節(jié)點(diǎn)返回PROMISE，并且將自己的max_id更新為1.2。注意，1號(hào)節(jié)點(diǎn)會(huì)進(jìn)行第二步繼續(xù)發(fā)送PROPOSE消息，PROPOSE(1.1，“張三”)，但此時(shí)3號(hào)節(jié)點(diǎn)已經(jīng)不會(huì)再接受它的提議了，因?yàn)楝F(xiàn)在對(duì)它而言，1.2是更新的提議。只有當(dāng)2號(hào)節(jié)點(diǎn)的PROPOSE消息發(fā)過(guò)來(lái)時(shí)它才會(huì)接受。
再考慮另一種情況，假設(shè)李四的操作比張三慢了那么一點(diǎn)點(diǎn)，當(dāng)2號(hào)節(jié)點(diǎn)成為提議者，并且發(fā)送PREPARE(1.2)的時(shí)候，3號(hào)節(jié)點(diǎn)已經(jīng)接受1號(hào)節(jié)點(diǎn)的提議了（提議號(hào)為1.1），即ACCEPTED消息已經(jīng)發(fā)送。而這時(shí)2號(hào)節(jié)點(diǎn)因?yàn)楦鞣N原因還沒(méi)有收到1號(hào)節(jié)點(diǎn)的PREPARE消息，渾然不知1號(hào)和3號(hào)已達(dá)成共識(shí)（票賣給張三）。那么根據(jù)Paxos算法，當(dāng)3號(hào)節(jié)點(diǎn)收到來(lái)自2號(hào)的PREPARE(1.2)消息時(shí)，由于1.2是3號(hào)見(jiàn)過(guò)的最大的提議號(hào)，所以它的確會(huì)向2號(hào)返回一個(gè)PROMISE消息，但是因?yàn)?號(hào)又已經(jīng)接受此前的提議1.1了，所以在它返回的PROMISE消息中，會(huì)附上之前所接受提議的序號(hào)以及值，即PROMISE(1.1，“張三”)，即告訴2號(hào)：我收到你的提議號(hào)了，它的確是最新的提議，但是我此前已經(jīng)接受過(guò)序號(hào)為1.1的提議了，它的內(nèi)容是“張三”。2號(hào)收到該消息，了解到票已經(jīng)賣出，此時(shí)根據(jù)Paxos算法，2號(hào)必須將自己要propose的值更改為“張三”，然后繼續(xù)發(fā)送PROPOSE消息，于是所有的節(jié)點(diǎn)依然是達(dá)成了共識(shí)。
最終客戶端的李四看到的結(jié)果便是：票已售罄。事實(shí)上，提議者可能會(huì)收到多個(gè)帶此前接受值的PROMISE消息，它將會(huì)選取這些所有PROMISE里面提議序號(hào)最大的那個(gè)對(duì)應(yīng)的值，作為自己要propose的值，如果沒(méi)有任何PROMISE消息里帶有此前接受的提議信息，提議者則繼續(xù)用自己原本想propose的值。更新后的接受者和提議者的完整邏輯分別如下圖所示。
PREPARE-PROMISE過(guò)程。圖片來(lái)源：https://people.cs.rutgers.edu/~pxk/417/notes/paxos.html
這便是完整的Paxos算法。最后我們?cè)賮?lái)簡(jiǎn)單考慮下斷網(wǎng)或者節(jié)點(diǎn)宕機(jī)的情況，看看Paxos如何在故障情況下依然能正確運(yùn)行。
網(wǎng)絡(luò)或節(jié)點(diǎn)失效下的Paxos
不管是提議者還是接受者都有宕機(jī)的可能性。當(dāng)接收者宕機(jī)時(shí)，實(shí)際上對(duì)系統(tǒng)運(yùn)行影響不大，這正是分布式系統(tǒng)的優(yōu)勢(shì)：哪怕有一些節(jié)點(diǎn)不對(duì)PREPARE消息或者PROPOSE消息做任何反應(yīng)，只要有多數(shù)的節(jié)點(diǎn)依然在線，系統(tǒng)依然能做出反應(yīng)，提議者依然能得到多數(shù)人的回復(fù)，于是算法運(yùn)行。而當(dāng)宕機(jī)的節(jié)點(diǎn)死而復(fù)生后，他們終究也會(huì)通過(guò)其他節(jié)點(diǎn)發(fā)來(lái)的帶有此前已接受提議信息的PROMISE消息來(lái)了解到自己錯(cuò)過(guò)的共識(shí)，在自己本地也進(jìn)行更新。
那如果提議者（譬如1號(hào)節(jié)點(diǎn)）宕機(jī)呢？分為三種情況：
1.假如它在發(fā)送PREPARE消息之前宕機(jī)，那相當(dāng)于系統(tǒng)里面什么也沒(méi)有發(fā)生。其他節(jié)點(diǎn)接收用戶的需求時(shí)會(huì)變?yōu)樾碌奶嶙h者；
2.如果提議者在發(fā)送PREPARE消息之后宕機(jī)，還沒(méi)來(lái)得及發(fā)送PROPOSE，如我們剛所說(shuō)，它的提議會(huì)被之后更新的PREPARE所取代（由新的提議者所發(fā)出）；
3.如果提議者已經(jīng)完成了第一步PREPARE-PROMISE，進(jìn)入了第二步，但是在給部分節(jié)點(diǎn)發(fā)送PROPOSE消息后宕機(jī)，譬如1號(hào)在給3號(hào)發(fā)送完P(guān)ROPOSE之后宕機(jī)，沒(méi)來(lái)得及發(fā)給2號(hào)；那它的提議將會(huì)被3號(hào)接受，而2號(hào)最終還是會(huì)了解到1號(hào)和3號(hào)達(dá)成的共識(shí)。因?yàn)?號(hào)在某時(shí)會(huì)成為提議者，它終究會(huì)收到3號(hào)返回的帶有此前已接受提議信息的PROMISE消息，并據(jù)此來(lái)更新自己本地的信息，于是與1號(hào)、3號(hào)保持了一致。
所以最后回到搶票上，當(dāng)我們從客戶端發(fā)出買票請(qǐng)求以后，它會(huì)和背后復(fù)雜的分布式系統(tǒng)進(jìn)行交互，大家如果搶不到票并不一定因?yàn)樽约菏炙俨粔蚩欤€有可能是網(wǎng)絡(luò)延遲、連接的服務(wù)器宕機(jī)，或者和系統(tǒng)算法本身的運(yùn)作有關(guān)。
結(jié)語(yǔ)
分布式系統(tǒng)作為現(xiàn)代計(jì)算機(jī)系統(tǒng)的基石，能夠支持12306購(gòu)票這樣的高負(fù)載、高并發(fā)場(chǎng)景。本文討論了分布式系統(tǒng)中關(guān)于一致性與容錯(cuò)性的一些基本概念與技術(shù)實(shí)現(xiàn)。
事實(shí)上，分布式系統(tǒng)的應(yīng)用不只是線上網(wǎng)購(gòu)，在加密領(lǐng)域，分布式系統(tǒng)為區(qū)塊鏈技術(shù)提供了基礎(chǔ)支持，確保數(shù)據(jù)的安全性和一致性；在科學(xué)計(jì)算領(lǐng)域，分布式系統(tǒng)也被用來(lái)解決更大規(guī)模的問(wèn)題。這些領(lǐng)域都展示了分布式系統(tǒng)在我們?nèi)粘Ｉ詈图夹g(shù)發(fā)展中發(fā)揮著不可或缺的作用。
本文來(lái)源：虎嗅網(wǎng)
文章轉(zhuǎn)載于其他網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系我們及時(shí)刪除！
