分布式一緻性

引言

本文從分布式一緻性問題出發，介紹了各種一緻性算法，希望通過該文能讓大家對分布式系統有一定的認識。更多關于分布式系統的文章均收錄于

中。

分布式系統

分布式系統是一個硬體或軟體元件分布在不同的網絡計算機上,彼此之間僅僅通過消息傳遞進行通信和協調的系統。

由來

在過去的很長一段時間裡，集中式的計算機系統架構一直占據主流市場，因為集中式系統一般都是依賴下層卓越的大型主機，它們的處理能力非常優秀，而且穩定性良好。但是随着網際網路的普及，集中式系統越來越難以滿足大型網絡系統發展的需要，一來大型主機的價格也非常昂貴，而且存在單點問題。此時依賴于小型機的分布式系統應運而生，它們憑借可量化的可靠性，以及水準擴充能力，逐漸在大型網際網路系統中嶄露頭角。

目标

分布式系統的設計目标，一般包括如下幾個方面：

可用性:可用性是分布式系統的核心需求,其用于衡量一個分布式系統持續對外提供服務的能力。
可擴充性:增加機器後不會改變或極少改變系統行為,并且能獲得近似線性的性能提升。
容錯性:系統發生錯誤時,具有對錯誤進行規避以及從錯誤中恢複的能力。
性能:對外服務的響應延時和吞吐率要能滿足使用者的需求。

面臨的問題

分布式系統雖然目标很美好，但是在實際的實作過程中，還是會面臨許多問題，它們主要集中在如下幾個方面：

通信異常：分布式系統需要在各個節點之間進行網絡通信,是以每次網絡通信都會伴随着網絡不可用的風險，此外每一次的通信都有可能産生較大的消息延時，甚至消息丢失。
網絡分區：網絡分區和通信異常雖然都是因為網絡傳輸出現問題，但是在分布式系統的層面卻分化出兩類問題。而網絡分區特指那些系統分化出大小兩個網絡組，每個組内都能正常通訊通信，但是組間通訊被阻隔，我們将這種現象稱為"腦裂"。
三态：分布式系統的每一次請求，可能存在三種結果，成功，失敗和逾時，當發生逾時現象時，請求者無法判斷目前請求是否成功處理。
節點故障：節點故障是一個非常常見的問題，指分布式系統的伺服器節點可能出現當機，僵死，器件損壞等問題。

經典理論

CAP

CAP理論告訴我們,一個分布式系統不可能同時滿足一緻性(C:Consistency)、可用性(A: Availability)和分區容錯性(P:Partition tolerance)這三個基本需求,最多隻能同時滿足其中的兩項。

一緻性

在分布式環境中,一緻性是指資料在多個副本之間是否能夠保持一緻的特性。如果對第一個節點的資料進行了更新操作并且更新成功後,卻沒有使得第二個節點上的資料得到相應的更新,于是在對第二個節點的資料進行讀取操作時,擷取的依然是老資料(或稱為髒資料),這就是典型的分布式資料不一緻情況。在分布式系統中,如果能夠做到針對一個資料項的更新操作執行成功後,所有的使用者都可以讀取到其最新的值,那麼這樣的系統就被認為具有強一緻性(或嚴格的一緻性)。

可用性

可用性是指系統提供的服務必須一直處于可用的狀态,對于使用者的每一個操作請求總是能夠在有限的時間内傳回結果。

分區容錯性

分布式系統在遇到任何網絡分區故障的時候,仍然需要能夠保證對外提供滿足一緻性和可用性的服務,除非是整個網絡環境都發生了故障。

從 CAP 定理中我們可以看出,一個分布式系統不可能同時滿足一緻性、可用性和分區容錯性這三個需求。另一方面,需要明确的一點是,對于一個分布式系統而言,分區容錯性可以說是一個最基本的要求。因為既然是一個分布式系統,那麼分布式系統中的元件必然需要被部署到不同的節點,是以必然出現子網絡。而對于分布式系統而言,網絡問題又是一個必定會出現的異常情況,是以分區容錯性也就成為了一個分布式系統必然需要面對和解決的問題。是以系統架構設計師往往需要把精力花在如何根據業務特點在C(一緻性)和A(可用性)之間尋求平衡。

BASE

BASE 是 Basically Available(基本可用)、Soft state(軟狀态)和 Eventually consistent(最終一緻性)三個短語的簡寫。BASE是對CAP中一緻性和可用性權衡的結果,其來源于對大規模網際網路系統分布式實踐的總結,是基于CAP定理逐漸演化而來的,其核心思想是即使無法做到強一緻性(Strong consistency),但每個應用都可以根據自身的業務特點,采用适當的方式來使系統達到最終一緻性(Eventual consistency)。

基本可用

基本可用是指分布式系統在出現不可預知故障的時候,允許損失部分可用性，但這絕不等價于系統不可用。比如一個請求本來需要0.5秒傳回結果，但是因為系統故障，最終花了2秒。

軟狀态

允許系統中的資料存在中間狀态,并認為該中間狀态的存在不會影響系統的整體可用性,即允許系統在不同節點的資料副本之間進行資料同步的過程存在延時。

最終一緻性

最終一緻性強調的是系統中所有的資料副本,在經過一段時間的同步後,最終能夠達到一個一緻的狀态。是以,最終一緻性的本質是需要系統保證最終資料能夠達到一緻,而不需要實時保證系統資料的強一緻性。

最終一緻性是一種特殊的弱一緻性，系統能夠保證在沒有其他新的更新操作的情況下,資料最終一定能夠達到一緻的狀态,是以所有用戶端對系統的資料通路都能夠擷取到最新的值。同時,在沒有發生故障的前提下,資料達到一緻狀态的時間延遲,取決于網絡延遲、系統負載和資料複制方案設計等因素。

一緻性模型

嚴格一緻性

嚴格一緻性也稱強一緻性,原子一緻性或者是可線性化(Linearizability),是要求最高的一緻性模型。嚴格一緻性的要求具體如下。

任何一次讀都能讀到某個資料的最近一次寫的資料。
系統中的所有程序,看到的操作順序,都與全局時鐘下的順序一緻。

對于嚴格一緻性的存儲器，要求寫操作在任一時刻對所有的程序都是可見的，同時還要維護一個絕對全局時間順序。一旦存儲器中的值發生改變，那麼不管讀寫之間的事件間隔有多小，不管是哪個程序執行了讀操作，以後讀出的都是新更改的值。同樣，如果執行了讀操作，那麼不管後面的寫操作有多迅速，該讀操作仍應讀出原來的值。

