分布式協(xié)商：建立穩(wěn)固分布式大數(shù)據(jù)系統(tǒng)的基石

陳康，黃劍，劉建楠

1. 清華信息科學(xué)與技術(shù)國家實驗室（籌），清華大學(xué)計算機(jī)科學(xué)與技術(shù)系，北京 100084；2. 深圳清華大學(xué)研究院，廣東 深圳 518057；3. 浙江清華長三角研究院鄞州創(chuàng)新中心，浙江 寧波 315000；4. 中國石油天然氣股份有限公司慶陽石化分公司，甘肅 慶陽 745002

分布式協(xié)商：建立穩(wěn)固分布式大數(shù)據(jù)系統(tǒng)的基石

陳康1,2,3，黃劍1，劉建楠4

1. 清華信息科學(xué)與技術(shù)國家實驗室（籌），清華大學(xué)計算機(jī)科學(xué)與技術(shù)系，北京 100084；2. 深圳清華大學(xué)研究院，廣東 深圳 518057；3. 浙江清華長三角研究院鄞州創(chuàng)新中心，浙江 寧波 315000；4. 中國石油天然氣股份有限公司慶陽石化分公司，甘肅 慶陽 745002

分布式協(xié)商的目的是在分布式環(huán)境下在一組進(jìn)程之間決定一個共同的值，這是在分布式系統(tǒng)中最基本的問題。分布式協(xié)商問題的目標(biāo)非常簡單，但是在面對節(jié)點出錯、網(wǎng)絡(luò)出錯、網(wǎng)絡(luò)時延等環(huán)境的時候，協(xié)議設(shè)計以及處理起來十分困難。討論分布式協(xié)商問題的基本形式，在不同的系統(tǒng)假設(shè)下的基本結(jié)果以及分布式協(xié)商在構(gòu)建穩(wěn)固的分布式大數(shù)據(jù)系統(tǒng)中的作用。

分布式協(xié)商；副本狀態(tài)機(jī)；網(wǎng)絡(luò)錯誤；安全性；活躍性

1 引言

隨著云計算以及大數(shù)據(jù)的發(fā)展，為了系統(tǒng)的可靠性與性能，將應(yīng)用系統(tǒng)構(gòu)建在分布式環(huán)境中成為了一個不得不做出的選擇。并行處理系統(tǒng)為大數(shù)據(jù)處理提供大規(guī)模并行的處理能力，能夠處理更多的數(shù)據(jù)以及進(jìn)行更復(fù)雜的計算。另外一個方面，分布式環(huán)境也帶來了系統(tǒng)的可靠性，一個基本的想法是如果系統(tǒng)中有多個計算資源的話，某一小部分計算資源失效不應(yīng)影響系統(tǒng)的總體運行。這在單機(jī)系統(tǒng)中由于計算資源有限的關(guān)系不可能實現(xiàn)。在分布式環(huán)境下，實現(xiàn)可靠性最常用以及最基本的結(jié)構(gòu)是進(jìn)行副本復(fù)制。在分布式文件系統(tǒng)[1]中，可以通過使用副本的方式將一個邏輯的數(shù)據(jù)塊復(fù)制到多個其他物理節(jié)點中，這樣在某一個物理節(jié)點損壞不能工作時，分布式文件系統(tǒng)仍可以繼續(xù)工作。副本容錯的方式不僅僅可以進(jìn)行數(shù)據(jù)的容錯，也可以進(jìn)行計算的容錯?？梢詫⑿枰蒎e的計算分布到不同的物理節(jié)點中，這樣即使一部分節(jié)點失效了，仍然可以保證計算繼續(xù)進(jìn)行。

使用副本進(jìn)行容錯最基本的要求是副本之間需要保持一致。在系統(tǒng)的實現(xiàn)上，可以通過名為副本狀態(tài)機(jī)（replicated state machine，RSM）的方式進(jìn)行副本的復(fù)制，這是一種維持多個副本一致的機(jī)制。以數(shù)據(jù)的副本狀態(tài)機(jī)為例，基本的思想是，所有在數(shù)據(jù)上做的操作，在每一個副本上操作都一樣，并且順序也一樣。簡單地說，如果數(shù)據(jù)的初始值是一樣的，那么最終獲得的數(shù)據(jù)也是一樣的，這就是副本狀態(tài)機(jī)的基本思想。副本狀態(tài)機(jī)不僅可以應(yīng)用在數(shù)據(jù)上，還可以應(yīng)用在計算上。副本狀態(tài)機(jī)顧名思義是與狀態(tài)機(jī)相關(guān)的概念，在系統(tǒng)中計算或者數(shù)據(jù)會被表達(dá)為狀態(tài)機(jī)的形式。由于狀態(tài)機(jī)是整個計算機(jī)科學(xué)的理論基礎(chǔ)，因此使用狀態(tài)機(jī)的方式理論上就能夠完成所有的計算功能。

圖1 副本狀態(tài)機(jī)的基本結(jié)構(gòu)

圖1是副本狀態(tài)機(jī)的基本結(jié)構(gòu)。這里只畫出了兩個副本的狀態(tài)變化過程。實際中會使用5個或者更多的副本狀態(tài)機(jī)來達(dá)到極高的可靠性。上下兩個狀態(tài)機(jī)都是從一個狀態(tài)S0開始，即副本在多個服務(wù)器上的初始狀態(tài)是同樣的狀態(tài)。另外，還需要假設(shè)所有的狀態(tài)機(jī)都是確定性的狀態(tài)機(jī)。這里“確定性”的含義是給定一個狀態(tài)，如果給出相同的輸入的話，那么都會轉(zhuǎn)換到相同的唯一的一個狀態(tài)。這樣的話，每一次的狀態(tài)轉(zhuǎn)換都是確定性的，而不是不確定的。如果所有的狀態(tài)轉(zhuǎn)換的順序是一樣的，那么可以認(rèn)為最終的狀態(tài)也是一樣的。這一點是很顯然的，使用數(shù)學(xué)歸納法就可以證明。

副本狀態(tài)機(jī)是進(jìn)行容錯的基本結(jié)構(gòu)。例如，在通常提供的可靠性機(jī)制中總有一個選項被稱為雙機(jī)熱備份。雙機(jī)熱備份提供兩個完全一樣的運行副本，使得兩臺機(jī)器中的任意一臺出現(xiàn)了錯誤，另外一臺可以接管工作，完全掌控剩下的工作。雙機(jī)熱備份的基本思想在很多系統(tǒng)中都有體現(xiàn)。但是，雙機(jī)熱備份實際上并不能真正解決可靠性的問題。最基本的問題是如果雙機(jī)熱備份中的一個節(jié)點通過超時的機(jī)制判斷對方不在線的時候，并不能保證對方節(jié)點就一定不在線。因此，如果兩個節(jié)點都認(rèn)為對方不在線，那么就會造成兩個節(jié)點同時服務(wù)的情況，很容易打破副本狀態(tài)機(jī)的條件，執(zhí)行不同的操作，產(chǎn)生狀態(tài)的分叉，造成不一致。

