深度解讀分布式存儲(chǔ)技術(shù)之分布式剪枝系統(tǒng)

　　　分布式存儲(chǔ)簡(jiǎn)單的來(lái)說(shuō)，就是將數(shù)據(jù)分散存儲(chǔ)到多個(gè)數(shù)據(jù)存儲(chǔ)存儲(chǔ)服務(wù)器上。分布式存儲(chǔ)目前多借鑒Google的經(jīng)驗(yàn)，在眾多的服務(wù)器搭建一個(gè)分布式文件系統(tǒng)，再在這個(gè)分布式文件系統(tǒng)上實(shí)現(xiàn)相關(guān)的數(shù)據(jù)存儲(chǔ)業(yè)務(wù)，甚至是再實(shí)現(xiàn)二級(jí)存儲(chǔ)業(yè)務(wù)如Bigtable。

???????? 分布式文件系統(tǒng)存儲(chǔ)目標(biāo)以非結(jié)構(gòu)化數(shù)據(jù)為主，但在實(shí)際應(yīng)用中，存在大量的結(jié)構(gòu)化和半結(jié)構(gòu)化的數(shù)據(jù)存儲(chǔ)需求。分布式鍵值系統(tǒng)是一種有別于我們所熟悉的分布式數(shù)據(jù)庫(kù)系統(tǒng)的，用于存儲(chǔ)關(guān)系簡(jiǎn)單的半結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)應(yīng)用。

　　在分布式鍵值系統(tǒng)中，半結(jié)構(gòu)化數(shù)據(jù)被封裝成由《key，value，timestamp》鍵值對(duì)組成的對(duì)象，其中key為唯一標(biāo)示符;value為屬性值，可以為任何類(lèi)型，如文字、圖片，也可以為空;timestamp為時(shí)間戳，可以提供數(shù)據(jù)的多版本支持。分布式鍵值系統(tǒng)以鍵值對(duì)存儲(chǔ)，它的結(jié)構(gòu)不固定，每一元組可以有不一樣的字段，可根據(jù)需要增加鍵值對(duì)，從而不局限于固定的結(jié)構(gòu)，適用面更大，可擴(kuò)展性更好。

　　分布式鍵值系統(tǒng)支持針對(duì)單個(gè)《key，value，timestamp》鍵值對(duì)的增、刪、查、改操作，可以運(yùn)行在PC服務(wù)器集群上，并實(shí)現(xiàn)集群按需擴(kuò)展，從而處理大規(guī)模數(shù)據(jù)，并通過(guò)數(shù)據(jù)備份保障容錯(cuò)性，避免了分割數(shù)據(jù)帶來(lái)的復(fù)雜性和成本。

　　總體來(lái)說(shuō)，分布式鍵值系統(tǒng)從存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的角度看，分布式鍵值系統(tǒng)與傳統(tǒng)的哈希表比較類(lèi)似，不同的是，分布式鍵值系統(tǒng)支持將數(shù)據(jù)分布到集群中的多個(gè)存儲(chǔ)節(jié)點(diǎn)。分布式鍵值系統(tǒng)可以配置數(shù)據(jù)的備份數(shù)目，可以將一份數(shù)據(jù)的所有副本存儲(chǔ)到不同的節(jié)點(diǎn)上，當(dāng)有節(jié)點(diǎn)發(fā)生異常無(wú)法正常提供服務(wù)時(shí)，其余的節(jié)點(diǎn)會(huì)繼續(xù)提供服務(wù)。

　　下面，我們來(lái)看看業(yè)界主流的分布式鍵值系統(tǒng)的架構(gòu)模式。

　　Amazon Dynamo

　　Dynamo是AWS上最基礎(chǔ)的分布式存儲(chǔ)應(yīng)用之一，也是AWS最早推出的云服務(wù)之一，它構(gòu)建在AWS的S3基礎(chǔ)之上，采用去中心節(jié)點(diǎn)化的P2P方式，采用這種模式的，還有Facebook推出的Cassandra。

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

