1 分布式一致性：共識(shí)算法

對(duì)于一個(gè)分布式系統(tǒng)來(lái)說(shuō)，保障集群中所有節(jié)點(diǎn)的數(shù)據(jù)完全相同（即一致性）是很重要的，隨著多節(jié)點(diǎn)的引入，這影響的是整個(gè)分布式系統(tǒng)對(duì)外服務(wù)的表象一致性。也就是說(shuō)，一個(gè)分布式系統(tǒng)想要做到完全的一致性，需要對(duì)外表現(xiàn)為順序一致性，即各個(gè)節(jié)點(diǎn)上的操作順序都一致。

而在現(xiàn)實(shí)運(yùn)行情況下，節(jié)點(diǎn)可能故障，可能增加，甚至可能被篡改，這就給分布式一致性帶來(lái)了挑戰(zhàn)。在這種情況的干擾下，分布式系統(tǒng)需要通過(guò)某些機(jī)制，來(lái)就一些事情達(dá)成一致的看法，也就是共識(shí)。

但要注意的是，共識(shí)算法并不能一次性解決所有分布式的不一致問(wèn)題。不同的算法能解決不同異常情況下的問(wèn)題，所以共識(shí)算法也有分類：

• 崩潰容錯(cuò)算法（Crash Fault Tolerance）：典型代表是Paxos、Raft、ZAB等。
• 拜占庭容錯(cuò)算法（Byzantine Fault Tolerance）：FBFT為代表的確定性算法，PoW為代表的的概率算法那等。
• 拜占庭將軍問(wèn)題：Lamport曾經(jīng)提出過(guò)在分布式網(wǎng)絡(luò)下的一種節(jié)點(diǎn)作惡場(chǎng)景。描述的是拜占庭需要通過(guò)信使來(lái)在守衛(wèi)邊境的多個(gè)將軍間傳遞消息，以達(dá)成一致的決定。如果此時(shí)出現(xiàn)叛徒，故意發(fā)送不同的消息來(lái)干擾共識(shí)的達(dá)成，應(yīng)該如何讓忠誠(chéng)的將軍們保持行動(dòng)一致。映射到分布式系統(tǒng)中就是多個(gè)節(jié)點(diǎn)就消息達(dá)成共識(shí)時(shí)如果出現(xiàn)錯(cuò)誤節(jié)點(diǎn)傳遞了錯(cuò)誤的消息該怎么辦。

對(duì)于拜占庭容錯(cuò)，往往都需要通過(guò)其他方面的激勵(lì)或懲罰，來(lái)讓“誠(chéng)實(shí)”表達(dá)的節(jié)點(diǎn)利益最大化，本文描述的Paxos算法不解決拜占庭的問(wèn)題，只解決崩潰容錯(cuò)算法條件下達(dá)成分布式共識(shí)的問(wèn)題。

2 Paxos

2.1 背景

有一種說(shuō)法，說(shuō)所有共識(shí)算法都是Paxos。這種說(shuō)法的來(lái)源，一方面是由于Paxos的第一次提出非常的早，另一方面則是因?yàn)?，Paxos解決的其實(shí)是在分布式環(huán)境下，所有服務(wù)達(dá)成一次某個(gè)值的共識(shí)的過(guò)程，而這一過(guò)程，可以說(shuō)每種共識(shí)算法都繞不開(kāi)。

最早在1990年，Paxos的作者Leslie Lamport就提交了關(guān)于Paxos的論文《The Part-Time Parliament》，但直到2001年Lamport第三次發(fā)表簡(jiǎn)化版的相關(guān)論文，且2006年Google使用Paxos的理念實(shí)現(xiàn)了分布式系統(tǒng)，該算法才被大眾所理解和追捧。

1990年的論文中，Lamport描述了一個(gè)名為Paxos的希臘城邦（算法得名于此），這個(gè)城邦是按照民主的議會(huì)制度來(lái)進(jìn)行選舉的，所有的居民進(jìn)行提議和投票來(lái)選出決議。但是居民們不想花時(shí)間一直在選舉上，大家都不定時(shí)地來(lái)提議、了解提議、投票、看進(jìn)展等等，而Paxos算法的目標(biāo)就是通過(guò)少數(shù)服從多數(shù)的方式來(lái)達(dá)成最終的一致意見(jiàn)。但是審稿人覺(jué)得這個(gè)背景太復(fù)雜了，要求刪去，Lamport不樂(lè)意就沒(méi)繼續(xù)投稿了（真大師）。 八年后的1998年，Lamport再次整理算法進(jìn)行投稿，但是大家還是不太理解，因此也沒(méi)有引出多少水花。 又過(guò)了三年，2001年，Lamport再次進(jìn)行了簡(jiǎn)化，發(fā)表了《Paxos Made Simple》，去掉了希臘城邦的背景，里面甚至沒(méi)有一個(gè)公式。但依然直到2006年被Google實(shí)現(xiàn)后才開(kāi)始吸引大家的眼球，而作者Lamport也才獲得了2013年圖靈獎(jiǎng)。