那么，如何確保系統(tǒng)中有一致的節(jié)點各個狀態(tài)的視圖呢？在分布式系統(tǒng)中，通常的做法與投票決定一樣。對副本狀態(tài)機(jī)進(jìn)行狀態(tài)轉(zhuǎn)換的每一個操作都進(jìn)行投票，只有大多數(shù)都同意的操作才作為下一步的操作。如果有成員不知道當(dāng)前的投票情況，那么就停止操作，等待將來其知道的時候再把操作補(bǔ)上。這樣可以避免出現(xiàn)狀態(tài)分叉的情況，同時也可以讓當(dāng)系統(tǒng)中的一小部分成員出現(xiàn)錯誤的時候，分布式系統(tǒng)的工作可以繼續(xù)。由于在兩個成員組成的系統(tǒng)中，大多數(shù)成員的情況就完全包含了這兩個成員，因此原則上由兩個成員組成的系統(tǒng)只有兩個成員都正常工作時，才能夠保證上層系統(tǒng)繼續(xù)工作，也就是說失去了容錯的能力。因此，一個分布式容錯系統(tǒng)起碼要包含3個成員（“大多數(shù)”為任意兩個成員），這樣即使有小部分成員出現(xiàn)了失敗，大部分成員可以繼續(xù)通過協(xié)商達(dá)成一致的結(jié)果，推動副本狀態(tài)機(jī)繼續(xù)執(zhí)行。

在這樣進(jìn)行容錯的系統(tǒng)中，分布式協(xié)商（distributed consensus）是一個基本的組成部分，用來讓一個副本狀態(tài)機(jī)決定下一步需要做什么樣的操作。抽象來說，分布式協(xié)商的目的是在一組分布式進(jìn)程之間協(xié)商決定一個值，至于這個值的類型是什么反而不是很重要。分布式協(xié)商需要在組成系統(tǒng)的大數(shù)據(jù)進(jìn)程都能夠正常工作的時候協(xié)商出一個值，這樣也就有了一定的容錯能力。

本文將探討各種不同的分布式協(xié)商協(xié)議、分布式協(xié)商在副本狀態(tài)機(jī)中的應(yīng)用以及在實際系統(tǒng)中如何使用分布式協(xié)商系統(tǒng)來保證系統(tǒng)的可靠性。本文的目的是揭開分布式協(xié)商的神秘面紗，幫助開發(fā)者在理解分布式協(xié)商的基礎(chǔ)上完成可靠的分布式系統(tǒng)的構(gòu)建。對于希望進(jìn)一步深入了解分布式協(xié)商的研究人員來說，本文也將提供足夠的信息來幫助進(jìn)一步的研究。

2 副本狀態(tài)機(jī)與系統(tǒng)可靠性

在進(jìn)入分布式協(xié)商討論之前，還需要看一下副本狀態(tài)機(jī)的結(jié)構(gòu)以及在副本狀態(tài)機(jī)上完成系統(tǒng)容錯特性需要完成的工作。分布式協(xié)商是副本狀態(tài)機(jī)機(jī)制重要的一環(huán)，但是不是唯一的一環(huán)。了解了副本狀態(tài)機(jī)的總體結(jié)構(gòu)之后，就知道分布式協(xié)商在副本狀態(tài)機(jī)中所處的位置，進(jìn)而可以理解其在副本狀態(tài)機(jī)中的作用。副本狀態(tài)機(jī)的結(jié)構(gòu)如圖1所示。為了保證副本狀態(tài)機(jī)的正確執(zhí)行，仍然需要一些條件，下面就對這些條件展開討論。

在副本狀態(tài)機(jī)的條件中，初始狀態(tài)相同非常容易保證，這個與具體應(yīng)用相關(guān)。例如，在進(jìn)行文件系統(tǒng)副本備份的時候，初始狀態(tài)為一個空的磁盤，之后開始文件系統(tǒng)的操作；或者在進(jìn)行數(shù)據(jù)庫備份的時候，初始狀態(tài)為空的數(shù)據(jù)庫；甚至是總體的計算機(jī)進(jìn)行熱備份的時候，可以讓節(jié)點處于同樣的狀態(tài)。這在使用物理節(jié)點進(jìn)行備份的時候不太容易做到，而軟件構(gòu)建的虛擬機(jī)很容易做到這一點。本節(jié)討論的內(nèi)容也是基于虛擬機(jī)的方式完成計算的容錯。

在副本狀態(tài)機(jī)中的另外一個條件是保證所有的操作是確定性的，不會出現(xiàn)隨機(jī)的情況，這比保證初始狀態(tài)一致稍微困難一些，但是使用記錄/重放的方式可以達(dá)到目的。對于大多數(shù)的存儲應(yīng)用，例如文件系統(tǒng)、數(shù)據(jù)庫等，最終的操作會轉(zhuǎn)化為底層磁盤的讀寫操作，即讀出一個數(shù)據(jù)塊或者寫入一個數(shù)據(jù)塊，操作也都是確定性的。對于計算容錯來說，最基本的單元是一條指令，指令的執(zhí)行與具體的節(jié)點相關(guān)，例如讀入當(dāng)前時鐘周期數(shù)的指令（x86下是rdtsc，用于讀取當(dāng)前處理器的時鐘周期數(shù)），很難保證在非常精確的時刻讀入兩臺物理機(jī)器相同的時鐘周期數(shù)。在這個時候需要使用記錄/重放技術(shù)，在一臺物理機(jī)中讀出真正的數(shù)據(jù)，在另外一臺物理機(jī)中只是模擬執(zhí)行一下，不去真正執(zhí)行底層的指令。一個更為簡單直接的例子是獲取隨機(jī)數(shù)，只能是記錄一個隨機(jī)數(shù)，然后直接傳送給另外一個狀態(tài)機(jī)獲得相同的隨機(jī)數(shù)。