但是在分布式計算機系統中為每個操作都配置設定一個準确的全局時間戳是不可能實作的。是以，嚴格一緻性，隻是存在于理論中的一緻性模型。但是，以通常的程式設計角度來看這個問題，每個語句的執行時刻并不重要，而讀和寫的順序至關重要，我們可以通過鎖來進行讀寫的同步，先拿到鎖的操作就會被認定是先執行，反之則是後執行的。這實際上是對嚴格一緻性的一種弱化。

順序一緻性

因為全局時鐘導緻嚴格一緻性很難實作，是以順序一緻性放棄了全局時鐘的限制，改為分布式邏輯時鐘實作。順序一緻性是指所有的程序都以相同的順序看到所有的修改。讀操作未必能夠及時得到此前其他程序對同一資料的寫更新，但是每個程序讀到的該資料不同值的順序卻是一緻的。

圖中a滿足順序一緻性，但是不滿足強一緻性。原因在于，從全局時鐘的觀點來看，P2程序對變量 X 的讀操作在P1程序對變量 X 的寫操作之後，然而讀出來的卻是舊的資料。但是這個圖卻是滿足順序一緻性的，因為兩個程序P1，P2的順序一緻性并沒有沖突。從這兩個程序的角度來看，順序應該是這樣的: Write(y，2)→ Read(x,O)→ Write(x,4)→ Read(y,2)，每個程序内部的讀寫順序都是合理的，但是顯然這個順序與全局時鐘下看到的順序并不一樣。

圖中b滿足強一緻性，因為每個讀操作都讀到了該變量最新寫的結果，同時兩個程序看到的操作順序與全局時鐘的順序一樣，都是 Write(y,2)→ Read (x,4)→ Write(x,4)→ Read(y,2)。

圖中c 不滿足順序一緻性，當然也就不滿足強一緻性。因為從程序P1的角度來看，它對變量Y的讀操作傳回了結果0。也就是說，P1程序的對變量Y的讀操作在P2程序對變量Y的寫操作之前，這意味着它認為的順序是這樣的: Write(x,4)→ Read(y,O)→ Write(y,2)→ Read(x,O)，顯然這個順序是不能滿足的，因為最後一個對變量x的讀操作讀出來的也是舊的資料。是以這個順序是有沖突的，不滿足順序一緻性。

因果一緻性

因果一緻性是指,如果程序A在更新完某個資料項後通知了程序B,那麼程序B之後對該資料項的通路都應該能夠擷取到程序A更新後的最新值,并且如果程序B要對該資料項進行更新操作的話,務必基于程序A更新後的最新值,即不能發生丢失更新情況。與此同時,與程序A無因果關系的程序C的資料通路則沒有這樣的限制。

讀己之所寫

讀己之所寫是指,程序A更新一個資料項之後,它自己總是能夠通路到更新過的最新值,而不會看到舊值。也就是說對于單個資料擷取者來說,其讀取到的資料,一定不會比自己上次寫入的值舊。是以,讀己之所寫也可以看作是一種特殊的因果一緻性。

會話一緻性

會話一緻性将對系統資料的通路過程框定在了一個會話當中系統能保證在同一個有效的會話中實作“讀己之所寫”的一緻性,也就是說,執行更新操作之後,用戶端能夠在同一個會話中始終讀取到該資料項的最新值。

單調一緻性

單調讀一緻性是指如果一個程序從系統中讀取出一個資料項的某個值後,那麼系統對于該程序後續的任何資料通路都不應該傳回更舊的值。

以上就是最終一緻性的五類常見的變種,在實際系統實踐中,可以将其中的若幹個變種互相結合起來,以建構一個具有最終一緻性特性的分布式系統。

複制狀态機

複制狀态機的思想是一個分布式的複制狀态機系統由多個複制單元組成，每個複制單元均是一個狀态機，它的狀态儲存在一組狀态變量中。狀态機的狀态能夠并且隻能通過外部指令來改變。

上文提到的“一組狀态變量”通常是基于記錄檔來實作的。每一個複制單元存儲一個包含一系列指令的日志，并且嚴格按照順序逐條執行日志上的指令。因為每個狀态機都是确定的，是以每個外部指令都将産生相同的操作序列 (日志)。又因為每一個日志都是按照相同的順序包含相同的指令，是以每一個伺服器都将執行相同的指令序列，并且最終到達相同的狀态。

綜上所述，在複制狀态機模型下，一緻性算法的主要工作就變成了如何保證記錄檔的一緻性。

伺服器上的一緻性子產品負責接收外部指令，然後追加到自己的記錄檔中。它與其他伺服器上的一緻性子產品進行通信以保證每一個伺服器上的記錄檔最終都以相同的順序包含相同的指令。一旦指令被正确複制，那麼每一個伺服器的狀态機都将按照記錄檔的順序來處理它們，然後将輸出結果傳回給用戶端。

複制狀态機之是以能夠工作是基于下面這樣的假設:如果一些狀态機具有相同的初始狀态，并且它們接收到的指令也相同，處理這些指令的順序也相同，那麼它們處理完這些指令後的狀态也應該相同。因為所有的複制節點都具有相同的狀态，它們都能獨立地從自己的本地日志中讀取資訊作為輸人指令，是以即使其中一些伺服器發生故障，也不會影響整個叢集的可用性。不論伺服器叢集包含多少個節點，從外部看起來都隻像是單個高可用的狀态機一樣。

複制狀态機在分布式系統中常被用于解決各種容錯相關的問題，例如，GFS、HDFS、Chubby、ZooKeeper和etcd等分布式系統都是基于複制狀态機模型實作的。

FLP不可能性

No completely asynchronous consensus protocol can tolerate even a single unannounced process death.

在異步通信場景下，任何一緻性協定都不能保證：隻有一個程序失敗，其他非失敗程序能達成一緻。這裡的“unannounced process death” 指的是一個程序發生了故障，但其他節點并不知道，繼續認為這個程序還沒有處理完成或發生消息延遲了。

舉個例子來說，甲、乙、丙三個人各自分開進行投票(投票結果是0或1)。他們彼此可以通過電話進行溝通，但有人會睡着。例如:甲投票0，乙投票 1，這時候甲和乙打平，丙的選票就很關鍵。然而丙睡着了，在他醒來之前甲和乙都将無法達成最終的結果。即使重新投票，也有可能陷入無盡的循環之中。