　　Dynamo使用了改進(jìn)的一致性哈希算法：每個(gè)物理節(jié)點(diǎn)根據(jù)其性能的差異分配多個(gè)token，每個(gè)token對(duì)應(yīng)一個(gè)“虛擬節(jié)點(diǎn)”。所有節(jié)點(diǎn)每隔固定時(shí)間（比如1s）通過(guò)Gossip協(xié)議的方式從其他節(jié)點(diǎn)中任意選擇一個(gè)與之通信的節(jié)點(diǎn)。如果連接成功，雙方交換各自保存的集群信息。

　　Gossip協(xié)議用于P2P系統(tǒng)中自治的節(jié)點(diǎn)協(xié)調(diào)對(duì)整個(gè)集群的認(rèn)識(shí)，比如集群的節(jié)點(diǎn)狀態(tài)、負(fù)載情況。由于種子節(jié)點(diǎn)的存在，新節(jié)點(diǎn)加入可以做得比較簡(jiǎn)單：新節(jié)點(diǎn)加入時(shí)首先與種子節(jié)點(diǎn)交換集群信息，從而了解整個(gè)集群。

　　2、一致性與復(fù)制

　　一般來(lái)說(shuō)，從機(jī)器K+i宕機(jī)開(kāi)始到被認(rèn)定為永久失效的時(shí)間不會(huì)太長(zhǎng)，積累的寫(xiě)操作也不會(huì)太多，可以利用Merkle樹(shù)對(duì)機(jī)器的數(shù)據(jù)文件進(jìn)行快速同步。Dynamo引入向量時(shí)鐘（Vector lock）的技術(shù)手段來(lái)嘗試解決沖突，這個(gè)策略依賴(lài)集群內(nèi)節(jié)點(diǎn)之間的時(shí)鐘同步算法，但不能完全保證準(zhǔn)確性。Dynamo只保證最終一致性，如果多個(gè)節(jié)點(diǎn)之間的更新順序不一致，客戶(hù)端可能讀取不到期望的結(jié)果。

　　3、容錯(cuò)

　　核心機(jī)制就是：數(shù)據(jù)回傳+Merkle樹(shù)同步+讀取修復(fù)

　　Dynamo在數(shù)據(jù)讀寫(xiě)中采用了一種稱(chēng)為弱quorum （Sloppy quorum）的機(jī)制，涉及三個(gè)參數(shù)W、R、N，見(jiàn)其中W代表一次成功的寫(xiě)操作至少需要寫(xiě)入的副本數(shù)，R代表一次成功讀操作需由服務(wù)器返回給用戶(hù)的最小副本數(shù)，N是每個(gè)數(shù)據(jù)存儲(chǔ)的副本數(shù)。Dynamo要求R+W〉N，滿(mǎn)足這個(gè)要求，保證用戶(hù)讀取數(shù)據(jù)時(shí)，始終可以獲得一個(gè)最新的數(shù)據(jù)版本。

　　針對(duì)臨時(shí)故障，一旦某個(gè)節(jié)點(diǎn)出現(xiàn)問(wèn)題，則將這個(gè)節(jié)點(diǎn)值傳送給“同組”中的下一個(gè)正常節(jié)點(diǎn)，并在這個(gè)數(shù)據(jù)副本的元數(shù)據(jù)中記錄失效的節(jié)點(diǎn)位置，便于數(shù)據(jù)回傳;然后，由這個(gè)節(jié)點(diǎn)上一個(gè)臨時(shí)空間進(jìn)行存儲(chǔ)和處理數(shù)據(jù)，同時(shí)該節(jié)點(diǎn)還對(duì)失效的節(jié)點(diǎn)進(jìn)行監(jiān)測(cè)，一旦失效的節(jié)點(diǎn)重新可用，則將自己所保存的最新數(shù)據(jù)回傳給它，然后刪除自己開(kāi)辟的臨時(shí)空間數(shù)據(jù)。

