[[188561]]

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

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

大規(guī)模系統(tǒng)的重要目標是節(jié)省成本，因而只能采用性價比較高的PC服務器。這些服務器性能很好，但是故障率很高，要求系統(tǒng)能夠在軟件層面實現(xiàn)自動容錯。當存儲節(jié)點出現(xiàn)故障時，系統(tǒng)能夠檢測出來，并將原有的數(shù)據(jù)和服務遷移到集群中其他正常工作的節(jié)點。

基本概念

異常

在分布式存儲系統(tǒng)中，往往將一臺服務器或者服務器上運行的一個進程稱為一個節(jié)點，節(jié)點與節(jié)點之間通過網(wǎng)絡互聯(lián)。然而，服務節(jié)點是不可靠的，網(wǎng)絡也是不可靠的，它們之間通信可能會出現(xiàn)各種異常。

服務器宕機

引發(fā)服務器宕機的原因有很多，例如內(nèi)存錯誤、服務器停電等等。服務器宕機可能隨時發(fā)生，當發(fā)生宕機時，節(jié)點無法正常工作。服務器重啟后，節(jié)點將失去所有的內(nèi)存信息。

因此，設計存儲系統(tǒng)時需要考慮如何通過讀取持久化介質(zhì)(如機械硬盤、固態(tài)硬盤)中的數(shù)據(jù)來恢復內(nèi)存信息，從而恢復到宕機前的某個一致的狀態(tài)。

網(wǎng)絡異常

引發(fā)網(wǎng)絡異常的原因可能是消息丟失、消息亂序或者網(wǎng)絡包數(shù)據(jù)錯誤。有一種特殊的網(wǎng)絡異常稱為“網(wǎng)絡分區(qū)”，即集群的所有節(jié)點被劃分為多個區(qū)域，每個區(qū)域內(nèi)部可以正常通信，但是區(qū)域之間無法通信。例如，某分布式系統(tǒng)部署在兩個數(shù)據(jù)中心，由于網(wǎng)絡調(diào)整，導致數(shù)據(jù)中心之間無法通信，但是，數(shù)據(jù)中心內(nèi)部可以正常通信。

磁盤故障

磁盤故障可以分為兩種情況：磁盤損壞和磁盤數(shù)據(jù)錯誤。磁盤損壞時，將會丟失存儲在上面的數(shù)據(jù)，因而，分布式存儲系統(tǒng)需要考慮將數(shù)據(jù)存儲到多臺服務器，即使其中一臺服務器磁盤出現(xiàn)故障，也能從其他服務器上恢復數(shù)據(jù)。對于磁盤數(shù)據(jù)錯誤，往往可以采用校驗和機制來解決，這樣的機制既可以在操作系統(tǒng)層面實現(xiàn)，又可以在上層的分布式存儲系統(tǒng)層面實現(xiàn)。

超時

由于網(wǎng)絡異常的存在，分布式系統(tǒng)中請求結(jié)果存在“三態(tài)”的概念，即“成功”、“失敗”、“超時”(未知狀態(tài))。“成功”和“失敗”指客戶端請求明確收到服務器的返回值;而“超時”指客戶端發(fā)出了一個請求但是沒有收到回復，但客戶端不能簡單地認為服務端處理失敗，因為有可能服務端已經(jīng)處理成功了，但在返回結(jié)果時出現(xiàn)了網(wǎng)絡異常或宕機。

對于超時(未知)狀態(tài)，有兩種處理思路：1)不斷讀取之前操作的狀態(tài)來驗證rpc操作是否成功;2)將操作設計為“冪等”的，也就是說，操作執(zhí)行一次與執(zhí)行多次的結(jié)果相同。

一致性

由于異常的存在，分布式存儲系統(tǒng)設計時往往將數(shù)據(jù)冗余存儲多份，每一份稱為一個副本(replica)。這樣，當一個節(jié)點出現(xiàn)故障時，可以從其他副本上讀取數(shù)據(jù)。可以認為，副本是分布式存儲系統(tǒng)容錯技術的唯一手段。

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

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

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