2.2 算法過(guò)程

2.2.1 少數(shù)服從多數(shù)

首先要認(rèn)識(shí)到，這是一個(gè)分布式系統(tǒng)下的共識(shí)算法，要解決的問(wèn)題，簡(jiǎn)化一點(diǎn)，就是一堆機(jī)器，每一臺(tái)都可能會(huì)收到客戶端的一條消息，那需要將自己收到的消息，告訴其他的機(jī)器，讓所有分布式系統(tǒng)中的機(jī)器，達(dá)到最終的一致，這就是達(dá)到共識(shí)。

Paxos采取了一個(gè)我們非常熟悉的達(dá)成共識(shí)的方法：少數(shù)服從多數(shù)。只要有超過(guò)一半的機(jī)器認(rèn)可某一個(gè)消息，那么最終就所有機(jī)器都接受這條消息并將它作為本次的結(jié)論。而競(jìng)選失敗的少數(shù)派消息，就會(huì)被拒絕，并由第一個(gè)從客戶端處接收到該消息的機(jī)器，向客戶端發(fā)送失敗結(jié)果，由客戶端進(jìn)行重試，去嘗試在下一輪競(jìng)選中勝出。

少數(shù)服從多數(shù)，說(shuō)來(lái)簡(jiǎn)單，如果是一群人的話，大家碰個(gè)頭一起舉手表決就好了。但是放到一個(gè)分布式系統(tǒng)中就變復(fù)雜了。機(jī)器之間怎么傳遞提議，怎么表決，怎么統(tǒng)計(jì)多數(shù)，網(wǎng)絡(luò)傳輸需要時(shí)間，在表決過(guò)程中，其他機(jī)器收到了新的消息怎么辦，都需要一整套機(jī)制來(lái)解決。

下面就來(lái)逐步講解Paxos的過(guò)程，但在講解過(guò)程之前，先說(shuō)Paxos中最常見(jiàn)的兩種角色：

• Proposer：提案者。也就是在選舉中提出提案的人，放到分布式系統(tǒng)里，就是接收到客戶端寫(xiě)操作的人。一切行為都由Proposer提出提案開(kāi)始，Paxos會(huì)將提案想要進(jìn)行的操作，抽象為一個(gè)“value”，去在多臺(tái)機(jī)器中傳遞，最后被所有機(jī)器接受。
• Acceptor：批準(zhǔn)者。Acceptor 從含義上來(lái)說(shuō)就是除了當(dāng)前Proposer以外的其他機(jī)器，他們之間完全平等和獨(dú)立，Proposer需要爭(zhēng)取超過(guò)半數(shù)（N/2+1）的 Acceptor 批準(zhǔn)后，其提案才能通過(guò)，它倡導(dǎo)的“value”操作才能被所有機(jī)器所接受。

除了以上兩種角色，實(shí)際上Paxos還會(huì)提到Learner，即學(xué)習(xí)者這個(gè)角色，該角色是在達(dá)成決議時(shí)，對(duì)結(jié)論的學(xué)習(xí)者，也即是從其他節(jié)點(diǎn)“學(xué)習(xí)”最終提案內(nèi)容，比較簡(jiǎn)單。需要注意，這些角色只是在不同時(shí)間下，邏輯上的劃分，實(shí)際上任何一臺(tái)機(jī)器都可以充當(dāng)這三個(gè)角色之一。

2.2.2 一個(gè)簡(jiǎn)單的提案

先描述最簡(jiǎn)單的情況，假設(shè)現(xiàn)在有四臺(tái)機(jī)器，其中一臺(tái)收到了來(lái)自客戶端的寫(xiě)操作請(qǐng)求，需要同步給其他機(jī)器。

此時(shí)這臺(tái)收到請(qǐng)求的機(jī)器，我們稱它為Proposer，因?yàn)樗鼘⒁_(kāi)始將收到的請(qǐng)求，作為一個(gè)提案，提給其他的機(jī)器。這里為了方便，我們假設(shè)這個(gè)請(qǐng)求是要將一個(gè)地址設(shè)置為“深圳”，那么如下圖所示：

