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

指標

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

[[213691]]

均勻性(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/e^2相關，而與節點數或數據數均無關，也就是說當集群規模擴大時，數據遷移量并不會隨著顯著增加。另外，使用者可以通過調整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算法本質上也是一種分片的數據分布方式，其試圖在以下幾個方面進行優化：

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

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

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

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

應用

常見的存儲系統大多采用類似與分片的數據分布和定位方式。Dynamo及Cassandra采用分片的方式并通過gossip在對等節點間同步；Redis Cluster將key space劃分為slots，同樣利用gossip通信；Zeppelin將數據分片為Partition，通過Meta集群提供中心目錄服務；Bigtable將數據切割為Tablet，類似于可變的分片，Tablet Server可以進行分片的切割，最終分片信息記錄在Chubby中；Ceph采用CRUSH方式，由中心集群Monitor維護并提供集群拓撲的變化。