根據FLP定理，實際的一緻性協定(Paxos、 Raft等)在理論上都是有缺陷的，最大的問題是理論上存在不可終止性!至于 Paxos 和 Raft協定在工程的實作上都做了哪些調整(例如，Paxos 和 Raft都通過随機的方式顯著降低了發生算法無法終止的機率)，進而規避了理論上存在的問題，下文将會有詳細的解釋。

一緻性算法

前文已經提到了，分布式系統都可以通過複制狀态機模型來實作，而複制狀态機模型又需要一緻性協定來保證各個節點的日志寫入順序，是以接下來我們着重介紹一下各種一緻性協定。

2PC

2PC是 Two-Phase Commit的縮寫,即二階段送出,是計算機網絡尤其是在資料庫領域内,為了使基于分布式系統架構下的所有節點在進行事務處理過程中能夠保持原子性和一緻性而設計的一種算法。通常,二階段送出協定也被認為是一種一緻性協定,用來保證分布式系統資料的一緻性。目前,絕大部分的關系型資料庫都是采用二階段送出協定來完成分布式事務處理的,利用該協定能夠非常友善地完成所有分布式事務參與者的協調,統一決定事務的送出或復原,進而能夠有效地保證分布式資料一緻性,是以二階段送出協定被廣泛地應用在許多分布式系統中。

階段1: 送出事務請求

事務詢問：協調者向所有的參與者發送事務内容,詢問是否可以執行事務送出操作,并開始等待各參與者的響應。
執行事務：各參與者節點執行事務操作,并将Undo和Redo資訊記入事務日志中。
各參與者向協調者回報事務詢問的響應：如果參與者成功執行了事務操作,那麼就回報給協調者Yes響應,表示事務可以執行。如果參與者沒有成功執行事務,那麼就回報給協調者No響應,表示事務不可以執行。

階段2：執行事務送出

在這個階段，協調者會根據參與者回報來決定是否進行事務的送出。假如協調者從所有的參與者獲得的回報都是Yes響應,那麼就會執行事務送出。

假如任何一個參與者向協調者回報了No響應,或者在等待逾時之後,協調者尚無法接收到所有參與者的回報響應,那麼就會中斷事務。

2PC的就是将處理過程分為2個階段，第一個階段是投票，如果大家都覺得沒問題，那麼就接着往下進行，否則取消。2PC的關鍵是階段1的Undo和Redo寫入日志，如果之後的Commit過程失敗了，可以根據事務log找到未完成的事務，然後找協調者确認該事務的最終提案，如果最終提案是Commit那麼就執行Redo日志做完之前沒做完的工作，如果最終提案是Rollback那麼就需要執行Undo日志，撤銷之前寫入的内容，當處理完所有的事務日志之後，再對外提供服務，這樣整個系統就達到了最終一緻性。

但是，如果在協調者剛準備Commit時，發送了一個Commit請求給其中一個節點，這時候協調者和收到Commit的節點都挂了，其他節點就無法知道應當怎麼做了,這時候他們會一直阻塞直到協調者恢複。而即便選取出新的協調者之後，這個新協調者也無法作出判斷，因為可能存在潛在的節點已經Commit了相關内容，是以它要等所有節點都恢複之後，才能得出Commit或者Rollback的結論，而這整個過程中所有用戶端都将阻塞。

3PC

3PC是 3-Phase Commit的縮寫，它将原來的Commit拆分成了PreCommit和Commit兩個階段。

階段1:CanCommit

事務詢問：協調者向所有的參與者發送一個包含事務内容的canCommit 請求,詢問是否可以執行事務送出操作,并開始等待各參與者的響應。
各參與者向協調者回報事務詢問的響應：參與者在接收到來自協調者的 canCommit請求後,正常情況下,如果其自身認為可以順利執行事務,那麼會回報Yes響應,并進入預備狀态,否則回報No響應。

階段2: PreCommit

在這個階段，協調者會根據參與者回報來決定是否進行事務的預送出。假如協調者從所有的參與者獲得的回報都是Yes響應,那麼就會執行預送出。

事務預送出：參與者接收到preCommit請求後,會執行事務操作,并将Undo 和 Redo 資訊記錄到事務日志中。
各參與者向協調者回報事務執行的響應。如果參與者成功執行了事務操作,那麼就會回報給協調者 Ack 響應,同時等待最終的指令:送出 (commit)或中止 (abort)。

發送中斷請求：協調者向所有參與者節點發出abort請求。
中斷事務：無論是收到來自協調者的abort請求,或者是在等待協調者請求過程中出現逾時,參與者都會中斷事務。

階段3：DoCommit

如果二階段的參與者都傳回了ACK，那麼協調者就會給所有參與者發送DoCommit請求。

事務送出：參與者接收到doCommit請求後,會正式執行事務送出操作,并在完成送出之後釋放在整個事務執行期間占用的事務資源。
回報事務送出結果：參與者在完成事務送出之後,向協調者發送 Ack消息。
完成事務：協調者接收到所有參與者回報的 Ack消息後,完成事務。

如果二階段任意參與者傳回了No或者等待逾時之後，那麼就會執行中斷事務。

發送中斷請求：協調者向所有的參與者節點發送abort 請求。
事務復原:參與者接收到abort請求後,會利用其在階段二中記錄的Undo資訊來執行事務復原操作,并在完成復原之後釋放在整個事務執行期間占用的資源。
回報事務復原結果:參與者在完成事務復原之後,向協調者發送Ack消息。
中斷事務: 協調者接收到所有參與者回報的 Ack消息後,中斷事務。

看過很多人的文章，他們認為引出3PC能解決前面提到的的2PC的一緻性問題，但我卻看不出它是怎麼解決的。如果協調者在PreCommit階段有一個節點回報了No，這時候協調者作出Abort的決定，并将Abort請求發送給其中一個節點A，A做完復原操作後和協調者一起挂了，這時候新選出的協調者也沒法明确之前的協調者最終作出了什麼決定。新協調者隻能根據目前參與者的PreCommit回報，如果大家都傳回ACK，那麼協調者大膽假設之前的協調者也做出了Commit的決定，通過這樣的方式3PC确實減少了2PC中的阻塞問題。3PC相對于2PC有了一個PreCommit狀态作為參考，進而增大了猜對的可能性，因為正常來說，如果進入了PreCommit階段那麼所有節點都對CanCommit的決議作出了ACK的回應，那麼它們對PreCommit作出ACK的回應的幾率也會很大。

既然我們已經知道了3PC方案的一緻性問題，那麼接下來就讓我們看一看去中心化的一緻性算法是如何來做的吧。

