分布式存儲系統基礎

最近讀了楊傳輝的《大規模分布式存儲系統：原理解析與架構實踐》，這本書寫的很好，涉及的知識點枚不勝舉。本篇對於其中的分布式存儲系統基礎知識做些整理，以饗諸君。

分布式存儲系統首先要面對的問題就是數據分片，即將數據均勻地分布到多個存儲節點。另外，為了保證可靠性和可用性，需要將數據複製多個副本，這就帶來了多個副本的數據一致性問題。

大規模系統的重要目標是節省成本，因而只能採用性價比較高的PC伺服器。這些伺服器性能很好，但是故障率很高，要求系統能夠在軟體層面實現自動容錯。當存儲節點出現故障時，系統能夠檢測出來，並將原有的數據和服務遷移到集群中其他正常工作的節點。

在分布式存儲系統中，往往將一台伺服器或者伺服器上運行的一個進程稱為一個節點，節點與節點之間通過網路互聯。然而，服務節點是不可靠的，網路也是不可靠的，它們之間通信可能會出現各種異常。

引發伺服器宕機的原因有很多，例如內存錯誤、伺服器停電等等。伺服器宕機可能隨時發生，當發生宕機時，節點無法正常工作。伺服器重啟後，節點將失去所有的內存信息。

因此，設計存儲系統時需要考慮如何通過讀取持久化介質（如機械硬碟、固態硬碟）中的數據來恢復內存信息，從而恢復到宕機前的某個一致的狀態。

引發網路異常的原因可能是消息丟失、消息亂序或者網路包數據錯誤。有一種特殊的網路異常稱為「網路分區」，即集群的所有節點被劃分為多個區域，每個區域內部可以正常通信，但是區域之間無法通信。例如，某分布式系統部署在兩個數據中心，由於網路調整，導致數據中心之間無法通信，但是，數據中心內部可以正常通信。

磁碟故障可以分為兩種情況：磁碟損壞和磁碟數據錯誤。磁碟損壞時，將會丟失存儲在上面的數據，因而，分布式存儲系統需要考慮將數據存儲到多台伺服器，即使其中一台伺服器磁碟出現故障，也能從其他伺服器上恢複數據。對於磁碟數據錯誤，往往可以採用校驗和機制來解決，這樣的機制既可以在操作系統層面實現，又可以在上層的分布式存儲系統層面實現。

由於網路異常的存在，分布式系統中請求結果存在「三態」的概念，即「成功」、「失敗」、「超時」（未知狀態）。「成功」和「失敗」指客戶端請求明確收到伺服器的返回值；而「超時」指客戶端發出了一個請求但是沒有收到回復，但客戶端不能簡單地認為服務端處理失敗，因為有可能服務端已經處理成功了，但在返回結果時出現了網路異常或宕機。

對於超時（未知）狀態，有兩種處理思路：1）不斷讀取之前操作的狀態來驗證rpc操作是否成功；2）將操作設計為「冪等」的，也就是說，操作執行一次與執行多次的結果相同。

由於異常的存在，分布式存儲系統設計時往往將數據冗餘存儲多份，每一份稱為一個副本（replica）。這樣，當一個節點出現故障時，可以從其他副本上讀取數據。可以認為，副本是分布式存儲系統容錯技術的唯一手段。

由於多個副本的存在，如何保證副本之間的一致性是整個分布式系統的理論核心。

可以從兩個角度理解一致性：第一個角度是客戶端，即客戶端讀寫操作是否符合某種特性；第二個角度是存儲系統，即存儲系統的多個副本是否一致，更新的順序是否相同等等。

首先定義如下場景，這個場景包含三個組成部分：

• 存儲系統：存儲系統可以理解為一個黑盒子，它為我們提供了可用性和持久性的保證。
• 客戶端A：客戶端A主要實現從存儲系統write和read操作。
• 客戶端B和客戶端C：客戶端B和客戶端C是獨立於A，並且B和C也相互獨立，它們同時也實現對存儲系統的write和read操作。

從客戶端的角度看，一致性包含如下三種情況：

