陳康，黃劍，劉建楠

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

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

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

1 引言

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

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

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

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

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

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

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

本文將探討各種不同的分布式協(xié)商協(xié)議、分布式協(xié)商在副本狀態(tài)機(jī)中的應(yīng)用以及在實(shí)際系統(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)容錯(cuò)特性需要完成的工作。分布式協(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)相同非常容易保證，這個(gè)與具體應(yīng)用相關(guān)。例如，在進(jìn)行文件系統(tǒng)副本備份的時(shí)候，初始狀態(tài)為一個(gè)空的磁盤，之后開始文件系統(tǒng)的操作；或者在進(jìn)行數(shù)據(jù)庫備份的時(shí)候，初始狀態(tài)為空的數(shù)據(jù)庫；甚至是總體的計(jì)算機(jī)進(jìn)行熱備份的時(shí)候，可以讓節(jié)點(diǎn)處于同樣的狀態(tài)。這在使用物理節(jié)點(diǎn)進(jìn)行備份的時(shí)候不太容易做到，而軟件構(gòu)建的虛擬機(jī)很容易做到這一點(diǎn)。本節(jié)討論的內(nèi)容也是基于虛擬機(jī)的方式完成計(jì)算的容錯(cuò)。

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

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

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

3 分布式協(xié)商

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ZAB協(xié)議沒有在單個(gè)的分布式協(xié)商基礎(chǔ)上進(jìn)行討論。由于使用了副本狀態(tài)機(jī)，ZAB協(xié)議考慮多個(gè)協(xié)商共同進(jìn)行的情況。ZAB協(xié)議包含了一個(gè)領(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)者需要將前面一個(gè)領(lǐng)導(dǎo)者（已經(jīng)失效）遺留的操作都提交一遍。這個(gè)過程就是錯(cuò)誤恢復(fù)的過程，能夠保證所有操作的有序性。之后，整個(gè)協(xié)議將進(jìn)入上述分布式協(xié)商的基本結(jié)構(gòu)中，快速將操作同步到所有的跟隨節(jié)點(diǎn)。

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

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

上述的3個(gè)協(xié)議是當(dāng)前在實(shí)際系統(tǒng)中使用最為廣泛的分布式協(xié)商協(xié)議，3個(gè)協(xié)議各有特點(diǎn)，可以使用在不同的場景下。3個(gè)協(xié)議要完成的目標(biāo)是相同的，都是如何可靠地推動副本狀態(tài)機(jī)的執(zhí)行。3個(gè)協(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é)商的含義以及在實(shí)際系統(tǒng)中的使用的分布式協(xié)商協(xié)議的情況。由于協(xié)議本身的復(fù)雜性，這部分內(nèi)容需要感興趣的讀者花費(fèi)較長的時(shí)間進(jìn)行理解。但是，在實(shí)際系統(tǒng)中，遇到的問題更多的是如何使用分布式協(xié)商。分布式協(xié)商在實(shí)際的系統(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)視作一個(gè)分布式數(shù)據(jù)庫，并且這個(gè)數(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ù)分表。任何一個(gè)客戶端，如果需要訪問BigTable中的數(shù)據(jù)分表，首先需要經(jīng)過元數(shù)據(jù)表的路由才可以訪問到具體的數(shù)據(jù)分表。整個(gè)路由表的根的指針放置在名為Chubby[7]的系統(tǒng)中，這是進(jìn)行路由啟動部分的數(shù)據(jù)。Chubby基于副本狀態(tài)機(jī)以及Paxos協(xié)議[8]建立了一個(gè)穩(wěn)固的分布式協(xié)同系統(tǒng)，為其上的應(yīng)用程序提供基礎(chǔ)服務(wù)。

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

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

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

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

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

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

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

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

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

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

將上述的原理應(yīng)用在實(shí)際工作的系統(tǒng)中，還需要考慮網(wǎng)絡(luò)時(shí)延以及時(shí)間測量的誤差，確保在訪問共享資源時(shí)，最多只有一個(gè)節(jié)點(diǎn)進(jìn)行訪問，其他節(jié)點(diǎn)都被排除在外，這樣才算是正確的互斥鎖的語義。如果時(shí)延的數(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ù)操作等?？梢哉f，任何一個(gè)分布式系統(tǒng)，對于共享資源的訪問是無可避免的操作，因此分布式的互斥鎖的機(jī)制是無可避免的分布式的系統(tǒng)功能。建立一個(gè)穩(wěn)固的分布式鎖的環(huán)境是建立高可靠的分布式系統(tǒng)的關(guān)鍵組成部分。

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

5 結(jié)束語

本文對現(xiàn)有的保證可靠性的副本狀態(tài)機(jī)進(jìn)行了詳細(xì)的討論，包括副本狀態(tài)機(jī)需要滿足的條件、基本的執(zhí)行流程以及副本狀態(tài)機(jī)在實(shí)現(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é)議各有特點(diǎn)，并有不同的分布式系統(tǒng)的實(shí)現(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é)議，完善了在實(shí)際系統(tǒng)中的各個(gè)細(xì)節(jié)。在分析完成常用的分布式協(xié)商協(xié)議的基礎(chǔ)之上，還分析了如何通過副本狀態(tài)機(jī)構(gòu)造可靠的分布式系統(tǒng)。需要提供的主要模塊是完成整個(gè)系統(tǒng)的節(jié)點(diǎn)狀態(tài)的監(jiān)測與維護(hù)以及協(xié)調(diào)正常工作節(jié)點(diǎn)之間的工作?？梢钥吹剑植际絽f(xié)商技術(shù)能夠提供可靠性的基本模塊，是建立可靠性系統(tǒng)的基礎(chǔ)。通過本文的分析，讀者可以對分布式協(xié)商有一個(gè)基本概念，為建立可靠的分布式系統(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ì)算機(jī)科學(xué)與技術(shù)系、深圳清華大學(xué)研究院、浙江清華長三角研究院鄞州創(chuàng)新中心副教授，主要研究方向?yàn)榉植际较到y(tǒng)、存儲系統(tǒng)。

黃劍（1993-），男，清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系碩士生，主要研究方向?yàn)槲募鎯ζ骱头植际较到y(tǒng)。

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

2015-06-20

國家自然科學(xué)基金資助項(xiàng)目（No.61433008, No.U1435216, No.61373145, No.61170210）；國家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目（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)