定義

分布式存儲系統是大量普通PC服務器通過Internet互聯，對外作為一個整體提供存儲服務

分類

• 非結構化數據，一般的文檔
• 結構化數據， 存儲在關系數據庫中
• 半結構化數據，HTML文檔

不同的分布式存儲系統適合處理不同類型的數據：

分布式文件系統

• 非結構化數據，這類數據以對象的形式組織，不同對象之間沒有關聯，這樣的數據一般稱為Blob(二進制大對象)數據
• 典型的有Facebook Haystack 以及 Taobao File System
• 另外，分布式文件系統也常作為分布式表格系統以及分布式數據庫的底層存儲，如谷歌的GFS可以作為分布式表格系統Google Bigtable 的底層存儲，Amazon的EBS(彈性存儲塊)系統可以作為分布式數據庫(Amazon RDS)的底層存儲
• 總體上看，分布式文件系統存儲三種類型的數據：Blob對象、定長塊以及大文件

[[245104]]

分布式鍵值系統

• 較簡單的半結構化數據，只提供主鍵的CRUD(創建、讀取、更新、刪除)
• 典型的有Amazon Dynamo 以及 Taobao Tair

分布式表格系統

• 較復雜的半結構化數據，不僅支持CRUD，而且支持掃描某個主鍵范圍
• 以表格為單位組織數據，每個表格包括很多行，通過主鍵標識一行，支持根據主鍵的CRUD功能以及范圍查找功能
• 典型的有Google Bigtable 以及 Megastore，Microsoft Azure Table Storage，Amazon DynamoDB等

分布式數據庫

• 存儲結構化數據，一般是由單機關系數據庫擴展而來
• 典型的包括MySQL數據庫分片集群、Amazon RDS以及Microsoft SQL Azure

問題域

分布式存儲解決的是單機存儲的性能, 單點故障問題, 容量一開始到還在其次, 但隨著應用規模的發展, 要解決容量也得必須分布式了.

• 分布式存儲解決容量問題即可擴展性的方式, 就是數據分片. 可擴展性是分布式的已經解決的問題, 任何關于分布式存儲的現存問題的討論, 都不會再涉及可擴展性.
• 數據分片也能部分的解決性能問題. 而解決性能問題的方法還包括數據復制.
• 分布式存儲解決單點故障問題的手段, 也許是唯一的手段, 就是復制.
• 而復制會帶來一致性問題.

鑒于解決容量問題的手段并沒有引入新問題, 因而如果要實現一種分布式存儲機制, 需解決或者需平衡的是性能(或者說可用性), 單點故障(或者說分區容忍性), 及一致性

基礎結構

分層，一般是兩到三層

• ***層分布式文件系統, 解決數據分塊，復制, 讀寫等需求
• 往上是數據結構層, 解決數據模型, CAP取舍等
• 再往上是更高層API, 解決諸如事物等問題

實現關注點

數據分布策略

考慮因素包括讀寫場景, 即隨機還是順序, 包括如何保證負載均衡從而提高性能等

• 哈希分布, 一致性哈希等
• 順序分布

一致性策略

• 強一致性: 強一致性(即時一致性) 假如A先寫入了一個值到存儲系統，存儲系統保證后續A,B,C的讀取操作都將返回***值
• 弱一致性: 假如A先寫入了一個值到存儲系統，存儲系統不能保證后續A,B,C的讀取操作能讀取到***值。此種情況下有一個“不一致性窗口”的概念，它特指從A寫入值，到后續操作A,B,C讀取到***值這一段時間。
• 最終一致性: 最終一致性是弱一致性的一種特例。假如A首先write了一個值到存儲系統，存儲系統保證如果在A,B,C后續讀取之前沒有其它寫操作更新同樣的值的話，最終所有的讀取操作都會讀取到最A寫入的***值。此種情況下，如果沒有失敗發生的話，“不一致性窗口”的大小依賴于以下的幾個因素：交互延遲，系統的負載，以及復制技術中replica的個數(這個可以理解為master/salve模式中，salve的個數)，最終一致性方面最出名的系統可以說是DNS系統，當更新一個域名的IP以后，根據配置策略以及緩存控制策略的不同，最終所有的客戶都會看到***的值。