• 強一致性：假如A先寫入了一個值到存儲系統，存儲系統保證後續A，B，C的讀取操作都將返回最新值。
• 弱一致性：假如A先寫入了一個值到存儲系統，存儲系統不能保證後續A，B，C的讀取操作是否能夠讀取到最新值。
• 最終一致性：最終一致性是弱一致性的一種特例。假如A首先寫入一個值到存儲系統，存儲系統保證如果後續沒有寫操作更新同樣的值，A，B，C的讀取操作「最終」都會讀取到A寫入的值。「最終」一致性有一個「不一致窗口」的概念，它特指從A寫入值，到後續A，B，C讀取到最新值得這段時間。

最終一致性的描述比較粗略，其他常見的變體如下：

• 讀寫（Read-your-writes）一致性：如果客戶端A寫入了最新值，那麼A的後續操作都會讀取到最新值。但是其他用戶（比如B或者C）可能要過一會才能看到。
• 會話（Session）一致性：要求客戶端和存儲系統交互的整個會話期間保證讀寫一致性。如果原有會話因為某種原因失敗而創建了新的會話，原有會話和新會話之間的操作不保證讀寫一致性。
• 單調讀（Monotonic read）一致性：如果客戶端A已經讀取了對象的某個值，那麼後續操作不會讀取到更早的值。
• 單調寫（Monotonic write）一致性：客戶端A的寫操作按順序完成，這就意味著，對於同一個客戶端的操作，存儲系統的多個副本需要按照與客戶單相同的順序完成。

從存儲系統的角度看，一致性主要包含如下幾個方面：

• 副本一致性：存儲系統的多個副本之間的數據是否一致，不一致的時間窗口等；
• 更新順序一致性：存儲系統的多個副本之間是否按照相同的順序執行更新操作。

衡量指標

評價分布式存儲系統有一些常用的指標，下面分別介紹。

常見的性能指標有：系統的吞吐能力（throughput）以及系統的響應時間（latency）。其中，系統的吞吐能力指系統在某一段時間可以處理的請求總數，通常用每秒處理的讀操作數（QPS，Query Per Second）或者寫操作數（TPS，Transaction Per Second）來衡量。系統的響應時間，指從某個請求發出到接收到返回結果消耗的時間，通常用平均延時或者99.9%以上請求的最大延時來衡量。

這兩個指標往往是矛盾的，追求高吞吐的系統，往往很難做到低延遲；追求低延遲的系統，吞吐量也會受到限制。因此，設計系統時需要權衡這兩個指標。

系統的可能性（availability）是指系統在面對各種異常時可以提供正常服務的能力。系統的可用性可以用系統停服務的時間與正常服務的時間的比例來衡量，例如某系統的可用性為4個9（99.99%），相當於系統一年停服務時間不能超過365 * 24 * 60 / 10000 = 52.56分鐘。系統可用性往往體現了系統的整體代碼質量以及容錯能力。

前面已經說明了系統的一致性。一般來說，越是強的一致性模型，用戶使用起來越簡單。

系統的可擴展性（scalability）指分布式存儲系統通過擴展集群伺服器規模來提高系統存儲容量、計算量和性能的能力。隨著業務的發展，對底層存儲系統的性能需求不斷增加，比較好的方式就是通過自動增加伺服器提高系統的能力。理想的分布式存儲系統實現「線性可擴展」，也就是說，隨著集群規模的增加，系統整體性能與伺服器數量呈線性關係。

分布式系統區別於傳統單機系統在於能夠將數據分布到多個節點，並在多個節點之間實現負載均衡。數據分布的方式主要有兩種，一種是哈希分布，如一致性哈希，代表系統為Amazon的Dynamo系統；另一種方法是順序分布，即數據按照主鍵整體有序，代表系統為Google的Bigtable系統。Bigtable將一張大表根據主鍵切分為有序的範圍，每個有序的範圍是一個子表。

哈希取模的方法很常見，其方法是根據數據的某一種特徵計算哈希值，並將哈希值與集群中的伺服器建立映射關係，從而將不同哈希值得數據分布到不同的伺服器上。

如果哈希函數的散列特性很好，哈希方式可以將數據比較均勻地分布到集群中去。然而，找出一個散列特性很好的哈希函數是很難的。舉個例子，如果按照主鍵散列，那麼同一個用戶id下的數據可能被分散到多台伺服器，這會使得一次操作同一個用戶id下的多條記錄變得困難；如果按照用戶id散列，容易出現「數據傾斜」問題，即某些大用戶的數據量很大，無論集群的規模有多大，這些用戶始終由一台伺服器處理。

