Google 提出的 Jump Consistent Hash

堆了一陣子的文章...

當有 n 台 cache server 給你使用,最傳統的作法是 hash(key) % n 決定挑哪一台 cache server,但這個方法在增加或減少機器時就會讓 cache 大規模失效。Consistent Hashing 就是希望在這種情況下 (增加或是移除 cache server 時) 可以避免大規模 cache 失效的問題。

比較基本的 Consistent Hash 作法是將 hash(key) 的值對應到 ring 上 (假設是 hash value 的範圍是 32bits,也就是 0 到 0xFFFFFFFF,那麼 ring 繞一圈平均分佈),像是一開始只有三台,所以就是三個 bucket:


取自「Consistent hashing」這裡。

等加了機器後就分擔掉本來的 hash value 區段:


取自「Consistent hashing」這裡。

這樣的作法通常會需要 O(log N) 的時間複雜度 (query & add/remove server) 與 O(n) 的空間複雜度。

另外會有平均性的問題需要解決,通常的 workaround 是讓一個 server 有很多 virtual bucket 在 ring 上面解,像是這樣:


取自「The Simple Magic of Consistent Hashing」。

Google 在 2014 年發表出來的 Jump Consistent Hash 則給了更好的方案,O(1) 的空間使用率以及 O(logN) 的時間複雜度 (query only),而且非常平均的打散:「A Fast, Minimal Memory, Consistent Hash Algorithm」。

論文裡面給了 C++ 的實作:

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;
}

神秘數字 (還出現 double) 與神秘的迴圈... 在 Performance Analysis 這段解釋了時間複雜度明顯跟迴圈有關,分析後可以得到 O(log N):

The time complexity of the algorithm is determined by the number of iterations of the while loop. [...] So the expected number of iterations is less than ln(n) + 1.

再來是 Consistent Hash 會討論「平均性」這個問題,可以看到跟以前的方法不是同一個級別:

執行的效率也非常好,要注意的是 X 軸是對數座標:

在 Note 的部份也說明了這個演算法 Google 沒有計畫要弄專利 (也公開出來了):

Google has not applied for patent protection for this algorithm, and, as of this writing, has no plans to. Rather, it wishes to contribute this algorithm to the community.