　　針對(duì)永久性故障，Dynamo必須檢査和保持?jǐn)?shù)據(jù)的同步 ，Dynamo采用一種稱(chēng)為反熵協(xié)議的手段來(lái)保證數(shù)據(jù)的同步。為了減少數(shù)據(jù)同步檢測(cè)中需要傳輸?shù)臄?shù)據(jù)量，加快檢測(cè)速度，Dynamo使用了Merkle哈希樹(shù)技術(shù)，每個(gè)虛擬節(jié)點(diǎn)保存三顆Merkle樹(shù)，即每個(gè)鍵值區(qū)間建立一個(gè)Merkle樹(shù)。Dynamo中Merkle哈希樹(shù)的葉子節(jié)點(diǎn)是存儲(chǔ)每個(gè)數(shù)據(jù)分區(qū)內(nèi)所有數(shù)據(jù)對(duì)應(yīng)的哈希值，父節(jié)點(diǎn)是其所有子節(jié)點(diǎn)的哈希值。

　　4、負(fù)載均衡

　　采用改進(jìn)的一致性Hash+虛擬節(jié)點(diǎn)模式。

　　在傳統(tǒng)的一致性哈希算法上，服務(wù)節(jié)點(diǎn)跟哈希環(huán)上的點(diǎn)是一一對(duì)應(yīng)的。這里會(huì)存在一個(gè)問(wèn)題，就是每一個(gè)節(jié)點(diǎn)的負(fù)載最后是不均勻的，而我們也無(wú)法進(jìn)行調(diào)整。Dynamo通過(guò)一個(gè)服務(wù)節(jié)點(diǎn)可以有多個(gè)哈希環(huán)上的虛擬節(jié)點(diǎn)的方法，使得每一個(gè)服務(wù)節(jié)點(diǎn)的負(fù)載都是均勻的。并且假如發(fā)現(xiàn)了某一個(gè)節(jié)點(diǎn)的負(fù)載過(guò)高，少分配虛擬節(jié)點(diǎn)給它便可以降低該服務(wù)節(jié)點(diǎn)的負(fù)載，從而實(shí)現(xiàn)了自動(dòng)地負(fù)載均衡。

　　5、讀寫(xiě)流程

　　由于采用了去中心化的模式，因此，需要采用較復(fù)雜的模式來(lái)控制并發(fā)，Dynamo使用Paxos協(xié)議結(jié)合Gossip來(lái)進(jìn)行并發(fā)處理。具體處理模式如圖1所示。

　　圖1 Dynamo 寫(xiě)入和讀取流程

　　Dynamo采用去中心節(jié)點(diǎn)的P2P設(shè)計(jì)，增加了系統(tǒng)可擴(kuò)展性，但同時(shí)帶來(lái)了一致性問(wèn)題，影響上層應(yīng)用。一致性問(wèn)題使得異常情況下的測(cè)試變得更加困難，由于Dynamo只保證最基本的最終一致性，多客戶(hù)端并發(fā)操作的時(shí)候很難預(yù)測(cè)操作結(jié)果，也很難預(yù)測(cè)不一致的時(shí)間窗口，影響測(cè)試用例設(shè)計(jì)。

　　由于去中心化模式所導(dǎo)致的復(fù)雜性和不確定性。目前主流的分布式系統(tǒng)一般都帶有中心節(jié)點(diǎn)，這樣能夠簡(jiǎn)化設(shè)計(jì)，而且中心節(jié)點(diǎn)只維護(hù)少量元數(shù)據(jù)，一般不會(huì)成為性能瓶頸。

　　淘寶Tair

　　Tair是阿里巴巴推出的一個(gè)高性能，分布式，可擴(kuò)展，高可靠的key/value結(jié)構(gòu)存儲(chǔ)系統(tǒng)，它專(zhuān)門(mén)針對(duì)小文件的存儲(chǔ)做了優(yōu)化，并提供簡(jiǎn)單易用的接口（類(lèi)似Map）。

