前言
一致性哈希（consistent hashing）是分布式系統(tǒng)中非常重要的算法，在平滑擴縮容、動態(tài)負載均衡等方向有大量應用噪伊。相對于傳統(tǒng)的線性（取模）哈希算法，一致性哈系ǎ可以保證在分布式哈希表中的桶數量發(fā)生變化時鉴吹，受到影響需要重新映射的key盡量少。本文先簡要復習下經典的割環(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>>瞒渠，起初是為了解決網絡中的熱點問題良蒸，后來發(fā)展成分布式系統(tǒng)中通用的算法。為了與此后出現的其他一致性哈希算法相區(qū)別伍玖，一般將這個經典方法稱為“割環(huán)法”嫩痰。該算法能夠滿足論文中提出的兩大目標，即平衡性（balance）和單調性（monotonicity）窍箍。
顧名思義串纺，割環(huán)法將整個哈侠雎茫空間組織成一個首尾相接的圓環(huán)，一般設為[0, 232 - 1]造垛。以分布式K-V存儲為例魔招，哈希桶即為存儲節(jié)點。將節(jié)點N的編號或IP等按哈希函數hash(N)映射在環(huán)上五辽，再將數據的key按同樣的哈希函數hash(k)映射在環(huán)上办斑，數據就會存儲在環(huán)上以順時針方向遍歷找到的第一個節(jié)點。當節(jié)點擴容或縮容時杆逗，仍然按照順時針原則乡翅，將受到影響的區(qū)間內的數據重新分布到相鄰的節(jié)點上去，達到增量更新的目的罪郊，即滿足單調性蠕蚜。以下3張圖能夠簡單地說明。
雖然哈希函數的結果是均勻的悔橄，但節(jié)點映射在環(huán)上可能不均勻靶累，節(jié)點數越少，數據傾斜的可能性就越大癣疟。解決此問題的方法是將物理節(jié)點虛擬成多個影子節(jié)點挣柬，數據經過哈希后按順時針原則落到影子節(jié)點指向的物理節(jié)點上。如果我們想要人為干預各節(jié)點上數據量的權重睛挚，還可以指定不同的影子節(jié)點數量邪蛔。如下圖所示，影子節(jié)點數量為3:2:2:1扎狱。
虛擬節(jié)點擴縮容時的數據遷移方法與僅采用物理節(jié)點相同侧到，因此調整權重值也會觸發(fā)數據遷移。
對于有N個桶和K個鍵的一致性哈希方案淤击，其時間復雜度是：
- 添加匠抗、刪除節(jié)點——O(K / N + logN)；
- 添加污抬、刪除key——O(logN)戈咳。
其中，O(K / N)是數據重分布操作的平均代價壕吹，O(log N)則是在環(huán)上進行二分查找定位哈希桶的代價。
最后有一個小問題：節(jié)點擴縮容以及節(jié)點宕機時如何保證系統(tǒng)仍然可用呢删铃？有兩種直接的思路：
- 中繼——如果在某個節(jié)點上查不到所需的數據耳贬，就把請求轉發(fā)給該節(jié)點的順時針方向下一個節(jié)點進行處理。
- 雙寫——每次寫入數據時猎唁，都另外寫一份到目標節(jié)點的順時針方向下一個節(jié)點咒劲。
割環(huán)法已經能夠滿足一般分布式系統(tǒng)中的多數需求，Cassandra、Memcached等著名的存儲系統(tǒng)都用到了它（注意Redis Cluster并沒有）腐魂。下面介紹思想更加精妙帐偎，效率也更高的跳躍一致性哈希（jump consistent hash）方法。
跳躍一致性哈希
這個算法比較年輕蛔屹，在2014年由Google的大佬John Lamping和Eric Veach提出削樊，原始論文見<<A Fast, Minimal Memory, Consistent Hash Algorithm>>。它的實現非常簡潔兔毒，僅有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?
}
看官可能還無法理解為什么能這樣實現育叁，接下來重走一遍論文的推導思路迅脐。
假設最終要求的滿足平衡性和單調性的哈希函數是ch(k, n)（k為數據的鍵，n為哈希桶的數量）豪嗽，有如下簡單的遞推關系：
- 當n = 1時谴蔑，所有key都要映射到同一個桶中，即ch(k, 1) = 0龟梦；
- 當n = 2時隐锭，為保證均勻性，需有K / 2個key分別映射到兩個桶中（K是key的總數量）变秦，故K / 2個key需要重新映射成榜；
- ......
- 當桶數量由n變?yōu)閚 + 1時，有K / (n + 1)個key需要重新映射蹦玫。
那么該如何決定哪些key被重新映射到新的桶中呢赎婚？答案是采用線性同余法（LCG）生成的偽隨機數決定。關于線性同余法樱溉，可參見筆者之前寫過的這篇文章挣输，上文中的magic number 2862933555777941757就是線性同余法的乘數a。
以k作為種子生成一個偽隨機數序列福贞，可以保證對于確定的k撩嚼，ch(k, n)的結果也是確定的，進而使用條件rand < 1 / (j + 1)即可保證哈希桶由j個變?yōu)閖 + 1個時挖帘，有1 / (j + 1)比例的數據會重新映射完丽。
此時ch()函數的邏輯如下，時間復雜度顯然為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?
}
這個復雜度比割環(huán)法還要高逻族，如何優(yōu)化？容易想到骄崩，rand < 1 / (j + 1)的概率肯定是相對小的聘鳞，也就是說隨著j的增大薄辅，發(fā)生重分布的key的比例越來越小，j可以不必逐次自增抠璃，而是跳躍前進站楚，這也就是算法名稱中"jump"一詞的由來。
觀察上面的代碼搏嗡，b表示k最后一跳的目的哈希桶的編號窿春，即滿足條件：
ch(k, b + 1) ≠ ch(k, b) && ch(k, b + 1) = b
假設k連續(xù)不跳變，直到增加到j + 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悍赢，將其向下取整即可决瞳。改進后的ch()函數如下。
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，在哈希桶數從1增加到n的過程中赏迟，發(fā)生跳躍的期望次數是1 / 2 + ... + 1 / i + ... + 1 / n屡贺。根據歐拉常數的定義，調和級數與自然對數的差值的極限會收斂到一個小數锌杀，因此跳躍一致性哈希算法的復雜度是O(ln n)甩栈，比割環(huán)法更優(yōu)。
根據論文給出的實驗數據糕再，跳躍一致性哈希產生的分布的標準差遠遠比割環(huán)法小量没，也就是非常均勻。
隨著桶數量的增加突想，跳躍一致性哈希算法的執(zhí)行時間增長也不明顯殴蹄。
另外，它不需要額外的數據結構猾担，內存占用極邢啤（即論文標題中所說的minimal memory）。
但是绑嘹，它相對于割環(huán)法而言有個非常大的缺點妓蛮，即只能在哈希桶序列的尾部添加和刪除桶，而不能在中間增刪圾叼。顯而易見蛤克，如果在中間增刪桶，由于桶的標號是按自然順序來的夷蚊，因此會導致后方所有桶的標號發(fā)生變化构挤，不再滿足一致性哈希的基本性質。
仍然考慮節(jié)點擴縮容以及節(jié)點宕機時如何保證系統(tǒng)仍然可用的問題惕鼓。
- 中繼——如果在尾部的哈希桶j + 1中查不到所需的數據筋现，就把請求轉發(fā)給ch(k, j)桶，即它的上一跳節(jié)點箱歧。
- 雙寫——每次寫入數據時矾飞，如果寫入的是尾部的哈希桶j + 1，就另外寫一份到ch(k, j)呀邢；如果寫入的是非尾部的哈希桶i洒沦，就另外寫一份到i + 1。這樣价淌，不管是哪個節(jié)點失敗申眼，數據都不會丟失。
Greenplum中的應用
Greenplum提供了一個為集群擴容的工具gpexpand蝉衣。在GP v5中括尸，執(zhí)行gpexpand時需要將所有哈希分布改為隨機分布，按照新的集群規(guī)模重新根據hash key計算哈希值病毡，再將數據重新均衡到各個segment節(jié)點上濒翻，相當于進行了一次完全的shuffle，如下圖所示啦膜。
這種方式的缺點顯而易見：集群在擴容期間處于不可用狀態(tài)有送，數據交換量巨大。并且在數據由隨機分布轉為新的哈希分布之前功戚，無法利用數據的本地性信息做查詢優(yōu)化娶眷，拖累性能。
在GP v6中啸臀，通過將跳躍一致性哈希引入gpexpand届宠，實現了完全在線、高性能的集群擴容方式乘粒。如下圖所示豌注，將集群由3節(jié)點擴容到4節(jié)點，只有1/4的數據需要重分布灯萍。
GP v6的跳躍一致性哈希實現與Google原版完全相同秽誊，可參見這里。
另外努酸，如何保證那些沒有重分布完畢的表被正確地查詢呢？GP v6在catalog表gp_distribution_policy里加入了一個新的字段numsegments药薯，表示一張表的數據分布在前numsegments個節(jié)點上。因此救斑，就算擴容的過程中有事務正在運行童本，只要numsegments沒有改變，就仍然只在原有節(jié)點上執(zhí)行查詢脸候。
最后穷娱，可以通過全局配置gp_use_legacy_hashops設定是否改回舊版的取模哈希方式，默認當然為false运沦。
The End
最近天氣有點冷泵额，民那注意保暖。
晚安晚安携添。