最終一致性變體

• Causal consistency(因果一致性): 如果Process A通知Process B它已經更新了數據，那么Process B的后續讀取操作則讀取A寫入的***值，而與A沒有因果關系的C則可以最終一致性。
• Read-your-writes consistency : 如果Process A寫入了***的值，那么Process A的后續操作都會讀取到***值。但是其它用戶可能要過一會才可以看到。
• Session consistency : 此種一致性要求客戶端和存儲系統交互的整個會話階段保證Read-your-writes consistency.Hibernate的session提供的一致性保證就屬于此種一致性。
• Monotonic read consistency : 此種一致性要求如果Process A已經讀取了對象的某個值，那么后續操作將不會讀取到更早的值。
• Monotonic write consistency : 此種一致性保證系統會序列化執行一個Process中的所有寫操作。

故障監控策略

• 租約
• 心跳

集群管理策略

• 主控, Paxos協議
• 點對點

分布式事務策略

• 兩階段提交協議

數據模型

• 表
• kv
• 文檔
• 列族
• 圖

列族和文檔在某種程度上是存儲模型, 而不是對外的接口模型. 列式存儲更適合olap，列族則是對存取性能的優化

查詢方式

• SQL
• 主鍵
• path
• 索引
• 聚合

領域語言

CAP理論

當分布式存儲網絡中有一臺機器與其它機器的連接斷開了, 但與客戶的連接還在, 即依然有讀寫請求進來, 那么:

• 如果返回本機上存儲的結果, 則保證了AP, 犧牲了C, 即依然在有限時間內返回了響應給請求, 依然沒有停止服務, 但不保證結果是正確的
• 如果告訴客戶無法完成請求, 則保證了AC, 犧牲了P, 即依然在有限時間內返回了響應給請求, 并保證結果要么是正確的, 要么沒結果, 但停止了服務
• 如果一直等待網絡連接恢復, 則保證了CP, 犧牲了A, 即依然提供服務, 依然保證返回正確的結果, 但不保證讀寫操作是可終止的.

一致性哈希

在傳統的哈希表中，添加或刪除一個節點幾乎需要對所有關鍵字進行重新映射(對N取模變成了對N-1或N+1取模, 影響大了)。而Hash算法的一個衡量指標是單調性( Monotonicity )，定義如下：

• 單調性是指如果已經有一些內容通過哈希分派到了相應的節點中，又有新的節點加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的節點中去，而不會被映射到舊的節點集合中的其他節點區。

一致性哈希是一種特殊的哈希算法。在使用一致哈希算法后，哈希表節點數(大小)的改變平均只需要對K/n 個關鍵字重新映射，其中 K是關鍵字的數量，n是節點數量。

向量時鐘

當系統中存在同一份數據的多份副本時, 如何決定更新順序, 處理更新沖突成了一個問題, 因為不存在一個全局時鐘(存在的話, 我們就可以在每次更新時記錄全局時鐘值, 這樣的話就有明確的先后順序). 因此我們需要發明一種在分布式環境下有明確順序定義的機制. 傳統的順序定義通過版本來定義(時鐘只是版本的一種實現手段). 將版本的概念擴展到分布式環境下時, 我們便得到了向量時鐘: 對于同一份數據的N份副本, 都獨立維護自己的一個版本號, 這些版本號合在一起, 組成一個N個元素的vector, 作為該數據的版本. 每個節點都維護這樣一個vector, 初值可能都是0, 每次更新數據時, 一起更新vector中對應自己節點的那個版本號, 然后將vector和被更新的數據一起傳播給其它節點. 這樣每個節點都可以據此來發現更新沖突。

租約協議

租約主要用來解決心跳的誤會問題. 在通常的集群系統中，我們采用心跳來檢測節點狀態。但普通的心跳機制存在誤報警的可能. 普通心跳通常是在規定的時限內定期向檢測節點發送存活性報告，若超出一段時間未能收到心跳報告，那么檢測節點則判斷節點可能失效，并采取一系列措施(報警、通知節點的使用者)。這種機制存在的問題是，檢測節點單方面判定節點失效，在某些業務集群系統中可能存在風險。節點自身并未認識自己已被認定失效，還在繼續提供正常的服務。若該節點在集群中承擔唯一 primary 節點的職責，而檢測節點的失效判定發起了重新選擇新的主節點，會引發“雙主”問題。