處理大用戶問題一般有兩種方式，一種方式是手動拆分，即線下標記系統中的大用戶，並根據這些大用戶的數據量將其拆分到多台伺服器上。這相當於在哈希分布的基礎上針對這些大用戶特殊處理；另一種方式是自動拆分，即數據分布演算法能夠動態調整，自動將大用戶的數據拆分到多台伺服器上。

傳統的哈希分布演算法還有一個問題：當伺服器上線或者下線時，N值發生變化，數據映射完全被打亂，幾乎所有的數據都需要重新分布，這將帶來大量的數據遷移。

一種思路是不再簡單地將哈希值和伺服器個數之間做除法取模映射，而是將哈希值與伺服器的對應關係作為元數據，交給專門的元數據伺服器來管理。訪問數據時，首先計算哈希值，再查詢元數據伺服器，獲得該哈希值對應的伺服器。這樣，集群擴容時，可以將部分哈希值分配給新加入的機器並遷移對應的數據。

另一種思路就是採用一致性哈希演算法。演算法思想如下：給系統中每個節點分配一個隨機token，這些token構成一個哈希環。執行數據存放操作時，先計算Key（主鍵）的哈希值，然後存放到順時針方向第一個大於或者等於該哈希值得token所在的節點。一致性哈希的優點在於節點加入/刪除時隻影響到在哈希環中相鄰的節點，而對其他節點沒影響。

哈希散列破壞了數據的有序性，只支持隨機讀操作，不能夠支持順序掃描。順序分布在分布式表格系統中比較常見，一般的做法是將大表順序劃分為連續的範圍，每個範圍稱為一個子表，總控伺服器負責將這些子表按照一定的策略分配到存儲節點上。

例如，用戶表（User表）的主鍵範圍為為1~7000，在分布式存儲系統中劃分為多個子表，分別對應數據範圍1~1000，1001~2000，…，6001~7000。某些系統只有根表（Root表）一級索引，在Root表中維護用戶表的位置信息，即每個用戶子表存放在哪個存儲節點上。為了支持更大的集群規模，Bigtable這樣的系統將索引分為兩級：根表以及元數據表（Meta表），由Meta表維護User表的位置信息，而Root表維護Meta表的位置信息。

順序分布與B+樹數據結構比較類似，每個子表相當於葉子節點，隨著數據的插入和刪除，某些子表可能變得很大，某些變得很小，數據分布不均勻，系統設計時需要考慮子表的分裂與合并。

分布式存儲系統的每個集群中一般都有一個總控節點，其他節點為工作節點，由總控節點根據全局負載信息進行整體調度。系統運行過程中需要不斷地執行遷移任務，將數據從負載較高的工作節點遷移到負載較低的工作節點。

工作節點通過心跳包（Heartbeat，定時發送）將節點負載相關的信息，如CPU，內存，磁碟，網路等資源使用率，讀寫次數及讀寫數據量發送給總控節點。總控節點計算出工作節點的負載以及需要遷移的數據，生成遷移任務放入遷移隊列中等待執行。

分布式存儲系統中往往會存儲數據的多個副本，其中一個副本為主副本，其他副本為備副本，由主副本對外提供服務。遷移備副本不會對服務造成影響，遷移主副本也可以首先將數據的讀寫服務切換到其他備副本。整個遷移過程可以做到無縫，對用戶完全透明。

為了保證分布式存儲系統的高可靠和高可用，數據在系統中一般存儲多個副本。當某個副本所在的存儲節點出現故障時，分布式存儲系統能夠將服務切換到其他副本，從而實現自動容錯。分布式存儲系統通過將複製協議將數據同步到多個存儲節點，並保證多個副本的數據一致性。

同一份數據的多個副本往往有一個副本為主副本（Primary），其他副本為備副本（Backup），由主副本將數據複製到備副本。複製協議分為兩種，強同步複製以及非同步複製。二者的區別在於用戶的寫請求是否需要同步到備副本才可以返回成功。假如備副本不止一個，複製協議還會要求寫請求至少需要同步到幾個備副本。