Paxos

拜占庭帝國有許多支軍隊,不同軍隊的将軍之間必須制訂一個統一的行動計劃,進而做出進攻或者撤退的決定,同時,各個将軍在地理上都是被分隔開來的,隻能依靠軍隊的通訊員來進行通訊。然而,在所有的通訊員中可能會存在叛徒,這些叛徒可以任意篡改消息,進而達到欺騙将軍的目的。

這就是著名的“拜占廷将軍問題”。從理論上來說,在分布式計算領域,試圖在異步系統和不可靠的通道上來達到一緻性狀态是不可能的,是以在對一緻性的研究過程中,都往往假設信道是可靠的,即消息不會被篡改，對于這類問題隻需一套簡單的校驗算法即可避免。是以,在實際工程實踐中,可以假設不存在拜占庭問題（或者說拜占庭錯誤）,也即假設所有消息都是完整的,沒有被篡改的。那麼,在這種情況下需要什麼樣的算法來保證一緻性呢?

在古希臘有一個叫做Paxos的小島,島上采用議會的形式來通過法令,議會中的議員通過信使進行消息的傳遞。值得注意的是,議員和信使都是兼職的,他們随時有可能會離開議會廳,并且信使可能會重複的傳遞消息,也可能一去不複返。是以,議會協定要保證在這種情況下法令仍然能夠正确的産生,并且不會出現沖突。

這就是論文The Part-Time Parliament中提到的兼職議會,而Paxos算法名稱的由來也是取自論文中提到的 Paxos 小島。

問題描述

假設有一組可以提出提案的程序集合,那麼對于一個一緻性算法來說需要保證以下幾點:

在這些被提出的提案中,隻有一個會被標明。
如果沒有提案被提出,那麼就不會有被標明的提案。
當一個提案被標明後,程序應該可以擷取被標明的提案資訊。

安全性需求如下:

隻有被提出的提案才能被標明 (Chosen) 。
隻能有一個值被標明。
如果某個程序認為某個提案被標明了,那麼這個提案必須是真的被標明的那個。

在一緻性算法中有三種角色，Proposer，Acceptor，Learner。在具體實作中，一個程序可能充當不止一種角色。由前面提到分布式系統面臨的問題，我們知道：

每個參與者以任意的速度執行,可能會因為出錯而停止,也可能會重新開機。同時,即使一個提案被標明後,所有的參與者也都有可能失敗或重新開機。
消息在傳輸過程中可能會出現不可預知的延遲,也可能會重複或丢失,但是消息不會被損壞,即消息内容不會被纂改(拜占庭式的問題)。

提案的標明

要標明一個唯一提案的最簡單方式莫過于隻允許一個 Acceptor存在,這樣的話,Proposer隻能發送提案給該 Acceptor, Acceptor會選擇它接收到的第一個提案作為被標明的提案。這種解決方式盡管實作起來非常簡單,但是卻很難讓人滿意,因為一旦這個Acceptor出現問題,那麼整個系統就無法工作了。

是以,應該尋找一種更好的解決方式,在存在多個 Acceptor的情況下,如何進行提案的選取:Proposer向一個Acceptor集合發送提案,集合中的每個 Acceptor都可能會準許(Accept)該提案,當有足夠多的Acceptor準許這個提案的時候,我們就可以認為該提案被通過。那麼怎麼來定義足夠多呢？我們假定足夠多的Acceptor是所有Acceptor集合的一個子集，并且讓這個子集大到可能包含Acceptor集合的大多數成員，這樣一來任意兩個包含大多數Acceptor的集合必然會有至少一個公共成員。另外我們規定每個Acceptor最多隻能準許一個提案，這樣，在一輪提議中，就隻會有一個提案被標明。

推導過程

如果我們規定拿到大多數Acceptor的投票後就算提案被選中，并且我們希望每輪隻有一個提案被選中，最簡單的一個約定就是：

P1：一個Acceptor必須準許它收到的第一個提案

但是隻有這一層保證會有一個問題，多個提案被不同的Acceptor準許，但是每個人提案都沒有獲得大多數的選票。

因為我們希望每輪的提案都能選出一個結果，而不是輪空，那麼我們就需要加入一些别的限制。首先，我們要放開

一個Acceptor隻能準許一個提案

的限制，然後我們引入一個全局唯一編号的機制，生成這個全局唯一編号的方法不是我們關注的重點。有了這個編号之後，我們的提案就變成【編号，Value】這樣的一對組合了。

根據上面的内容，現在我們的Acceptor可以允許多個提案了，但是我們必須要保證，所有被接受的提案最終會具有相同的Value。那麼我們就簡單地約定編号越小優先級越高，那麼在一輪選舉中，編号最小的提案如果被選中了，那麼其對應的Value，将成為最終選舉結果。該約定可以定義如下：

P2:如果編号為M0，Value值為V0,的提案(即[M0,V0])被標明了,那麼如果這一輪選舉中最終標明的提案編号Mn比M0更高的的話,那麼該提案Mn其Value值必須也是V0。

在P2的基礎上，我們知道一個提案如果要被標明，就必須被至少一個Acceptor準許，是以我們的P2可以轉化為如下形式：

P2a:如果編号為M0，Value值為V0,的提案(即[M0,V0])被標明了,那麼如果這一輪選舉中被Acceptor準許的提案編号Mn比M0更高的的話,那麼該提案Mn其Value值必須也是V0。

因為通信是異步的，一個提案可能會在某個Acceptor沒收到任何其他提案時就被選中，如下圖：

如圖所示,在 Acceptor1沒有收到任何提案的情況下,其他4個 Acceptor 已經準許了來自Proposer2的提案【M0,V0】,而此時,Proposer1産生了一個具有其他 Value 值的編号更高的提案【M1,V1】,并發送給了 Acceptor1。根據P1,就需要 Acceptor1準許該提案,但是這與P2a沖突,是以如果要同時滿足P1和P2a,需要對P2a進行如下強化:

P2b:如果一個提案[M0,V0],被標明後,那麼之後任何Proposer産生的編号更高的提案,其 Value 值都為V0。

我們假設編号為M0，value為V0的提案已經被標明了,這就意味着肯定存在一個由半數以上的 Acceptor組成的集合C,C中的每個Acceptor都準許了該提案。

因為任何包含半數以上 Acceptor的集合S都至少包含C中的一個成員,是以我們可以認為如果保證如下約定,那麼編号為Mn,的提案的 Value也為 V0。

