前言

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

[[283891]]

正文

(一) 指標(biāo)

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

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

可以看出，這兩個(gè)目標(biāo)在一定程度上是 相互矛盾 的。當(dāng)有 存儲節(jié)點(diǎn)增加或刪除時(shí)，為了保持穩(wěn)定應(yīng)該 盡量少 的進(jìn)行 數(shù)據(jù)的移動 和 重新分配，而這樣又勢必會帶來 負(fù)載不均衡。同樣追求 極致均勻 也會導(dǎo)致較多的 數(shù)據(jù)遷移。

所以我們希望在這兩個(gè)極端之間，找到一個(gè)點(diǎn)以獲得合適的均勻性和穩(wěn)定性。除了上述兩個(gè)基本目標(biāo)外，工程中還需要從以下幾個(gè)方面考慮數(shù)據(jù)分布算法的優(yōu)劣：

• 性能可擴(kuò)展性：這個(gè)主要考慮的是算法相對于 存儲節(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í)際工程中，不同 存儲節(jié)點(diǎn) 之間可能會有很大的 性能 或 容量差異，好的數(shù)據(jù)分布算法應(yīng)該能很好的應(yīng)對這種 異構(gòu)，提供 加權(quán)的數(shù)據(jù)均勻。
• 隔離故障域：為了 數(shù)據(jù)的高可用，數(shù)據(jù)分布算法應(yīng)該為每個(gè) key 找到 一組存儲節(jié)點(diǎn)，這些節(jié)點(diǎn)可能提供的是 數(shù)據(jù)的鏡像副本，也可能是類似 擦除碼的副本方式。數(shù)據(jù)分布算法應(yīng)該盡量 隔離 這些副本的故障域，如 不同機(jī)房、不同機(jī)架、不同交換機(jī)、不同機(jī)器。

(二) 演進(jìn)

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

1. Hash

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

2. 一致性Hash 

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

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

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

如上圖所示，假設(shè)每個(gè)桶 當(dāng)前上限 是 2，紅色的小球按序號訪問，當(dāng)編號為 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ù)量 均無關(guān)。

也就是說當(dāng) 集群規(guī)模擴(kuò)大 時(shí)，數(shù)據(jù)遷移量 并不會隨著顯著增加。另外，使用者可以通過調(diào)整 e 的值來控制 均勻性 和 穩(wěn)定性 之間的權(quán)衡，就是一種 以時(shí)間換空間的算法?？傮w來說，無論是 一致性 Hash 還是 帶負(fù)載限制 的 一致性 Hash，都無法解決 節(jié)點(diǎn)異構(gòu) 的問題。

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

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

如下圖所示，存儲節(jié)點(diǎn) A 負(fù)責(zé) (1,3]，(4,8]，(10, 14]，存儲節(jié)點(diǎn) B 負(fù)責(zé) (14,1]，(8,10]。 

這個(gè)算法的問題在于，一個(gè) 實(shí)際存儲節(jié)點(diǎn) 的 加入 或 退出，會影響 多個(gè)虛擬節(jié)點(diǎn)的重新分配，進(jìn)而引起 很多節(jié)點(diǎn) 參與到 數(shù)據(jù)遷移 中來。

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

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

6. CRUSH算法

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

• 分片映射信息量：避免 中心目錄服務(wù) 和 存儲節(jié)點(diǎn) 及 客戶端之間 交互大量的 分片映射信息，而改由 存儲節(jié)點(diǎn) 或 客戶端 自己根據(jù) 少量 且 穩(wěn)定 的集群節(jié)點(diǎn)拓?fù)浜痛_定的規(guī)則自己計(jì)算分片映射。
• 完善的故障域劃分：支持 層級 的 故障域控制，將 同一分片 的 不同副本 按照配置劃分到 不同層級 的 故障域中。

客戶端 或 存儲節(jié)點(diǎn) 利用 key、存儲節(jié)點(diǎn) 的 拓?fù)浣Y(jié)構(gòu) 和 分配算法，獨(dú)立的進(jìn)行 分片位置 的計(jì)算，得到一組負(fù)責(zé)對應(yīng) 分片 及 副本 的 存儲位置。

如圖所示是 一次定位 的過程，最終選擇了一個(gè) row 下的 cab21，cab23，cab24 三個(gè)機(jī)柜下的三個(gè)存儲節(jié)點(diǎn)。 

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

(三) 應(yīng)用案例

常見的 分布式存儲系統(tǒng) 大多采用類似于 分片 的 數(shù)據(jù)分布和定位方式：

• Cassandra/Dynamo：采用 分片 的方式并通過 Gossip 協(xié)議在對等節(jié)點(diǎn)間通信;
• Redis Cluster：將 key Space 劃分為 slots，同樣利用 Gossip 協(xié)議通信;
• Zeppelin：將數(shù)據(jù)分片為 Partition，通過 Meta 集群提供 中心目錄服務(wù);
• Bigtable：將數(shù)據(jù)切割為 Tablet，類似于可變的分片，Tablet Server 可以進(jìn)行分片的切割，最終分片信息記錄在 Chubby 中;
• Ceph：采用 CRUSH 方式，由 中心集群 Monitor 提供并維護(hù) 集群拓?fù)?的變化。