此時(shí)，其他的Acceptor都閑著呢，也沒(méi)其他人找，所以當(dāng)它們收到Proposer的提案時(shí)，就直接投票了，說(shuō)可以可以，我是空的，贊成提案（同意提議）：

到這里，就還是一個(gè)簡(jiǎn)單的同步的故事，但需要注意的是，這里Proposer實(shí)際上是經(jīng)歷了兩步的。

在這個(gè)簡(jiǎn)單的提案過(guò)程中，Proposer其實(shí)也經(jīng)歷了兩個(gè)階段：

1. Prepare階段：Proposer告訴所有其他機(jī)器，我這里有一個(gè)提案（操作），想要你們投投票支持一下，想聽(tīng)聽(tīng)大家的意見(jiàn)。Acceptor看自己是NULL，也就是目前還沒(méi)有接受過(guò)其他的提案，就說(shuō)我肯定支持。
2. Accept階段：Proposer收到其他機(jī)器的回復(fù)，說(shuō)他們都是空的，也就是都可以支持接受Proposer的提案（操作），于是正式通知大家這個(gè)提案被集體通過(guò)了，可以生效了，操作就會(huì)被同步到所有機(jī)器正式生效。

2.2.3 兩個(gè)提案并發(fā)進(jìn)行

現(xiàn)在考慮一個(gè)更復(fù)雜的場(chǎng)景，因?yàn)槲覀兲幱谝粋€(gè)分布式的場(chǎng)景，每臺(tái)機(jī)器都可能會(huì)收到請(qǐng)求，那如果有兩臺(tái)機(jī)器同時(shí)收到了兩個(gè)客戶端的不同請(qǐng)求，該怎么處理呢？大家聽(tīng)誰(shuí)的呢？最后的共識(shí)以誰(shuí)的為準(zhǔn)呢？如下圖

在這種情況下，由于網(wǎng)絡(luò)傳輸?shù)臅r(shí)間問(wèn)題，兩個(gè)Proposer的提案到達(dá)各個(gè)機(jī)器，是會(huì)存在先后順序的。假設(shè)Proposer 1 的提案先達(dá)到了 Acceptor 1 和 Acceptor 2，而Proposer 2 的提案先達(dá)到了 Acceptor 3，其達(dá)到 Acceptor 1 和 Acceptor 2 時(shí)，由于機(jī)器已經(jīng)投票給Proposer 1 了，所以Proposer 2 的提案遭到拒絕，Proposer 1 達(dá)到 Acceptor 3 的時(shí)候同樣被拒。

Acceptor們迷了，Proposer們也迷了，到底應(yīng)該接受誰(shuí)？此時(shí)，還是遵循自由民主的法則——少數(shù)服從多數(shù)。

Proposer 1 發(fā)現(xiàn)超過(guò)半數(shù)的Acceptor都接受了自己，所以放心大膽地發(fā)起要求，讓所有Acceptor都按照自己的值來(lái)操作。而Proposer 2 發(fā)現(xiàn)只有不到半數(shù)的Acceptor支持自己，而有超過(guò)半數(shù)是支持Proposer 1 的值的，因此只能拒絕Client 2，并將自己也改為Proposer 1 的操作：

到此為止，看起來(lái)沒(méi)有問(wèn)題，但是，這是因?yàn)榍『肁cceptor的數(shù)量是單數(shù)，可以選出“大多數(shù)”，但是因?yàn)橥瑫r(shí)成為Proposer的機(jī)器數(shù)量是不確定的，因此是無(wú)法保證Acceptor的數(shù)量一定是單數(shù)的，如下面這種情況就無(wú)法選出“大多數(shù)”了：

這時(shí)，兩個(gè)Proposer有可能總是先搶到一個(gè)Acceptor的支持，然后在另一個(gè)Acceptor處折戟沉沙，算法就一直循環(huán)死鎖下去了。為了解決這種情況，Paxos給提案加了一個(gè)編號(hào)。

2.2.4 給提案加上編號(hào)

之前我們Proposer的提案都是只有操作內(nèi)容的，現(xiàn)在我們給他加一個(gè)編號(hào)，即：

• Proposer 1 的提案為：[n1, v1]
• Proposer 2 的提案為：[n2, v2]