P2c:對于任意的Mn和Vn,如果提案[Mn,Vn]被提出,那麼肯定存在一個由半數以上的Acceptor組成的集合S,滿足以下兩個條件中的任意一個。
- S中不存在任何準許過編号小于Mn的提案的 Acceptor。
- 選取S中所有Acceptor準許的編号小于M的提案,其中編号最大的那個提案其 Value值是V。

Proposer生成提案

Proposer選擇一個新的提案編号Mn,然後向某個Acceptor集合的成員發送請求,要求該集合中的 Acceptor 做出如下回應。

向Proposer承諾,保證不再準許任何編号小于Mn的提案。
如果 Acceptor已經準許過任何提案,那麼其就向Proposer回報目前該Acceptor已經準許的編号小于Mn,但為最大編号的那個提案的值。

我們将該請求稱為編号為Mn的提案的Prepare請求。如果Proposer收到了來自半數以上的 Acceptor的響應結果,那麼它就可以産生編号為Mn,Value值為Vn的提案,這裡的Vn是所有響應中編号最大的提案的 Value值。當然還存在另一種情況,就是半數以上的 Acceptor都沒有準許過任何提案,即響應中不包含任何的提案,那麼此時Vn值就可以由Proposer 任意決定。

換個通俗一點的說法，如果隻有一個Proposer發出提案【M0，V0】，那麼所有Acceptor都會接受它的提案，那麼最終被標明的提案就是【M0，V0】，但是如果有兩個并發的提案【M0，V0】，【M1，V1】，如果M0先被AcceptorA準許了，AcceptorA會記錄下V0，之後它收到了M1的提案，它會告訴M1提案的Proposer自己已經接受了【M0，V0】,最後M1的Proposer會将自己的提案改成【M1，V0】。因為任意兩個半數以上的Acceptor集合必然有至少一個公共Acceptor，是以在每一輪投票中，M1提案的Proposer必然會感覺到M0提案的存在。

從上圖中，我們就能看到【M1，V1】最終是如何變成【M1，V0】的。圖中P代表Prepare請求，A代表Accept請求，M0=3.1，M1=4.5，V0=X，V1=Y，首先M0的prepare請求先到達了s1，s2，s3，這時候已經達到了半數以上的人接受，是以它将X的值發送給了s1，s2，s3，這時候我們稱【M0，V0】已經被準許，而這時候M1提案被提出，M1想要通過必然會有和之前的提案M0有一個公共Acceptor，就是圖中的s3。因為s3已經準許了【M0=3.1，V0=X】，他就将V0=X的資訊發送給了M1的Proposer，該Proposer為了讓系統的一緻性得到保證，就将最初要提議的V1=Y改成了V1=X。最後的結果，就如大家看到的一樣，整個系統達到一緻的狀态，即X成為本輪提案的最終選中Value。

Acceptor準許提案

根據上面的内容,一個Acceptor可能會收到來自Proposer的兩種請求,分别是Prepare請求和Accept請求,對這兩類請求做出響應的條件分别如下：

Prepare請求:Acceptor可以在任何時候響應一個Prepare請求，但是如果接受了一個Mn的prepare請求，那麼它再也不會接受小于Mn的Prepare請求。
Accept請求:Acceptor可以在任何時候響應 Accept請求，但是隻有在尚未響應任意大于Mn的prepare請求的情況下，它才可以接受Mn的提案。

前面的例子已經介紹了【M0，V0】先被接受然後【M1，V1】最終變成【M1，V0】的過程。接下來會介紹一下因為【M1，V1】先被接受【M0，V0】被拒的過程。

和上圖一樣，P代表Prepare請求，A代表Accept請求，M0=3.1，M1=4.5，V0=X，V1=Y。這裡s3在收到M0的Accept請求之前先收到了M1的prepare請求，是以他最終會拒絕V0=3.1，而是接受了V1=Y，最終【M1=4.5，V1=Y】得到了大多數Acceptor的準許成為了最終提案。圖中雖然已經s1，s2接受了【M0=3.1，V0=X】的提案，但是該提案并沒有得到大多數Acceptor的認可，也就是說這輪選舉隻有【M1=4.5，V1=Y】一個提案勝出，最終s1，s2會在接收到M1的Accept請求後将Value改成V1=Y，整個系統達到最終一緻性。

Learner擷取提案

在一個提案被半數以上Acceptor準許以後，就需要将提案的内容分發給所有Learner，如果讓Acceptor和每個Learner進行通信，那麼通信次數就是兩者個數的乘積就很大，如果在Learner中選舉一位Master，Acceptor隻和Learner Master通訊，有可能存在單點問題，是以一般都是讓Acceptor和一部分Learner通訊，然後這些Learner再将消息傳播開來。

并發分析

看到這，我覺得大家可能還會有一些疑問，覺得如果超過兩個并發的提案是不是可能造成一緻性無法達成。下面我們以同一時刻的3個提案【M0，V0】，【M1，V1】，【M2，V2】作為例子，這裡我們不考慮prepare請求被拒絕的情況，因為如果prepare未達半數時不會發送Accept請求，是以該情況不會對一緻性産生影響。

上圖中，M0=3.1，M1=4.5，M2=5.1，V0，V1，V2分别為X，Y，Z，我們先假設M0=3.1的prepare請求先被多數節點接受，這時候M1=4.5的也被多數節點接受，因為它們存在公共Acceptor s3，是以M0與M1的沖突會根據M0=3.1的Accept請求與M1=4.5的prepare請求的到達順序決定，如果M0的Accept請求先于M1的prepare到達，那麼M1的值最終會改成V0=X，否則M1的值會依舊保持自己的值V1=Y。

然後讓我們再來看M2，他會和M0的支援者以及M1的支援者都有至少一個公共Acceptor，我們就拿圖中s2和s3為例。

如果M0的Accept請求A3.1X先于M2的Prepare請求P5.1到達S2，并且M1的Accept請求A4.5？先于M2的Prepare請求P5.1到達s3：M2的Proposer會取最大編号M1的值？(取決于A3.1是否先于P4.5到達s3)作為自己的Value。
如果M0的Accept請求A3.1X後于M2的Prepare請求P5.1到達S2，并且M1的Accept請求A4.5？先于M2的Prepare請求P5.1到達s3：M2的Proposer會取最大編号M1的值？(取決于A3.1是否先于P4.5到達s3)作為自己的Value。
如果M0的Accept請求A3.1X先于M2的Prepare請求P5.1到達S2，并且M1的Accept請求A4.5？後于M2的Prepare請求P5.1到達s3：M2的Proposer會取最大編号M0的值X作為自己的Value。
如果M0的Accept請求A3.1X後于M2的Prepare請求P5.1到達S2，并且M1的Accept請求A4.5？後于M2的Prepare請求P5.1到達s3：M2的Proposer會使用自己的原始Value=Z。

