分布式存儲系統基礎

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

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

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

 作者：佚名

來源：51cto