分布式存儲系統(tǒng)中面臨著的首要問題就是如何將大量的數(shù)據(jù)分布在不同的存儲節(jié)點(diǎn)上，無論上層接口是KV存儲、對象存儲、塊存儲、亦或是列存儲，在這個(gè)問題上大體是一致的。本文將介紹在分布式存儲系統(tǒng)中做數(shù)據(jù)分布目標(biāo)及可選的方案，并試著總結(jié)他們之間的關(guān)系及權(quán)衡。

指標(biāo)

這里假設(shè)目標(biāo)數(shù)據(jù)是以key標(biāo)識的數(shù)據(jù)塊或?qū)ο螅谝粋€(gè)包含多個(gè)存儲節(jié)點(diǎn)的急群眾，數(shù)據(jù)分布算法需要為每一個(gè)給定的key指定一個(gè)或多個(gè)對應(yīng)的存儲節(jié)點(diǎn)負(fù)責(zé)，數(shù)據(jù)分布算法有兩個(gè)基本目標(biāo)：

[[213691]]

均勻性(Uniformity) ：不同存儲節(jié)點(diǎn)的負(fù)載應(yīng)該均衡；

穩(wěn)定性(Consistency)：每次一個(gè)key通過數(shù)據(jù)分布算法得到的分布結(jié)果應(yīng)該保持基本穩(wěn)定，即使再有存儲節(jié)點(diǎn)發(fā)生變化的情況下。

可以看出，這兩個(gè)目標(biāo)在一定程度上是相互矛盾的，當(dāng)有存儲節(jié)點(diǎn)增加或刪除時(shí)，為了保持穩(wěn)定應(yīng)該盡量少的進(jìn)行數(shù)據(jù)的移動和重新分配，而這樣又勢必會帶來負(fù)載不均。同樣追求***均勻也會導(dǎo)致較多的數(shù)據(jù)遷移。所以我們希望在這兩個(gè)極端之間找到一個(gè)點(diǎn)以獲得合適的均勻性和穩(wěn)定性。除了上述兩個(gè)基本目標(biāo)外，工程中還需要從以下幾個(gè)方面考慮數(shù)據(jù)分布算法的優(yōu)劣：

性能可擴(kuò)展性，這個(gè)主要考慮的是算法相對于存儲節(jié)點(diǎn)規(guī)模的時(shí)間復(fù)雜度，為了整個(gè)系統(tǒng)的可擴(kuò)展性，數(shù)據(jù)分布算法不應(yīng)該在集群規(guī)模擴(kuò)大后顯著的增加運(yùn)行時(shí)間。

考慮節(jié)點(diǎn)異構(gòu)，實(shí)際工程中，不同存儲節(jié)點(diǎn)之間可能會有很大的性能或容量差異，好的數(shù)據(jù)分布算法應(yīng)該能很好的應(yīng)對這種異構(gòu)，提供加權(quán)的數(shù)據(jù)均勻。

隔離故障域，為了數(shù)據(jù)的高可用，數(shù)據(jù)分布算法應(yīng)該沒每個(gè)key找到一組存儲節(jié)點(diǎn)，這些節(jié)點(diǎn)可能提供的是數(shù)據(jù)的鏡像副本，也可能是類似擦除碼的副本方式。數(shù)據(jù)分布算法應(yīng)該盡量隔離這些副本的故障域，如不同機(jī)房、不同機(jī)架、不同交換機(jī)、不同機(jī)器。

演進(jìn)

看完算法的評價(jià)指標(biāo)后，接下來介紹一些可能的方案演進(jìn)，并分析他們的優(yōu)劣。這里假設(shè)key的值足夠分散。

1，Hash

一個(gè)簡單直觀的想法是直接用Hash來計(jì)算，簡單的以Key做哈希后對節(jié)點(diǎn)數(shù)取模。可以看出，在key足夠分散的情況下，均勻性可以獲得，但一旦有節(jié)點(diǎn)加入或退出，所有的原有節(jié)點(diǎn)都會受到影響。 穩(wěn)定性無從談起。

2，一致性Hash

