一致性哈希及其在Greenplum中的應(yīng)用
前言一致性哈希(consistent hashing)是分布式系統(tǒng)中非常重要的算法，在平滑擴(kuò)縮容、動態(tài)負(fù)載均衡等方向有大量應(yīng)用。相對于傳統(tǒng)的線性(取模)哈希算法，一致性哈希可以保證在分布式哈希表中的桶數(shù)量發(fā)生變化時，受到影響需要重新映射的key盡量少。本文先簡要復(fù)習(xí)下經(jīng)典的割環(huán)一致性哈希方案，然后介紹它的變種——跳躍一致性哈希(jump consistent hash)。
割環(huán)一致性哈希
一致性哈希的概念最初在1997年由David Karger等大佬提出，原始論文見Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web，起初是為了解決網(wǎng)絡(luò)中的熱點問題，后來發(fā)展成分布式系統(tǒng)中通用的算法。為了與此后出現(xiàn)的其他一致性哈希算法相區(qū)別，一般將這個經(jīng)典方法稱為“割環(huán)法”。該算法能夠滿足論文中提出的兩大目標(biāo)，即平衡性(balance)和單調(diào)性(monotonicity)。
顧名思義，割環(huán)法將整個哈?？臻g組織成一個首尾相接的圓環(huán)，一般設(shè)為[0, 232 - 1]。以分布式K-V存儲為例，哈希桶即為存儲節(jié)點。將節(jié)點N的編號或IP等按哈希函數(shù)hash(N)映射在環(huán)上，再將數(shù)據(jù)的key按同樣的哈希函數(shù)hash(k)映射在環(huán)上，數(shù)據(jù)就會存儲在環(huán)上以順時針方向遍歷找到的第一個節(jié)點。當(dāng)節(jié)點擴(kuò)容或縮容時，仍然按照順時針原則，將受到影響的區(qū)間內(nèi)的數(shù)據(jù)重新分布到相鄰的節(jié)點上去，達(dá)到增量更新的目的，即滿足單調(diào)性。以下3張圖能夠簡單地說明。
雖然哈希函數(shù)的結(jié)果是均勻的，但節(jié)點映射在環(huán)上可能不均勻，節(jié)點數(shù)越少，數(shù)據(jù)傾斜的可能性就越大。解決此問題的方法是將物理節(jié)點虛擬成多個影子節(jié)點，數(shù)據(jù)經(jīng)過哈希后按順時針原則落到影子節(jié)點指向的物理節(jié)點上。如果我們想要人為干預(yù)各節(jié)點上數(shù)據(jù)量的權(quán)重，還可以指定不同的影子節(jié)點數(shù)量。如下圖所示，影子節(jié)點數(shù)量為3:2:2:1。
虛擬節(jié)點擴(kuò)縮容時的數(shù)據(jù)遷移方法與僅采用物理節(jié)點相同，因此調(diào)整權(quán)重值也會觸發(fā)數(shù)據(jù)遷移。
對于有N個桶和K個鍵的一致性哈希方案，其時間復(fù)雜度是：
添加、刪除節(jié)點——O(K / N + logN)；
添加、刪除key——O(logN)。
其中，O(K / N)是數(shù)據(jù)重分布操作的平均代價，O(log N)則是在環(huán)上進(jìn)行二分查找定位哈希桶的代價。
最后有一個小問題：節(jié)點擴(kuò)縮容以及節(jié)點宕機(jī)時如何保證系統(tǒng)仍然可用呢？有兩種直接的思路：
中繼——如果在某個節(jié)點上查不到所需的數(shù)據(jù)，就把請求轉(zhuǎn)發(fā)給該節(jié)點的順時針方向下一個節(jié)點進(jìn)行處理。
雙寫——每次寫入數(shù)據(jù)時，都另外寫一份到目標(biāo)節(jié)點的順時針方向下一個節(jié)點。
割環(huán)法已經(jīng)能夠滿足一般分布式系統(tǒng)中的多數(shù)需求，Cassandra、Memcached等著名的存儲系統(tǒng)都用到了它(注意Redis Cluster并沒有)。下面介紹思想更加精妙，效率也更高的跳躍一致性哈希(jump consistent hash)方法。
跳躍一致性哈希
這個算法比較年輕，在2014年由Google的大佬John Lamping和Eric Veach提出，原始論文見A Fast, Minimal Memory, Consistent Hash Algorithm。它的實現(xiàn)非常簡潔，僅有5行代碼，如下。
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
int64_t b = 1, j = 0?
while (j < num_buckets) {
b = j?
key = key * 2862933555777941757ULL + 1?
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1))?
}
return b?
}
看官可能還無法理解為什么能這樣實現(xiàn)，接下來重走一遍論文的推導(dǎo)思路。
假設(shè)最終要求的滿足平衡性和單調(diào)性的哈希函數(shù)是ch(k, n)(k為數(shù)據(jù)的鍵，n為哈希桶的數(shù)量)，有如下簡單的遞推關(guān)系：
當(dāng)n = 1時，所有key都要映射到同一個桶中，即ch(k, 1) = 0；
當(dāng)n = 2時，為保證均勻性，需有K / 2個key分別映射到兩個桶中(K是key的總數(shù)量)，故K / 2個key需要重新映射；
......
當(dāng)桶數(shù)量由n變?yōu)閚 + 1時，有K / (n + 1)個key需要重新映射。
那么該如何決定哪些key被重新映射到新的桶中呢？答案是采用線性同余法(LCG)生成的偽隨機(jī)數(shù)決定。上文中的magic number 2862933555777941757就是線性同余法的乘數(shù)a。
以k作為種子生成一個偽隨機(jī)數(shù)序列，可以保證對于確定的k，ch(k, n)的結(jié)果也是確定的，進(jìn)而使用條件rand < 1 / (j + 1)即可保證哈希桶由j個變?yōu)閖 + 1個時，有1 / (j + 1)比例的數(shù)據(jù)會重新映射。
此時ch()函數(shù)的邏輯如下，時間復(fù)雜度顯然為O(n)。
int ch(int key, int num_buckets) {
random.seed(key)?
int b = 0? // This will track ch(key, j+1).
for (int j = 1? j < num_buckets? j++) {
if (random.next() < 1.0 / (j + 1)) b = j?
}
return b?
}
這個復(fù)雜度比割環(huán)法還要高，如何優(yōu)化？容易想到，rand < 1 / (j + 1)的概率肯定是相對小的，也就是說隨著j的增大，發(fā)生重分布的key的比例越來越小，j可以不必逐次自增，而是跳躍前進(jìn)，這也就是算法名稱中"jump"一詞的由來。
觀察上面的代碼，b表示k最后一跳的目的哈希桶的編號，即滿足條件：
ch(k, b + 1) ≠ ch(k, b) && ch(k, b + 1) = b
假設(shè)k連續(xù)不跳變，直到增加到j(luò) + 1個桶才發(fā)生跳變，可知此概率為：
[(b + 1)/(b + 2)] * [(b + 2)/(b + 3)] * ... * [(j - 1)/j] = (b + 1) / j
或者表示為：
P[j ≥ i] = P[ch(k, i) = ch(k, b + 1)] = (b + 1) / i
圖示如下。
那么，j最多可以直接跳到哪里才不至于漏掉原有的循環(huán)過程呢？容易得知，要滿足rand < (b + 1) / j，需要j < (b + 1) / rand，將其向下取整即可。改進(jìn)后的ch()函數(shù)如下。
int ch(int k, int n) {
random.seed(k);
int b = -1, j = 0;
while (j < n) {
b = j;
r = random.next();
j = floor((b+1) / r);
}
return b;
}
將random替換為具體的LCG，就是本節(jié)開頭的算法了。
分析時間復(fù)雜度：對于任意一個k，在哈希桶數(shù)從1增加到n的過程中，發(fā)生跳躍的期望次數(shù)是1 / 2 + ... + 1 / i + ... + 1 / n。根據(jù)歐拉常數(shù)的定義，調(diào)和級數(shù)與自然對數(shù)的差值的極限會收斂到一個小數(shù)，因此跳躍一致性哈希算法的復(fù)雜度是O(ln n)，比割環(huán)法更優(yōu)。
根據(jù)論文給出的實驗數(shù)據(jù)，跳躍一致性哈希產(chǎn)生的分布的標(biāo)準(zhǔn)差遠(yuǎn)遠(yuǎn)比割環(huán)法小，也就是非常均勻。
隨著桶數(shù)量的增加，跳躍一致性哈希算法的執(zhí)行時間增長也不明顯。
另外，它不需要額外的數(shù)據(jù)結(jié)構(gòu)，內(nèi)存占用極小(即論文標(biāo)題中所說的minimal memory)。
但是，它相對于割環(huán)法而言有個非常大的缺點，即只能在哈希桶序列的尾部添加和刪除桶，而不能在中間增刪。顯而易見，如果在中間增刪桶，由于桶的標(biāo)號是按自然順序來的，因此會導(dǎo)致后方所有桶的標(biāo)號發(fā)生變化，不再滿足一致性哈希的基本性質(zhì)。
仍然考慮節(jié)點擴(kuò)縮容以及節(jié)點宕機(jī)時如何保證系統(tǒng)仍然可用的問題。
中繼——如果在尾部的哈希桶j + 1中查不到所需的數(shù)據(jù)，就把請求轉(zhuǎn)發(fā)給ch(k, j)桶，即它的上一跳節(jié)點。
雙寫——每次寫入數(shù)據(jù)時，如果寫入的是尾部的哈希桶j + 1，就另外寫一份到ch(k, j)；如果寫入的是非尾部的哈希桶i，就另外寫一份到i + 1。這樣，不管是哪個節(jié)點失敗，數(shù)據(jù)都不會丟失。
Greenplum中的應(yīng)用
Greenplum提供了一個為集群擴(kuò)容的工具gpexpand。在GP v5中，執(zhí)行g(shù)pexpand時需要將所有哈希分布改為隨機(jī)分布，按照新的集群規(guī)模重新根據(jù)hash key計算哈希值，再將數(shù)據(jù)重新均衡到各個segment節(jié)點上，相當(dāng)于進(jìn)行了一次完全的shuffle，如下圖所示。
這種方式的缺點顯而易見：集群在擴(kuò)容期間處于不可用狀態(tài)，數(shù)據(jù)交換量巨大。并且在數(shù)據(jù)由隨機(jī)分布轉(zhuǎn)為新的哈希分布之前，無法利用數(shù)據(jù)的本地性信息做查詢優(yōu)化，拖累性能。
在GP v6中，通過將跳躍一致性哈希引入gpexpand，實現(xiàn)了完全在線、高性能的集群擴(kuò)容方式。如下圖所示，將集群由3節(jié)點擴(kuò)容到4節(jié)點，只有1/4的數(shù)據(jù)需要重分布。
GP v6的跳躍一致性哈希實現(xiàn)與Google原版完全相同。
另外，如何保證那些沒有重分布完畢的表被正確地查詢呢？GP v6在catalog表gp_distribution_policy里加入了一個新的字段numsegments，表示一張表的數(shù)據(jù)分布在前numsegments個節(jié)點上。因此，就算擴(kuò)容的過程中有事務(wù)正在運行，只要numsegments沒有改變，就仍然只在原有節(jié)點上執(zhí)行查詢。
最后，可以通過全局配置gp_use_legacy_hashops設(shè)定是否改回舊版的取模哈希方式，默認(rèn)當(dāng)然為false。
