分佈式存儲系統面臨著的首要問題，就是如何將 大量的數據 分佈在 不同的存儲節點 上。無論上層接口是 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/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 三個機櫃下的三個存儲節點。
當 節點變化 時，由於 節點拓撲 的變化，會影響 少量分片 數據進行遷移，如下圖是加入 新節點 引起的 數據遷移 。通過良好的 分配算法 ，可以得到很好的 負載均衡 和 穩定性 ， CRUSH 提供了 Uniform 、 List 、 Tree 、 Straw 四種分配算法。
(三). 應用案例
常見的 分佈式存儲系統 大多采用類似於 分片 的 數據分佈和定位方式 ：
- Cassandra/Dynamo：採用 分片 的方式並通過 Gossip 協議在對等節點間通信；
- Redis Cluster：將 key Space 劃分為 slots ，同樣利用 Gossip 協議通信；
- Zeppelin：將數據分片為 Partition ，通過 Meta 集群提供 中心目錄服務 ；
- Bigtable：將數據切割為 Tablet ，類似於可變的分片， Tablet Server 可以進行分片的切割，最終分片信息記錄在 Chubby 中；
- Ceph：採用 CRUSH 方式，由 中心集群 Monitor 提供並維護 集群拓撲 的變化。
注：關注作者，瞭解更多分佈式架構、微服務、netty、MySQL、spring、、性能優化、等知識點。
閱讀更多 JAVA技術程序員 的文章
