NO IMAGE

Hash 大家都知道,把某個要儲存的內容的索引 key 通過某個規則計算一下,算出來一個值,這個值往往範圍比原來小,且概率意義上不會衝突。

由於 Hash 計算複雜度往往比查詢要快,被大量應用到各種大規模的系統中,特別是分散式系統。具體實踐中有幾個典型的問題。

問題來源

一致性 Hash 討論地已經很多,基本故事就是分散式儲存系統中,通過 Hash 來決定內容存到哪個節點上。

典型的比如 cache 系統,後面放若干節點,查詢某個 key,hash 到某個節點,再進一步檢索。

最簡單的自然是按照節點數量取個模,理想狀態下不會有啥問題。

但是如果發生如下情況,就無法正常工作了。 加節點(一般是有計劃的) 減節點(可能突然故障,無法預知)

所以提出了一致性 hash,即考慮如下四個方面的演算法: 平衡性(Balance):雜湊結果儘可能分佈到所有的節點,這樣可以使得所有的節點都得到利用; 單調性(Monotonicity):加入新的節點後,已經分配節點的 hash 結果 被對映到原有的或者新的節點上去,而不會被對映到其他節點; 分散性(Spread):同樣內容儘量避免 hash 到不同節點; 負載(Load):不同內容避免 hash 到同樣節點。

簡單的說,就是有一個演算法,首先分配儘量均勻,其次,當節點個數變化的時候,儘量維持原來內容的對映,並進行區域性調整。

能滿足的演算法有很多,這裡介紹兩個比較經典的。

基於環的實現

該演算法最初於 1997 年在論文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving
Hot Spots on the World Wide Web
 中提出。演算法複雜度為 O(log(n))。

主要設計思想為:構造一個環(順序標上編號比如 0 ~ 2^32-1),將已有節點編號並分配到這個環上,分割環為不同的段。

對每個內容,hash 後是一個獨一無二的數字,這個數字肯定會落入某個段上,按照固定方向往前找到的第一個節點編號即為要分配到的節點。

考慮兩個相鄰的節點 A 和 C,如果要在中間新增一個節點 B,那麼 AB 段上內容會從 C 節點重新分配到 B 節點。反之,如果刪除掉 B 節點,那麼 AB 段上內容會再次分配到 C 節點上。

這種演算法很好的滿足性質 2-4,唯獨平衡性沒有解決。即當節點個數不多的時候,內容可能會集中在某些段,劃分到部分節點上。要解決這個問題也很簡單,把一個節點虛擬為多個虛節點,提高整體節點個數,然後再分散放到環上。這樣就提高了平衡性。

基於概率轉移的實現

該演算法最初於 2014 年在論文 A Fast, Minimal Memory, Consistent Hash Algorithm 中由 Google 工程師 John
Lamping 和 Eric Veach 提出。演算法複雜度為 O(log(n))。

主要設計思想為:假設原先有 n 個節點,新加上一個節點後,每個 key 都有 1/n 1 的概率轉移到新的節點上,n/n 1 的概率留在原先分配的節點。

舉個例子,原先有 1 個節點,再加一個節點,那麼已有內容有 1/2 的概率跳轉到到第二個節點。原先有 2 個節點(每個裡面有 1/2 的內容),再加一個節點,則已分配內容應該有 1/3 的概率轉移到新的節點。

一個簡單的實現程式碼為:

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

即根據 key 生成 num_buckets-1 個(0~1.0)的偽隨機數,依次檢查隨機數序列:

  • 第一個隨機數 <1/2,則放第二個節點;
  • 第二個隨機數 <1/3,則放第三個節點;

注意偽裝隨機數序列由 key 唯一確定。意味著同樣的內容在多次分配中,分配結果將是一致的。

另外,可以計算出如果當前分配為 b,下一個結果 j >= i 的概率(即 b 1 到 i-1 的過程都不發生跳變)

P(j>=i) = (b 1)/i

最終優化為如下程式碼:

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

這個演算法依賴於偽隨機演算法的輸出,特點有: 分佈均勻性由偽隨機演算法決定,而跟 key 自身均勻性無關,實踐均勻性遠好於基於環的演算法; 不需要對 key 進行計算,複雜度低,實踐計算時間也比基於環的演算法好。

演算法沒解決的問題:當中間減掉節點的時候,序號會發生變化,變為 0…n-1。因此需要在外面維護一個對映關係,動態對映到原先的節點上。

轉載請註明:http://blog.csdn.net/yeasy/article/details/50736182