• 存儲系統(tǒng)：存儲系統(tǒng)可以理解為一個黑盒子，它為我們提供了可用性和持久性的保證。
• 客戶端A：客戶端A主要實現(xiàn)從存儲系統(tǒng)write和read操作。
• 客戶端B和客戶端C：客戶端B和客戶端C是獨立于A，并且B和C也相互獨立，它們同時也實現(xiàn)對存儲系統(tǒng)的write和read操作。
• 從客戶端的角度看，一致性包含如下三種情況：
• 強一致性：假如A先寫入了一個值到存儲系統(tǒng)，存儲系統(tǒng)保證后續(xù)A，B，C的讀取操作都將返回最新值。
• 弱一致性：假如A先寫入了一個值到存儲系統(tǒng)，存儲系統(tǒng)不能保證后續(xù)A，B，C的讀取操作是否能夠讀取到最新值。
• 最終一致性：最終一致性是弱一致性的一種特例。假如A首先寫入一個值到存儲系統(tǒng)，存儲系統(tǒng)保證如果后續(xù)沒有寫操作更新同樣的值，A，B，C的讀取操作“最終”都會讀取到A寫入的值。“最終”一致性有一個“不一致窗口”的概念，它特指從A寫入值，到后續(xù)A，B，C讀取到最新值得這段時間。

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

• 讀寫(Read-your-writes)一致性：如果客戶端A寫入了最新值，那么A的后續(xù)操作都會讀取到最新值。但是其他用戶(比如B或者C)可能要過一會才能看到。
• 會話(Session)一致性：要求客戶端和存儲系統(tǒng)交互的整個會話期間保證讀寫一致性。如果原有會話因為某種原因失敗而創(chuàng)建了新的會話，原有會話和新會話之間的操作不保證讀寫一致性。
• 單調(diào)讀(Monotonic read)一致性：如果客戶端A已經(jīng)讀取了對象的某個值，那么后續(xù)操作不會讀取到更早的值。
• 單調(diào)寫(Monotonic write)一致性：客戶端A的寫操作按順序完成，這就意味著，對于同一個客戶端的操作，存儲系統(tǒng)的多個副本需要按照與客戶單相同的順序完成。
• 從存儲系統(tǒng)的角度看，一致性主要包含如下幾個方面：
• 副本一致性：存儲系統(tǒng)的多個副本之間的數(shù)據(jù)是否一致，不一致的時間窗口等;
• 更新順序一致性：存儲系統(tǒng)的多個副本之間是否按照相同的順序執(zhí)行更新操作。

衡量指標

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

性能

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

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

可用性

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

一致性

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

可擴展性

系統(tǒng)的可擴展性(scalability)指分布式存儲系統(tǒng)通過擴展集群服務器規(guī)模來提高系統(tǒng)存儲容量、計算量和性能的能力。隨著業(yè)務的發(fā)展，對底層存儲系統(tǒng)的性能需求不斷增加，比較好的方式就是通過自動增加服務器提高系統(tǒng)的能力。理想的分布式存儲系統(tǒng)實現(xiàn)“線性可擴展”，也就是說，隨著集群規(guī)模的增加，系統(tǒng)整體性能與服務器數(shù)量呈線性關系。

數(shù)據(jù)分布

分布式系統(tǒng)區(qū)別于傳統(tǒng)單機系統(tǒng)在于能夠?qū)?shù)據(jù)分布到多個節(jié)點，并在多個節(jié)點之間實現(xiàn)負載均衡。數(shù)據(jù)分布的方式主要有兩種，一種是哈希分布，如一致性哈希，代表系統(tǒng)為Amazon的Dynamo系統(tǒng);另一種方法是順序分布，即數(shù)據(jù)按照主鍵整體有序，代表系統(tǒng)為Google的Bigtable系統(tǒng)。Bigtable將一張大表根據(jù)主鍵切分為有序的范圍，每個有序的范圍是一個子表。

哈希分布

哈希取模的方法很常見，其方法是根據(jù)數(shù)據(jù)的某一種特征計算哈希值，并將哈希值與集群中的服務器建立映射關系，從而將不同哈希值得數(shù)據(jù)分布到不同的服務器上。

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

處理大用戶問題一般有兩種方式，一種方式是手動拆分，即線下標記系統(tǒng)中的大用戶，并根據(jù)這些大用戶的數(shù)據(jù)量將其拆分到多臺服務器上。這相當于在哈希分布的基礎上針對這些大用戶特殊處理;另一種方式是自動拆分，即數(shù)據(jù)分布算法能夠動態(tài)調(diào)整，自動將大用戶的數(shù)據(jù)拆分到多臺服務器上。

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

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