從上面的例子我們看出，即便存在大量的并發，也會通過

如果 Acceptor已經準許過任何提案,那麼其就向Proposer回報目前該Acceptor已經準許的編号小于Mn,但為最大編号的那個提案的值。

這條準則來化解，因為任意兩個多數派都會有一個公共Acceptor，他們就是通過這個關鍵的Acceptor來交換資訊，最終讓結果趨于一緻。

活鎖問題

看到這大家可能還有一個問題，如果有兩個并發提案，但是它們的Accept請求總是慢了一步，讓另一個提案的Prepare先到了，就會陷入不斷發送Prepare請求的循環中無法解脫，這就是前面提到的的FLP問題。下圖就是Paxos發生FLP問題時的例子：

從圖中我們可以看到P3.1的Accept請求慢于P3.5的prepare請求，導緻自己的提案被駁回，于是它又重新發起新的一輪提案P4.1，而P4.1又恰好先于P3.5的Accept請求，是以A3.5被駁回，又發起了P5.5提案。他們會無休止地循環下去，直到某一方的Accept請求先傳輸給多數Acceptor。

Multi-Paxos

原始的Paxos算法（Basic Paxos）隻能對一個值形成決議，決議的形成至少需要兩次網絡來回，在高并發情況下可能需要更多的網絡來回，極端情況下甚至可能形成活鎖。如果想連續确定多個值，Basic Paxos 就效率很低。是以Basic Paxos幾乎隻是用來做理論研究，并不直接應用在實際工程中。

實際應用中幾乎都需要連續确定多個值，而且希望能有更高的效率。Multi-Paxos正是為解決此問題而提出。Multi-Paxos基于Basic Paxos做了改進：

在所有Proposers中選舉一個Leader，由Leader唯一地送出Proposal給Acceptors進行表決。這樣沒有Proposer競争，解決了活鎖問題。在系統中僅有一個Leader進行Value送出的情況下，Prepare階段就可以跳過，進而将兩階段變為一階段，提高效率。

Multi-Paxos首先需要選舉Leader，Leader的确定也是一次決議的形成，是以可執行一次Basic Paxos來選舉出一個Leader。選出Leader之後隻能由Leader送出Proposal，在Leader當機之後服務臨時不可用，需要重新選舉Leader繼續服務。在系統中僅有一個Leader進行Proposal送出的情況下，Prepare階段可以跳過。

Multi-Paxos通過改變Prepare階段的作用範圍，進而使得Leader的連續送出隻需要執行一次Prepare階段，後續隻需要執行Accept階段，将兩階段變為一階段，提高了效率。

Multi-Paxos允許有多個自認為是Leader的節點并發送出Proposal而不影響其安全性，這樣的場景即退化為Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的變形。

Raft

Paxos算法向來以難以了解，難以實作而聞名。而接下來要說的Raft算法則以容易了解，容易實作作為設計目标來解決一緻性問題。盡可能地将問題分解成為若幹個可解決的、更容易了解的小問題，這是衆所周知的簡化問題的方法論。Raft算法把問題分解成了領袖選舉(leader election)、日志複制(log replication)、安全性(safety)和成員關系變化(membership changes)這幾個子問題。

領袖選舉:在一個領袖節點發生故障之後必須重新給出一個新的領袖節點。
日志複制:領袖節點從用戶端接收操作請求,然後将記錄檔複制到叢集中的其他伺服器上,并且強制要求其他伺服器的日志必須和自己的保持一緻。
安全性:Raft關鍵的安全特性是下文提到的狀态機安全原則(StateMachine Safety)。如果一個伺服器已經将給定索引位置的日志條目應用到狀态機中,則所有其他伺服器不會在該索引位置應用不同的條目。下文将會證明Raft是如何保證這條原則的。
成員關系變化:配置發生變化的時候,叢集能夠繼續工作。

Raft将系統中的角色分為上司者（Leader）、跟從者（Follower）和候選人（Candidate）：

Leader：接受用戶端請求，并向Follower同步請求日志，當日志同步到大多數節點上後告訴Follower送出日志。
Follower：接受并持久化Leader同步的日志，在Leader告之日志可以送出之後，送出日志。
Candidate：Leader選舉過程中的臨時角色。

Raft要求系統在任意時刻最多隻有一個Leader，正常工作期間隻有Leader和Followers。當請求發送給leader後，leader保證該請求修改的内容已經在大多數節點修改完成後，再回複請求方。

衆所周知，分布式環境下的“時間同步”是一個大難題，但是有時為了識别“過期資訊”，時間資訊又是必不可少的。于是，任期在Raft中起着邏輯時鐘的作用，同時也可用于在Raft節點中檢測過期資訊，比如過期的上司人。Raft算法将時間分為一個個的任期（term），每一個term的開始都是Leader選舉。在成功選舉Leader之後，Leader會在整個term内管理整個叢集。如果Leader選舉失敗，該term就會因為沒有Leader而結束。

每個Raft節點各自都在本地維護一個目前任期值，觸發這個數字變化(增加) 主要有兩個場景:開始選舉和與其他節點交換資訊。當節點之間進行通信時，會互相交換目前的任期号。如果一個節點(包括上司人)的目前任期号比其他節點的任期号小，則将自己本地的任期号自覺地更新為較大的任期号。如果一個候選人或者上司人意識到它的任期号過時了(比别人的小)，那麼它會立刻切換回群衆狀态;如果一個節點收到的請求所攜帶的任期号是過時的，那麼該節點就會拒絕響應本次請求。

選舉Leader

Raft叢集三類角色的有限狀态機如上圖所示，其中有一個“times out”(逾時)條件，這是觸發有限狀态自動機發生狀态遷移的一個重要條件。在 Raft的選舉中，有兩個概念非常重要:心跳和選舉定時器。每個Raft節點都有一個選舉定時器，所有的Raft節點最開始以Follower角色運作時都會啟動這個選舉定時器。

Leader在任期内必須定期向叢集内的其他節點廣播心跳包，昭告自己的存在。Follower每次收到心跳包後就會主動将自己的選舉定時器清零重置(reset)。是以如果Follower選舉定時器逾時，則意味着在Raft規定的一個選舉逾時時間周期内，Leader的心跳包并沒有發給 Follower (或者已經發送了但在網絡傳輸過程中發生了延遲或被丢棄了)，于是Follower就假定Leader已經不存在或者發生了故障，于是會發起一次新的選舉。