假設(shè)Proposer 1 接到Clint 1 的消息稍微早一點(diǎn)，那么它的編號(hào)就是1，Proposer 2 的編號(hào)就是2，那么他們的提案實(shí)際就是：

• Proposer 1 的提案為：[1, { Set Addr = "深圳"}]
• Proposer 2 的提案為：[2, { Set Addr = "北京"}]

此時(shí)，Paxos加上一條規(guī)則：

• Acceptor如果還沒(méi)有正式通過(guò)提案（即還沒(méi)有Accept使操作生效），就可以接受編號(hào)更大的Prepare請(qǐng)求。

所以，回到上面的困境

1. 當(dāng)Proposer 1 想要向Acceptor 2 尋求支持時(shí)，Acceptor 2 一看你的編號(hào)（1）比我已經(jīng)支持的編號(hào)（2）要小，拒絕拒絕。此時(shí)Proposer 1 由于沒(méi)有得到過(guò)半數(shù)的支持，會(huì)重新尋求支持。

2. 而當(dāng)Proposer 2 想要向Acceptor 1 尋求支持時(shí)，Acceptor 1 一看你的編號(hào)（2）比我已經(jīng)支持的編號(hào)（1）要大，好的你是老大我聽(tīng)你的。此時(shí)Proposer 2 已經(jīng)得到了超過(guò)半數(shù)的支持，可以進(jìn)入正式生效的Accept階段了。

   
   

這里需要補(bǔ)充一下，Proposer 1 這里支持提案失敗，他是怎么讓自己也接受Proposer 2 的提案的呢？

所以這里的后續(xù)會(huì)發(fā)生的事情是：

1. Proposer 2 發(fā)現(xiàn)得到了過(guò)半數(shù)的支持，開(kāi)始向所有Acceptor發(fā)送Accept請(qǐng)求。
2. 所有Acceptor接收到Accept請(qǐng)求后，按照之前Prepare時(shí)收到的信息與承諾，去生效Proposer 2 的提案內(nèi)容（即Set Addr = “北京”的操作）。
3. Proposer 1 之前已經(jīng)收到了所有Acceptor的回復(fù)，發(fā)現(xiàn)沒(méi)有得到過(guò)半數(shù)的支持，直接回復(fù)Client 1 請(qǐng)求失敗，并變成一個(gè)Acceptor（或者說(shuō)Learner），接受Proposer 2 的Accept請(qǐng)求。

這里再想多一點(diǎn)，考慮另一種場(chǎng)景：假設(shè)Proposer 2 的Accept請(qǐng)求先達(dá)到了Acceptor 2，然后Proposer 1 向Acceptor 2 發(fā)送的Prepare請(qǐng)求才到達(dá) Acceptor 2，會(huì)發(fā)生什么呢？

最直觀的處理是， Acceptor 2 直接拒絕，然后Proposer 1 走上面的流程，但Paxos為了效率，又增加了另一條規(guī)則：

• 如果一個(gè)Prepare請(qǐng)求，到達(dá)Acceptor時(shí)，發(fā)現(xiàn)該Acceptor已經(jīng)接受生效了另一個(gè)提案，那么它除了回復(fù)提案被拒絕外，還會(huì)帶上Acceptor已經(jīng)通過(guò)的編號(hào)最大的那個(gè)提案的內(nèi)容回到Proposer。Proposer收到帶內(nèi)容的拒絕后，需要修改自己的提案為返回的內(nèi)容。

此時(shí)會(huì)發(fā)生的事情就變成了：

1. 此時(shí)Acceptor 2 除了會(huì)拒絕它的請(qǐng)求，還會(huì)告訴Proposer 1，說(shuō)我已經(jīng)通過(guò)并生效了另一個(gè)編號(hào)為2的提案，內(nèi)容是Set Addr = “北京”。
2. 然后Proposer 1 查看回復(fù)時(shí)，發(fā)現(xiàn)已經(jīng)有Acceptor生效提案了，于是就修改自己的提案，也改為Set Addr = “北京”，并告知Client 1 你的請(qǐng)求失敗了。
3. 接著Proposer 1 開(kāi)始充當(dāng)Proposer 2 的小幫手，幫他一起傳播 Proposer 2 的提案，加快達(dá)成共識(shí)的過(guò)程。