最后一個條件就是操作的定序問題。這在文件系統(tǒng)和數(shù)據(jù)庫中最終會表現(xiàn)為所有的磁盤讀寫操作的順序。在計算容錯方面，最終表現(xiàn)為所有指令的執(zhí)行順序。還有一個問題與定序相關(guān)，即對于外界請求的定序。對于外部請求進(jìn)行不同的定序，非常有可能導(dǎo)致最終內(nèi)部的執(zhí)行流程是不相同的。多個節(jié)點進(jìn)行定序很困難，因為缺乏全局的時鐘（這里所有的操作都要賦予一個自然數(shù)的序號）。為解決這個問題，最簡單也是最通用的做法是選取副本狀態(tài)機(jī)中的一個狀態(tài)機(jī)所在的節(jié)點作為負(fù)責(zé)定序的節(jié)點。所有的請求先在這個節(jié)點定出順序，之后其他的服務(wù)器按照相同的順序操作這些請求。當(dāng)然，定序節(jié)點不應(yīng)該是固定的，否則如果出現(xiàn)錯誤的話會導(dǎo)致不能繼續(xù)定序工作，如何可靠地選擇定序服務(wù)器也是一個非常困難的問題。

因為是在分布式環(huán)境下構(gòu)建副本狀態(tài)機(jī)，還有一個需要解決的問題是系統(tǒng)成員的變化，被稱為配置更新（view change）。這與副本狀態(tài)機(jī)本身沒有關(guān)系，而是分布式系統(tǒng)特有的問題。一般來說，針對特定的分布式算法需要限定參與的成員。這里不是說成員必須是固定的，而是將情況進(jìn)行簡化，首先考慮成員不變化的情況如何設(shè)計分布式算法來達(dá)到目的；之后再加上成員變化的情況。成員變化的情況包括增加成員以及減少成員。無論在哪種情況下，原有的分布式算法需要達(dá)到的目標(biāo)在加入或者減少成員之后都應(yīng)該保持不變。例如，在副本狀態(tài)機(jī)的情況下，原有的狀態(tài)機(jī)都決定在一個文件中寫入數(shù)據(jù)A，那么加入一個新的成員的時候，也需要保持這樣一個動作。這種成員變化的情況被稱為配置的更新，即配置包括了成員的組成，配置更新代表了成員組成的變化。另外還有一種情況也屬于配置更新，即參與成員的角色變化。關(guān)于角色的問題實際上是與具體的分布式算法相關(guān)的。前面在討論對于客戶端請求的排序上，由于一般通過排序節(jié)點完成排序工作，那么這個排序節(jié)點就是一個特殊的角色。排序節(jié)點的變化也就屬于配置更新的情況?？傊渲么砹藚⑴c分布式算法中的成員以及成員的角色，其中任意一項發(fā)生了變化，都稱之為分布式系統(tǒng)的配置更新。分布式算法不僅要在成員固定的時候正確執(zhí)行，也要在配置更新之前、配置更新進(jìn)行中以及配置更新完成后都能夠正確執(zhí)行。

綜上所述，為了使用副本狀態(tài)機(jī)的方法來構(gòu)造穩(wěn)固的分布式系統(tǒng)，需要滿足副本狀態(tài)機(jī)的基本條件以及需要對配置更新情況做出正確響應(yīng)。副本狀態(tài)機(jī)的基本條件包括初始狀態(tài)相同、所有的狀態(tài)轉(zhuǎn)換都是確定性的，并且每一步的轉(zhuǎn)換都是相同的。其中，確定每一步轉(zhuǎn)換需要進(jìn)行的處理動作是通過成員之間協(xié)商后確定下來的。這樣可以建立一個在大多數(shù)成員能夠正常工作的條件下推動副本狀態(tài)機(jī)執(zhí)行的可靠機(jī)制。

3 分布式協(xié)商

3.1 分布式協(xié)商的基本描述與理論結(jié)果

維持副本狀態(tài)機(jī)一致的最基本的問題就是讓一組狀態(tài)機(jī)（由一組服務(wù)器維護(hù)）共同決定某個步驟之后的下一個步驟應(yīng)該執(zhí)行哪一個操作。因此，核心問題是如何讓一組服務(wù)器就某一件事情（例如狀態(tài)機(jī)下一步需要做的狀態(tài)轉(zhuǎn)換）達(dá)成一致。這個問題被稱為分布式協(xié)商。一般意義下，可以說分布式協(xié)商是在一組服務(wù)器之間協(xié)商出一個值。這個值的含義是與具體的應(yīng)用相關(guān)的，本文不再贅述。對于任何應(yīng)用來說，分布式協(xié)商都有一些無意義的平凡協(xié)議。這些平凡協(xié)議在一組服務(wù)器之間決定一件事情或者決定一個值是直截了當(dāng)?shù)模恍枰械姆?wù)器都預(yù)先確定一個值即可。在任何時刻如果要進(jìn)行協(xié)商的話，只需要直接給出這個預(yù)定值即可。例如，不管協(xié)商的內(nèi)容是什么，所有的服務(wù)器都給出一個固定的值0，顯然這也是完成了分布式協(xié)商，但并沒有什么意義。因此，分布式協(xié)商必須要滿足有意義這個條件。

實際上，一個分布式協(xié)商需要滿足的條件大致有以下幾點。

· 最后的協(xié)商結(jié)果只能是一個，協(xié)商完成后不能被更改。這是顯然的，否則算法就不能被稱為分布式協(xié)商，這本來就是分布式協(xié)商的定義。

· 避免平凡解的條件，即最后決定的值必須是某一個人提出的某一個值（可以稱之為提議），不能設(shè)置一個默認(rèn)的值，否則這個算法就沒有實際的意義。

· 第三個條件比較隱晦，它涉及如果沒有人提出任何值，算法應(yīng)該怎么辦，此時算法不能憑空造出一個值來讓成員進(jìn)行確定；另外算法還沒有得出結(jié)論的時候，任何一個節(jié)點都不能獲知這個結(jié)論。

因為上述條件的任何一個條件在任何時刻都不能違反，因此這些條件往往被稱為安全性（safety）條件。整個算法需要滿足一個必須能夠結(jié)束的條件，即分布式協(xié)商最終應(yīng)當(dāng)?shù)贸鼋Y(jié)論，選擇一個值，而不是由于算法陷入無限循環(huán)中。

這個條件是最終必須要得出結(jié)果的條件。由于系統(tǒng)網(wǎng)絡(luò)可能出現(xiàn)數(shù)據(jù)到達(dá)時延、數(shù)據(jù)丟失等，任何一個算法都不可能在確定的一段時間內(nèi)完成協(xié)商工作，只能保證最終得出結(jié)論。這樣的條件也常常被稱為活躍性（liveness）條件。

