目錄

前言

指標

演進

應用案例

---

前言

分布式存儲系統面臨著的首要問題，就是如何將大量的數據分布在不同的存儲節點上。無論上層接口是 KV存儲、對象存儲、塊存儲、亦或是列存儲，在這個問題上大體是一致的。本文將介紹如何分布式存儲系統中做數據分布目標及可選的方案，并試著總結和權衡他們之間的關系及優缺點。

?

?

指標

這里假設目標數據是以?key 標識的數據塊或對象。在一個包含多個存儲節點的集群中，數據分布算法需要為每一個給定的?key 指定一個或多個對應的存儲節點負責，數據分布算法有兩個基本目標：

均勻性(Uniformity)：不同存儲節點的負載應該均衡；

穩定性(Consistency)：每次一個?key 通過數據分布算法得到的分布結果應該保持基本穩定，即使在有存儲節點發生變化的情況下也能保持這種穩定。

可以看出，這兩個目標在一定程度上是相互矛盾的。當有存儲節點增加或刪除時，為了保持穩定應該盡量少的進行數據的移動和重新分配，而這樣又勢必會帶來負載不均衡。同樣追求極致均勻也會導致較多的數據遷移。

所以我們希望在上述這兩種極端情況之間，找到一個點以獲得合適的均勻性和穩定性。除了上述兩個基本目標外，工程中還需要從以下幾個方面考慮數據分布算法的優劣：

性能可擴展性：這個主要考慮的是數據分布算法相對于存儲節點規模的時間復雜度。為了整個系統的可擴展性，數據分布算法不應該在集群規模擴大后顯著的增加運行時間。

考慮節點異構：實際工程中，不同存儲節點之間可能會有很大的性能或容量差異，好的數據分布算法應該能很好的應對這種異構，提供加權的數據均勻。

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

?

?

演進

看完算法的評價指標后，接下來介紹一些可能的方案演進，并分析他們的優劣。這里假設?key 的值足夠分散。

1. Hash

一個簡單直觀的想法是直接用?Hash?來計算，簡單的以?key 做哈希后對節點數取模(存儲節點的數量)。可以看出，在?key 足夠分散的情況下，均勻性可以獲得。可是一旦集群中有存儲節點加入或退出時(此時取模的值會變)，所有的原有節點都會受到影響(模值改變，同一個數據計算的結果可能會不同)。穩定性無從談起。

?

2. 一致性 Hash

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

?

3. 帶負載上限的一致性?Hash

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

如上圖所示，假設每個桶當前上限是2，紅色的小球按序號大小先后訪問，當編號為6的紅色小球到達時，發現順時針首先遇到的B（3，4），C（1，5）都已經達到上限。因此，最終會放置在桶A里。

這個算法最吸引人的地方在于當有節點變化時，需要遷移的數據量是?1/e2?相關，而與節點數或數據數量均無關。也就是說當集群規模擴大時，數據遷移量并不會隨著顯著增加。另外，使用者可以通過調整?e?的值來控制均勻性和穩定性之間的權衡，就是一種以時間換空間的算法。總體來說，無論是一致性?Hash?還是帶負載限制的一致性?Hash，都無法解決節點異構的問題。

?

4. 帶虛擬節點的一致性?Hash

為了解決負載不均勻和異構的問題，可以在一致性Hash的基礎上引入虛擬節點。即Hash環上的每個節點并不是實際的存儲節點，而是一個虛擬節點。實際的存儲節點根據其不同的權重，對應一個或多個虛擬節點，所有落到相應虛擬節點上的?key 都由該存儲節點負責。

如下圖所示，存儲節點A負責(1,3]，(4,8]，(10,14]，存儲節點B負責(14,1]，(8,10]。

這個算法的問題在于，一個實際存儲節點的加入或退出，會影響多個虛擬節點的重新分配，進而引起很多節點參與到數據遷移中來。另外，實踐中將一個虛擬節點重新分配給新的實際節點時，需要將這部分數據遍歷出來發送給新節點。我們需要一個更合適的虛擬節點切分和分配方式，那就是分片。

?

5. 分片

分片將哈希環切割為相同大小的分片，然后將這些分片交給不同的節點負責。注意這里跟上面提到的虛擬節點有著很本質的區別：分片的劃分和分片的分配被解耦。

一個節點退出時，其所負責的分片并不需要順時針合并給之后節點，而是可以更靈活的將整個分片作為一個整體交給任意節點。在實踐中，一個分片多作為最小的數據遷移和備份單位。

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

上圖是分布式KV存儲Zeppelin中的分片方式，?key Space通過?Hash?到分片，分片及其副本又通過一層映射到最終的存儲節點?Node Server。

?

6. CRUSH 算法

CRUSH 算法本質上也是一種基于分片的數據分布方式，其試圖在以下幾個方面進行優化：

(1)?分片映射信息量：避免中心目錄服務和存儲節點及客戶端之間交互大量的分片映射信息，而改由存儲節點或客戶端自己根據少量且穩定的集群節點拓撲和確定的規則自己計算分片映射。

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

客戶端或存儲節點利用?key 、存儲節點的拓撲結構和分配算法，獨立的進行分片位置的計算，得到一組負責對應分片及副本的存儲位置。如圖所示是一次定位的過程，最終選擇了一個row下的cab21，cab23，cab24三個機柜下的三個存儲節點。

當節點變化時，由于節點拓撲的變化，會影響少量分片數據進行遷移，如下圖是加入新節點引起的數據遷移。通過良好的分配算法，可以得到很好的負載均衡和穩定性，CRUSH提供了?Uniform、List、Tree、Straw?四種分配算法。

?

?

應用案例

常見的分布式存儲系統大多采用類似于分片的數據分布和定位方式：

(1)?Cassandra/Dynamo：采用分片的方式并通過 Gossip 協議在對等節點間通信；

(2)?Redis Cluster：將?key Space 劃分為 slots，同樣利用 Gossip 協議通信；

(3)?Zeppelin：將數據分片為Partition，通過 Meta 集群提供中心目錄服務；

(4)?Bigtable：將數據切割為 Tablet，類似于可變的分片，Tablet Server 可以進行分片的切割，最終分片信息記錄在?Chubby?中；

(5)?Ceph：采用?CRUSH?方式，由中心集群?Monitor?提供并維護集群拓撲的變化。

?

轉載自：https://juejin.im/post/5b38cffae51d4558e36037ec

總結

以上是生活随笔為你收集整理的浅谈分布式存储系统数据分布算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。