序言
分佈式系統面臨的第一個問題就是數據分佈，即將數據均勻地分佈到多個存儲節點。另外，為了保證可靠性和可用性，需要將數據複製多個副本，這就帶來了多個副本之間的數據一致性問題。大規模分佈式存儲系統的重要目標就是節省成本，因而只能採用性價比較高的PC服務器。這些服務器性能很好，但是故障率很高，要求系統能夠在軟件層面實現自動容錯。當存儲節點出現故障時，系統能夠自動檢測出來，並將原有的數據和服務遷移到集群中其他正常工作的節點。
分佈式系統中有兩個重要的協議，包括Paxos選舉協議以及兩階段提交協議。Paxos協議用於多個節點之間達成一致，往往用於實現總控節點選舉。兩階段提交協議用於保證跨多個節點操作的原子性，這些操作要麼全部成功，要麼全部失敗。理解了這兩個分佈式協議之後，學習其他分佈式協議會變得相當容易。
異常
在分佈式存儲系統中，往往將一臺服務器或者服務器上運行的一個進程稱為一個節點，節點與節點之間通過網絡互聯。大規模分佈式存儲系統的一個核心問題在於自動容錯。然而，服務器節點是不可靠的，網絡也是不可靠的，本節介紹系統運行過程中可能會遇到的各種異常。
1.異常類型
（1）服務器宕機
引發服務器宕機的原因可能是內存錯誤、服務器停電等。服務器宕機可能隨時發生，當發生宕機時，節點無法正常工作，稱為“不可用”（unavailable）。服務器重啟後，節點將失去所有的內存信息。因此，設計存儲系統時需要考慮如何通過讀取持久化介質（如機械硬盤，固態硬盤）中的數據來恢復內存信息，從而恢復到宕機前的某個一致的狀態。進程運行過程中也可能隨時因為core dump等原因退出，和服務器宕機一樣，進程重啟後也需要恢復內存信息。
（2）網絡異常
引發網絡異常的原因可能是消息丟失、消息亂序（如採用UDP方式通信）或者網絡包數據錯誤。有一種特殊的網絡異常稱為“網絡分區”，即集群的所有節點被劃分為多個區域，每個區域內部可以正常通信，但是區域之間無法通信。例如，某分佈式系統部署在兩個數據中心，由於網絡調整，導致數據中心之間無法通信，但是，數據中心內部可以正常通信。
設計容錯系統的一個基本原則是：網絡永遠是不可靠的，任何一個消息只有收到對方的回覆後才可以認為發送成功，系統設計時總是假設網絡將會出現異常並採取相應的處理措施。
（3）磁盤故障
磁盤故障是一種發生概率很高的異常。磁盤故障分為兩種情況：磁盤損壞和磁盤數據錯誤。磁盤損壞時，將會丟失存儲在上面的數據，因而，分佈式存儲系統需要考慮將數據存儲到多臺服務器，即使其中一臺服務器磁盤出現故障，也能從其他服務器上恢復數據。對於磁盤數據錯誤，往往可以採用校驗和（checksum）機制來解決，這樣的機制既可以在操作系統層面實現，又可以在上層的分佈式存儲系統層面實現。
（4）超時
由於網絡異常的存在，分佈式存儲系統中請求結果存在“三態”的概念。在單機系統中，只要服務器沒有發生異常，每個函數的執行結果是確定的，要麼成功，要麼失敗。然而，在分佈式系統中，如果某個節點向另外一個節點發起RPC（Remote Procedure Call）調用，這個RPC執行的結果有三種狀態：“成功”、“失敗”、“超時”（未知狀態），也稱為分佈式存儲系統的三態。
圖3-1給出了RPC執行成功但超時的例子。服務器（Server）收到併成功處理完成客戶端（Client）的請求，但是由於網絡異常或者服務器宕機，客戶端沒有收到服務器端的回覆。此時，RPC的執行結果為超時，客戶端不能簡單地認為服務器端處理失敗。
當出現超時狀態時，只能通過不斷讀取之前操作的狀態來驗證RPC操作是否成功。當然，設計分佈式存儲系統時可以將操作設計為“冪等”的，也就是說，操作執行一次與執行多次的結果相同，例如，覆蓋寫就是一種常見的冪等操作。如果採用這種設計，當出現失敗和超時時，都可以採用相同的處理方式，即一直重試直到成功。
一致性
由於異常的存在，分佈式存儲系統設計時往往會將數據冗餘存儲多份，每一份稱為一個副本（replica/copy）。這樣，當某一個節點出現故障時，可以從其他副本上讀到數據。可以這麼認為，副本是分佈式存儲系統容錯技術的唯一手段。由於多個副本的存在，如何保證副本之間的一致性是整個分佈式系統的理論核心。
可以從兩個角度理解一致性：第一個角度是用戶，或者說是客戶端，即客戶端讀寫操作是否符合某種特性；第二個角度是存儲系統，即存儲系統的多個副本之間是否一致，更新的順序是否相同，等等。
首先定義如下場景，這個場景包含三個組成部分：
●存儲系統：存儲系統可以理解為一個黑盒子，它為我們提供了可用性和持久性的保證。
●客戶端A：客戶端A主要實現從存儲系統write和read操作。
●客戶端B和客戶端C：客戶端B和C是獨立於A，並且B和C也相互獨立的，它們同時也實現對存儲系統的write和read操作。
從客戶端的角度來看，一致性包含如下三種情況：
●強一致性：假如A先寫入了一個值到存儲系統，存儲系統保證後續A,B，C的讀取操作都將返回最新值。當然，如果寫入操作“超時”，那麼成功或者失敗都是可能的，客戶端A不應該做任何假設。
●弱一致性：假如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的寫操作按順序完成，這就意味著，對於同一個客戶端的操作，存儲系統的多個副本需要按照與客戶端相同的順序完成。
從存儲系統的角度看，一致性主要包含如下幾個方面：
●副本一致性：存儲系統的多個副本之間的數據是否一致，不一致的時間窗口等；
●更新順序一致性：存儲系統的多個副本之間是否按照相同的順序執行更新操作。
一般來說，存儲系統可以支持強一致性，也可以為了性能考慮只支持最終一致性。從客戶端的角度看，一般要求存儲系統能夠支持讀寫一致性，會話一致性，單調讀，單調寫等特性，否則，使用比較麻煩，適用的場景也比較有限。
衡量指標
評價分佈式存儲系統有一些常用的指標，下面分別介紹。
（1）性能
常見的性能指標有：系統的吞吐能力以及系統的響應時間。其中，系統的吞吐能力指系統在某一段時間可以處理的請求總數，通常用每秒處理的讀操作數（QPS,Query Per Second）或者寫操作數（TPS,Transaction Per Second）來衡量；系統的響應延遲，指從某個請求發出到接收到返回結果消耗的時間，通常用平均延時或者99.9%以上請求的最大延時來衡量。這兩個指標往往是矛盾的，追求高吞吐的系統，往往很難做到低延遲；追求低延遲的系統，吞吐量也會受到限制。因此，設計系統時需要權衡這兩個指標。
（2）可用性
系統的可用性（availability）是指系統在面對各種異常時可以提供正常服務的能力。系統的可用性可以用系統停服務的時間與正常服務的時間的比例來衡量，例如某系統的可用性為4個9（99.99%），相當於系統一年停服務的時間不能超過365×24×60/10000=52.56分鐘。系統可用性往往體現了系統的整體代碼質量以及容錯能力。
3）一致性
3.1.2節說明了系統的一致性。一般來說，越是強的一致性模型，用戶使用起來越簡單。筆者認為，如果系統部署在同一個數據中心，只要系統設計合理，在保證強一致性的前提下，不會對性能和可用性造成太大的影響。後文中筆者在Alibaba參與開發的OceanBase系統以及Google的分佈式存儲系統都傾向強一致性。
4）可擴展性
系統的可擴展性（scalability）指分佈式存儲系統通過擴展集群服務器規模來提高系統存儲容量、計算量和性能的能力。隨著業務的發展，對底層存儲系統的性能需求不斷增加，比較好的方式就是通過自動增加服務器提高系統的能力。理想的分佈式存儲系統實現了“線性可擴展”，也就是說，隨著集群規模的增加，系統的整體性能與服務器數量呈線性關係。
性能分析
給定一個問題，往往會有多種設計方案，而方案評估的一個重要指標就是性能，如何在系統設計之初估算存儲系統的性能是存儲工程師的必備技能。性能分析用來判斷設計方案是否存在瓶頸點，權衡多種設計方案，另外，性能分析也可作為後續性能優化的依據。性能分析與性能優化是相對的，系統設計之初通過性能分析確定設計目標，防止出現重大的設計失誤，等到系統試運行後，需要通過性能優化方法找出系統中的瓶頸點並逐步消除，使得系統達到設計之初確定的設計目標。
性能分析的結果是不精確的，然而，至少可以保證，估算的結果與實際值不會相差一個數量級。設計之初首先分析整體架構，接著重點分析可能成為瓶頸的單機模塊。系統中的資源（CPU、內存、磁盤、網絡）是有限的，性能分析就是需要找出可能出現的資源瓶頸。本節通過幾個實例說明性能分析方法。
1.生成一張有30張縮略圖（假設圖片原始大小為256KB）的頁面需要多少時間？
●方案1：順序操作，每次先從磁盤中讀取圖片，再執行生成縮略圖操作，執行時間為：30×10ms（磁盤隨機讀取時間）+30×256K/30MB/s（假設縮略圖生成速度為30MB/s）=560ms
●方案2：並行操作，一次性發送30個請求，每個請求讀取一張圖片並生成縮略圖，執行時間為：10ms+256K/300MB/s=18ms
當然，系統實際運行的時候可能有緩存以及其他因素的干擾，這些因素在性能估算階段可以先不考慮，簡單地將估算結果乘以一個係數即為實際值。
2.1GB的4字節整數，執行一次快速排序需要多少時間？
Google的Jeff Dean提出了一種排序性能分析方法：排序時間=比較時間（分支預測錯誤）+內存訪問時間。快速排序過程中會發生大量的分支預測錯誤，所以比較次數為2_{28}×log（2_{28}）≈2_{33}，其中，約1/2的比較會發生分支預測錯誤，所以比較時間為1/2×2_{33}×5ns=21s，另外，快速排序每次分割操作都需要掃描一遍內存，假設內存順序訪問性能為4GB/s，所以內存訪問時間為28×1GB/4GB=7s。因此，單線程排序1GB 4字節整數總時間約為28s。
3.Bigtable系統性能分析
Bigtable是Google的分佈式表格系統，它的優勢是可擴展性好，可隨時增加或者減少集群中的服務器，但支持的功能有限，支持的操作主要包括：
●單行操作：基於主鍵的隨機讀取，插入，更新，刪除（CRUD）操作；
●多行掃描：掃描一段主鍵範圍內的數據。Bigtable中每行包括多個列，每一行的某一列對應一個數據單元，每個數據單元包括多個版本，可以按照列名或者版本對掃描結果進行過濾。
假設某類Bigtable系統的總體設計中給出的性能指標為：
●系統配置：同一個機架下40臺服務器（8核，24GB內存，10路15000轉SATA硬盤）；
●表格：每行數據1KB，64KB一個數據塊，不壓縮。
a）隨機讀取（緩存不命中）：1KB/item×300item/s=300KB/s
Bigtable系統中每次隨機讀取需要首先從GFS中讀取一個64KB的數據塊，經過CPU處理後返回用戶一行數據（大小為1KB）。因此，性能受限於GFS中ChunkServer（GFS系統中的工作節點）的磁盤IOPS以及Bigtable Tablet Server（Bigtable系統中的工作節點）的網絡帶寬。先看底層的GFS，每臺機器擁有10塊SATA盤，每塊SATA盤的IOPS約為100，因此，每臺機器的IOPS理論值約為1000，考慮到負載均衡等因素，將隨機讀取的QPS設計目標定為300，保留一定的餘量。另外，每臺機器每秒從GFS中讀取的數據量為300×64KB=19.2MB，由於所有的服務器分佈在同一個機架下，網絡不會成為瓶頸。
b）隨機讀取（內存表）：1KB/item×20000items/s=20MB/s
Bigtable中支持內存表，內存表的數據全部加載到內存中，讀取時不需要讀取底層的GFS。隨機讀取內存表的性能受限於CPU以及網絡，內存型服務的QPS一般在10W，由於網絡發送小數據有較多overhead且Bigtable內存操作有較多的CPU開銷，保守估計每個節點的QPS為20000，客戶端和Tablet Server之間的網絡流量為20MB/s。
c）隨機寫/順序寫：1KB/item×8000item/s=8MB/s
Bigtable中隨機寫和順序寫的性能是差不多的，寫入操作需要首先將操作日誌寫入到GFS，接著修改本地內存。為了提高性能，Bigtable實現了成組提示技術，即將很多寫操作湊成一批（比如512KB～2MB）一次性提交到GFS中。Bigtable每次寫一份數據需要在GFS系統中重複寫入3份到10份，當寫入速度達到8000 QPS，即8MB/s後Tablet Server的網絡將成為瓶頸。
d）掃描：1KB/item×30000item/s=30MB/s
Bigtable掃描操作一次性從GFS中讀取大量的數據（比如512KB～2MB），GFS的磁盤IO不會成為瓶頸。另外，批量操作減少了CPU以及網絡收發包的開銷，掃描操作的瓶頸在於Tablet Server讀取底層GFS的帶寬，估計為30MB/s，對應30000 QPS。
如果集群規模超過40臺，不能保證所有的服務器在同一個機架下，系統設計以及性能分析都會有所不同。性能分析可能會很複雜，因為不同情況下系統的瓶頸點不同，有的時候是網絡，有的時候是磁盤，有的時候甚至是機房的交換機或者CPU，另外，負載均衡以及其他因素的干擾也會使得性能更加難以量化。只有理解存儲系統的底層設計和實現，並在實踐中不斷地練習，性能估算才會越來越準。
數據分佈
分佈式系統區別於傳統單機系統在於能夠將數據分佈到多個節點，並在多個節點之間實現負載均衡。數據分佈的方式主要有兩種，一種是哈希分佈，如一致性哈希，代表系統為Amazon的Dynamo系統；另外一種方法是順序分佈，即每張表格上的數據按照主鍵整體有序，代表系統為Google的Bigtable系統。Bigtable將一張大表根據主鍵切分為有序的範圍，每個有序範圍是一個子表。
將數據分散到多臺機器後，需要儘量保證多臺機器之間的負載是比較均衡的。衡量機器負載涉及的因素很多，如機器Load值，CPU，內存，磁盤以及網絡等資源使用情況，讀寫請求數及請求量，等等，分佈式存儲系統需要能夠自動識別負載高的節點，當某臺機器的負載較高時，將它服務的部分數據遷移到其他機器，實現自動負載均衡。
分佈式存儲系統的一個基本要求就是透明性，包括數據分佈透明性，數據遷移透明性，數據複製透明性，故障處理透明性。本節介紹數據分佈以及數據遷移相關的基礎知識。
哈希分佈
哈希取模的方法很常見，其方法是根據數據的某一種特徵計算哈希值，並將哈希值與集群中的服務器建立映射關係，從而將不同哈希值的數據分佈到不同的服務器上。所謂數據特徵可以是key-value系統中的主鍵（key），也可以是其他與業務邏輯相關的值。例如，將集群中的服務器按0到N-1編號（N為服務器的數量），根據數據的主鍵（hash（key）%N）或者數據所屬的用戶id（hash（user_id）%N）計算哈希值，來決定將數據映射到哪一臺服務器。
如果哈希函數的散列特性很好，哈希方式可以將數據比較均勻地分佈到集群中去。而且，哈希方式需要記錄的元信息也非常簡單，每個節點只需要知道哈希函數的計算方式以及模的服務器的個數就可以計算出處理的數據應該屬於哪臺機器。然而，找出一個散列特性很好的哈希函數是很難的。這是因為，如果按照主鍵散列，那麼同一個用戶id下的數據可能被分散到多臺服務器，這會使得一次操作同一個用戶id下的多條記錄變得困難；如果按照用戶id散列，容易出現“數據傾斜”（data skew）問題，即某些大用戶的數據量很大，無論集群的規模有多大，這些用戶始終由一臺服務器處理。
傳統的哈希分佈算法還有一個問題：當服務器上線或者下線時，N值發生變化，數據映射完全被打亂，幾乎所有的數據都需要重新分佈，這將帶來大量的數據遷移。
一種思路是不再簡單地將哈希值和服務器個數做除法取模映射，而是將哈希值與服務器的對應關係作為元數據，交給專門的元數據服務器來管理。訪問數據時，首先計算哈希值，再查詢元數據服務器，獲得該哈希值對應的服務器。這樣，集群擴容時，可以將部分哈希值分配給新加入的機器並遷移對應的數據。
另一種思路就是採用一致性哈希（Distributed Hash Table,DHT）算法。算法思想如下：給系統中每個節點分配一個隨機token，這些token構成一個哈希環。執行數據存放操作時，先計算Key（主鍵）的哈希值，然後存放到順時針方向第一個大於或者等於該哈希值的token所在的節點。一致性哈希的優點在於節點加入/刪除時只會影響到在哈希環中相鄰的節點，而對其他節點沒影響。
●首先求出每個服務器的hash值，將其配置到一個0～2_{n}的圓環區間上；
●其次使用同樣的方法求出待存儲對象的主鍵哈希值，也將其配置到這個圓環上；
●然後從數據映射的位置開始順時針查找，將數據分佈到找到的第一個服務器節點。
增加服務節點5以後，某些原來分佈到節點3的數據需要遷移到節點5，其他數據分佈均保持不變。可以看出，一致性哈希算法在很大程度上避免了數據遷移。
為了查找集群中的服務器，需要維護每臺機器在哈希環中位置信息，常見的做法如下。
（1）O（1）位置信息
每臺服務器記錄它的前一個以及後一個節點的位置信息。這種做法的維護的節點位置信息的空間複雜度為O（1），然而每一次查找都可能遍歷整個哈希環中的所有服務器，即時間複雜度為O（N），其中，N為服務器數量。
（2）O（logN）位置信息
假設哈希空間為0～2_{n}（即N=2_{n}），以Chord系統為例，為了加速查找，它在每臺服務器維護了一個大小為n的路由表（finger table），FT^{P}[i]=succ（p+2_{i-1}），其中p為服務器在哈希環中的編號，路由表中的第i個元素記錄了編號為p+2_{i-1}的後繼節點。通過維護O（logN）的位置信息，查找的時間複雜度改進為O（logN）。
（3）O（N）位置信息
Dynamo系統通過犧牲空間換時間，在每臺服務器維護整個集群中所有服務器的位置信息，將查找服務器的時間複雜度降為O（1）。工程上一般都採用這種做法，Dynamo這樣的P2P系統在每個服務器節點上都維護了所有服務器的位置信息，而帶有總控節點的存儲系統往往由總控節點統一維護。
一致性哈希還需要考慮負載均衡，增加服務節點node5後，雖然隻影響到node5的後繼，即node3的數據分佈，但node3節點需要遷移的數據過多，整個集群的負載不均衡。一種自然的想法是將需要遷移的數據分散到整個集群，每臺服務器只需要遷移1/N的數據量。為此，Dynamo中引入虛擬節點的概念，5.1節會詳細討論。
順序分佈
希散列破壞了數據的有序性，只支持隨機讀取操作，不能夠支持順序掃描。某些系統可以在應用層做折衷，比如互聯網應用經常按照用戶來進行數據拆分，並通過哈希方法進行數據分佈，同一個用戶的數據分佈到相同的存儲節點，允許對同一個用戶的數據執行順序掃描，由應用層解決跨多個用戶的操作問題。另外，這種方式可能出現某些用戶的數據量太大的問題，由於用戶的數據限定在一個存儲節點，無法發揮分佈式存儲系統的多機並行處理能力。
順序分佈在分佈式表格系統中比較常見，一般的做法是將大表順序劃分為連續的範圍，每個範圍稱為一個子表，總控服務器負責將這些子表按照一定的策略分配到存儲節點上。如圖3-3所示，用戶表（User表）的主鍵範圍為1～7000，在分佈式存儲系統中劃分為多個子表，分別對應數據範圍1～1000，1001～2000，……6001～7000。Meta表是可選的，某些系統只有根表（Root表）一級索引，在Root表中維護用戶表的位置信息，即每個User子表在哪個存儲節點上。為了支持更大的集群規模，Bigtable這樣的系統將索引分為兩級：根表以及元數據表（Meta表），由Meta表維護User表的位置信息，而Root表用來維護Meta表的位置信息。讀User表時，需要通過Meta表查找相應的User子表所在的存儲節點，而讀取Meta表又需要通過Root表查找相應的Meta子表所在的存儲節點。
順序分佈與B+樹數據結構比較類似，每個子表相當於葉子節點，隨著數據的插入和刪除，某些子表可能變得很大，某些變得很小，數據分佈不均勻。如果採用順序分佈，系統設計時需要考慮子表的分裂與合併，這將極大地增加系統複雜度。子表分裂指當一個子表太大超過一定閥值時需要分裂為兩個子表，從而有機會通過系統的負載均衡機制分散到多個存儲節點。子表合併一般由數據刪除引起，當相鄰的兩個子表都很小時，可以合併為一個子表。一般來說，單個服務節點能夠服務的子表數量是有限的，比如4000～10000個，子表合併的目的是為了防止系統中出現過多太小的子表，減少系統中的元數據。
負載均衡
分佈式存儲系統的每個集群中一般有一個總控節點，其他節點為工作節點，由總控節點根據全局負載信息進行整體調度。工作節點剛上線時，總控節點需要將數據遷移到該節點，另外，系統運行過程中也需要不斷地執行遷移任務，將數據從負載較高的工作節點遷移到負載較低的工作節點。
工作節點通過心跳包（Heartbeat，定時發送）將節點負載相關的信息，如CPU，內存，磁盤，網絡等資源使用率，讀寫次數及讀寫數據量等發送給主控節點。主控節點計算出工作節點的負載以及需要遷移的數據，生成遷移任務放入遷移隊列中等待執行。需要注意的是，負載均衡操作需要控制節奏，比如一臺全新的工作節點剛上線的時候，由於負載最低，如果主控節點將大量的數據同時遷移到這臺新加入的機器，整個系統在新增機器的過程中服務能力會大幅下降。負載均衡操作需要做到比較平滑，一般來說，從新機器加入到集群負載達到比較均衡的狀態需要較長一段時間，比如30分鐘到一個小時。
負載均衡需要執行數據遷移操作。在分佈式存儲系統中往往會存儲數據的多個副本，其中一個副本為主副本，其他副本為備副本，由主副本對外提供服務。遷移備副本不會對服務造成影響，遷移主副本也可以首先將數據的讀寫服務切換到其他備副本。整個遷移過程可以做到無縫，對用戶完全透明。
假設數據分片D有兩個副本D1和D2，分別存儲在工作節點A1和A2，其中，D1為主副本，提供讀寫服務，D2為備副本。如果需要將D1從工作節點A1中遷移出去，大致的操作步驟如下：
1）將數據分片D的讀寫服務由工作節點A1切換到A2，D2變成主副本；
2）增加副本：選擇某個節點，例如B節點，增加D的副本，即B節點從A2節點獲取D的副本數據（D2）並與之保持同步；
3）刪除工作節點A1上的D1副本。
複製
為了保證分佈式存儲系統的高可靠和高可用，數據在系統中一般存儲多個副本。當某個副本所在的存儲節點出現故障時，分佈式存儲系統能夠自動將服務切換到其他的副本，從而實現自動容錯。分佈式存儲系統通過複製協議將數據同步到多個存儲節點，並確保多個副本之間的數據一致性。
同一份數據的多個副本中往往有一個副本為主副本（Primary），其他副本為備副本（Backup），由主副本將數據複製到備份副本。複製協議分為兩種，強同步複製以及異步複製，二者的區別在於用戶的寫請求是否需要同步到備副本才可以返回成功。假如備份副本不止一個，複製協議還會要求寫請求至少需要同步到幾個備副本。當主副本出現故障時，分佈式存儲系統能夠將服務自動切換到某個備副本，實現自動容錯。
一致性和可用性是矛盾的，強同步複製協議可以保證主備副本之間的一致性，但是當備副本出現故障時，也可能阻塞存儲系統的正常寫服務，系統的整體可用性受到影響；異步複製協議的可用性相對較好，但是一致性得不到保障，主副本出現故障時還有數據丟失的可能。
複製的概述
分佈式存儲系統中數據保存多個副本，一般來說，其中一個副本為主副本，其他副本為備副本，常見的做法是數據寫入到主副本，由主副本確定操作的順序並複製到其他副本。
如圖3-4所示，客戶端將寫請求發送給主副本，主副本將寫請求複製到其他備副本，常見的做法是同步操作日誌（Commit Log）。主副本首先將操作日誌同步到備副本，備副本回放操作日誌，完成後通知主副本。接著，主副本修改本機，等到所有的操作都完成後再通知客戶端寫成功。圖3-4中的複製協議要求主備同步成功才可以返回客戶端寫成功，這種協議稱為強同步協議。強同步協議提供了強一致性，但是，如果備副本出現問題將阻塞寫操作，系統可用性較差。
假設所有副本的個數為N，且N＞2，即備副本個數大於1。那麼，實現強同步協議時，主副本可以將操作日誌併發地發給所有備副本並等待回覆，只要至少1個備副本返回成功就可以回覆客戶端操作成功。強同步的好處在於如果主副本出現故障，至少有1個備副本擁有完整的數據，分佈式存儲系統可以自動地將服務切換到最新的備副本而不用擔心數據丟失的情況。
與強同步對應的複製方式是異步複製。在異步模式下，主副本不需要等待備副本的迴應，只需要本地修改成功就可以告知客戶端寫操作成功。另外，主副本通過異步機制，比如單獨的複製線程將客戶端修改操作推送到其他副本。異步複製的好處在於系統可用性較好，但是一致性較差，如果主副本發生不可恢復故障，可能丟失最後一部分更新操作。
強同步複製和異步複製都是將主副本的數據以某種形式發送到其他副本，這種複製協議稱為基於主副本的複製協議（Primary-based protocol）。這種方法要求在任何時刻只能有一個副本為主副本，由它來確定寫操作之間的順序。如果主副本出現故障，需要選舉一個備副本成為新的主副本，這步操作稱為選舉，經典的選舉協議為Paxos協議，3.7.2節將專門進行介紹。
主備副本之間的複製一般通過操作日誌來實現。操作日誌的原理很簡單：為了利用好磁盤的順序讀寫特性，將客戶端的寫操作先順序寫入到磁盤中，然後應用到內存中，由於內存是隨機讀寫設備，可以很容易通過各種數據結構，比如B+樹將數據有效地組織起來。當服務器宕機重啟時，只需要回放操作日誌就可以恢復內存狀態。為了提高系統的併發能力，系統會積攢一定的操作日誌再批量寫入到磁盤中，這種技術一般稱為成組提交。
如果每次服務器出現故障都需要回放所有的操作日誌，效率是無法忍受的，檢查點（checkpoint）正是為了解決這個問題。系統定期將內存狀態以檢查點文件的形式dump到磁盤中，並記錄檢查點時刻對應的操作日誌回放點。檢查點文件成功創建後，回放點之前的日誌可以被垃圾回收，以後如果服務器出現故障，只需要回放檢查點之後的操作日誌。
除了基於主副本的複製協議，分佈式存儲系統中還可能使用基於寫多個存儲節點的複製協議（Replicated-write protocol）。比如Dynamo系統中的NWR複製協議，其中，N為副本數量，W為寫操作的副本數，R為讀操作的副本數。NWR協議中多個副本不再區分主和備，客戶端根據一定的策略往其中的W個副本寫入數據，讀取其中的R個副本。只要W+R＞N，可以保證讀到的副本中至少有一個包含了最新的更新。然而，這種協議的問題在於不同副本的操作順序可能不一致，從多個副本讀取時可能出現衝突。這種方式在實際系統中比較少見，不建議使用。
一致性與可用性
來自Berkerly的Eric Brewer教授提出了一個著名的CAP理論：一致性（Consistency），可用性（Availability）以及分區可容忍性（Tolerance of network Partition）三者不能同時滿足。筆者認為沒有必要糾結CAP理論最初的定義，在工程實踐中，可以將C、A、P三者按如下方式理解：
●一致性：讀操作總是能讀取到之前完成的寫操作結果，滿足這個條件的系統稱為強一致系統，這裡的“之前”一般對同一個客戶端而言；
●可用性：讀寫操作在單臺機器發生故障的情況下仍然能夠正常執行，而不需要等待發生故障的機器重啟或者其上的服務遷移到其他機器；
●分區可容忍性：機器故障、網絡故障、機房停電等異常情況下仍然能夠滿足一致性和可用性。
分佈式存儲系統要求能夠自動容錯，也就是說，分區可容忍性總是需要滿足的，因此，一致性和寫操作的可用性不能同時滿足。
如果採用強同步複製，保證了存儲系統的一致性，然而，當主備副本之間出現網絡或者其他故障時，寫操作將被阻塞，系統的可用性無法得到滿足。如果採用異步複製，保證了存儲系統的可用性，但是無法做到強一致性。
存儲系統設計時需要在一致性和可用性之間權衡，在某些場景下，不允許丟失數據，在另外一些場景下，極小的概率丟失部分數據時允許的，可用性更加重要。例如，Oracle數據庫的DataGuard複製組件包含三種模式：
●最大保護模式（Maximum Protection）：即強同步複製模式，寫操作要求主庫先將操作日誌（數據庫的redo/undo日誌）同步到至少一個備庫才可以返回客戶端成功。這種模式保證即使主庫出現無法恢復的故障，比如硬盤損壞，也不會丟失數據。
●最大性能模式（Maximum Performance）：即異步複製模式，寫操作只需要在主庫上執行成功就可以返回客戶端成功，主庫上的後臺線程會將重做日誌通過異步的方式複製到備庫。這種方式保證了性能及可用性，但是可能丟失數據。
●最大可用性模式（Maximum Availability）：上述兩種模式的折衷。正常情況下相當於最大保護模式，如果主備之間的網絡出現故障，切換為最大性能模式。這種模式在一致性和可用性之間做了一個很好的權衡，推薦大家在設計存儲系統時使用。
容錯
隨著集群規模變得越來越大，故障發生的概率也越來越大，大規模集群每天都有故障發生。容錯是分佈式存儲系統設計的重要目標，只有實現了自動化容錯，才能減少人工運維成本，實現分佈式存儲的規模效應。
單臺服務器故障的概率是不高的，然而，只要集群的規模足夠大，每天都可能有機器故障發生，系統需要能夠自動處理。首先，分佈式存儲系統需要能夠檢測到機器故障，在分佈式系統中，故障檢測往往通過租約（Lease）協議實現。接著，需要能夠將服務複製或者遷移到集群中的其他正常服務的存儲節點。
本節首先介紹Google某數據中心發生的故障，接著討論分佈式系統中的故障檢測以及恢復方法。
可擴展性
通過數據分佈，複製以及容錯等機制，能夠將分佈式存儲系統部署到成千上萬臺服務器。可擴展性的實現手段很多，如通過增加副本個數或者緩存提高讀取能力，將數據分片使得每個分片可以被分配到不同的工作節點以實現分佈式處理，把數據複製到多個數據中心，等等。
分佈式存儲系統大多都帶有總控節點，很多人會自然地聯想到總控節點的瓶頸問題，認為P2P架構更有優勢。然而，事實卻並非如此，主流的分佈式存儲系統大多帶有總控節點，且能夠支持成千上萬臺的集群規模。
另外，傳統的數據庫也能夠通過分庫分表等方式對系統進行水平擴展，當系統處理能力不足時，可以通過增加存儲節點來擴容。
那麼，如何衡量分佈式存儲系統的可擴展性，它與傳統數據庫的可擴展性又有什麼區別？可擴展性不能簡單地通過系統是否為P2P架構或者是否能夠將數據分佈到多個存儲節點來衡量，而應該綜合考慮節點故障後的恢復時間，擴容的自動化程度，擴容的靈活性等。
本節首先討論總控節點是否會成為性能瓶頸，接著介紹傳統數據庫的可擴展性，最後討論同構系統與異構系統增加節點時的差別。
總控節點
分佈式存儲系統中往往有一個總控節點用於維護數據分佈信息，執行工作機管理，數據定位，故障檢測和恢復，負載均衡等全局調度工作。通過引入總控節點，可以使得系統的設計更加簡單，並且更加容易做到強一致性，對用戶友好。那麼，總控節點是否會成為性能瓶頸呢？
分為兩種情況：分佈式文件系統的總控節點除了執行全局調度，還需要維護文件系統目錄樹，內存容量可能會率先成為性能瓶頸；而其他分佈式存儲系統的總控節點只需要維護數據分片的位置信息，一般不會成為瓶頸。另外，即使是分佈式文件系統，只要設計合理，也能夠擴展到幾千臺服務器。例如，Google的分佈式文件系統能夠擴展到8000臺以上的集群，開源的Hadoop也能夠擴展到3000臺以上的集群。當然，設計時需要減少總控節點的負載，比如Google的GFS捨棄了對小文件的支持，並且把對數據的讀寫控制權下放到工作機ChunkServer，通過客戶端緩存元數據減少對總控節點的訪問等。
如果總控節點成為瓶頸，例如需要支持超過一萬臺的集群規模，或者需要支持海量的小文件，那麼，可以採用兩級結構，如圖3-6所示。在總控機與工作機之間增加一層元數據節點，每個元數據節點只維護一部分而不是整個分佈式文件系統的元數據。這樣，總控機也只需要維護元數據節點的元數據，不可能成為性能瓶頸。假設分佈式文件系統（Distributed File System,DFS）中有100個元數據節點，每個元數據節點服務1億個文件，系統總共可以服務100億個文件。圖3-6中的DFS客戶端定位DFS工作機時，需要首先訪問DFS總控機找到DFS元數據服務器，再通過元數據服務器找到DFS工作機。雖然看似增加了一次網絡請求，但是客戶端總是能夠緩存DFS總控機上的元數據，因此並不會帶來額外的開銷。
異構系統
傳統數據庫擴容與大規模存儲系統的可擴展性有何區別呢？為了說明這一問題，我們首先定義同構系統，如圖3-8所示。
將存儲節點分為若干組，每個組內的節點服務完全相同的數據，其中有一個節點為主節點，其他節點為備節點。由於同一個組內的節點服務相同的數據，這樣的系統稱為同構系統。同構系統的問題在於增加副本需要遷移的數據量太大，假設每個存儲節點服務的數據量為1TB，內部傳輸帶寬限制為20MB/s，那麼增加副本拷貝數據需要的時間為1TB/20MB/s=50000s，大約十幾個小時，由於拷貝數據的過程中存儲節點再次發生故障的概率很高，所以這樣的架構很難做到自動化，不適用大規模分佈式存儲系統。
大規模分佈式存儲系統要求具有線性可擴展性，即隨時加入或者刪除一個或者多個存儲節點，系統的處理能力與存儲節點的個數成線性關係。為了實現線性可擴展性，存儲系統的存儲節點之間是異構的。否則，當集群規模達到一定程度後，增加節點將變得特別困難。異構系統將數據劃分為很多大小接近的分片，每個分片的多個副本可以分佈到集群中的任何一個存儲節點。如果某個節點發生故障，原有的服務將由整個集群而不是某幾個固定的存儲節點來恢復。
如圖3-9所示，系統中有五個分片（A,B,C,D,E），每個分片包含三個副本，如分片A的三個副本分別為A1，A2以及A3。假設節點1發生永久性故障，那麼可以從剩餘的節點中任意選擇健康的節點來增加A,B以及E的副本。由於整個集群都參與到節點1的故障恢復過程，故障恢復時間很短，而且集群規模越大，優勢就會越明顯。
分佈式協議
分佈式系統涉及的協議很多，例如租約，複製協議，一致性協議，其中以兩階段提交協議和Paxos協議最具有代表性。兩階段提交協議用於保證跨多個節點操作的原子性，也就是說，跨多個節點的操作要麼在所有節點上全部執行成功，要麼全部失敗。Paxos協議用於確保多個節點對某個投票（例如哪個節點為主節點）達成一致。本節介紹這兩個分佈式協議。
兩階段提交協議
兩階段提交協議（Two-phase Commit，2PC）經常用來實現分佈式事務，在兩階段協議中，系統一般包含兩類節點：一類為協調者（coordinator），通常一個系統中只有一個；另一類為事務參與者（participants,cohorts或workers），一般包含多個。協議中假設每個節點都會記錄操作日誌並持久化到非易失性存儲介質，即使節點發生故障日誌也不會丟失。顧名思義，兩階段提交協議由兩個階段組成。在正常的執行過程中，這兩個階段的執行過程如下所述：
●階段1：請求階段（Prepare Phase）。在請求階段，協調者通知事務參與者準備提交或者取消事務，然後進入表決過程。在表決過程中，參與者將告知協調者自己的決策：同意（事務參與者本地執行成功）或者取消（事務參與者本地執行失敗）
●階段2：提交階段（Commit Phase）。在提交階段，協調者將基於第一個階段的投票結果進行決策：提交或者取消。當且僅當所有的參與者同意提交事務協調者才通知所有的參與者提交事務，否則協調者通知所有的參與者取消事務。參與者在接收到協調者發來的消息後將執行相應的操作。
例如，A組織B、C和D三個人去爬長城：如果所有人都同意去爬長城，那麼活動將舉行；如果有一人不同意去爬長城，那麼活動將取消。用2PC算法解決該問題的過程如下：
1）首先A將成為該活動的協調者，B、C和D將成為該活動的參與者。
2）準備階段：A發郵件給B、C和D，提出下週三去爬山，問是否同意。那麼此時A需要等待B、C和D的回覆。B、C和D分別查看自己的日程安排表。B、C發現自己在當日沒有活動安排，則發郵件告訴A他們同意下週三去爬長城。由於某種原因，D白天沒有查看郵件。那麼此時A、B和C均需要等待。到晚上的時候，D發現了A的郵件，然後查看日程安排，發現下週三當天已經有別的安排，那麼D回覆A說活動取消吧。
3）此時A收到了所有活動參與者的郵件，並且A發現D下週三不能去爬山。那麼A將發郵件通知B、C和D，下週三爬長城活動取消。此時B、C回覆A“太可惜了”，D回覆A“不好意思”。至此該事務終止。
通過該例子可以發現，2PC協議存在明顯的問題。假如D一直不能回覆郵件，那麼A、B和C將不得不處於一直等待的狀態。並且B和C所持有的資源一直不能釋放，即下週三不能安排其他活動。當然，A可以發郵件告訴D如果晚上六點之前不回覆活動就自動取消，通過引入事務的超時機制防止資源一直不能釋放的情況。更為嚴重的是，假如A發完郵件後生病住院了，即使B、C和D都發郵件告訴A同意下週三去爬長城，如果A沒有備份，事務將被阻塞，B、C和D下週三都不能安排其他活動。
兩階段提交協議可能面臨兩種故障：
●事務參與者發生故障。給每個事務設置一個超時時間，如果某個事務參與者一直不響應，到達超時時間後整個事務失敗。
●協調者發生故障。協調者需要將事務相關信息記錄到操作日誌並同步到備用協調者，假如協調者發生故障，備用協調者可以接替它完成後續的工作。如果沒有備用協調者，協調者又發生了永久性故障，事務參與者將無法完成事務而一直等待下去。
總而言之，兩階段提交協議是阻塞協議，執行過程中需要鎖住其他更新，且不能容錯，大多數分佈式存儲系統都採用敬而遠之的做法，放棄對分佈式事務的支持。
總結
以上是對分佈式系統，分享給大家，希望大家可以瞭解什麼是分佈式系統。覺得收穫的話可以點個關注收藏轉發一波喔，謝謝大佬們支持。（吹一波，233~~）