　　1、整體架構(gòu)

　　Tair作為一個(gè)分布式系統(tǒng)，是由一個(gè)中心控制節(jié)點(diǎn)和若干個(gè)服務(wù)節(jié)點(diǎn)組成。Config Server是控制點(diǎn)，而且是單點(diǎn)，目前采用一主一備的形式來(lái)保證可靠性，所有的Data Server地位都是等價(jià)的。

　　圖2 Tair系統(tǒng)架構(gòu)

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

　　Tair根據(jù)數(shù)據(jù)的主鍵計(jì)算哈希值后，分布到Q個(gè)桶中，根據(jù)Dynamo論文中的實(shí)驗(yàn)結(jié)論，Q取值需要遠(yuǎn)大于集群的物理機(jī)器數(shù)，例如Q取值102400。

　　3、容錯(cuò)

　　如果是備副本，則直接遷移;如果是主副本，則先切換再遷移。

　　4、數(shù)據(jù)遷移

　　機(jī)器加入或者負(fù)載不均衡可能導(dǎo)致桶遷移，遷移的過(guò)程中需要保證對(duì)外服務(wù)。當(dāng)遷移發(fā)生時(shí)，假設(shè)Data Server A要把桶1、2、3遷移到Data Server B。遷移完成前，客戶(hù)端的路由表沒(méi)有變化，客戶(hù)端對(duì)1、2、3的訪問(wèn)請(qǐng)求都會(huì)路由到A?，F(xiàn)在假設(shè)1還沒(méi)開(kāi)始遷移，2正在遷移中，3已經(jīng)遷移完成。那么如果對(duì)1訪問(wèn)，A直接服務(wù);如果對(duì)3訪問(wèn)，A會(huì)把請(qǐng)求轉(zhuǎn)發(fā)給B，并且將B的返回結(jié)果返回給用戶(hù);如果對(duì)2訪問(wèn)，由A處理，同時(shí)如果是對(duì)2的修改操作，會(huì)記錄修改日志，等到桶2遷移完成時(shí)，還要把修改日志發(fā)送到B，在B上應(yīng)用這些修改操作，直到A和B之間數(shù)據(jù)完全一致遷移才真正完成。

　　5、配置服務(wù)器（Config Server）

　　客戶(hù)端緩存路由表，大多數(shù)情況下，客戶(hù)端不需要訪問(wèn)配置服務(wù)器（Config Server），Config Server宕機(jī)也不影響客戶(hù)端正常訪問(wèn)。如果Data Server發(fā)現(xiàn)客戶(hù)端的版本號(hào)過(guò)舊，則會(huì)通知客戶(hù)端去Config Server獲取一份新的路由表。如果客戶(hù)端訪問(wèn)某臺(tái)Data Server發(fā)生了不可達(dá)的情況（該Data Server可能宕機(jī)了），客戶(hù)端會(huì)主動(dòng)去Config Server獲取新的路由表。

　　6、數(shù)據(jù)服務(wù)器（Data Server）

　　Tair存儲(chǔ)引擎有一個(gè)抽象層，只要滿(mǎn)足存儲(chǔ)引擎需要的接口，就可以很方便地替換Tair底層的存儲(chǔ)引擎。

　　Tair最主要的用途在于分布式緩存，持久化存儲(chǔ)起步比較晚，在實(shí)現(xiàn)細(xì)節(jié)上也有一些不盡如人意的地方。例如，Tair持久化存儲(chǔ)通過(guò)復(fù)制技術(shù)來(lái)提高可靠性，然而，這種復(fù)制是異步的。因此，當(dāng)有Data Server發(fā)生故障時(shí)，客戶(hù)有可能在一定時(shí)間內(nèi)讀不到最新的數(shù)據(jù)，甚至發(fā)生最新修改的數(shù)據(jù)丟失的情況。