PS：這里需要注意，編號(hào)是需要保證全局唯一的，而且是全局遞增的，否則在比較編號(hào)大小的時(shí)候就會(huì)出現(xiàn)問(wèn)題，怎么保證編號(hào)唯一且遞增有很多方法，比如都向一個(gè)統(tǒng)一的編號(hào)生成器請(qǐng)求新編號(hào)；又比如每個(gè)機(jī)器的編號(hào)用機(jī)器ID拼接一個(gè)數(shù)字，該數(shù)字按一個(gè)比總機(jī)器數(shù)更大的數(shù)字間隔遞增。

2.2.5 一些異常情況

上面的規(guī)則是不是就能保證整個(gè)算法解決所有問(wèn)題了呢？恐怕不是，這里再看看一些異常情況。

異常情況一：假設(shè)現(xiàn)在有三個(gè)Proposer同時(shí)收到客戶端的請(qǐng)求，那么他們會(huì)生成全局唯一的不同編號(hào)，帶著各自接收到的請(qǐng)求提案，去尋求Acceptor的支持。但假設(shè)他們都分別爭(zhēng)取到了一個(gè)Acceptor的支持，此時(shí)由于Prepare階段只會(huì)接受編號(hào)更大的提案，所以正常情況下只有Proposer 3 的提案會(huì)得到所有Acceptor的支持。但假設(shè)這時(shí)候Proposer 3 機(jī)器掛了，無(wú)法進(jìn)行下一步的Accept了，怎么辦呢？那么所有Acceptor就會(huì)陷入持續(xù)的等待，而其他的Proposer也會(huì)一直重試然后一直失敗。

為了解決這個(gè)問(wèn)題，Paxos決定，允許Proposer在提案遭到過(guò)半數(shù)的拒絕時(shí)，更新自己的提案編號(hào)，用新的更大的提案編號(hào)，去發(fā)起新的Prepare請(qǐng)求。

那么此時(shí)Proposer 1 和Proposer 2 就會(huì)更新自己的編號(hào)，從【1】與【2】，改為比如【4】和【5】，重新嘗試提案。這時(shí)即使Proposer 3 機(jī)器掛了，沒(méi)有完成Accept，Acceptor也會(huì)由于接收到了編號(hào)更大的提案，從而覆蓋掉Proposer 3 的提案，進(jìn)入新的投票支持階段。

異常情況二：雖然更新編號(hào)是解決了上面的問(wèn)題，但卻又引入了活鎖的問(wèn)題。由于可以更新編號(hào)，那么有概率出現(xiàn)這種情況，即每個(gè)Proposer都在被拒絕時(shí)，增大自己的編號(hào)，然后每個(gè)Proposer在新的編號(hào)下又爭(zhēng)取到了小于半數(shù)的Acceptor，都無(wú)法進(jìn)入Accept，又重新加大編號(hào)發(fā)起提案，一直這樣往復(fù)循環(huán)，就成了活鎖（和死鎖的區(qū)別是，他們的狀態(tài)一直在變化，嘗試解鎖，但還是被鎖住了）。

要解決活鎖的問(wèn)題，有幾種常見(jiàn)的方法：

• 當(dāng)Proposer接收到回復(fù)，發(fā)現(xiàn)支持它的Acceptor小于半數(shù)時(shí)，可以不立即更新編號(hào)重試，而是隨機(jī)延遲一小段時(shí)間，來(lái)錯(cuò)開(kāi)彼此的沖突。
• 可以設(shè)置一個(gè)Proposer的Leader，全部由它來(lái)進(jìn)行提案，這即使共識(shí)算法的常見(jiàn)套路，選擇一個(gè)Leader。這需要進(jìn)行Leader的選舉，以及解決存活性檢查以及換屆的問(wèn)題。實(shí)際上就已經(jīng)演變成Multi-Paxos了。

異常情況三：由于在提案時(shí)，Proposer都是根據(jù)是否得到超過(guò)半數(shù)的Acceptor的支持，來(lái)作為是否進(jìn)入Accept階段的依據(jù)，那如果在算法進(jìn)行中新增或下線了機(jī)器呢？如果此時(shí)一些Proposer知道機(jī)器數(shù)變了，一些Proposer不知道，那么大家對(duì)半數(shù)的判斷就會(huì)不一致，導(dǎo)致算法出錯(cuò)。

因此在實(shí)際運(yùn)行中，機(jī)器節(jié)點(diǎn)數(shù)的變動(dòng)，也需要作為一條要達(dá)成共識(shí)的請(qǐng)求提案，通過(guò)Paxos算法本身，傳達(dá)到所有機(jī)器節(jié)點(diǎn)上。

