定義

分布式存儲(chǔ)系統(tǒng)是大量普通PC服務(wù)器通過(guò)Internet互聯(lián)，對(duì)外作為一個(gè)整體提供存儲(chǔ)服務(wù)

分類

• 非結(jié)構(gòu)化數(shù)據(jù)，一般的文檔
• 結(jié)構(gòu)化數(shù)據(jù)， 存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中
• 半結(jié)構(gòu)化數(shù)據(jù)，HTML文檔

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

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

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

[[245104]]

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

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

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

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

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

• 存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)，一般是由單機(jī)關(guān)系數(shù)據(jù)庫(kù)擴(kuò)展而來(lái)
• 典型的包括MySQL數(shù)據(jù)庫(kù)分片集群、Amazon RDS以及Microsoft SQL Azure

問(wèn)題域

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

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

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

基礎(chǔ)結(jié)構(gòu)

分層，一般是兩到三層

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

實(shí)現(xiàn)關(guān)注點(diǎn)

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

考慮因素包括讀寫(xiě)場(chǎng)景, 即隨機(jī)還是順序, 包括如何保證負(fù)載均衡從而提高性能等

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

一致性策略

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

最終一致性變體

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

故障監(jiān)控策略

• 租約
• 心跳

集群管理策略

• 主控, Paxos協(xié)議
• 點(diǎn)對(duì)點(diǎn)

分布式事務(wù)策略

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

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

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

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

查詢方式

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

領(lǐng)域語(yǔ)言

CAP理論

當(dāng)分布式存儲(chǔ)網(wǎng)絡(luò)中有一臺(tái)機(jī)器與其它機(jī)器的連接斷開(kāi)了, 但與客戶的連接還在, 即依然有讀寫(xiě)請(qǐng)求進(jìn)來(lái), 那么:

• 如果返回本機(jī)上存儲(chǔ)的結(jié)果, 則保證了AP, 犧牲了C, 即依然在有限時(shí)間內(nèi)返回了響應(yīng)給請(qǐng)求, 依然沒(méi)有停止服務(wù), 但不保證結(jié)果是正確的
• 如果告訴客戶無(wú)法完成請(qǐng)求, 則保證了AC, 犧牲了P, 即依然在有限時(shí)間內(nèi)返回了響應(yīng)給請(qǐng)求, 并保證結(jié)果要么是正確的, 要么沒(méi)結(jié)果, 但停止了服務(wù)
• 如果一直等待網(wǎng)絡(luò)連接恢復(fù), 則保證了CP, 犧牲了A, 即依然提供服務(wù), 依然保證返回正確的結(jié)果, 但不保證讀寫(xiě)操作是可終止的.

一致性哈希

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

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

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

向量時(shí)鐘

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

租約協(xié)議

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

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

租約過(guò)期前必須向頒發(fā)者續(xù)約才能繼續(xù)使用, 因此若因?yàn)楦鞣N原因續(xù)約未果, 則使用者必須放棄租約規(guī)定的權(quán)利, 而頒發(fā)者可以將該權(quán)利頒發(fā)給其它節(jié)點(diǎn).

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

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

Paxos協(xié)議

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

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

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

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

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

NWR

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

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

常用實(shí)現(xiàn)技巧

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