一致性Hash可以很好的解決穩(wěn)定問題，可以將所有的存儲節(jié)點(diǎn)排列在收尾相接的Hash環(huán)上，每個(gè)key在計(jì)算Hash后會順時(shí)針找到先遇到的一組存儲節(jié)點(diǎn)存放。而當(dāng)有節(jié)點(diǎn)加入或退出時(shí)，僅影響該節(jié)點(diǎn)在Hash環(huán)上順時(shí)針相鄰的后續(xù)節(jié)點(diǎn)，將數(shù)據(jù)從該節(jié)點(diǎn)接收或者給予。但這有帶來均勻性的問題，即使可以將存儲節(jié)點(diǎn)等距排列，也會在存儲節(jié)點(diǎn)個(gè)數(shù)變化時(shí)帶來數(shù)據(jù)的不均勻。而這種可能成倍數(shù)的不均勻在實(shí)際工程中是不可接受的。

3，帶負(fù)載上限的一致性Hash

一致性Hash有節(jié)點(diǎn)變化時(shí)不均勻的問題，Google在2017年提出了Consistent Hashing with Bounded Loads來控制這種不均勻的程度。簡單的說，該算法給Hash環(huán)上的每個(gè)節(jié)點(diǎn)一個(gè)負(fù)載上限為1 + e倍的平均負(fù)載，這個(gè)e可以自定義，當(dāng)key在Hash環(huán)上順時(shí)針找到合適的節(jié)點(diǎn)后，會判斷這個(gè)節(jié)點(diǎn)的負(fù)載是否已經(jīng)到達(dá)上限，如果已達(dá)上限，則需要繼續(xù)找之后的節(jié)點(diǎn)進(jìn)行分配。

如上圖所示，假設(shè)每個(gè)桶當(dāng)前上限是2，紅色的小球按序號訪問，當(dāng)編號為6的紅色小球到達(dá)時(shí)，發(fā)現(xiàn)順時(shí)針首先遇到的B（3，4），C（1，5）都已經(jīng)達(dá)到上限，因此最終放置在桶A。這個(gè)算法最吸引人的地方在于當(dāng)有節(jié)點(diǎn)變化時(shí)，需要遷移的數(shù)據(jù)量是1/e^2相關(guān)，而與節(jié)點(diǎn)數(shù)或數(shù)據(jù)數(shù)均無關(guān)，也就是說當(dāng)集群規(guī)模擴(kuò)大時(shí)，數(shù)據(jù)遷移量并不會隨著顯著增加。另外，使用者可以通過調(diào)整e的值來控制均勻性和穩(wěn)定性之間的權(quán)衡。無論是一致性Hash還是帶負(fù)載限制的一致性Hash都無法解決節(jié)點(diǎn)異構(gòu)的問題。

4，帶虛擬節(jié)點(diǎn)的一致性Hash

為了解決負(fù)載不均勻和異構(gòu)的問題，可以在一致性Hash的基礎(chǔ)上引入虛擬節(jié)點(diǎn)，即hash環(huán)上的每個(gè)節(jié)點(diǎn)并不是實(shí)際的存儲節(jié)點(diǎn)，而是一個(gè)虛擬節(jié)點(diǎn)。實(shí)際的存儲節(jié)點(diǎn)根據(jù)其不同的權(quán)重，對應(yīng)一個(gè)或多個(gè)虛擬節(jié)點(diǎn)，所有落到相應(yīng)虛擬節(jié)點(diǎn)上的key都由該存儲節(jié)點(diǎn)負(fù)責(zé)。如下圖所示，存儲節(jié)點(diǎn)A負(fù)責(zé)(1,3]，(4,8]，(10, 14]，存儲節(jié)點(diǎn)B負(fù)責(zé)(14,1]，(8,10]。

這個(gè)算法的問題在于，一個(gè)實(shí)際存儲節(jié)點(diǎn)的加入或退出，會影響多個(gè)虛擬節(jié)點(diǎn)的重新分配，進(jìn)而影響很多節(jié)點(diǎn)參與到數(shù)據(jù)遷移中來；另外，實(shí)踐中將一個(gè)虛擬節(jié)點(diǎn)重新分配給新的實(shí)際節(jié)點(diǎn)時(shí)需要將這部分?jǐn)?shù)據(jù)遍歷出來發(fā)送給新節(jié)點(diǎn)。我們需要一個(gè)跟合適的虛擬節(jié)點(diǎn)切分和分配方式，那就是分片。