為了使Paxos運(yùn)行得更穩(wěn)定，不需要時(shí)刻擔(dān)心是否有節(jié)點(diǎn)數(shù)變化，可以固定一個(gè)周期，要求只有在達(dá)到固定周期時(shí)才允許變更節(jié)點(diǎn)數(shù)，比如只有在經(jīng)過(guò)十次客戶端請(qǐng)求的提案與接受后，才處理一次機(jī)器節(jié)點(diǎn)數(shù)變化的提案。

那如果這個(gè)間隔設(shè)置地相對(duì)過(guò)久，導(dǎo)致現(xiàn)在想要修改節(jié)點(diǎn)數(shù)時(shí)，一直要苦等提案數(shù)，怎么辦呢？畢竟有時(shí)候機(jī)器壞了是等不了的。那么可以支持主動(dòng)填充空的提案數(shù)，來(lái)讓節(jié)點(diǎn)變更的提案盡早生效。

2.2.6 Paxos協(xié)議的兩階段

抽象和完善一下這個(gè)過(guò)程，就是：

1. Prepare準(zhǔn)備階段：在該階段，Proposer會(huì)嘗試告訴所有的其他機(jī)器，我現(xiàn)在有一個(gè)提案（操作），請(qǐng)告訴我你們是否支持（是否能接受）。其他機(jī)器會(huì)看看自己是否已經(jīng)支持其他提案了（是否接受過(guò)其他操作請(qǐng)求），并回復(fù)給Proposer（如果曾經(jīng)接受過(guò)其他值，就告訴Proposer接受過(guò)什么值/操作）。
   1. Acceptor如果已經(jīng)支持了編號(hào)N的提案，那么不會(huì)再支持編號(hào)小于N的提案，但可以支持編號(hào)更大的提案；
   2. Acceptor如果生效了編號(hào)為N的提案，那么不會(huì)再接受編號(hào)小于N的提案，且會(huì)在回復(fù)時(shí)告知當(dāng)前已生效的提案編號(hào)與內(nèi)容。
2. Accept提交階段：在該階段，Proposer根據(jù)上一階段接收到的回復(fù)，來(lái)決定行為：
   1. 如果上一階段超過(guò)半數(shù)的機(jī)器回復(fù)說(shuō)接受提案，那么Proposer就正式通知所有機(jī)器去生效這個(gè)操作；
   2. 如果上一階段超過(guò)半數(shù)的機(jī)器回復(fù)說(shuō)他們已經(jīng)先接受了其他編號(hào)更大的提案，那么Proposer會(huì)更新一個(gè)更大的編號(hào)去重試（隨機(jī)延時(shí)）；
   3. 如果上一階段的機(jī)器回復(fù)說(shuō)他們已經(jīng)生效了其他編號(hào)的提案，那么Proposer就也只能接受這個(gè)其他人的提案，并告知所有機(jī)器直接接受這個(gè)新的提案；
   4. 如果上一階段都沒(méi)收到半數(shù)的機(jī)器回復(fù)，那么提案取消。
   5. PS：接受其他提案，以及提案取消的情況下，Proposer就要直接告訴客戶端該次請(qǐng)求失敗了，等待客戶端重試即可。

這里可以看到，超過(guò)半數(shù)以上的機(jī)器是個(gè)很重要的決定結(jié)果走向的條件。

至此，已經(jīng)描述完了針對(duì)一次達(dá)成共識(shí)的過(guò)程，這被稱為Basic-Paxos。

那如果有多個(gè)值需要達(dá)成共識(shí)呢？

2.2.7 Multi-Paxos

如果有多個(gè)值要不斷地去針對(duì)一次次請(qǐng)求達(dá)成共識(shí)，使用Basic-Paxos也是可以的，無(wú)非就是一遍遍地執(zhí)行算法取得共識(shí)并生效嘛，但在分布式系統(tǒng)下，容易由于多次的通信協(xié)程造成響應(yīng)過(guò)慢的問(wèn)題，何況還有活鎖問(wèn)題存在。因此Lamport給出的解法是：

1. 先選擇一個(gè)Leader來(lái)?yè)?dān)當(dāng)Proposer的角色，取消多Proposer，只有一個(gè)Leader來(lái)提交提案，這樣就沒(méi)有了競(jìng)爭(zhēng)（也沒(méi)有了活鎖）。同時(shí)，由于無(wú)需協(xié)商判斷，有了Leader后就可以取消Prepare階段，兩階段變一階段，提高效率。
2. 對(duì)于每一次要確定的值/操作，使用唯一的一個(gè)標(biāo)識(shí)來(lái)區(qū)分，保證其單調(diào)遞增即可。