主副本將寫請求複製到其他備副本常見的做法是同步操作日誌（Commit Log），主副本首先將操作日誌同步到備副本，備副本回放操作日誌，完成後通知主副本。等這些操作完成後再通知客戶端寫成功。這種協議稱為強同步協議。強同步協議提供了強一致性，但是，如果備副本出現問題將阻塞寫操作，系統可用性較差。

操作日誌的原理很簡單：為了利用磁碟的順序讀寫特性，將客戶端的寫操作先順序寫入磁碟中，然後應用到內存中。當伺服器宕機重啟時，只需要回放操作日誌就可以恢復內存狀態。為了提高系統的並發能力，系統會積攢一定的操作日誌再批量寫入到磁碟中，這種技術稱為成組提交。

如果每次伺服器出現故障都需要回放所有的操作日誌，效率是無法忍受的，檢查點（checkpoint）正是為了解決這個問題。系統定期將內存狀態以檢查點文件的形式dump到磁碟中，並記錄檢查點時刻對應的操作日誌回放點。檢查點文件創建成功後，回放點之前的日誌可以被垃圾回收，以後如果伺服器出現故障，只需要回放檢查點之後的操作日誌。

強同步複製和非同步複製都是基於主副本的複製協議（Primary-based protocol）。這種方法要求在任何時刻只能有一個副本為主副本，由它來確定寫操作之間的順序。如果主副本出現故障，需要選舉一個備副本稱為新的主副本，這步操作稱為選舉，經典的選舉協議為Paxos協議。

一致性和可用性是矛盾的，強同步複製協議可以保證主備副本之間的一致性，但是備副本出現故障時，也可能阻塞存儲系統的正常寫服務，系統的整體可用性受到影響；非同步複製的可用性相對較好，但是一致性得不到保障，主副本出現故障還有數據丟失的可能。

除了基於主副本的複製協議，分布式存儲系統還可能使用基於寫多個存儲節點的複製協議（Replicated-write protocol）。比如Dynamo系統中的NWR複製協議，其中N為副本數量，W為寫操作的副本數，R為讀操作的副本數。NWR協議中不再區分主和備，客戶端根據一定的策略往其中的W個副本寫入數據，讀其中的R個副本。只要W+R>N，可以保證讀到的副本中至少有一個包含了最新的更新。

來自Berkerly的Eric Brewer教授提出了一個著名的CAP理論：一致性（Consistency），可用性（Availability）以及分區可容忍性（Toleration of network Partition）三者不能同時滿足。

• 一致性：讀操作總能讀取到之前完成的寫操作結果。
• 可用性：讀寫操作始終能夠成功。
• 分區可容忍性：系統能夠容忍由於機器故障、網路故障、機房停電等異常情況所造成的網路分區。

在分布式系統中，分區可容忍性總是要滿足的，因此一致性和可用性不能同時滿足。存儲系統設計時需要在一致性和可用性之間權衡，在某些場景下，不允許丟失數據，在另外一些場景下，極小的概率丟失部分數據是允許的，可用性更加重要。例如，Oracle資料庫的DataGuard複製組件包含三種模式：

• 最大保護模式（Maximum Protection）：即強同步複製模式，寫操作要求主庫先將操作日誌（資料庫的redo/undo日誌）同步到至少一個備庫才可以返回客戶端成功。這種模式保證即使主庫出現無法恢復的故障，比如硬碟損壞，也不會丟失數據。
• 最大性能模式（Maximum Performance）：即非同步複製模式，寫操作只需要在主庫上執行成功就可以返回客戶端成功，主庫上的後台線程會將重做日誌通過非同步的方式複製到備庫。這種方式保證了性能和可用性，但是可能丟失數據。
• 最大可用性模式（Maximum Availability）：上述兩種模式的折衷。正常情況下相當於最大保護模式，如果主備之間的網路出現故障，切換為最大性能模式。

容錯

隨著集群規模越來越大，故障發生的概率也越來越大，大規模集群每天都有故障發生。容錯是分布式存儲系統涉及的重要目標，只有實現了自動化容錯，才能減少人工運維成本，實現分布式存儲的規模效應。

首先，分布式存儲系統需要能夠檢測到機器故障，例如通過租約（Lease）協議實現。接著，需要能夠將服務複製或者遷移到集群中的其他正常服務的存儲節點。

