[[188561]]

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

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

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

基本概念

異常

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

服務(wù)器宕機(jī)

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

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

網(wǎng)絡(luò)異常

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

磁盤故障

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

超時(shí)

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

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

一致性

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

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

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

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

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

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

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

衡量指標(biāo)

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

性能

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

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

可用性

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

一致性

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

可擴(kuò)展性

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

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

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

哈希分布

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

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

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

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

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

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

順序分布

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

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

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

負(fù)載均衡

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

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

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

復(fù)制

復(fù)制的概述

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

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

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

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

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

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

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

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

一致性與可用性

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

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

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

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

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

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

容錯(cuò)

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

首先，分布式存儲系統(tǒng)需要能夠檢測到機(jī)器故障，例如通過租約(Lease)協(xié)議實(shí)現(xiàn)。接著，需要能夠?qū)⒎?wù)復(fù)制或者遷移到集群中的其他正常服務(wù)的存儲節(jié)點(diǎn)。

故障檢測

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

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

故障恢復(fù)

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

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

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

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

可擴(kuò)展性

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

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

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

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

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

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

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

分布式協(xié)議

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

兩階段提交協(xié)議

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

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

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

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

Paxos協(xié)議

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

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

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

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

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

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

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

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

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

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

Paxos與2PC

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

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

跨機(jī)房部署

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

1.集群整體切換

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

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

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

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

2.單個(gè)集群跨機(jī)房

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

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

3.Paxos選主副本

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

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

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