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

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

[[207789]]

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

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

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

Amazon Dynamo

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

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

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

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

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

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

3、容錯

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

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

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

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

4、負(fù)載均衡

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

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

5、讀寫流程

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

圖1 Dynamo 寫入和讀取流程

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

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

淘寶Tair

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

1、整體架構(gòu)

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

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

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

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

3、容錯

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

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

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

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

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

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

Tair存儲引擎有一個抽象層，只要滿足存儲引擎需要的接口，就可以很方便地替換Tair底層的存儲引擎。

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