Tag: algorithm

堆了一陣子的文章...

當有 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.