另一種思路就是采用一致性哈希算法。算法思想如下：給系統(tǒng)中每個節(jié)點分配一個隨機token，這些token構(gòu)成一個哈希環(huán)。執(zhí)行數(shù)據(jù)存放操作時，先計算Key(主鍵)的哈希值，然后存放到順時針方向第一個大于或者等于該哈希值得token所在的節(jié)點。一致性哈希的優(yōu)點在于節(jié)點加入/刪除時只影響到在哈希環(huán)中相鄰的節(jié)點，而對其他節(jié)點沒影響。

順序分布

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

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

順序分布與B+樹數(shù)據(jù)結(jié)構(gòu)比較類似，每個子表相當于葉子節(jié)點，隨著數(shù)據(jù)的插入和刪除，某些子表可能變得很大，某些變得很小，數(shù)據(jù)分布不均勻，系統(tǒng)設計時需要考慮子表的分裂與合并。

負載均衡

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

工作節(jié)點通過心跳包(Heartbeat，定時發(fā)送)將節(jié)點負載相關的信息，如CPU，內(nèi)存，磁盤，網(wǎng)絡等資源使用率，讀寫次數(shù)及讀寫數(shù)據(jù)量發(fā)送給總控節(jié)點。總控節(jié)點計算出工作節(jié)點的負載以及需要遷移的數(shù)據(jù)，生成遷移任務放入遷移隊列中等待執(zhí)行。

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

復制

復制的概述

為了保證分布式存儲系統(tǒng)的高可靠和高可用，數(shù)據(jù)在系統(tǒng)中一般存儲多個副本。當某個副本所在的存儲節(jié)點出現(xiàn)故障時，分布式存儲系統(tǒng)能夠?qū)⒎涨袚Q到其他副本，從而實現(xiàn)自動容錯。分布式存儲系統(tǒng)通過將復制協(xié)議將數(shù)據(jù)同步到多個存儲節(jié)點，并保證多個副本的數(shù)據(jù)一致性。

同一份數(shù)據(jù)的多個副本往往有一個副本為主副本(Primary)，其他副本為備副本(Backup)，由主副本將數(shù)據(jù)復制到備副本。復制協(xié)議分為兩種，強同步復制以及異步復制。二者的區(qū)別在于用戶的寫請求是否需要同步到備副本才可以返回成功。假如備副本不止一個，復制協(xié)議還會要求寫請求至少需要同步到幾個備副本。

主副本將寫請求復制到其他備副本常見的做法是同步操作日志(Commit Log)，主副本首先將操作日志同步到備副本，備副本回放操作日志，完成后通知主副本。等這些操作完成后再通知客戶端寫成功。這種協(xié)議稱為強同步協(xié)議。強同步協(xié)議提供了強一致性，但是，如果備副本出現(xiàn)問題將阻塞寫操作，系統(tǒng)可用性較差。

操作日志的原理很簡單：為了利用磁盤的順序讀寫特性，將客戶端的寫操作先順序?qū)懭氪疟P中，然后應用到內(nèi)存中。當服務器宕機重啟時，只需要回放操作日志就可以恢復內(nèi)存狀態(tài)。為了提高系統(tǒng)的并發(fā)能力，系統(tǒng)會積攢一定的操作日志再批量寫入到磁盤中，這種技術稱為成組提交。

如果每次服務器出現(xiàn)故障都需要回放所有的操作日志，效率是無法忍受的，檢查點(checkpoint)正是為了解決這個問題。系統(tǒng)定期將內(nèi)存狀態(tài)以檢查點文件的形式dump到磁盤中，并記錄檢查點時刻對應的操作日志回放點。檢查點文件創(chuàng)建成功后，回放點之前的日志可以被垃圾回收，以后如果服務器出現(xiàn)故障，只需要回放檢查點之后的操作日志。

強同步復制和異步復制都是基于主副本的復制協(xié)議(Primary-based protocol)。這種方法要求在任何時刻只能有一個副本為主副本，由它來確定寫操作之間的順序。如果主副本出現(xiàn)故障，需要選舉一個備副本稱為新的主副本，這步操作稱為選舉，經(jīng)典的選舉協(xié)議為Paxos協(xié)議。