分布式協(xié)商是否能夠達(dá)成與網(wǎng)絡(luò)條件有著密切的關(guān)系。有一個著名的結(jié)論發(fā)表于1985年，被稱為FLP不可能性定理。Fischer、Lynch、Patterson 3位科學(xué)家指出，在異步通信模式下，即使只有一個參與者發(fā)生了失敗，也沒有任何算法能夠保證完成分布式協(xié)商，此為結(jié)論1。

這雖然是一個令人沮喪的結(jié)論，但是實際系統(tǒng)并不是運行在這樣一個嚴(yán)酷的環(huán)境下。實際系統(tǒng)或多或少是一個同步的系統(tǒng)，例如集群環(huán)境下，大部分的數(shù)據(jù)分組都可以在給定的時間內(nèi)到達(dá)。即使是分布在互聯(lián)網(wǎng)上的節(jié)點，也可以合理假設(shè)為到一定超時時間之后，數(shù)據(jù)分組已經(jīng)丟失。這樣，可以對上述條件進(jìn)行加強(qiáng)，即在一個更加合理的半異步的模型下，一致性協(xié)商是可以達(dá)到的，并由明確的算法達(dá)到這個協(xié)商的目的。半異步模型保證了雖然網(wǎng)絡(luò)數(shù)據(jù)分組可以丟棄分組，可以有時延，但是在一段足夠長的時間內(nèi)，大部分節(jié)點之間的網(wǎng)絡(luò)是正常通信，并且在超時之前將數(shù)據(jù)分組分發(fā)給對應(yīng)的進(jìn)程。半異步模型是一個更加合理的模型，實際系統(tǒng)中如果需要系統(tǒng)工作，那么在構(gòu)建系統(tǒng)的時候還是需要底層網(wǎng)絡(luò)比較可靠的支持，起碼需要保證在大部分的時間內(nèi)大部分的網(wǎng)絡(luò)可以正常工作。在這種模型下，有一個著名的Paxos算法[2]能夠解決分布式協(xié)商的問題。Paxos算法指出，具有f個可能錯誤節(jié)點的半異步通信模式下，總數(shù)為2f+1個節(jié)點是可以達(dá)成分布式協(xié)商的，此為結(jié)論2?？梢钥吹?，這里的條件就是讓大部分的節(jié)點可以正常工作。

最后一個有意思的結(jié)論是如果將錯誤模型進(jìn)行更改，允許節(jié)點“故意”出錯，破壞分布式協(xié)商的過程，這樣的模型被稱為拜占庭通信模式[3]。在拜占庭通信模式下，具有f個可能錯誤的節(jié)點，總數(shù)為3f+1個節(jié)點是可以達(dá)成分布式協(xié)商的，此為結(jié)論3。

以上3個結(jié)論即為在實際系統(tǒng)中會使用到的結(jié)論，其中結(jié)論1和結(jié)論3主要具有理論意義，能夠指出滿足假設(shè)前提下進(jìn)行協(xié)商的極限。結(jié)論2是一個明確的算法，能夠直接用來構(gòu)架可靠的副本狀態(tài)機(jī)。

3.2 實際系統(tǒng)中的分布式協(xié)商協(xié)議

實際系統(tǒng)往往是前面所說的半異步的通信模型，因此分布式協(xié)商是可以在大多數(shù)成員之間達(dá)成的。當(dāng)前實際系統(tǒng)中使用的協(xié)議包括著名的由圖靈獎得主Lamport提出的Paxos協(xié)議、Yahoo研究院提出的ZooKeeper協(xié)議（ZooKeeper Atomic Broadcast協(xié)議，簡稱ZAB協(xié)議）[4]以及Stanford大學(xué)研究人員提出的專用于教學(xué)的Raft協(xié)議[5]。

上述3個協(xié)議的核心結(jié)構(gòu)都是相同的。

圖2 分布式協(xié)商中的核心協(xié)商結(jié)構(gòu)

圖2是分布式協(xié)商協(xié)議中核心的協(xié)商結(jié)構(gòu)，上述3個協(xié)商協(xié)議的核心部分都是基于這樣的一個結(jié)構(gòu)來完成的。在這個核心結(jié)構(gòu)中，客戶端（client）將請求發(fā)送給一個領(lǐng)導(dǎo)者（leader）。領(lǐng)導(dǎo)者是唯一的，用以對并發(fā)的客戶端請求進(jìn)行定序，保證輸入到副本狀態(tài)機(jī)中的操作是有序的。唯一的領(lǐng)導(dǎo)者也是上述3個協(xié)議的活躍性的保證，能夠保證最終協(xié)商完成。領(lǐng)導(dǎo)者將客戶端的請求發(fā)送給所有其他副本狀態(tài)機(jī)中的成員，這些成員被稱為追隨者（follower）。這些追隨者都復(fù)制領(lǐng)導(dǎo)者的操作，把發(fā)過來的操作加入本地的日志隊列中。如果大多數(shù)的追隨者都同意領(lǐng)導(dǎo)者發(fā)過來的一條操作（一個值），那么領(lǐng)導(dǎo)者將提交這個值，將其作為分布式協(xié)商的最后結(jié)論。

在這個核心結(jié)構(gòu)的外圍，需要一些輔助的模塊，包括兩個非常重要的功能，一個是領(lǐng)導(dǎo)者的選擇（leader election）；另外一個是如何進(jìn)行配置更新（成員增加或者減少）。這3個協(xié)議在不同的層面上完成了分布式協(xié)商，并推動上層的副本狀態(tài)機(jī)的執(zhí)行。Paxos協(xié)議是純粹的分布式協(xié)商協(xié)議；ZAB協(xié)議考慮了領(lǐng)導(dǎo)者的選擇算法，將其集成到協(xié)議中；Raft協(xié)議則更進(jìn)一步將配置更新的協(xié)議也加入到其中，完善了分布式協(xié)商的外圍工作。需要注意的是，雖然3個協(xié)議共享了類似的協(xié)商核心結(jié)構(gòu)，但是具體的協(xié)商過程各不相同。