如果決定要參加選舉，會按照如下步驟操作：

将自己本地維護的目前任期号(current term id)加1。
将自己的狀态切換到候選人(Candidate)，并為自己投票。也就是說每個候選人的第一張選票來自于他自己。
向其所在叢集中的其他節點發送RequestVote RPC(RPC消息會攜帶“current term id”值)，要求它們投票給自己。

接下來我們看一下可能發生的情況：

收到大多數Follower的投票，赢得選舉。在一個任期内一個節點最多隻為一個候選人投票，它會投給最早來拉選票的人。如果某個候選人赢得了選舉，它就會開始發送心跳包。
拉票過程中收到其他Leader的心跳包。如果心跳包中的任期号比自己本地地大，就承認其合法性，并放棄選舉。如果不合法則拒絕該心跳包，并告訴他目前最新的任期号，這能讓該上司人意識到自己已經過時了。
多個候選人均未得到超過半數的選票，他們會重新發起下一輪選舉。但是這就會出現前面提到的FLP問題，為了避免這種問題，Raft采用了一種随機延時重試的方式。例如每個節點等待100-300ms後再開始下一輪拉票。通過這種方式，FLP問題發生的可能性會快速收斂并接近為0。

日志同步

Leader選出後，就開始接收用戶端的請求。Leader把請求作為日志條目（Log entries）加入到它的日志中，然後并行的向其他伺服器發起 AppendEntries RPC 複制日志條目。當這條日志被複制到大多數伺服器上，Leader将這條日志應用到它的狀态機并向用戶端傳回執行結果。

某些Followers可能沒有成功的複制日志，Leader會無限的重試 AppendEntries RPC直到所有的Followers最終存儲了所有的日志條目。

日志由有序編号（log index）的日志條目組成。每個日志條目包含它被建立時的任期号（term），和用于狀态機執行的指令。如果一個日志條目被複制到大多數伺服器上，就被認為可以送出（commit）了。

Raft日志同步保證如下兩點：

如果不同日志中的兩個條目有着相同的索引和任期号，則它們所存儲的指令是相同的。
如果不同日志中的兩個條目有着相同的索引和任期号，則它們之前的所有條目都是完全一樣的。

第一條特性源于Leader在一個term内在給定的一個log index最多建立一條日志條目，同時該條目在日志中的位置也從來不會改變。

第二條特性源于 AppendEntries 的一個簡單的一緻性檢查。當發送一個 AppendEntries RPC 時，Leader會把新日志條目緊接着之前的條目的log index和term都包含在裡面。如果Follower沒有在它的日志中找到log index和term都相同的日志，它就會拒絕新的日志條目。

一般情況下，Leader和Followers的日志保持一緻，是以 AppendEntries 一緻性檢查通常不會失敗。然而，Leader崩潰可能會導緻日志不一緻：舊的Leader可能沒有完全複制完日志中的所有條目。

上圖闡述了一些Followers可能和新的Leader日志不同的情況。一個Follower可能會丢失掉Leader上的一些條目，也有可能包含一些Leader沒有的條目，也有可能兩者都會發生。丢失的或者多出來的條目可能會持續多個任期。

Leader通過強制Followers複制它的日志來處理日志的不一緻，Followers上的不一緻的日志會被Leader的日志覆寫。

Leader為了使Followers的日志同自己的一緻，Leader需要找到Followers同它的日志一緻的地方，然後覆寫Followers在該位置之後的條目。

Leader會從後往前試，每次AppendEntries失敗後嘗試前一個日志條目，直到成功找到每個Follower的日志一緻位點，然後向後逐條覆寫Followers在該位置之後的條目。

安全性

Raft增加了如下兩條限制以保證安全性：

擁有最新的已送出的log entry的Follower才有資格成為Leader。RequestVote RPC中攜帶last term和log index，term和log index越大的才會成為Leader。
Leader隻能推進commit index來送出目前term的已經複制到大多數伺服器上的日志，舊term日志的送出要等到送出目前term的日志來間接送出（log index 小于 commit index的日志被間接送出）。

之是以要這樣，是因為可能會出現已送出的日志又被覆寫的情況：

在階段a，term為2，S1是Leader，且S1寫入日志（term, index）為(2, 2)，并且日志被同步寫入了S2。

在階段b，S1離線，觸發一次新的選主，此時S5被選為新的Leader，此時系統term為3，且寫入了日志（term, index）為（3， 2）。

S5尚未将日志推送到Followers就離線了，進而觸發了一次新的選主，而之前離線的S1經過重新上線後被選中變成Leader，此時系統term為4，此時S1會将自己的日志同步到Followers，按照上圖就是将日志（2， 2）同步到了S3，而此時由于該日志已經被同步到了多數節點（S1, S2, S3），是以，此時日志（2，2）可以被送出了。

在階段d，S1又下線了，觸發一次選主，而S5有可能被選為新的Leader（這是因為S5可以滿足作為主的一切條件：1. term = 5 > 4，2. 最新的日志為（3，2），比大多數節點（如S2/S3/S4的日志都新），然後S5會将自己的日志更新到Followers，于是S2、S3中已經被送出的日志（2，2）被截斷了。

增加上述限制後，即使日志（2，2）已經被大多數節點（S1、S2、S3）确認了，但是它不能被送出，因為它是來自之前term（2）的日志，直到S1在目前term（4）産生的日志（4， 4）被大多數Followers确認，S1方可送出日志（4，4）這條日志，當然，根據Raft定義，（4，4）之前的所有日志也會被送出。此時即使S1再下線，重新選主時S5不可能成為Leader，因為它沒有包含大多數節點已經擁有的日志（4，4）。

日志壓縮

在實際的系統中，不能讓日志無限增長，否則系統重新開機時需要花很長的時間進行回放，進而影響可用性。Raft采用對整個系統進行snapshot來解決，snapshot之前的日志都可以丢棄。

每個副本獨立的對自己的系統狀态進行snapshot，并且隻能對已經送出的日志記錄進行snapshot。

Snapshot中包含以下内容：

日志中繼資料。最後一條已送出的 log entry的 log index和term。這兩個值在snapshot之後的第一條log entry的AppendEntries RPC的完整性檢查的時候會被用上。
系統目前狀态。