容錯處理的第一步是故障檢測，心跳是一種很自然地想法。假設總控機A需要確認工作機B是否發生故障，那麼總控機A每隔一段時間，比如1秒，向工作機B發送一個心跳包。如果一切正常，機器B將響應機器A的心跳包；否則，機器A重試了一定次數後認為機器B發生了故障。但是，機器A收不到機器B的心跳並不能確保機器B發生故障並停止了服務，比如可能是A和B之間出現網路問題導致A收不到回復。由於在機器A「認為」機器B發生故障後，往往需要將它上面的服務遷移到集群中的其他伺服器，為了保證強一致性，需要確保機器B不再提供服務。

這裡的問題是機器A和機器B之間需要對「機器B是否應該被認為發生故障且停止服務」達成一致。我們可以通過租約（Lease）機制進行故障檢測，機器A可以通過機器B發放租約，機器B持有的租約在有效期內才允許提供服務，否則主動停止服務。機器B的租約快要到期的時候向機器A重新申請租約。正常情況下，機器B通過不斷申請租約來延長有效期，當機器B出現故障或者與機器A之間的網路發生故障時，機器B的租約將過期，從而機器A能夠確保機器B不再提供服務，機器B的服務可以被安全地遷移到其他伺服器。

當總控機檢測到工作機發生故障時，需要將服務遷移到其他工作節點。常見的分布式存儲系統分為兩種結構：單層結構和雙層結構。大部分系統為單層結構，在系統中對每個數據分票維護多個副本；只有類Bigtable系統為雙層結構，將存儲和服務分為兩層，存儲層對每個數據分片維護多個副本，服務層只有一個副本提供服務。單層結構和雙層結構的故障恢復機制有所不同。

單層結構和雙層結構如下圖所示：

單層結構的分布式存儲系統維護了多個副本，例如副本個數為3，主備副本之間通過操作日誌同步。如上圖所示，某單層結構的分布式存儲系統有3個數據分片A、B、C，每個數據分片存儲了三個副本。其中，A1，B1，C1為主副本，分別存儲在節點1，節點2以及節點3.假設節點1發生故障，總控節點選擇一個最新的副本（比如A2或者A3）來替換A1成為新的主副本並提供寫服務。

兩層結構的分布式存儲系統會將所有的數據持久化寫入底層的分布式文件系統，每個數據分片同一時刻只有一個提供服務的節點。如上圖所示，某雙層結構的分布式存儲系統有3個數據分片，A、B和C。它們分別被節點1，節點2和節點3所服務。當節點1發生故障時，總控節點將選擇一個工作節點，比如節點2，載入A的服務。由於A的所有數據都存儲在共享的分布式文件系統中，節點2隻需要從底層的分布式文件系統讀取A的數據並載入到內存中。

可擴展性同構系統

同構系統將存儲節點分為若干組，組內的節點服務完全相同的數據，其中有一個節點為主節點，其他節點為備節點。由於同一個組內的節點服務相同的數據，這樣的系統稱為同構系統。如下圖所示。

同構系統的問題在於增加副本需要遷移的數據量太大，假設每個存儲節點服務的數據量為1TB，內部傳輸帶寬限制為20MB/s，那麼增加副本拷貝數據需要的時間為1TB/20MB=50000s，大約十幾個小時，由於拷貝數據的過程中存儲節點再次發生故障的概率很高，所以這樣的架構很難做到自動化，不適合大規模分布式存儲系統。

大規模分布式存儲系統要求具有線性可擴展性，即隨時加入或者刪除一個或者多個存儲節點，系統的處理能力與存儲節點的個數成線性關係。為了實現線性可擴展性，存儲系統的存儲節點之間是異構的。

異構系統將數據分為很多大小相近的分片，每個分片的多個副本可以分布到集群的任何一個存儲節點。如果某個節點發生故障，原有的服務將由整個集群而不是某幾個固定的存儲節點來恢復。

如下圖所示，系統中有五個分片（A，B，C，D，E），每個分片包含三個副本，如分片A的三個副本分別為A1，A2以及A3。假如節點1發生永久性故障，那麼可以從剩餘的節點中任意挑選健康的節點來增加A，B以及E的副本。由於整個集群都參與到節點1的故障恢復過程，故障恢復時間很短，而且集群規模越大，優勢越明顯。