Paxos協(xié)議最為簡單，是一個純粹的分布式協(xié)商協(xié)議。Paxos協(xié)議只考慮一次協(xié)商，不考慮多次協(xié)商，這雖然與副本狀態(tài)機(jī)的要求有差距，但是這還是一個非?；镜膯栴}，能夠用來協(xié)商副本狀態(tài)某一次具體的操作。Paxos協(xié)議基于投票的思想，一旦某個提議（包含某一個值）被大多數(shù)成員接受，那么這個提議的值就作為協(xié)商的結(jié)果。但是，由于分布式系統(tǒng)的特點，這樣一個協(xié)商完成的結(jié)果不見得被其他成員知道，投票過程可能會繼續(xù)。分布式協(xié)商需要保證的是：如果一個值已經(jīng)被協(xié)商完成，被“固定”在系統(tǒng)中，那么無論如何進(jìn)一步地投票，最終的投票結(jié)果就是已經(jīng)完成協(xié)商的值。核心思想就是在進(jìn)行值的提議的時候，必須要詢問足夠的但盡可能少的成員，將可能已經(jīng)完成協(xié)商的值作為值的提議。Paxos協(xié)議只解決一次協(xié)商問題，但是副本狀態(tài)機(jī)需要多次協(xié)商，那么就需要為每一次協(xié)商執(zhí)行一次Paxos算法。Paxos本身不完成定序的問題，多個Paxos協(xié)議可以并行執(zhí)行，通過標(biāo)記可以相互獨立運行。

ZAB協(xié)議沒有在單個的分布式協(xié)商基礎(chǔ)上進(jìn)行討論。由于使用了副本狀態(tài)機(jī)，ZAB協(xié)議考慮多個協(xié)商共同進(jìn)行的情況。ZAB協(xié)議包含了一個領(lǐng)導(dǎo)者選舉的算法。領(lǐng)導(dǎo)者選舉過程中，所有成員都互相交換信息，看看當(dāng)前自己的內(nèi)部狀態(tài)是不是能夠跟上最新的副本狀態(tài)機(jī)的狀態(tài)。包含最新信息的成員自動成為領(lǐng)導(dǎo)者。新領(lǐng)導(dǎo)者被選出之后，為了保證所有操作的有序性，新領(lǐng)導(dǎo)者需要將前面一個領(lǐng)導(dǎo)者（已經(jīng)失效）遺留的操作都提交一遍。這個過程就是錯誤恢復(fù)的過程，能夠保證所有操作的有序性。之后，整個協(xié)議將進(jìn)入上述分布式協(xié)商的基本結(jié)構(gòu)中，快速將操作同步到所有的跟隨節(jié)點。

Raft協(xié)議與ZAB協(xié)議非常相像，都是盡量讓新的領(lǐng)導(dǎo)者幫助完成上一個領(lǐng)導(dǎo)者尚未完成的工作。并且，Raft協(xié)議是一個更加完整的協(xié)議，因為其加入了配置更新的協(xié)議。Raft協(xié)議的第一個部分是關(guān)于領(lǐng)導(dǎo)者選舉的，在一個隨機(jī)的超時時間范圍內(nèi)進(jìn)行投票，獲得足夠多投票的成員自動成為領(lǐng)導(dǎo)者。之后，協(xié)議進(jìn)入上述的分布式協(xié)商的基本結(jié)構(gòu)中。領(lǐng)導(dǎo)者會復(fù)制自己的整個狀態(tài)給所有的跟隨者，并且在大部分的跟隨節(jié)點完成復(fù)制之后提交對應(yīng)的日志。這是將上述的分布式協(xié)商基本結(jié)構(gòu)與狀態(tài)恢復(fù)的過程結(jié)合在一起，在新的領(lǐng)導(dǎo)者完成提交的同時，“順便”將前一個領(lǐng)導(dǎo)者的協(xié)商值的提議一起提交。Raft協(xié)議的完整性體現(xiàn)在對于配置更新方面的支持。通過兩個階段轉(zhuǎn)換的方式，Raft協(xié)議可以正確完成配置更新，并不影響正常分布式協(xié)商的正確性。為了能夠維護(hù)整個系統(tǒng)的長期穩(wěn)定運行，配置更新協(xié)議也是必不可少的。

3個協(xié)議的最大的區(qū)別在于對領(lǐng)導(dǎo)者進(jìn)行轉(zhuǎn)換時處理，即從一個舊的領(lǐng)導(dǎo)者換成新的領(lǐng)導(dǎo)者時需要做什么樣的工作。在Paxos協(xié)議中，新的領(lǐng)導(dǎo)者將觀察自己保存的狀態(tài)，嚴(yán)格按照協(xié)議執(zhí)行，不破壞已經(jīng)決定的值。這個過程不涉及多個執(zhí)行中的Paxos協(xié)議，因此領(lǐng)導(dǎo)者在進(jìn)行轉(zhuǎn)換的時候，沒有其他信息幫助提交多個值，只能盡可能去保護(hù)現(xiàn)有的可能已經(jīng)選定的值。ZAB協(xié)議和Raft協(xié)議不是一個單純的一次性的分布式協(xié)商協(xié)議，這兩個協(xié)議是與副本狀態(tài)機(jī)緊密結(jié)合在一起的。在這兩個協(xié)議中，如果發(fā)生了領(lǐng)導(dǎo)者的轉(zhuǎn)換，那么就必須考慮如何處理上一個領(lǐng)導(dǎo)者遺留的尚未提交的協(xié)商值。因此，這兩個協(xié)議都對新的領(lǐng)導(dǎo)者的選擇作出了限制，即新的領(lǐng)導(dǎo)者必須知道一些必要的關(guān)于當(dāng)前系統(tǒng)狀態(tài)的信息。在ZAB協(xié)議中，新的領(lǐng)導(dǎo)者選舉出來之后，需要確定在獲得的支持成員中有最新的一個請求作為出發(fā)點，之后將自己的請求接到最新請求的后面，作為下一個請求。ZAB協(xié)議保證必須讓新的領(lǐng)導(dǎo)者幫助提交上一個領(lǐng)導(dǎo)者工作時產(chǎn)生的請求，只有全部提交完成之后，新的領(lǐng)導(dǎo)者才能工作，領(lǐng)導(dǎo)者才真正成為領(lǐng)導(dǎo)者。在Raft協(xié)議中，也對新的領(lǐng)導(dǎo)者選擇做出了限制，為了保證正確性，需要保證在選出新的領(lǐng)導(dǎo)者的時候，必須要從之前的已經(jīng)完成提交的最后一條請求對應(yīng)的成員節(jié)點中去選擇，而不是去任意選擇一個成員節(jié)點。這樣的限制使得在投票選出新的領(lǐng)導(dǎo)者時，每一個成員都需要看一下領(lǐng)導(dǎo)者的候選節(jié)點具有的信息是否比自己的信息要更新一點，如果是的話則同意候選節(jié)點，否則將拒絕候選節(jié)點。通過這種方式，新當(dāng)選的領(lǐng)導(dǎo)者不必進(jìn)行幫助前一個領(lǐng)導(dǎo)者提交提議的過程，而是可以直接進(jìn)入自己提議的過程，并且在這個基礎(chǔ)上“順便”幫助前一個領(lǐng)導(dǎo)者提交遺留在系統(tǒng)中的提議。這也是Raft協(xié)議和ZAB協(xié)議最大的不同。

