一致性哈希及其在Greenplum中的應(yīng)用

一致性哈希(consistent hashing)是分布式系統(tǒng)中非常重要的算法，在平滑擴(kuò)縮容、動(dòng)態(tài)負(fù)載均衡等方向有大量應(yīng)用。相對(duì)于傳統(tǒng)的線性(取模)哈希算法，一致性哈希可以保證在分布式哈希表中的桶數(shù)量發(fā)生變化時(shí)，受到影響需要重新映射的key盡量少。本文先簡(jiǎn)要復(fù)習(xí)下經(jīng)典的割環(huán)一致性哈希方案，然后介紹它的變種——跳躍一致性哈希(jump consistent hash)。

割環(huán)一致性哈希

一致性哈希的概念最初在1997年由David Karger等大佬提出，原始論文見(jiàn)Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web，起初是為了解決網(wǎng)絡(luò)中的熱點(diǎn)問(wèn)題，后來(lái)發(fā)展成分布式系統(tǒng)中通用的算法。為了與此后出現(xiàn)的其他一致性哈希算法相區(qū)別，一般將這個(gè)經(jīng)典方法稱(chēng)為“割環(huán)法”。該算法能夠滿足論文中提出的兩大目標(biāo)，即平衡性(balance)和單調(diào)性(monotonicity)。

顧名思義，割環(huán)法將整個(gè)哈?？臻g組織成一個(gè)首尾相接的圓環(huán)，一般設(shè)為[0, 232 - 1]。以分布式K-V存儲(chǔ)為例，哈希桶即為存儲(chǔ)節(jié)點(diǎn)。將節(jié)點(diǎn)N的編號(hào)或IP等按哈希函數(shù)hash(N)映射在環(huán)上，再將數(shù)據(jù)的key按同樣的哈希函數(shù)hash(k)映射在環(huán)上，數(shù)據(jù)就會(huì)存儲(chǔ)在環(huán)上以順時(shí)針?lè)较虮闅v找到的第一個(gè)節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)擴(kuò)容或縮容時(shí)，仍然按照順時(shí)針原則，將受到影響的區(qū)間內(nèi)的數(shù)據(jù)重新分布到相鄰的節(jié)點(diǎn)上去，達(dá)到增量更新的目的，即滿足單調(diào)性。以下3張圖能夠簡(jiǎn)單地說(shuō)明。

雖然哈希函數(shù)的結(jié)果是均勻的，但節(jié)點(diǎn)映射在環(huán)上可能不均勻，節(jié)點(diǎn)數(shù)越少，數(shù)據(jù)傾斜的可能性就越大。解決此問(wèn)題的方法是將物理節(jié)點(diǎn)虛擬成多個(gè)影子節(jié)點(diǎn)，數(shù)據(jù)經(jīng)過(guò)哈希后按順時(shí)針原則落到影子節(jié)點(diǎn)指向的物理節(jié)點(diǎn)上。如果我們想要人為干預(yù)各節(jié)點(diǎn)上數(shù)據(jù)量的權(quán)重，還可以指定不同的影子節(jié)點(diǎn)數(shù)量。如下圖所示，影子節(jié)點(diǎn)數(shù)量為3:2:2:1。

虛擬節(jié)點(diǎn)擴(kuò)縮容時(shí)的數(shù)據(jù)遷移方法與僅采用物理節(jié)點(diǎn)相同，因此調(diào)整權(quán)重值也會(huì)觸發(fā)數(shù)據(jù)遷移。

對(duì)于有N個(gè)桶和K個(gè)鍵的一致性哈希方案，其時(shí)間復(fù)雜度是：

• 添加、刪除節(jié)點(diǎn)——O(K / N + logN)；

• 添加、刪除key——O(logN)。

其中，O(K / N)是數(shù)據(jù)重分布操作的平均代價(jià)，O(log N)則是在環(huán)上進(jìn)行二分查找定位哈希桶的代價(jià)。

最后有一個(gè)小問(wèn)題：節(jié)點(diǎn)擴(kuò)縮容以及節(jié)點(diǎn)宕機(jī)時(shí)如何保證系統(tǒng)仍然可用呢？有兩種直接的思路：

