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)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。