上述的3個協(xié)議是當(dāng)前在實際系統(tǒng)中使用最為廣泛的分布式協(xié)商協(xié)議，3個協(xié)議各有特點，可以使用在不同的場景下。3個協(xié)議要完成的目標(biāo)是相同的，都是如何可靠地推動副本狀態(tài)機(jī)的執(zhí)行。3個協(xié)議提出的背景各不相同，ZAB協(xié)議和Raft協(xié)議改進(jìn)了Paxos協(xié)議中的難于理解的困難，特別是Raft協(xié)議一開始就是為了教學(xué)所提出的。Raft協(xié)議已經(jīng)非常完善地描述了副本狀態(tài)機(jī)需要解決的問題以及相關(guān)的解決方案，值得初學(xué)者首先選擇進(jìn)行閱讀理解。

4 分布式協(xié)商協(xié)議的應(yīng)用場景

第3節(jié)分析了分布式協(xié)商的含義以及在實際系統(tǒng)中的使用的分布式協(xié)商協(xié)議的情況。由于協(xié)議本身的復(fù)雜性，這部分內(nèi)容需要感興趣的讀者花費較長的時間進(jìn)行理解。但是，在實際系統(tǒng)中，遇到的問題更多的是如何使用分布式協(xié)商。分布式協(xié)商在實際的系統(tǒng)中具有廣泛的應(yīng)用，對建立可靠的分布式系統(tǒng)起到?jīng)Q定性的作用。下面就以分布式協(xié)商系統(tǒng)在BigTable[6]系統(tǒng)中的作用來闡述分布式協(xié)商系統(tǒng)如何應(yīng)用于大規(guī)模的大數(shù)據(jù)系統(tǒng)中來保證系統(tǒng)的可靠性。

將BigTable系統(tǒng)視作一個分布式數(shù)據(jù)庫，并且這個數(shù)據(jù)庫是經(jīng)過排序的，即按照數(shù)據(jù)記錄的主鍵進(jìn)行排序。圖3是BigTable系統(tǒng)進(jìn)行數(shù)據(jù)查找的流程。

從圖3可以看出，在分布式環(huán)境下，BigTable的數(shù)據(jù)表被組織成類似于分布式環(huán)境下的“B+樹”的形式。根的數(shù)據(jù)表和第一級的元數(shù)據(jù)表用來進(jìn)行路由工作，之后再依據(jù)獲得的用戶數(shù)據(jù)表的位置來真正讀寫用戶的數(shù)據(jù)表。由于表格中的數(shù)據(jù)太大了，在BigTable中使用了按照行進(jìn)行分割的方式，被稱為數(shù)據(jù)分表。任何一個客戶端，如果需要訪問BigTable中的數(shù)據(jù)分表，首先需要經(jīng)過元數(shù)據(jù)表的路由才可以訪問到具體的數(shù)據(jù)分表。整個路由表的根的指針放置在名為Chubby[7]的系統(tǒng)中，這是進(jìn)行路由啟動部分的數(shù)據(jù)。Chubby基于副本狀態(tài)機(jī)以及Paxos協(xié)議[8]建立了一個穩(wěn)固的分布式協(xié)同系統(tǒng)，為其上的應(yīng)用程序提供基礎(chǔ)服務(wù)。

在維護(hù)系統(tǒng)可靠性方面，兩個特別典型的問題需要解決，一個問題是如何得知整個系統(tǒng)中當(dāng)前能夠正常執(zhí)行的節(jié)點的數(shù)目；另外一個問題是如何協(xié)調(diào)正常執(zhí)行的節(jié)點之間的數(shù)據(jù)訪問。

（1）維護(hù)系統(tǒng)正常工作節(jié)點的狀態(tài)信息

關(guān)于節(jié)點是否正常工作的信息是進(jìn)行容錯的一個基礎(chǔ)性問題，只有得知系統(tǒng)中的哪些節(jié)點在正常工作，哪些節(jié)點已經(jīng)出現(xiàn)了錯誤，才可能進(jìn)行后續(xù)的修復(fù)工作。實際上在分布式系統(tǒng)中是非常有必要進(jìn)行這樣的狀態(tài)維護(hù)的，這樣不僅可以協(xié)調(diào)系統(tǒng)的容錯恢復(fù)功能，也可以給管理員提供建議信息，為自動以及手動維護(hù)提供依據(jù)。這件事情雖然看起來非常簡單，但是如果系統(tǒng)的規(guī)模達(dá)到了數(shù)千臺機(jī)器，那么進(jìn)行節(jié)點狀態(tài)維護(hù)就變得極為復(fù)雜，用人工的辦法根本沒有辦法實現(xiàn)。

圖3 BigTable系統(tǒng)中的數(shù)據(jù)查表的流程

維護(hù)節(jié)點正常工作一般的做法是通過節(jié)點之間的心跳。但是，節(jié)點之間的心跳會出現(xiàn)信息不準(zhǔn)確的問題，即雙方都不能探測到對方的存在，但是仍然不能確信對方確實下線，這有信息不一致的問題。這里一個最典型的情況就是引言中討論的雙機(jī)熱備份的問題。在雙機(jī)熱備份問題中，一臺機(jī)器為主要的副本，另外一臺機(jī)器是備份的副本。在這里，關(guān)鍵的問題是主要副本與備份副本之間的網(wǎng)絡(luò)情況會造成雙方都無法確信對方是否真的不在線。

