淺談分布式存儲(chǔ)系統(tǒng)數(shù)據(jù)分布方法

作者：佚名 2017-12-18 10:47:04

存儲(chǔ)

存儲(chǔ)軟件

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

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到堯都網(wǎng)站設(shè)計(jì)與堯都網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站建設(shè)、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、主機(jī)域名、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋堯都地區(qū)。

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

指標(biāo)

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

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

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

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

性能可擴(kuò)展性，這個(gè)主要考慮的是算法相對(duì)于存儲(chǔ)節(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í)際工程中，不同存儲(chǔ)節(jié)點(diǎn)之間可能會(huì)有很大的性能或容量差異，好的數(shù)據(jù)分布算法應(yīng)該能很好的應(yīng)對(duì)這種異構(gòu)，提供加權(quán)的數(shù)據(jù)均勻。

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

演進(jìn)

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

1，Hash

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

2，一致性Hash

一致性Hash可以很好的解決穩(wěn)定問(wèn)題，可以將所有的存儲(chǔ)節(jié)點(diǎn)排列在收尾相接的Hash環(huán)上，每個(gè)key在計(jì)算Hash后會(huì)順時(shí)針找到先遇到的一組存儲(chǔ)節(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)接收或者給予。但這有帶來(lái)均勻性的問(wèn)題，即使可以將存儲(chǔ)節(jié)點(diǎn)等距排列，也會(huì)在存儲(chǔ)節(jié)點(diǎn)個(gè)數(shù)變化時(shí)帶來(lái)數(shù)據(jù)的不均勻。而這種可能成倍數(shù)的不均勻在實(shí)際工程中是不可接受的。

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

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

如上圖所示，假設(shè)每個(gè)桶當(dāng)前上限是2，紅色的小球按序號(hào)訪問(wèn)，當(dāng)編號(hào)為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ù)均無(wú)關(guān)，也就是說(shuō)當(dāng)集群規(guī)模擴(kuò)大時(shí)，數(shù)據(jù)遷移量并不會(huì)隨著顯著增加。另外，使用者可以通過(guò)調(diào)整e的值來(lái)控制均勻性和穩(wěn)定性之間的權(quán)衡。無(wú)論是一致性Hash還是帶負(fù)載限制的一致性Hash都無(wú)法解決節(jié)點(diǎn)異構(gòu)的問(wèn)題。

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

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

這個(gè)算法的問(wèn)題在于，一個(gè)實(shí)際存儲(chǔ)節(jié)點(diǎn)的加入或退出，會(huì)影響多個(gè)虛擬節(jié)點(diǎn)的重新分配，進(jìn)而影響很多節(jié)點(diǎn)參與到數(shù)據(jù)遷移中來(lái)；另外，實(shí)踐中將一個(gè)虛擬節(jié)點(diǎn)重新分配給新的實(shí)際節(jié)點(diǎn)時(shí)需要將這部分?jǐn)?shù)據(jù)遍歷出來(lái)發(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ī)制來(lái)進(jìn)行分片到存儲(chǔ)節(jié)點(diǎn)的映射，由于分片數(shù)相對(duì)key空間已經(jīng)很小并且數(shù)量確定，可以更精確地初始設(shè)置，并引入中心目錄服務(wù)來(lái)根據(jù)節(jié)點(diǎn)存活修改分片的映射關(guān)系，并將這個(gè)映射信息通知給所有的存儲(chǔ)節(jié)點(diǎn)和客戶端。

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

6，CRUSH算法

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

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

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

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

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

應(yīng)用

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