• 中繼——如果在某個(gè)節(jié)點(diǎn)上查不到所需的數(shù)據(jù)，就把請(qǐng)求轉(zhuǎn)發(fā)給該節(jié)點(diǎn)的順時(shí)針?lè)较蛳乱粋€(gè)節(jié)點(diǎn)進(jìn)行處理。

• 雙寫(xiě)——每次寫(xiě)入數(shù)據(jù)時(shí)，都另外寫(xiě)一份到目標(biāo)節(jié)點(diǎn)的順時(shí)針?lè)较蛳乱粋€(gè)節(jié)點(diǎn)。

割環(huán)法已經(jīng)能夠滿足一般分布式系統(tǒng)中的多數(shù)需求，Cassandra、Memcached等著名的存儲(chǔ)系統(tǒng)都用到了它(注意Redis Cluster并沒(méi)有)。下面介紹思想更加精妙，效率也更高的跳躍一致性哈希(jump consistent hash)方法。

跳躍一致性哈希

這個(gè)算法比較年輕，在2014年由Google的大佬John Lamping和Eric Veach提出，原始論文見(jiàn)A Fast, Minimal Memory, Consistent Hash Algorithm。它的實(shí)現(xiàn)非常簡(jiǎ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?
}

看官可能還無(wú)法理解為什么能這樣實(shí)現(xiàn)，接下來(lái)重走一遍論文的推導(dǎo)思路。

假設(shè)最終要求的滿足平衡性和單調(diào)性的哈希函數(shù)是ch(k, n)(k為數(shù)據(jù)的鍵，n為哈希桶的數(shù)量)，有如下簡(jiǎn)單的遞推關(guān)系：

• 當(dāng)n = 1時(shí)，所有key都要映射到同一個(gè)桶中，即ch(k, 1) = 0；

• 當(dāng)n = 2時(shí)，為保證均勻性，需有K / 2個(gè)key分別映射到兩個(gè)桶中(K是key的總數(shù)量)，故K / 2個(gè)key需要重新映射；

• ......

• 當(dāng)桶數(shù)量由n變?yōu)閚 + 1時(shí)，有K / (n + 1)個(gè)key需要重新映射。

那么該如何決定哪些key被重新映射到新的桶中呢？答案是采用線性同余法(LCG)生成的偽隨機(jī)數(shù)決定。上文中的magic number 2862933555777941757就是線性同余法的乘數(shù)a。

以k作為種子生成一個(gè)偽隨機(jī)數(shù)序列，可以保證對(duì)于確定的k，ch(k, n)的結(jié)果也是確定的，進(jìn)而使用條件rand < 1 / (j + 1)即可保證哈希桶由j個(gè)變?yōu)閖 + 1個(gè)時(shí)，有1 / (j + 1)比例的數(shù)據(jù)會(huì)重新映射。

此時(shí)ch()函數(shù)的邏輯如下，時(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?
}

這個(gè)復(fù)雜度比割環(huán)法還要高，如何優(yōu)化？容易想到，rand < 1 / (j + 1)的概率肯定是相對(duì)小的，也就是說(shuō)隨著j的增大，發(fā)生重分布的key的比例越來(lái)越小，j可以不必逐次自增，而是跳躍前進(jìn)，這也就是算法名稱(chēng)中"jump"一詞的由來(lái)。

觀察上面的代碼，b表示k最后一跳的目的哈希桶的編號(hào)，即滿足條件：

ch(k, b + 1) ≠ ch(k, b) && ch(k, b + 1) = b

假設(shè)k連續(xù)不跳變，直到增加到j(luò) + 1個(gè)桶才發(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)過(guò)程呢？容易得知，要滿足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é)開(kāi)頭的算法了。

分析時(shí)間復(fù)雜度：對(duì)于任意一個(gè)k，在哈希桶數(shù)從1增加到n的過(guò)程中，發(fā)生跳躍的期望次數(shù)是1 / 2 + ... + 1 / i + ... + 1 / n。根據(jù)歐拉常數(shù)的定義，調(diào)和級(jí)數(shù)與自然對(duì)數(shù)的差值的極限會(huì)收斂到一個(gè)小數(shù)，因此跳躍一致性哈希算法的復(fù)雜度是O(ln n)，比割環(huán)法更優(yōu)。