當Leader要發給某個日志落後太多的Follower的log entry被丢棄，Leader會将snapshot發給Follower。或者當新加進一台機器時，也會發送snapshot給它。發送snapshot使用InstalledSnapshot RPC。

做snapshot既不要做的太頻繁，否則消耗磁盤帶寬，也不要做的太不頻繁，否則一旦節點重新開機需要回放大量日志，影響可用性。推薦當日志達到某個固定的大小做一次snapshot。

做一次snapshot可能耗時過長，會影響正常日志同步。可以通過使用copy-on-write技術避免snapshot過程影響正常日志同步。

成員變更

成員變更是在叢集運作過程中副本發生變化，如增加/減少副本數、節點替換等。

成員變更也是一個分布式一緻性問題，既所有伺服器對新成員達成一緻。但是成員變更又有其特殊性，因為在成員變更的一緻性達成的過程中，參與投票的程序會發生變化。

如果将成員變更當成一般的一緻性問題，直接向Leader發送成員變更請求，Leader複制成員變更日志，達成多數派之後送出，各伺服器送出成員變更日志後從舊成員配置（Cold）切換到新成員配置（Cnew）。

因為各個伺服器送出成員變更日志的時刻可能不同，造成各個伺服器從舊成員配置（Cold）切換到新成員配置（Cnew）的時刻不同。

成員變更不能影響服務的可用性，但是成員變更過程的某一時刻，可能出現在Cold和Cnew中同時存在兩個不相交的多數派，進而可能選出兩個Leader，形成不同的決議，破壞安全性。

為了解決這一問題，Raft提出了兩階段的成員變更方法。叢集先從舊成員配置Cold切換到一個過渡成員配置，稱為共同一緻（joint consensus），共同一緻是舊成員配置Cold和新成員配置Cnew的組合Cold U Cnew，一旦共同一緻Cold U Cnew被送出，系統再切換到新成員配置Cnew。

Raft兩階段成員變更過程如下：

Leader收到成員變更請求從Cold切成Cnew。
Leader在本地生成一個新的log entry，其内容是Cold∪Cnew，代表目前時刻新舊成員配置共存，寫入本地日志，同時将該log entry複制至Cold∪Cnew中的所有副本。在此之後新的日志同步需要保證得到Cold和Cnew兩個多數派的确認。
Follower收到Cold∪Cnew的log entry後更新本地日志，并且此時就以該配置作為自己的成員配置。
如果Cold和Cnew中的兩個多數派确認了Cold U Cnew這條日志，Leader就送出這條log entry。
接下來Leader生成一條新的log entry，其内容是新成員配置Cnew，同樣将該log entry寫入本地日志，同時複制到Follower上。
Follower收到新成員配置Cnew後，将其寫入日志，并且從此刻起，就以該配置作為自己的成員配置，并且如果發現自己不在Cnew這個成員配置中會自動退出。
Leader收到Cnew的多數派确認後，表示成員變更成功，後續的日志隻要得到Cnew多數派确認即可。Leader給用戶端回複成員變更執行成功。

異常分析：

如果Leader的Cold U Cnew尚未推送到Follower，Leader就挂了，此後選出的新Leader并不包含這條日志，此時新Leader依然使用Cold作為自己的成員配置。
如果Leader的Cold U Cnew推送到大部分的Follower後就挂了，此後選出的新Leader可能是Cold也可能是Cnew中的某個Follower。
如果Leader在推送Cnew配置的過程中挂了，那麼同樣，新選出來的Leader可能是Cold也可能是Cnew中的某一個，此後用戶端繼續執行一次改變配置的指令即可。
如果大多數的Follower确認了Cnew這個消息後，那麼接下來即使Leader挂了，新選出來的Leader肯定位于Cnew中。

兩階段成員變更比較通用且容易了解，但是實作比較複雜，同時兩階段的變更協定也會在一定程度上影響變更過程中的服務可用性，是以我們期望增強成員變更的限制，以簡化操作流程。

兩階段成員變更，之是以分為兩個階段，是因為對Cold與Cnew的關系沒有做任何假設，為了避免Cold和Cnew各自形成不相交的多數派選出兩個Leader，才引入了兩階段方案。

如果增強成員變更的限制，假設Cold與Cnew任意的多數派交集不為空，這兩個成員配置就無法各自形成多數派，那麼成員變更方案就可能簡化為一階段。

那麼如何限制Cold與Cnew，使之任意的多數派交集不為空呢？方法就是每次成員變更隻允許增加或删除一個成員。

可從數學上嚴格證明，隻要每次隻允許增加或删除一個成員，Cold與Cnew不可能形成兩個不相交的多數派。

一階段成員變更：

成員變更限制每次隻能增加或删除一個成員（如果要變更多個成員，連續變更多次）。
成員變更由Leader發起，Cnew得到多數派确認後，傳回用戶端成員變更成功。
一次成員變更成功前不允許開始下一次成員變更，是以新任Leader在開始提供服務前要将自己本地儲存的最新成員配置重新投票形成多數派确認。
Leader隻要開始同步新成員配置，即可開始使用新的成員配置進行日志同步。

可用性與時序

上司人選取是Raft算法中對時序要求最多的地方。隻有當系統環境滿足以下時序要求時，Raft算法才能選舉并且保持一個穩定的上司人存在:

broadcastTime << electionTimeout << MTBF

在以上不等式中，broadcastTime指的是一個節點向叢集中其他節點發送RPC，并且收到它們響應的平均時間，electionTimeout就是在上文中多次出現的選舉逾時時間，MTBF指的是單個節點發生故障的平均時間間隔。為了使上司人能夠持續發送心跳包來阻止下面的Follower發起選舉，broadcastTime應該比electionTimeout小一個數量級。根據已經給出的随機化選舉逾時時間方法，這個不等式也顯著降低了候選人平分選票的機率。為了使得系統穩定運作，electionTimeout也應該比MTBF小幾個數量級。當上司人出現故障且在新的上司人選舉出來之前，系統對外将會不可用，這個時長大約為electionTimeout。

文章說明

更多有價值的文章均收錄于

貝貝貓的文章目錄

創作聲明：本文基于下列所有參考内容進行創作，其中可能涉及複制、修改或者轉換，圖檔均來自網絡，如有侵權請聯系我，我會第一時間進行删除。

參考内容

[1]《雲原生分布式存儲基石 etcd深入解析》

[2]《從Paxos到ZooKeeper 分布式一緻性原理與實踐》

[3]

漫話分布式系統共識協定: 2PC/3PC篇

[4]

Paxos算法詳解

[5]

Raft算法詳解