對(duì)于選擇Leader的過(guò)程，簡(jiǎn)單的做法很多，復(fù)雜的也只需要進(jìn)行一次Basic-Paxos即可。選出Leader后，直到Leader掛掉或者到期，都可以保持由它來(lái)進(jìn)行簡(jiǎn)化的Paxos協(xié)議。

如果有多個(gè)機(jī)器節(jié)點(diǎn)都由于某些問(wèn)題自認(rèn)為自己是Leader，從而都提交了提案，也沒(méi)關(guān)系，可以令其退化成Basic-Paxos，也可以在發(fā)現(xiàn)后再次選擇Leader即可。

3 其他共識(shí)算法

這里也順便對(duì)比一下另外兩種常見(jiàn)的共識(shí)算法：ZAB和Raft。

3.1 ZAB

ZAB全稱是Zookeeper Atomic Broadcast，也就是Zookeeper的原子廣播，顧名思義是用于Zookeeper的。

ZAB理解起來(lái)很簡(jiǎn)單，在協(xié)議中有兩種角色：

• Leader節(jié)點(diǎn)：有任期的領(lǐng)導(dǎo)節(jié)點(diǎn)，負(fù)責(zé)作為與客戶端的連接點(diǎn)接受讀寫(xiě)操作，然后將其廣播到其他節(jié)點(diǎn)去。
• Follower節(jié)點(diǎn)：主要是跟隨領(lǐng)導(dǎo)節(jié)點(diǎn)的廣播消息進(jìn)行同步，并關(guān)注領(lǐng)導(dǎo)節(jié)點(diǎn)的健康狀態(tài)，好隨時(shí)取而代之。

既然有Leader節(jié)點(diǎn)，就必然有Leader的選舉過(guò)程，ZAB的選舉，會(huì)先看各個(gè)節(jié)點(diǎn)所記錄的消息的時(shí)間戳（數(shù)據(jù)ID），時(shí)間戳（數(shù)據(jù)ID）越大，節(jié)點(diǎn)上的數(shù)據(jù)越新，就會(huì)優(yōu)先被投票，如果數(shù)據(jù)ID比較不出來(lái)，就再看事先定義的節(jié)點(diǎn)的優(yōu)先級(jí)（節(jié)點(diǎn)ID）。當(dāng)大家根據(jù)上述優(yōu)先級(jí)投票，超過(guò)半數(shù)去支持一個(gè)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)就成為L(zhǎng)eader節(jié)點(diǎn)了。

通過(guò)心跳算法可以共同檢查L(zhǎng)eader節(jié)點(diǎn)的健康度，如果出現(xiàn)問(wèn)題（比如機(jī)器下線、網(wǎng)絡(luò)分區(qū)、延遲過(guò)高等），就會(huì)考慮重新選舉。

可以看出，這種選舉方式相對(duì)Paxos是比較方便高效的，而且選出Leader節(jié)點(diǎn)后，就可以直接通過(guò)Leader節(jié)點(diǎn)接受消息進(jìn)行廣播，而不需要進(jìn)行兩階段提交。

其實(shí)ZAB就很像選出了Leader的Multi-Paxos，兩者的差異主要在選Leader的流程上。

3.2 Raft

Raft的應(yīng)用比Paxos要多，有人認(rèn)為Raft是Multi-Paxos的改進(jìn)，因?yàn)镽aft的作者也曾研究過(guò)Paxos。既然Paxos是前輩，為什么應(yīng)用的反而要少呢？這是因?yàn)锽asic-Paxos相對(duì)比較耗時(shí)，而Multi-Paxos，作者并沒(méi)有給出具體的實(shí)現(xiàn)細(xì)節(jié)，這雖然給了開(kāi)發(fā)者發(fā)揮的空間，但同樣可能會(huì)在實(shí)現(xiàn)的過(guò)程中由于開(kāi)發(fā)者不同的實(shí)現(xiàn)方式帶來(lái)不同的問(wèn)題，對(duì)于一個(gè)分布式共識(shí)算法，誰(shuí)也不知道潛在的問(wèn)題會(huì)不會(huì)就影響到一致性了。而Raft算法給出了大量實(shí)現(xiàn)細(xì)節(jié)，簡(jiǎn)單說(shuō)就是，實(shí)現(xiàn)起來(lái)更不容易出錯(cuò)。

