定義

分布式存儲系統(tǒng)是大量普通PC服務器通過Internet互聯(lián)，對外作為一個整體提供存儲服務

分類

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

不同的分布式存儲系統(tǒng)適合處理不同類型的數(shù)據(jù)：

分布式文件系統(tǒng)

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

[[245104]]

分布式鍵值系統(tǒng)

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

分布式表格系統(tǒng)

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

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

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

問題域

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

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

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

基礎結構

分層，一般是兩到三層

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

實現(xiàn)關注點

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

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

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

一致性策略

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

最終一致性變體

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

故障監(jiān)控策略

• 租約
• 心跳

集群管理策略

• 主控, Paxos協(xié)議
• 點對點

分布式事務策略

• 兩階段提交協(xié)議

數(shù)據(jù)模型

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

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

查詢方式

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

領域語言

CAP理論

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

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

一致性哈希

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

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

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

向量時鐘

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

租約協(xié)議

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

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

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

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

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

Paxos協(xié)議

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

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

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

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

具體算法, 可參考網(wǎng)絡資料

NWR

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

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

常用實現(xiàn)技巧

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