使用分布式協(xié)商就不會出現(xiàn)上面的不一致的問題。分布式協(xié)商就像一個委員會，對于某一個節(jié)點是否在線的問題可以由委員會的大多數(shù)成員來決定。這樣就可以判斷雙機(jī)熱備份的情況下，哪一臺是主要副本，哪一臺是備份副本。類似地，在BigTable系統(tǒng)中，集群中的成員是否正常工作的信息都保存在一個名為Chubby的系統(tǒng)中。每一個Chubby實例包含了5個成員，這5個成員分布在不同的地理位置，這就保證了在絕大多數(shù)的情況下大多數(shù)成員可以正常工作。在這5個成員之間組成了文件系統(tǒng)的副本狀態(tài)機(jī)，每一個集群中的服務(wù)器的信息都保存在這個文件系統(tǒng)中的某一個文件中。服務(wù)器如果在線的話，會按固定的時間間隔更新對應(yīng)的描述自身文件的信息。其他的服務(wù)器包括Chubby中的成員可以檢測對應(yīng)文件的有效性，如果無效的話，可以認(rèn)為對應(yīng)的服務(wù)器已經(jīng)下線。當(dāng)然，即使Chubby中的信息指示的對應(yīng)的服務(wù)器已經(jīng)下線了，這并不代表著對應(yīng)服務(wù)器確實出現(xiàn)了錯誤。為了保證正確性，BigTable中某一個數(shù)據(jù)分表最多由一個服務(wù)器負(fù)責(zé)，否則就會出現(xiàn)數(shù)據(jù)的不一致。只有Chubby能夠通過一致性協(xié)商的方式確定某個服務(wù)器是否下線，即使此時對應(yīng)的服務(wù)器還在正常工作，由于其在一定的時間內(nèi)不能成功更新在Chubby中關(guān)于自身的信息，這臺服務(wù)器依據(jù)協(xié)議的規(guī)定，應(yīng)當(dāng)自動解除自己對數(shù)據(jù)分表的負(fù)責(zé)工作，等待整個系統(tǒng)安排重新上線。這樣，可以保證在任何一個時間點，對于任何一個數(shù)據(jù)分表來說，最多只有一臺服務(wù)器負(fù)責(zé)，避免數(shù)據(jù)出現(xiàn)不一致的情況。

（2）協(xié)調(diào)成員節(jié)點之間的數(shù)據(jù)訪問

另一個問題是協(xié)調(diào)正常執(zhí)行節(jié)點之間的數(shù)據(jù)訪問。在單機(jī)多線程環(huán)境中，有共享數(shù)據(jù)訪問的問題。共享數(shù)據(jù)訪問是內(nèi)存中設(shè)置了共享變量，有兩個以及兩個以上的線程訪問（讀/寫）這些共享變量，其中至少有一個訪問是寫入數(shù)據(jù)。這樣的情況會產(chǎn)生數(shù)據(jù)訪問沖突。

在多線程環(huán)境中，解決數(shù)據(jù)訪問沖突一般使用保護(hù)鎖的方法。任何一個線程在訪問共享數(shù)據(jù)之前，首先要獲得一個鎖，之后再訪問數(shù)據(jù)，最后釋放鎖?；コ怄i的語義使得任何一個時刻只有一個線程可以訪問共享的數(shù)據(jù)，其他的線程只能等待。同樣的機(jī)制可以擴(kuò)展到分布式環(huán)境中。在分布式環(huán)境中，一般建立鎖的機(jī)制是使用鎖服務(wù)器?；コ怄i在進(jìn)行訪問協(xié)調(diào)的時候起到了非常重要的作用，如果互斥鎖發(fā)生了失敗，會造成整個分布式系統(tǒng)無法工作。

在分布式環(huán)境中，需要建立非常穩(wěn)固的鎖機(jī)制，將可能產(chǎn)生的鎖失效的概率降到最低。副本狀態(tài)機(jī)此時起到非常重要的作用。在Chubby中，互斥鎖被建立到副本狀態(tài)機(jī)中，表現(xiàn)形式為文件系統(tǒng)命名空間中的在文件以及目錄這樣的有名對象上所實現(xiàn)的鎖。在分布式環(huán)境中需要對共享資源進(jìn)行訪問的時候，首先要訪問鎖服務(wù)器，只有在成功獲得鎖的情況下，才可能訪問對應(yīng)的共享資源。但是在分布式環(huán)境中的鎖服務(wù)機(jī)制與傳統(tǒng)的單機(jī)環(huán)境的鎖服務(wù)機(jī)制不同。在單機(jī)環(huán)境中，不需要考慮出錯的情況，因為一旦出錯，那就是整個節(jié)點的錯誤，不僅僅是鎖的問題。因此，單機(jī)中沒有獲得鎖的線程原則上只能進(jìn)行無限的等待。但是，在分布式環(huán)境中這樣做是不允許的，因為數(shù)據(jù)分組會在網(wǎng)絡(luò)中進(jìn)行時延，也可能進(jìn)行分組丟棄。訪問鎖的情況可能會被延遲，獲得鎖的服務(wù)器可能會失效。如果獲得互斥鎖的服務(wù)器發(fā)生了失敗，那么對應(yīng)的鎖將永遠(yuǎn)不能釋放，這就造成了很大的問題。因此，在分布式環(huán)境中，對于鎖的訪問必須要加上超時機(jī)制?；镜姆绞绞窃讷@得鎖之后，默認(rèn)情況下只能擁有這個互斥鎖一段時間，超過了這段時間鎖將自動被鎖服務(wù)器釋放，便于其他的服務(wù)器進(jìn)行下一步的工作。如果一個服務(wù)器獲得了鎖，并且希望將來繼續(xù)使用這個鎖，那么這個服務(wù)器必須要進(jìn)行續(xù)租的操作，延長獲得鎖的時間。

將上述的原理應(yīng)用在實際工作的系統(tǒng)中，還需要考慮網(wǎng)絡(luò)時延以及時間測量的誤差，確保在訪問共享資源時，最多只有一個節(jié)點進(jìn)行訪問，其他節(jié)點都被排除在外，這樣才算是正確的互斥鎖的語義。如果時延的數(shù)據(jù)分組沒有到達(dá)，或者沒有獲得響應(yīng)，對應(yīng)的服務(wù)器只能認(rèn)為延長請求失效，退出對于對應(yīng)共享資源的控制，避免對數(shù)據(jù)造成不一致的操作。這樣鎖的協(xié)議會比較復(fù)雜，也是分布式與單機(jī)環(huán)境的區(qū)別。BigTable中有許多對共享資源的訪問，其中就有對于底層的分布式文件系統(tǒng)的文件的訪問。另外，也有對于數(shù)據(jù)分表的再拆分以及數(shù)據(jù)分表的合并的過程，也有對于共享日志的分配以及恢復(fù)操作等。可以說，任何一個分布式系統(tǒng)，對于共享資源的訪問是無可避免的操作，因此分布式的互斥鎖的機(jī)制是無可避免的分布式的系統(tǒng)功能。建立一個穩(wěn)固的分布式鎖的環(huán)境是建立高可靠的分布式系統(tǒng)的關(guān)鍵組成部分。