分布式系統涉及的協議很多，例如租約，複製協議，一致性協議，其中以兩階段提交協議和Paxos協議最具有代表性。兩階段提交協議用於保證跨多個節點操作的原子性，也就是說，跨多個節點的操作要麼在所有節點上全部執行成功，要麼全部失敗。Paxos協議用於確保多個節點對某個投票（例如哪個節點成為主節點）達成一致。

兩階段提交協議（Two-phase Commit，2PC）經常用來實現分布式事務，在兩階段提交協議中，系統一般包含兩類節點：一類為協調者（coordinator），通常一個系統中只有一個；另一類為事務參與者（participants），一般包含多個。顧名思義，兩階段提交協議由兩個階段組成，如下所述：

• 階段1：請求階段（Prepare Phase）。在請求階段，協調者通知事務參與者準備提交或者取消事務，然後進入表決過程。在表決過程，參與者將告知協調者自己的決策：同意（事務參與者本地執行成功，但沒有提交）或者取消（事務參與者本地執行失敗）。
• 階段2：提交階段（Commit Phase）。在提交階段，協調者將基於第一個階段的投票進行決策：提交或者取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者通知所有的參與者取消事務。參與者在接收到協調者發來的消息後將執行相應的操作。

兩階段提交協議可能面臨兩種故障：

• 事務參與者發生故障。給每個事務設置一個超時時間，如果某個事務參與者一直不響應，到達超時時間後整個事務失敗。
• 協調者發生故障。協調者需要將事務相關信息記錄到操作日誌並同步到備用協調者，假如協調者發生故障，備用協調者可以接替它完成後續的工作。如果沒有備用協調者，協調者又發生了永久性故障，事務參與者將無法完成事務而一直等待下去。

Paxos協議

Paxos協議用於解決多個節點之間的一致性問題。多個節點之間通過操作日誌同步數據，如果只有一個節點為主節點，那麼，很容易確保多個節點之間操作日誌的一致性。考慮到主節點可能出現故障，系統需要選舉出新的主節點。Paxos協議正是用來實現這個需求。只要保證多個節點之間操作日誌的一致性，就能夠在這些節點上構建高可用的全局服務，例如分布式鎖服務，全局命名和配置服務等。

為了實現高可用，主節點往往將數據以操作日誌的形式同步到備節點。如果主節點發生故障，備節點會提議自己成為主節點。這裡存在的問題是網路分區的時候，可能會存在多個備節點提議（Proposer，提議者）自己成為主節點。Paxos協議保證，即使同時存在多個proposer，也能夠保證所有節點最終達成一致，即選舉出唯一的主節點。

大多數情況下，系統只有一個proposer，他的提議也總是會很快被大多數節點接受。步驟如下：

1）批准（accept）：Proposer發送accept消息要求所有其他節點（acceptor，接受者）接受某個提議值，acceptor可以接受或者拒絕。

2）確認（acknowledge）：如果超過一半的acceptor接受，意味著提議值已經生效，Proposer發送acknowledge消息通知所有的acceptor提議生效。

當出現網路或者其他異常時，系統中可能存在多個Proposer，他們各自發起不同的提議。這裡的提議可以是一個修改操作，也可以是提議自己成為主節點。如果proposer第一次發起的accept請求沒有被acceptor中的多數派批准（例如與其他proposer的提議衝突），那麼，需要完整地執行一輪Paxos協議。過程如下：

1）準備（prepare）：Proposer首先選擇一個提議序號n給其他的acceptor節點發送prepare消息。Acceptor收到prepare消息後，如果提議的序號大於他已經回復的所有prepare消息，則acceptor將自己上次接受的提議回復給proposer，並承諾不再回復小於n的提議。

2）批准（accept）：Proposer收到了acceptor中的多數派對於prepare的回復後，就進入批准階段。如果在之前的prepare階段acceptor回復了上次接受的提議，那麼，proposer選擇其中序號最大的提議值發給acceptor批准；否則，proposer生成一個新的提議值發給acceptor批准。Acceptor在不違背他之前在prepare階段的承諾的前提下，接受這個請求。

3）確認（acknowledge）：如果超過一半的acceptor接受，提議值生效。Proposer發送acknowledge消息通知所有的acceptor提議生效。

