[[188561]]

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

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

大規模系統的重要目標是節省成本，因而只能采用性價比較高的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，都采用了這種方式。它的優點在于能夠降低對總控節點的依賴，缺點在于工程復雜度太高，難以在線下模擬所有的異常情況。