一致性和可用性是矛盾的，強同步復制協(xié)議可以保證主備副本之間的一致性，但是備副本出現(xiàn)故障時，也可能阻塞存儲系統(tǒng)的正常寫服務，系統(tǒng)的整體可用性受到影響;異步復制的可用性相對較好，但是一致性得不到保障，主副本出現(xiàn)故障還有數(shù)據(jù)丟失的可能。

除了基于主副本的復制協(xié)議，分布式存儲系統(tǒng)還可能使用基于寫多個存儲節(jié)點的復制協(xié)議(Replicated-write protocol)。比如Dynamo系統(tǒng)中的NWR復制協(xié)議，其中N為副本數(shù)量，W為寫操作的副本數(shù)，R為讀操作的副本數(shù)。NWR協(xié)議中不再區(qū)分主和備，客戶端根據(jù)一定的策略往其中的W個副本寫入數(shù)據(jù)，讀其中的R個副本。只要W+R>N，可以保證讀到的副本中至少有一個包含了最新的更新。

一致性與可用性

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

一致性：讀操作總能讀取到之前完成的寫操作結(jié)果。

可用性：讀寫操作始終能夠成功。

分區(qū)可容忍性：系統(tǒng)能夠容忍由于機器故障、網(wǎng)絡故障、機房停電等異常情況所造成的網(wǎng)絡分區(qū)。

在分布式系統(tǒng)中，分區(qū)可容忍性總是要滿足的，因此一致性和可用性不能同時滿足。存儲系統(tǒng)設計時需要在一致性和可用性之間權(quán)衡，在某些場景下，不允許丟失數(shù)據(jù)，在另外一些場景下，極小的概率丟失部分數(shù)據(jù)是允許的，可用性更加重要。例如，Oracle數(shù)據(jù)庫的DataGuard復制組件包含三種模式：

• 最大保護模式(Maximum Protection)：即強同步復制模式，寫操作要求主庫先將操作日志(數(shù)據(jù)庫的redo/undo日志)同步到至少一個備庫才可以返回客戶端成功。這種模式保證即使主庫出現(xiàn)無法恢復的故障，比如硬盤損壞，也不會丟失數(shù)據(jù)。
• 最大性能模式(Maximum Performance)：即異步復制模式，寫操作只需要在主庫上執(zhí)行成功就可以返回客戶端成功，主庫上的后臺線程會將重做日志通過異步的方式復制到備庫。這種方式保證了性能和可用性，但是可能丟失數(shù)據(jù)。
• 最大可用性模式(Maximum Availability)：上述兩種模式的折衷。正常情況下相當于最大保護模式，如果主備之間的網(wǎng)絡出現(xiàn)故障，切換為最大性能模式。

容錯

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

首先，分布式存儲系統(tǒng)需要能夠檢測到機器故障，例如通過租約(Lease)協(xié)議實現(xiàn)。接著，需要能夠?qū)⒎諒椭苹蛘哌w移到集群中的其他正常服務的存儲節(jié)點。

故障檢測

容錯處理的第一步是故障檢測，心跳是一種很自然地想法。假設總控機A需要確認工作機B是否發(fā)生故障，那么總控機A每隔一段時間，比如1秒，向工作機B發(fā)送一個心跳包。如果一切正常，機器B將響應機器A的心跳包;否則，機器A重試了一定次數(shù)后認為機器B發(fā)生了故障。但是，機器A收不到機器B的心跳并不能確保機器B發(fā)生故障并停止了服務，比如可能是A和B之間出現(xiàn)網(wǎng)絡問題導致A收不到回復。由于在機器A“認為”機器B發(fā)生故障后，往往需要將它上面的服務遷移到集群中的其他服務器，為了保證強一致性，需要確保機器B不再提供服務。

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

故障恢復

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

單層結(jié)構(gòu)和雙層結(jié)構(gòu)如下圖所示：

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

兩層結(jié)構(gòu)的分布式存儲系統(tǒng)會將所有的數(shù)據(jù)持久化寫入底層的分布式文件系統(tǒng)，每個數(shù)據(jù)分片同一時刻只有一個提供服務的節(jié)點。如上圖所示，某雙層結(jié)構(gòu)的分布式存儲系統(tǒng)有3個數(shù)據(jù)分片，A、B和C。它們分別被節(jié)點1，節(jié)點2和節(jié)點3所服務。當節(jié)點1發(fā)生故障時，總控節(jié)點將選擇一個工作節(jié)點，比如節(jié)點2，加載A的服務。由于A的所有數(shù)據(jù)都存儲在共享的分布式文件系統(tǒng)中，節(jié)點2只需要從底層的分布式文件系統(tǒng)讀取A的數(shù)據(jù)并加載到內(nèi)存中。