Raft協(xié)議同樣是需要選舉出Leader的，從這里也能看到，共識(shí)算法大都會(huì)走向選舉出一個(gè)Leader的方向，來(lái)提升效率和穩(wěn)定性。不同之處可能只在于選舉的方式，以及消息同步的方式。

Raft的選舉，會(huì)在上一任Leader失去聯(lián)系時(shí)發(fā)起，每個(gè)Follower便有機(jī)會(huì)成為Candidate，參與選舉。之所以說(shuō)有機(jī)會(huì)，是因?yàn)槊總€(gè)Follower都會(huì)先等一會(huì)，看是否有其他候選人過(guò)來(lái)拉票，避免人人都跑去湊熱鬧參與選舉浪費(fèi)通信，這個(gè)等待的時(shí)間是在一個(gè)范圍內(nèi)隨機(jī)的。

候選者參與選舉時(shí)會(huì)產(chǎn)生一個(gè)term概念，每個(gè)候選者會(huì)先投自己一票，然后帶著自己的term和自己的日志信息（代表著數(shù)據(jù)的新舊）去拉票，其他的Follower先看候選者的term是否大于等于當(dāng)前自己的term，再看其日志信息是否比自己新，如果都滿足就會(huì)投票。候選者收到超過(guò)半數(shù)的投票的話，就會(huì)成為新的Leader了。

在這個(gè)過(guò)程中投票的Follower也會(huì)更新自己的term為自己投票的候選者的term，這樣就可以拒絕低于它的term的候選者了。而候選者如果被拒絕，也會(huì)回去更新自己的term以獲得支持。

選出Leader后，Leader會(huì)把自己的日志發(fā)給大家做同步，以保持大家和自己的日志是一樣的，然后就進(jìn)行后續(xù)的接收客戶端請(qǐng)求的環(huán)節(jié)。

可以看到Raft和Multi-Paxos也都要選舉出一個(gè)Leader節(jié)點(diǎn)來(lái)，不同之處在于，Raft選舉的Leader節(jié)點(diǎn)上的日志信息是最新最全的，這一方面可以不丟失日志信息的順序，另一方面也可以讓選舉過(guò)程簡(jiǎn)化（日志信息的順序總是好比較的），而Multi-Paxos選Leader的過(guò)程偏隨機(jī)，就是看誰(shuí)先拉攏更多節(jié)點(diǎn)的支持并快速落定，這一方面會(huì)使其日志不連續(xù)，另一方面也會(huì)使得其實(shí)現(xiàn)變得復(fù)雜和相對(duì)不可控。

但實(shí)際上不連續(xù)也不完全是缺點(diǎn)，它也可以提高寫(xiě)入的并發(fā)性能，所以雖然Raft實(shí)現(xiàn)相對(duì)更簡(jiǎn)單，但微信的PaxosStore還是選擇了Paxos，甚至它都沒(méi)有選擇Multi-Paxos，而是Basic-Paxos，就是為了進(jìn)一步避免單點(diǎn)依賴和切換Leader時(shí)的拒絕服務(wù)，來(lái)提高可用性。

可以看到，共識(shí)算法基本都需要解決兩個(gè)基本問(wèn)題：

1. 如何提出一個(gè)需要達(dá)成共識(shí)的提案（選舉Leader、隨機(jī)投票...）
2. 如何讓多個(gè)節(jié)點(diǎn)對(duì)提案達(dá)成共識(shí)（廣播、復(fù)制、投票...）

在這兩個(gè)問(wèn)題的處理方案上選擇不同，就會(huì)導(dǎo)致性能、可用性等指標(biāo)的不同，所以其實(shí)，兵器各有利弊，還是要看使用場(chǎng)景和使用的人。

參考文檔

• 理解這兩點(diǎn)，也就理解了paxos協(xié)議的精髓
• Paxos 的誕生
• Paxos 協(xié)議簡(jiǎn)單介紹
• 【超詳細(xì)】分布式一致性協(xié)議 - Paxos
• Paxos算法 - 維基百科
• 分布式系統(tǒng)的一致性與共識(shí)算法-基礎(chǔ)理論
• Paxos和Raft的前世今生
• raft算法與paxos算法相比有什么優(yōu)勢(shì)，使用場(chǎng)景有什么差異
• 共識(shí)算法：一次性說(shuō)清楚 Paxos、Raft 等算法的區(qū)別

關(guān)注我的公眾號(hào)【月亮與二進(jìn)制】，鵝廠程序員的敲碼間隙，也能讀書(shū)觀影練劍寫(xiě)字，分享給你我的世界