通過BigTable的具體機(jī)制可以看到，通過分布式協(xié)商以及副本狀態(tài)機(jī)，Chubby建立了一個非常穩(wěn)固的、由副本狀態(tài)機(jī)推動的復(fù)制的文件系統(tǒng)。雖然文件系統(tǒng)的語義非?；A(chǔ)，不能夠提供高層的語義信息，但是Chubby提供了最基本的存儲模型。在這個模型的基礎(chǔ)之上，Chubby完成了整個系統(tǒng)的完整的活躍信息描述，協(xié)調(diào)了BigTable對于共享數(shù)據(jù)分表資源的訪問。實際上，Chubby成為了Google(谷歌)內(nèi)部的分布式大數(shù)據(jù)系統(tǒng)的基礎(chǔ)，為難于實現(xiàn)的可靠性問題提供了基石。在這個基礎(chǔ)之上，建立上層應(yīng)用系統(tǒng)的可靠性難度將大大降低。

5 結(jié)束語

本文對現(xiàn)有的保證可靠性的副本狀態(tài)機(jī)進(jìn)行了詳細(xì)的討論，包括副本狀態(tài)機(jī)需要滿足的條件、基本的執(zhí)行流程以及副本狀態(tài)機(jī)在實現(xiàn)可靠分布式系統(tǒng)中的作用。副本狀態(tài)機(jī)需要滿足的條件為初始狀態(tài)相同、狀態(tài)轉(zhuǎn)換函數(shù)必須是確定性的以及轉(zhuǎn)換操作與過程必須使用分布式協(xié)商算法。在此基礎(chǔ)上，詳細(xì)分析了現(xiàn)有的分布式協(xié)商算法的協(xié)議，包括Paxos協(xié)議、ZAB協(xié)議以及Raft協(xié)議。這些協(xié)議各有特點，并有不同的分布式系統(tǒng)的實現(xiàn)。Paxos協(xié)議是單次的分布式協(xié)商，雖然簡單，但是需要配合許多其他的組件才能夠真正構(gòu)成副本狀態(tài)機(jī)的工作機(jī)制。ZAB協(xié)議和Raft協(xié)議是完整的分布式副本狀態(tài)機(jī)的協(xié)議，能夠直接推動副本狀態(tài)機(jī)的執(zhí)行，其中Raft協(xié)議還繼續(xù)提供了配置更新的協(xié)議，完善了在實際系統(tǒng)中的各個細(xì)節(jié)。在分析完成常用的分布式協(xié)商協(xié)議的基礎(chǔ)之上，還分析了如何通過副本狀態(tài)機(jī)構(gòu)造可靠的分布式系統(tǒng)。需要提供的主要模塊是完成整個系統(tǒng)的節(jié)點狀態(tài)的監(jiān)測與維護(hù)以及協(xié)調(diào)正常工作節(jié)點之間的工作。可以看到，分布式協(xié)商技術(shù)能夠提供可靠性的基本模塊，是建立可靠性系統(tǒng)的基礎(chǔ)。通過本文的分析，讀者可以對分布式協(xié)商有一個基本概念，為建立可靠的分布式系統(tǒng)提供基礎(chǔ)的模型。

[1] GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google file system[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5): 29-43.

[2] LAMPORT L. Paxos made simple[J]. ACM SIGACT News, 2001, 32(4): 51-58.

[3] LAMPORT L, PEASE M, SHOSTAK R. The byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.

[4] HUNT P, KONAR M, JUNQUEIRA F P, et al. ZooKeeper: wait-free coordination for internet-scale systems [C]// The 2010 USENIX Annual Technical Conference, June 22-25, 2010, Boston, MA, USA. [S.l.:s.n.], 2010: 1-14.

[5] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm[C]// The 2014 USENIX Annual Technical Conference, June 19-20, 2014, Philadelphia, PA, USA. [S.l.:s.n.], 2014: 305-319.

[6] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: a distributed storage system for structured data[J]. ACM Transactions on Computer Systems, 2008, 26(2): 205-218.

[7] BURROWS M. The Chubby lock service for loosely-coupled distributed systems[C]// The 7th Symposium on Operating Systems Design and Implementation, November 6-8, 2006, Seattle, WA, USA. New York: ACM SIGOPS, 2006: 335-350.

[8] CHANDRA T D, GRIESEMER R,REDSTONE J. Paxos made live: an engineering perspective[C]//The 26th Annual ACM Symposium on Principles of Distributed Computing, August 12-15, 2007, Portland, Oregon, USA. New York: ACM Press, 2007: 398-407.

Distributed consensus: fundamental building block for distributed reliable big data system

CHEN Kang1,2,3, HUANG Jian1, LIU Jiannan4
1. Tsinghua National Laboratory for Information Science and Technology (TNLIST), Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China 2. Research Institute of Tsinghua University in Shenzhen, Shenzhen 518057, China 3. Technology Innovation Center at Yinzhou, Yangtze Delta Region Institute of Tsinghua University, Zhejiang, Ningbo 315000, China 4. Petro China Co. Ltd. Qingyang Petrochemical Company, Qingyang 745002, China

The goal of distributed consensus is quite simple i.e. how to decide a value among a group of coordinated processes in the distributed environment. However, the problem is turned out to be very difficult while facing the different distributed environment. The even harder problem is that some consensus protocols are hard to be implemented in practical systems. Some results of distributed consensus algorithms under different distributed environment assumptions were reviewed. In addition, some practical systems based on consensus for achieving high reliability were discussed.

distributed consensus, replicated state machine, network error, safety, liveness

TP338.8

A

10.11959/j.issn.2096-0271.2016039

陳康（1976-），男，博士，清華大學(xué)計算機(jī)科學(xué)與技術(shù)系、深圳清華大學(xué)研究院、浙江清華長三角研究院鄞州創(chuàng)新中心副教授，主要研究方向為分布式系統(tǒng)、存儲系統(tǒng)。

黃劍（1993-），男，清華大學(xué)計算機(jī)科學(xué)與技術(shù)系碩士生，主要研究方向為文件存儲器和分布式系統(tǒng)。

劉建楠（1963-），男，就職于中國石油天然氣股份有限公司慶陽石化分公司，主要從事企業(yè)經(jīng)營和信息化管理工作。

2015-06-20

國家自然科學(xué)基金資助項目（No.61433008, No.U1435216, No.61373145, No.61170210）；國家高技術(shù)研究發(fā)展計劃（“863”計劃）基金資助項目（No.2014AA01A302）

Foundation Items:The National Natural Science Foundation of China (No. 61433008, No. U1435216, No.61373145, No.61170210), The National High Technology Research and Development Program of China (863 Program) (No.2014AA01A302)