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

指標(biāo)

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

[[213691]]

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

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

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

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

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

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

演進(jìn)

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

1，Hash

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

2，一致性Hash

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

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

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

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

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

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

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

5，分片

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

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

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

6，CRUSH算法

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

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

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

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

當(dāng)節(jié)點變化時，由于節(jié)點拓?fù)涞淖兓?，會影響少量分片?shù)據(jù)進(jìn)行遷移，如下圖新節(jié)點加入是引起的數(shù)據(jù)遷移，通過良好的分配算法，可以得到很好的負(fù)載均衡和穩(wěn)定性。

應(yīng)用

常見的存儲系統(tǒng)大多采用類似與分片的數(shù)據(jù)分布和定位方式。Dynamo及Cassandra采用分片的方式并通過gossip在對等節(jié)點間同步；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>