根據(jù)論文給出的實(shí)驗(yàn)數(shù)據(jù)，跳躍一致性哈希產(chǎn)生的分布的標(biāo)準(zhǔn)差遠(yuǎn)遠(yuǎn)比割環(huán)法小，也就是非常均勻。

隨著桶數(shù)量的增加，跳躍一致性哈希算法的執(zhí)行時(shí)間增長(zhǎng)也不明顯。

另外，它不需要額外的數(shù)據(jù)結(jié)構(gòu)，內(nèi)存占用極小(即論文標(biāo)題中所說(shuō)的minimal memory)。

但是，它相對(duì)于割環(huán)法而言有個(gè)非常大的缺點(diǎn)，即只能在哈希桶序列的尾部添加和刪除桶，而不能在中間增刪。顯而易見(jiàn)，如果在中間增刪桶，由于桶的標(biāo)號(hào)是按自然順序來(lái)的，因此會(huì)導(dǎo)致后方所有桶的標(biāo)號(hào)發(fā)生變化，不再滿足一致性哈希的基本性質(zhì)。

仍然考慮節(jié)點(diǎn)擴(kuò)縮容以及節(jié)點(diǎn)宕機(jī)時(shí)如何保證系統(tǒng)仍然可用的問(wèn)題。

• 中繼——如果在尾部的哈希桶j + 1中查不到所需的數(shù)據(jù)，就把請(qǐng)求轉(zhuǎn)發(fā)給ch(k, j)桶，即它的上一跳節(jié)點(diǎn)。

• 雙寫(xiě)——每次寫(xiě)入數(shù)據(jù)時(shí)，如果寫(xiě)入的是尾部的哈希桶j + 1，就另外寫(xiě)一份到ch(k, j)；如果寫(xiě)入的是非尾部的哈希桶i，就另外寫(xiě)一份到i + 1。這樣，不管是哪個(gè)節(jié)點(diǎn)失敗，數(shù)據(jù)都不會(huì)丟失。

Greenplum中的應(yīng)用

Greenplum提供了一個(gè)為集群擴(kuò)容的工具gpexpand。在GP v5中，執(zhí)行g(shù)pexpand時(shí)需要將所有哈希分布改為隨機(jī)分布，按照新的集群規(guī)模重新根據(jù)hash key計(jì)算哈希值，再將數(shù)據(jù)重新均衡到各個(gè)segment節(jié)點(diǎn)上，相當(dāng)于進(jìn)行了一次完全的shuffle，如下圖所示。

這種方式的缺點(diǎn)顯而易見(jiàn)：集群在擴(kuò)容期間處于不可用狀態(tài)，數(shù)據(jù)交換量巨大。并且在數(shù)據(jù)由隨機(jī)分布轉(zhuǎn)為新的哈希分布之前，無(wú)法利用數(shù)據(jù)的本地性信息做查詢優(yōu)化，拖累性能。

在GP v6中，通過(guò)將跳躍一致性哈希引入gpexpand，實(shí)現(xiàn)了完全在線、高性能的集群擴(kuò)容方式。如下圖所示，將集群由3節(jié)點(diǎn)擴(kuò)容到4節(jié)點(diǎn)，只有1/4的數(shù)據(jù)需要重分布。

GP v6的跳躍一致性哈希實(shí)現(xiàn)與Google原版完全相同。

另外，如何保證那些沒(méi)有重分布完畢的表被正確地查詢呢？GP v6在catalog表gp_distribution_policy里加入了一個(gè)新的字段numsegments，表示一張表的數(shù)據(jù)分布在前numsegments個(gè)節(jié)點(diǎn)上。因此，就算擴(kuò)容的過(guò)程中有事務(wù)正在運(yùn)行，只要numsegments沒(méi)有改變，就仍然只在原有節(jié)點(diǎn)上執(zhí)行查詢。

最后，可以通過(guò)全局配置gp_use_legacy_hashops設(shè)定是否改回舊版的取模哈希方式，默認(rèn)當(dāng)然為false。