可擴展性

同構(gòu)系統(tǒng)

同構(gòu)系統(tǒng)將存儲節(jié)點分為若干組，組內(nèi)的節(jié)點服務完全相同的數(shù)據(jù)，其中有一個節(jié)點為主節(jié)點，其他節(jié)點為備節(jié)點。由于同一個組內(nèi)的節(jié)點服務相同的數(shù)據(jù)，這樣的系統(tǒng)稱為同構(gòu)系統(tǒng)。如下圖所示。

同構(gòu)系統(tǒng)的問題在于增加副本需要遷移的數(shù)據(jù)量太大，假設每個存儲節(jié)點服務的數(shù)據(jù)量為1TB，內(nèi)部傳輸帶寬限制為20MB/s，那么增加副本拷貝數(shù)據(jù)需要的時間為1TB/20MB=50000s，大約十幾個小時，由于拷貝數(shù)據(jù)的過程中存儲節(jié)點再次發(fā)生故障的概率很高，所以這樣的架構(gòu)很難做到自動化，不適合大規(guī)模分布式存儲系統(tǒng)。

異構(gòu)系統(tǒng)

大規(guī)模分布式存儲系統(tǒng)要求具有線性可擴展性，即隨時加入或者刪除一個或者多個存儲節(jié)點，系統(tǒng)的處理能力與存儲節(jié)點的個數(shù)成線性關系。為了實現(xiàn)線性可擴展性，存儲系統(tǒng)的存儲節(jié)點之間是異構(gòu)的。

異構(gòu)系統(tǒng)將數(shù)據(jù)分為很多大小相近的分片，每個分片的多個副本可以分布到集群的任何一個存儲節(jié)點。如果某個節(jié)點發(fā)生故障，原有的服務將由整個集群而不是某幾個固定的存儲節(jié)點來恢復。

如下圖所示，系統(tǒng)中有五個分片(A，B，C，D，E)，每個分片包含三個副本，如分片A的三個副本分別為A1，A2以及A3。假如節(jié)點1發(fā)生永久性故障，那么可以從剩余的節(jié)點中任意挑選健康的節(jié)點來增加A，B以及E的副本。由于整個集群都參與到節(jié)點1的故障恢復過程，故障恢復時間很短，而且集群規(guī)模越大，優(yōu)勢越明顯。

分布式協(xié)議

分布式系統(tǒng)涉及的協(xié)議很多，例如租約，復制協(xié)議，一致性協(xié)議，其中以兩階段提交協(xié)議和Paxos協(xié)議最具有代表性。兩階段提交協(xié)議用于保證跨多個節(jié)點操作的原子性，也就是說，跨多個節(jié)點的操作要么在所有節(jié)點上全部執(zhí)行成功，要么全部失敗。Paxos協(xié)議用于確保多個節(jié)點對某個投票(例如哪個節(jié)點成為主節(jié)點)達成一致。

兩階段提交協(xié)議

兩階段提交協(xié)議(Two-phase Commit，2PC)經(jīng)常用來實現(xiàn)分布式事務，在兩階段提交協(xié)議中，系統(tǒng)一般包含兩類節(jié)點：一類為協(xié)調(diào)者(coordinator)，通常一個系統(tǒng)中只有一個;另一類為事務參與者(participants)，一般包含多個。顧名思義，兩階段提交協(xié)議由兩個階段組成，如下所述：

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

兩階段提交協(xié)議可能面臨兩種故障：

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

Paxos協(xié)議

Paxos協(xié)議用于解決多個節(jié)點之間的一致性問題。多個節(jié)點之間通過操作日志同步數(shù)據(jù)，如果只有一個節(jié)點為主節(jié)點，那么，很容易確保多個節(jié)點之間操作日志的一致性。考慮到主節(jié)點可能出現(xiàn)故障，系統(tǒng)需要選舉出新的主節(jié)點。Paxos協(xié)議正是用來實現(xiàn)這個需求。只要保證多個節(jié)點之間操作日志的一致性，就能夠在這些節(jié)點上構(gòu)建高可用的全局服務，例如分布式鎖服務，全局命名和配置服務等。