Paxos協議需要考慮兩個問題：正確性，即只有一個提議值生效；可終止性，即最後總會有一個提議值生效。Paxos協議中要求每個生效的提議被acceptor中的多數派接受，並且每個acceptor不會接受兩個不同的提議，因此可以保證正確性。Paxos協議並不能嚴格保證可終止性，但是從Paxos協議的執行過程可以看出來，只要超過一個acceptor接受了提議，proposer很快就會發現，並重新提議其中序號最大的提議值。因此，隨著協議不斷進行，它會往「某個提議值被多數派接受並生效」這一最終目標靠攏。

Paxos與2PC

Paxos協議和2PC協議在分布式系統中所起的作用並不相同。Paxos協議用於保證同一個數據分片的多個副本之間的數據一致性。當這些副本分布到不同的數據中心時，這個需求尤其強烈。2PC協議用於保證多個數據分片上的操作的原子性。這些數據分片可能分布在不同的伺服器上，2PC協議保證多台伺服器上的操作要麼全部成功，要麼全部失敗。

常見的做法是，將2PC和Paxos協議結合起來，通過2PC保證多個數據分片上的操作的原子性，通過Paxos協議實現同一個數據分片的多個副本之間的一致性。另外，通過Paxos協議解決2PC協議中協調者宕機問題。當2PC協議中的協調者出現故障，通過Paxos協議選舉出新的協調者繼續提供服務。

在分布式系統中，跨機房問題一直都是老大難問題。機房之間的網路延遲較大，且不穩定。跨機房問題主要包含兩個方面：數據同步以及服務切換。跨機房部署方案有三個：集群整體切換、單個集群跨機房、Paxos選主副本。下面分別介紹。

1.集群整體切換

集群整體切換是最為常見的方案。如下圖所示，假設某系統部署在兩個機房：機房1和機房2。兩個機房保持獨立，每個機房部署單獨的總控節點，且每個總控節點各有一個備份節點。當總控節點出現故障時，能夠自動將機房內的備份節點切換為總控節點繼續提供服務。另外，兩個機房部署了相同的副本數，例如數據分片A在機房1存儲的副本為A11和A12，在機房2部署的副本為A21和A22.在某個時刻，機房1為主機房，機房2為備機房。

機房之間的數據同步方式可能為強同步或者非同步。

如果採用非同步模式，那麼備用機房的數據總是落後於主機房。當主機房整體出現故障時，有兩種選擇：要麼將服務切換到備機房，忍受數據丟失的風險；要麼停止服務，直到主機房恢復為止。因此，主備切換往往是手工的，因為需要根據業務特點選擇「丟失數據」或者「停止服務」。

如果採用強同步模式，那麼備機房的數據和主機房保持一致。當主機房出現故障時，可以通過分布式鎖服務發現，並自動將備用機房切換為主機房。

2.單個集群跨機房

上一種方案的所有主副本只能同時存在於一個機房內，另一種方案是將單個集群部署到多個機房，允許不同數據分片的主副本位於不同的機房。如下圖所示，每個數據分片在機房1和機房2，總共包含4個副本，其中A1、B1、C1是主副本，A1和B1在機房1，C1在機房2。整個集群只有一個總控節點，它需要同機房1和機房2的所有工作節點保持通信。當總控節點出現故障時，分布式鎖服務將檢測到，並將機房2的備份節點切換為總控節點。

如果採用這種部署方式，總控節點在執行數據分布時，需要考慮機房信息，也就是說，盡量將同一個數據分片的多個副本分布到多個機房，從而防止單個機房出現故障而影響正常服務。

3.Paxos選主副本

在前兩種方案中，總控節點需要和工作節點之間保持租約（lease），當工作節點出現故障時，自動將它上面服務的主副本切換到其他工作節點。

如果採用Paxos選主副本，那麼，每個數據分片的多個副本構成一個Paxos複製組。如下圖所示，B1、B2、B3、B4構成一個複製組，某一時刻B1為複製組的主副本，當B1出現故障時，其他副本將嘗試切換為主副本，Paxos協議保證只有一個副本會成功。這樣，總控節點和工作節點之間不再需要保持租約，總控節點出現故障也不會對工作節點產生影響。

Google後續開發的系統，包括Google Megastore以及Spanner，都採用了這種方式。它的優點在於能夠降低對總控節點的依賴，缺點在於工程複雜度太高，難以在線下模擬所有的異常情況。