5，分片

分片將哈希環(huán)切割為相同大小的分片，然后將這些分片交給不同的節(jié)點(diǎn)負(fù)責(zé)。注意這里跟上面提到的虛擬節(jié)點(diǎn)有著很本質(zhì)的區(qū)別，分片的劃分和分片的分配被解耦，一個(gè)節(jié)點(diǎn)退出時(shí)，其所負(fù)責(zé)的分片并不需要順時(shí)針合并給之后節(jié)點(diǎn)，而是可以更靈活的將整個(gè)分片作為一個(gè)整體交給任意節(jié)點(diǎn)，實(shí)踐中，一個(gè)分片多作為最小的數(shù)據(jù)遷移和備份單位。

而也正是由于上面提到的解耦，相當(dāng)于將原先的key到節(jié)點(diǎn)的映射拆成兩層，需要一個(gè)新的機(jī)制來進(jìn)行分片到存儲節(jié)點(diǎn)的映射，由于分片數(shù)相對key空間已經(jīng)很小并且數(shù)量確定，可以更精確地初始設(shè)置，并引入中心目錄服務(wù)來根據(jù)節(jié)點(diǎn)存活修改分片的映射關(guān)系，并將這個(gè)映射信息通知給所有的存儲節(jié)點(diǎn)和客戶端。

上圖是我們的分布式KV存儲Zeppelin中的分片方式，Key Space通過Hash到分片，分片極其副本又通過一層映射到最終的存儲節(jié)點(diǎn)Node Server。

6，CRUSH算法

CRUSH算法本質(zhì)上也是一種分片的數(shù)據(jù)分布方式，其試圖在以下幾個(gè)方面進(jìn)行優(yōu)化：

分片映射信息量：避免中心目錄服務(wù)和存儲節(jié)點(diǎn)及客戶端之間需要交互大量的分片映射信息，而改由存儲節(jié)點(diǎn)或客戶端自己根據(jù)少量且穩(wěn)定的集群節(jié)點(diǎn)拓?fù)浜痛_定的規(guī)則自己計(jì)算分片映射。

完善的故障域劃分：支持層級的故障域控制，將同一分片的不同副本按照配置劃分到不同層級的故障域中。

客戶端或存儲節(jié)點(diǎn)利用key、存儲節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)和分配算法，獨(dú)立進(jìn)行分片位置的計(jì)算，得到一組負(fù)責(zé)對應(yīng)分片及副本的存儲位置。如下圖所示是一次定位的過程，最終選擇了一個(gè)記下row下的cab21，cab23，cab24三個(gè)機(jī)柜下的三個(gè)存儲節(jié)點(diǎn)。

當(dāng)節(jié)點(diǎn)變化時(shí)，由于節(jié)點(diǎn)拓?fù)涞淖兓瑫绊懮倭糠制瑪?shù)據(jù)進(jìn)行遷移，如下圖新節(jié)點(diǎn)加入是引起的數(shù)據(jù)遷移，通過良好的分配算法，可以得到很好的負(fù)載均衡和穩(wěn)定性。

應(yīng)用

常見的存儲系統(tǒng)大多采用類似與分片的數(shù)據(jù)分布和定位方式。Dynamo及Cassandra采用分片的方式并通過gossip在對等節(jié)點(diǎn)間同步；Redis Cluster將key space劃分為slots，同樣利用gossip通信；Zeppelin將數(shù)據(jù)分片為Partition，通過Meta集群提供中心目錄服務(wù)；Bigtable將數(shù)據(jù)切割為Tablet，類似于可變的分片，Tablet Server可以進(jìn)行分片的切割，最終分片信息記錄在Chubby中；Ceph采用CRUSH方式，由中心集群Monitor維護(hù)并提供集群拓?fù)涞淖兓?/p>