為了實現(xiàn)高可用，主節(jié)點往往將數(shù)據(jù)以操作日志的形式同步到備節(jié)點。如果主節(jié)點發(fā)生故障，備節(jié)點會提議自己成為主節(jié)點。這里存在的問題是網(wǎng)絡分區(qū)的時候，可能會存在多個備節(jié)點提議(Proposer，提議者)自己成為主節(jié)點。Paxos協(xié)議保證，即使同時存在多個proposer，也能夠保證所有節(jié)點最終達成一致，即選舉出唯一的主節(jié)點。

大多數(shù)情況下，系統(tǒng)只有一個proposer，他的提議也總是會很快被大多數(shù)節(jié)點接受。步驟如下：

1)批準(accept)：Proposer發(fā)送accept消息要求所有其他節(jié)點(acceptor，接受者)接受某個提議值，acceptor可以接受或者拒絕。

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

當出現(xiàn)網(wǎng)絡或者其他異常時，系統(tǒng)中可能存在多個Proposer，他們各自發(fā)起不同的提議。這里的提議可以是一個修改操作，也可以是提議自己成為主節(jié)點。如果proposer第一次發(fā)起的accept請求沒有被acceptor中的多數(shù)派批準(例如與其他proposer的提議沖突)，那么，需要完整地執(zhí)行一輪Paxos協(xié)議。過程如下：

1)準備(prepare)：Proposer首先選擇一個提議序號n給其他的acceptor節(jié)點發(fā)送prepare消息。Acceptor收到prepare消息后，如果提議的序號大于他已經(jīng)回復的所有prepare消息，則acceptor將自己上次接受的提議回復給proposer，并承諾不再回復小于n的提議。

2)批準(accept)：Proposer收到了acceptor中的多數(shù)派對于prepare的回復后，就進入批準階段。如果在之前的prepare階段acceptor回復了上次接受的提議，那么，proposer選擇其中序號最大的提議值發(fā)給acceptor批準;否則，proposer生成一個新的提議值發(fā)給acceptor批準。Acceptor在不違背他之前在prepare階段的承諾的前提下，接受這個請求。

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

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

Paxos與2PC

Paxos協(xié)議和2PC協(xié)議在分布式系統(tǒng)中所起的作用并不相同。Paxos協(xié)議用于保證同一個數(shù)據(jù)分片的多個副本之間的數(shù)據(jù)一致性。當這些副本分布到不同的數(shù)據(jù)中心時，這個需求尤其強烈。2PC協(xié)議用于保證多個數(shù)據(jù)分片上的操作的原子性。這些數(shù)據(jù)分片可能分布在不同的服務器上，2PC協(xié)議保證多臺服務器上的操作要么全部成功，要么全部失敗。

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

跨機房部署

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

1.集群整體切換

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

機房之間的數(shù)據(jù)同步方式可能為強同步或者異步。

如果采用異步模式，那么備用機房的數(shù)據(jù)總是落后于主機房。當主機房整體出現(xiàn)故障時，有兩種選擇：要么將服務切換到備機房，忍受數(shù)據(jù)丟失的風險;要么停止服務，直到主機房恢復為止。因此，主備切換往往是手工的，因為需要根據(jù)業(yè)務特點選擇“丟失數(shù)據(jù)”或者“停止服務”。

如果采用強同步模式，那么備機房的數(shù)據(jù)和主機房保持一致。當主機房出現(xiàn)故障時，可以通過分布式鎖服務發(fā)現(xiàn)，并自動將備用機房切換為主機房。

2.單個集群跨機房

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

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

3.Paxos選主副本

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

如果采用Paxos選主副本，那么，每個數(shù)據(jù)分片的多個副本構(gòu)成一個Paxos復制組。如下圖所示，B1、B2、B3、B4構(gòu)成一個復制組，某一時刻B1為復制組的主副本，當B1出現(xiàn)故障時，其他副本將嘗試切換為主副本，Paxos協(xié)議保證只有一個副本會成功。這樣，總控節(jié)點和工作節(jié)點之間不再需要保持租約，總控節(jié)點出現(xiàn)故障也不會對工作節(jié)點產(chǎn)生影響。

Google后續(xù)開發(fā)的系統(tǒng)，包括Google Megastore以及Spanner，都采用了這種方式。它的優(yōu)點在于能夠降低對總控節(jié)點的依賴，缺點在于工程復雜度太高，難以在線下模擬所有的異常情況。