租約是一種雙方協議, 通常定義為：頒發者在一定期限內給予持有者一定權利的協議. 它表達了頒發者在一定期限內的承諾，只要未過期頒發者必須嚴格遵守 lease 約定的承諾。而 lease 的持有者可以在期限內使用頒發者的承諾，但 lease 一旦過期必須放棄使用或者重新和頒發者續約。

租約過期前必須向頒發者續約才能繼續使用, 因此若因為各種原因續約未果, 則使用者必須放棄租約規定的權利, 而頒發者可以將該權利頒發給其它節點.

lease 作為一種協議承諾，其承諾的范圍十分寬泛:

• 如果協議內容是確認客戶端存活，那么這個租約就相當于心跳。
• 如果協議內容是保證內容不會被修改，那么這個租約就相當于讀鎖。
• 如果協議內容是保證只能被某個客戶端修改，那么這個租約就相當于寫鎖。

Paxos協議

Paxos是一個分布式選舉算法, ***的用途就是保持多個節點數據的一致性. 基于消息傳遞通信模型的分布式系統，不可避免的會發生以下錯誤：進程可能會慢、垮、重啟，消息可能會延遲、丟失、重復，在基礎 Paxos 場景中，先不考慮可能出現消息篡改的情況。Paxos 算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。

一個典型的場景是，在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們***能得到一個一致的狀態。這里的問題在于: 為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個“一致性算法”以保證每個節點看到的指令一致。Paxos就是這么一種”一致性算法”

為描述 Paxos 算法，其提出者Lamport 虛擬了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人愿意將自己的全部時間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務員都不能承諾別人需要時一定會出現，也無法承諾批準決議或者傳遞消息的時間。但是這里假設沒有拜占庭將軍問題(Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息);只要等待足夠的時間，消息就會被傳到。另外，Paxos 島上的議員是不會反對其他議員提出的決議的。

對應于分布式系統，議員對應于各個節點，制定的法律對應于系統的狀態。各個節點需要進入一個一致的狀態，例如在獨立Cache的對稱多處理器系統中，各個處理器讀內存的某個字節時，必須讀到同樣的一個值，否則系統就違背了一致性的要求。一致性要求對應于法律條文只能有一個版本。議員和服務員的不確定性對應于節點和消息傳遞通道的不可靠性。

具體算法, 可參考網絡資料

NWR

NWR是一種在分布式存儲系統中用于控制一致性級別的策略。其中，N代表同一份數據的Replica的份數，W是更新一個數據對象時需要確保成功更新的份數;R代表讀取一個數據需要讀取的Replica的份數。

• R = N 或者 W = N, 強一致性, 弱可用性, 即所有副本數據完全一致才認為成功.
• W + R < N, 強可用性, 弱一致性
• W < N, R < N, 但 W + R > N, 比較均衡的可用性和一致性
• W + R > N，保證某個數據不被兩個不同的事務同時讀和寫
• W > N / 2, 保證兩個事務不能并發寫某一個數據

常用實現技巧

• 將隨機讀寫轉化為順序讀寫：操作日志+內存修改+定期刷盤 (先寫日志再更新內存)
• 批量提交，成組提交：增加了延遲，但提高了吞吐量
• 從A寫從B讀才會有一致性問題, 總是從一個入口讀寫，通過復制和自動選舉來解決可靠性可用性, 這是傳統熱備數據庫集群的思路. Mongo是主從結構, 但用戶只能與主節點打交道, 主節點宕機后自動選舉新主偏重CA, 類似傳統熱備數據庫集群
• 實體組, Entity Group, Aggregate Root: Megastore創新點之一是提出了實體組的概念, 用于融合RDBMS(實體組內)和Nosql(實體組間)的優點
• 將更新的記錄單獨存放: OceanBase通過分離基線和更新使寫操作的負擔戲劇性的降到單機可以承受的量，從而兼得了一致性和可靠性可用性
• 分離需要加鎖和可以并發的操作, 比如寫操作并發優化：分離占位和拷貝, 占位加鎖，拷貝不需，前提是位置不沖突