分布式系统Paxos算法
Paxos是能夠基于一大堆完全不可靠的網(wǎng)絡(luò)條件下卻能可靠確定地實(shí)現(xiàn)共識(shí)一致性的算法。也就是說(shuō):它允許一組不一定可靠的處理器(服務(wù)器)在某些條件得到滿足情況下就能達(dá)成確定的安全的共識(shí),如果條件不能滿足也確保這組處理器(服務(wù)器)保持一致。
什么是共識(shí)?
具體來(lái)說(shuō)是這樣:分布式系統(tǒng)中由于網(wǎng)絡(luò)之間通訊可能會(huì)中斷,雖然概率很低,但是沒(méi)有100%完美的網(wǎng)絡(luò)因此,依靠網(wǎng)絡(luò)通訊的計(jì)算機(jī)之間要達(dá)成共識(shí)就比較困難,假設(shè)有X, Y和Z三臺(tái)計(jì)算機(jī)謀劃在周一攻擊人類世界,它們的攻擊計(jì)劃是只要所有計(jì)算機(jī)可用于戰(zhàn)斗時(shí)就一起進(jìn)行攻擊,不落下任何一臺(tái)機(jī)器,但是當(dāng)他們決定具體什么時(shí)間開始攻擊時(shí),在這個(gè)關(guān)鍵問(wèn)題上往往會(huì)出錯(cuò)。
一個(gè)基本問(wèn)題是,每臺(tái)機(jī)器都有自己的攻擊時(shí)間建議,計(jì)算機(jī)X可以建議在08:00時(shí)間,因?yàn)檫@個(gè)時(shí)間正是周一早晨,而人們剛剛過(guò)完狂歡的周末休息天,但是計(jì)算機(jī)Z認(rèn)為13:00比較好,理由當(dāng)然也有一大堆,讓這三臺(tái)計(jì)算機(jī)基于某個(gè)時(shí)刻達(dá)成共識(shí)是非常困難的,因此,也給人類反擊留下了機(jī)會(huì)。
另外一個(gè)情況是,這三臺(tái)計(jì)算機(jī)是位于世界不同的位置,之間通訊或許通過(guò)電纜或者其他不太可靠的網(wǎng)絡(luò)設(shè)備通訊,如果X建議在08:00,它必須確認(rèn)它的這個(gè)建議能夠到達(dá)活著的Y和Z,以免一個(gè)人戰(zhàn)斗。
問(wèn)題是:我們不能準(zhǔn)確地知道某個(gè)計(jì)算機(jī)的延遲的原因:是因?yàn)樾阅苈诉€是已經(jīng)是徹底死機(jī)不能用?
那么,X怎么知道其他兩個(gè)計(jì)算機(jī)是可用的呢?也就是說(shuō),當(dāng)X和其他兩個(gè)計(jì)算機(jī)通訊發(fā)現(xiàn)得到響應(yīng)要過(guò)很長(zhǎng)時(shí)間,它不能確定這兩臺(tái)計(jì)算機(jī)到底還能不能繼續(xù)活下去,也許這次通訊有延遲了,下一次它們又活過(guò)來(lái)了沒(méi)有延遲了,也許下次延遲更長(zhǎng)了一點(diǎn),也許下次延遲稍微短了一點(diǎn),這些隨機(jī)概率問(wèn)題使得X不能確定Y和Z到底是出了什么問(wèn)題造成延遲的,是因?yàn)樘幚砹四硞€(gè)特別耗費(fèi)CPU的任務(wù)還是因?yàn)樗梨i等原因?當(dāng)然,有些天真的設(shè)計(jì)者會(huì)說(shuō),只要我們將性能監(jiān)控到位,如果延遲超過(guò)一定時(shí)間,我們?nèi)斯そ槿敫嬖VX確切情況就可以,那么這種人工介入的分布式系統(tǒng)不是一個(gè)天然自洽的自動(dòng)化系統(tǒng)了,不在我們討論范圍之內(nèi),而且這樣的系統(tǒng)會(huì)讓人疲于奔命。
因?yàn)閄不能確定Y或Z是否可用,所以X僅僅只能和Y與Z中一臺(tái)基于攻擊時(shí)間達(dá)成共識(shí),就無(wú)法完全三臺(tái)機(jī)器全部投入戰(zhàn)斗的計(jì)劃。注意的是,X Y Z三臺(tái)中任何一臺(tái)都可能會(huì)出現(xiàn)延遲,這就造成了三臺(tái)機(jī)器之間任何通訊都是無(wú)法確認(rèn)可靠的,比如X發(fā)出消息給Z,Z確認(rèn)后回執(zhí)給X,但是這段時(shí)間X突然死機(jī)了,那么Z要等待X多長(zhǎng)時(shí)間才能知道它收到確認(rèn)呢?還是再次等待X回復(fù)確認(rèn)的確認(rèn),這樣無(wú)限循環(huán)下去也不能解決它們之間通訊可能出現(xiàn)隨機(jī)不可靠的問(wèn)題。
所有關(guān)鍵問(wèn)題在于:由于這三臺(tái)機(jī)器之間通訊是無(wú)法保證100%可靠,它們就不能就任何事情達(dá)成共識(shí)。
下面以分布式拍賣案例說(shuō)明這種情況以及Paxos的基本原理?
在傳統(tǒng)拍賣場(chǎng)景中,價(jià)高者先得,這些拍賣者都是在同一個(gè)房間,彼此能夠直接看得到對(duì)方的報(bào)價(jià),如果我們假設(shè)分布式拍賣是將這些拍賣者分離到不同的地方,這樣我們可以用拍賣者之間的聯(lián)系模擬分布式計(jì)算機(jī)之間的通訊。
假設(shè)拍賣者各自在自己家里拍賣,通過(guò)郵局信件發(fā)出自己的拍賣信息,拍賣者之間除非等到郵局投遞人告訴他們彼此之間的報(bào)價(jià),否則是無(wú)法知道對(duì)方報(bào)價(jià)的。如果郵局信件投遞這個(gè)環(huán)節(jié)出了問(wèn)題,投遞速度慢了甚至無(wú)法投遞了,那么整個(gè)拍賣程序就無(wú)法繼續(xù)進(jìn)行下去。
?
Paxos解決共識(shí)思路
Paxos是一個(gè)解決共識(shí)問(wèn)題consensus problem的算法,現(xiàn)實(shí)中Paxos的實(shí)現(xiàn)以及成為一些世界級(jí)軟件的心臟,如Cassandra, Google的 Spanner數(shù)據(jù)庫(kù), 分布式鎖服務(wù)Chubby. 一個(gè)被Paxos管理的系統(tǒng)實(shí)際上談?wù)摰氖侵?狀態(tài)和跟蹤等問(wèn)題,其目標(biāo)是建造更高可用性和強(qiáng)一致性的分布式系統(tǒng)。
Paxos完成一次寫操作需要兩次來(lái)回,分別是prepare/promise, 和 propose/accept:
第一次由提交者Leader向所有其他服務(wù)器發(fā)出prepare消息請(qǐng)求準(zhǔn)備,所有服務(wù)器中大多數(shù)如果回復(fù)諾言承諾就表示準(zhǔn)備好了,可以接受寫入;第二次提交者向所有服務(wù)器發(fā)出正式建議propose,所有服務(wù)器中大多數(shù)如果回復(fù)已經(jīng)接收就表示成功了。
為了詳細(xì)描述這個(gè)兩段過(guò)程,首先讓我們定義一下我們將使用的一些名詞術(shù)語(yǔ):
- 一個(gè)進(jìn)程是系統(tǒng)中計(jì)算機(jī)的一個(gè). 人們使用有關(guān)復(fù)制或節(jié)點(diǎn)等詞語(yǔ)表達(dá),都差不多。
- 一個(gè)客戶端是屬于系統(tǒng)中一個(gè)成員的計(jì)算機(jī),但是詢問(wèn)系統(tǒng)值是什么或者要求系統(tǒng)獲取一個(gè)新的值。
Paxos構(gòu)建分布式數(shù)據(jù)庫(kù)的小片段: 它僅僅實(shí)現(xiàn)進(jìn)程將一個(gè)新的東西精確地寫入系統(tǒng)中,進(jìn)程是由Paxos的一個(gè)實(shí)例管治,可以失敗或者不知道任何東西、或者大多數(shù)進(jìn)程都知道一個(gè)同樣的值,這就是共識(shí),Paxos并不真的告訴我們?nèi)绾斡盟鼇?lái)構(gòu)建數(shù)據(jù)庫(kù)或類似的東西,它只是負(fù)責(zé)獨(dú)立節(jié)點(diǎn)之間通訊的進(jìn)程, 這些進(jìn)程服務(wù)器會(huì)基于一個(gè)新值執(zhí)行決定,Paxos會(huì)存儲(chǔ)一個(gè)值數(shù)據(jù),只是一次性的,一旦你第一次設(shè)置以后就不能再改變它。
?
Paxo讀操作
其實(shí)Paxos精華是在寫操作,將讀操作放在寫操作前面講解,是著重Paxos以大多數(shù)服務(wù)器達(dá)成共識(shí)為重要標(biāo)志,通過(guò)讀取判斷是否達(dá)成共識(shí)這一狀態(tài)。
為了從Paxos系統(tǒng)中讀取一個(gè)值數(shù)據(jù),客戶端會(huì)請(qǐng)求讀取所有進(jìn)程中存儲(chǔ)的當(dāng)前值,然后從大多數(shù)進(jìn)程服務(wù)器中獲得這個(gè)值,如果數(shù)量湊不夠大多數(shù)或者沒(méi)有足夠的客戶端響應(yīng),讀取操作失敗,下面圖示你會(huì)看到一個(gè)客戶端詢問(wèn)其他節(jié)點(diǎn)他們的值是多少,這些節(jié)點(diǎn)返回值給客戶端,當(dāng)客戶端獲得了大多數(shù)節(jié)點(diǎn)的響應(yīng),返回的值都是同樣的,它就算成功地讀操作了,并順便保存讀結(jié)果。
與單節(jié)點(diǎn)系統(tǒng)(只有一臺(tái)服務(wù)器)相比這有些奇怪,這兩個(gè)系統(tǒng)中,客戶端都需要觀察系統(tǒng)已決定狀態(tài),但是在非分布式系統(tǒng)中像MySQL或一個(gè)memcached服務(wù)器中, 客戶端只需直接向標(biāo)準(zhǔn)的狀態(tài)存儲(chǔ)的服務(wù)器地址獲取狀態(tài)即可,在簡(jiǎn)單的Paxos中, 客戶端也是同樣的方式觀察狀態(tài),但是因?yàn)椴](méi)有標(biāo)準(zhǔn)的狀態(tài)存儲(chǔ)的服務(wù)器地址,它需要詢問(wèn)所有的成員,以便能夠確定僅有一個(gè)會(huì)報(bào)告值數(shù)據(jù),實(shí)際上是大多數(shù)節(jié)點(diǎn)都持有的值數(shù)據(jù),如果客戶端詢問(wèn)一個(gè)節(jié)點(diǎn),有可能這個(gè)節(jié)點(diǎn)進(jìn)程已經(jīng)過(guò)期,得到了錯(cuò)誤的值數(shù)據(jù),進(jìn)程失效過(guò)期的原因有很多:由于不可靠的網(wǎng)絡(luò)導(dǎo)致本應(yīng)送達(dá)到它們的消息丟失了;或者他們也許當(dāng)機(jī)然后使用了一個(gè)過(guò)期狀態(tài)恢復(fù);或者算法還在運(yùn)行計(jì)算中,進(jìn)程并沒(méi)有正好得到消息等等。在現(xiàn)實(shí)中使用Paxos實(shí)現(xiàn)時(shí),其實(shí)不需要每個(gè)節(jié)點(diǎn)都進(jìn)行一次讀取,會(huì)有更好的讀取方式,但是他們都是拓展的原始 Paxos 算法。
?
Paxos寫操作
當(dāng)一個(gè)客戶端要求寫入系統(tǒng)一個(gè)新值時(shí),讓我們看看Paxos讓我們集群的進(jìn)程都做了什么?下面的過(guò)程都是只有一個(gè)值的寫入,最終我們能用這個(gè)進(jìn)程作為原始數(shù)據(jù),允許值數(shù)據(jù)在彼此之間一個(gè)個(gè)設(shè)置,但是基本的Paxos算法管治了一個(gè)新值數(shù)據(jù)的寫操作流程, 然后做重復(fù)的事情。
首先Paxos管理的系統(tǒng)中一個(gè)客戶端要求寫入一個(gè)新值,客戶端這里如圖所示是紅圈,其它進(jìn)程是藍(lán)圈, Paxos能保證客戶端發(fā)送它們的寫請(qǐng)求到Paxos集群中任何成員, 這里演示中客戶端隨機(jī)挑選進(jìn)程中任意一個(gè),這種方式是重要且巧妙的,意味著沒(méi)有任何單點(diǎn)風(fēng)險(xiǎn),意味著我們的Paxos管治系統(tǒng)能繼續(xù)保持在線可用,無(wú)論任何一個(gè)節(jié)點(diǎn)當(dāng)機(jī)或其他不可用原因無(wú)響應(yīng)。如果我們?cè)O(shè)計(jì)一個(gè)特定節(jié)點(diǎn)作為“推薦人proposer”或者 "the master" 等, 如果這個(gè)主節(jié)點(diǎn)死機(jī),那么整個(gè)系統(tǒng)就崩潰了。
當(dāng)寫請(qǐng)求被接受后,Paxos進(jìn)程會(huì)接受這個(gè)寫新值到系統(tǒng)中請(qǐng)求“建議”, “建議”是Paxos中一個(gè)正式概念: 向一個(gè)Paxos管治的系統(tǒng)建議可能會(huì)成功或失敗,需要步驟來(lái)確保共識(shí)能夠達(dá)成維系,這個(gè)建議以準(zhǔn)備消息從那些與客戶端連接的進(jìn)程節(jié)點(diǎn)們被發(fā)往整個(gè)系統(tǒng)。
序列號(hào)
這個(gè)準(zhǔn)備消息保存在被建議的值數(shù)據(jù)中,它們也稱為序列號(hào)sequence number,序列號(hào)是由建議進(jìn)程產(chǎn)生的,它定義了接受進(jìn)程應(yīng)該準(zhǔn)備接受帶有序列號(hào)的建議,這個(gè)序列號(hào)是關(guān)鍵: 它用于表明新舊建議之間的區(qū)別,如果兩個(gè)進(jìn)程試圖獲得需要設(shè)置一個(gè)值,Paxos認(rèn)為最后一個(gè)進(jìn)程應(yīng)該有優(yōu)先權(quán),這樣讓進(jìn)程分辨哪個(gè)是最后一個(gè),這樣它就能設(shè)置最新的值。
這些接受的進(jìn)程能夠進(jìn)行在系統(tǒng)中關(guān)鍵的檢查:這個(gè)在到來(lái)的準(zhǔn)備消息中序列號(hào)是我見過(guò)的最高級(jí)別嗎?如果是,那就很cool, 我能準(zhǔn)備好接受將要到來(lái)的值數(shù)據(jù),那就不要管之前聽到的任何其他值數(shù)據(jù)了,你能看到這個(gè)過(guò)程在右邊演示中:客戶端每隔一段向一個(gè)進(jìn)程建議一個(gè)新值,這個(gè)進(jìn)程發(fā)送準(zhǔn)備消息給其他進(jìn)程,然后那些進(jìn)程注意到這是一個(gè)成功的更高的超過(guò)舊的新序列號(hào),然后就放手那些舊建議。
這里有一個(gè)順序的設(shè)計(jì)(先發(fā)送準(zhǔn)備消息),這是為避免單點(diǎn)風(fēng)險(xiǎn),如果沒(méi)有這個(gè)順序,Paxos中成員就無(wú)法分辨哪個(gè)建議是他們可以有信心地準(zhǔn)備接受的。
我們不能想象有另外不同的共識(shí)算法,不是按照如下步驟:首先發(fā)送第一個(gè)消息詢問(wèn)其他進(jìn)程,以確保將設(shè)置的新值是最新的值,盡管方式可以再簡(jiǎn)單些,但是可能就不能滿足共識(shí)算法安全的需求了,如果兩個(gè)進(jìn)程正好同時(shí)建議不同的值,如下所示:
大自然經(jīng)常會(huì)這樣欺騙我們,每個(gè)包都能另外一半的進(jìn)程相信它們接受的也許是正確也許是錯(cuò)誤的值,系統(tǒng)將進(jìn)入一個(gè)僵局,存在兩個(gè)相同數(shù)量的組卻有不同的值,那么就無(wú)法確定大多數(shù)這個(gè)概念了,這個(gè)僵局能夠被第一個(gè)Paxos消息避免,因?yàn)镻axos的序列號(hào),那些有問(wèn)題的建議將有被其他更低的序列號(hào),這樣序列號(hào)更高的建議就會(huì)毫不含糊地被大多數(shù)進(jìn)程接收,它們也首先獲得了更高的序列號(hào),然后如果接受到更低的序列號(hào)就會(huì)拒絕,Paxos 就是這樣通過(guò)用序列號(hào)控制整個(gè)系統(tǒng)的時(shí)間節(jié)奏。
上圖演示了客戶端首先發(fā)一個(gè)準(zhǔn)備消息給Paxos進(jìn)程,Paxos進(jìn)程會(huì)檢查下一步將到來(lái)的建議的序列號(hào),以分辨是否準(zhǔn)備接受這個(gè)新值,所有進(jìn)程都是這樣消除歧義,共識(shí)由此達(dá)成。注意:保證沒(méi)有兩個(gè)建議使用相同的序列號(hào)是很重要的,這是確保他們的順序,這樣每個(gè)序列號(hào)只有一個(gè)建議,這樣才能比較兩個(gè)建議,實(shí)現(xiàn)Paxos時(shí),全局唯一有序的序列號(hào)實(shí)際是精確系統(tǒng)時(shí)間和集群中節(jié)點(diǎn)數(shù)量的拷貝,隨著時(shí)間不斷增加,從來(lái)不會(huì)重復(fù)。
Paxos第一階段:準(zhǔn)備Perpare/諾言Promises
Paxos的第一階段是prepare/promise,準(zhǔn)備階段就是將建議值發(fā)送到各個(gè)目標(biāo)節(jié)點(diǎn)。
當(dāng)建議被發(fā)到目標(biāo)節(jié)點(diǎn)后,進(jìn)程會(huì)會(huì)檢查建議中的序列號(hào),是否是它們見到過(guò)的最高級(jí),如果是最高級(jí),它們會(huì)發(fā)出一個(gè)promise不再接受比這個(gè)新序列號(hào)更舊的建議了,這個(gè)諾言promise作為消息從許下諾言的進(jìn)程發(fā)到提交建議新值的進(jìn)程服務(wù)器,這個(gè)諾言消息給提交建議的進(jìn)程后,提交建議的進(jìn)程需要自己統(tǒng)計(jì)一下有多少其他進(jìn)程已經(jīng)發(fā)回它們的諾言promise了,如果判斷數(shù)量上是否達(dá)到大多數(shù)?如果大多數(shù)進(jìn)程已經(jīng)同意接受這個(gè)建議或者更高級(jí)序列號(hào)的建議,這個(gè)提交建議的進(jìn)程就能知道它獲得了發(fā)言權(quán)(因?yàn)橛写蠖鄶?shù)支持),這樣就開始講話,算法中的下一步處理將可能進(jìn)行;如果回復(fù)諾言的節(jié)點(diǎn)數(shù)量沒(méi)有達(dá)到大多數(shù),也就是共識(shí)沒(méi)有達(dá)成,這樣這個(gè)節(jié)點(diǎn)提交的建議將退出,客戶端要求的寫操作失敗。
為了決定一個(gè)建議是否已經(jīng)有足夠的回復(fù)諾言promises, 提交建議者只是統(tǒng)計(jì)一下它接受到的?promise?消息數(shù)量,然后和整個(gè)系統(tǒng)中節(jié)點(diǎn)服務(wù)器數(shù)量比較一下,“足夠”意味著大多數(shù)(N/2 + 1)個(gè)進(jìn)程服務(wù)器在某段時(shí)間內(nèi)都回復(fù)了諾言promises。如果超過(guò)一半的進(jìn)程服務(wù)器沒(méi)有返回諾言,這意味著這個(gè)建議沒(méi)有被大多數(shù)通過(guò),那么在前面描述的讀算法中就不能滿足大多數(shù)的要求,也就不能達(dá)成共識(shí),這個(gè)建議就退出。其他包括網(wǎng)絡(luò)分區(qū)錯(cuò)誤也可能會(huì)阻止大多數(shù)達(dá)成共識(shí),
?
第二階段:Paoxs接納Acceptance
當(dāng)完成prepare/promise階段,進(jìn)入了 propose/accept階段。
一旦建議提交者已經(jīng)從大多數(shù)其他進(jìn)程服務(wù)器獲得了諾言,它會(huì)要求許諾的進(jìn)程服務(wù)器接收它們之前承諾接受的新值數(shù)據(jù),這是一個(gè)“確認(rèn)commit”階段,如果沒(méi)有沖突建議 失敗或分區(qū)錯(cuò)誤,那么這個(gè)新建議將被所有其他節(jié)點(diǎn)接受,那么Paxos過(guò)程就完成了。
你能看到右邊的演示,注意這個(gè)演示比上面promise在最后多了一個(gè)動(dòng)作,也就是提交建議者將新值發(fā)給那些許諾言的進(jìn)程服務(wù)器,讓它們接受了這個(gè)新值。
接受的過(guò)程也許可能會(huì)發(fā)生失敗,在回復(fù)了諾言消息以后,在接受到Accept消息之前,如果有足夠多的服務(wù)器正好在這個(gè)時(shí)間段失敗,那么接受行為只能是少數(shù)服務(wù)器,那么Paxos進(jìn)入了厄運(yùn)狀態(tài):一些進(jìn)程服務(wù)器接受了新值,而不是全部的,這種不一致已經(jīng)在前面讀操作中描述:一個(gè)客戶端試圖從系統(tǒng)中大多數(shù)節(jié)點(diǎn)服務(wù)器讀取它們同意接受的值,它發(fā)現(xiàn)一些節(jié)點(diǎn)服務(wù)器報(bào)告有不同的值數(shù)據(jù),這會(huì)引起讀失敗,但是Paxos還保持一致性,不允許在沒(méi)有達(dá)成共識(shí)情況下任何寫操作發(fā)生,這種壞的情況在實(shí)踐中經(jīng)常通過(guò)重復(fù)接受階段來(lái)讓大多數(shù)節(jié)點(diǎn)最終接受。
總結(jié)
Paxos算法是保證在分布式系統(tǒng)中寫操作能夠順利進(jìn)行,保證系統(tǒng)中大多數(shù)狀態(tài)是一致的,沒(méi)有機(jī)會(huì)看到不一致,因此,Paxos算法的特點(diǎn)是一致性>可用性。
vector clock向量時(shí)鐘是另外一種保證復(fù)制的算法,其特點(diǎn)是可用性>一致性,但是,一旦發(fā)生沖突,不像Paxos能自行解決,需要人工干預(yù)編寫代碼解決。
Paxos算法和Vector Clock都是由Leslie Lamport提出。
轉(zhuǎn)載來(lái)自http://www.jdon.com/artichect/paxos.html
總結(jié)
以上是生活随笔為你收集整理的分布式系统Paxos算法的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: JAVA中线程同步的方法(7种)汇总
- 下一篇: 比特币的区块结构解析