歡迎光臨
每天分享高質量文章

5分鐘理解一致性哈希演算法

(點擊上方藍字,快速關註我們)


來自:cywosp

鏈接:https://blog.csdn.net/cywosp/article/details/23397179

一致性哈希演算法在1997年由麻省理工學院提出的一種分佈式哈希(DHT)實現演算法,設計標的是為瞭解決因特網中的熱點(Hot spot)問題,初衷和CARP十分類似。一致性哈希修正了CARP使用的簡 單哈希演算法帶來的問題,使得分佈式哈希(DHT)可以在P2P環境中真正得到應用。

一致性hash演算法提出了在動態變化的Cache環境中,判定哈希演算法好壞的四個定義:

1、平衡性(Balance):平衡性是指哈希的結果能夠盡可能分佈到所有的緩衝中去,這樣可以使得所有的緩衝空間都得到利用。很多哈希演算法都能夠滿足這一條件。

2、單調性(Monotonicity):單調性是指如果已經有一些內容通過哈希分派到了相應的緩衝中,又有新的緩衝加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩衝中去,而不會被映射到舊的緩衝集合中的其他緩衝區。

3、分散性(Spread):在分佈式環境中,終端有可能看不到所有的緩衝,而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩衝上時,由於不同終端所見的緩衝範圍有可能不同,從而導致哈希的結果不一致,最終的結果是相同的內容被不同的終端映射到不同的緩衝區中。這種情況顯然是應該避免的,因為它導致相同內容被儲存到不同緩衝中去,降低了系統儲存的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠儘量避免不一致的情況發生,也就是儘量降低分散性。

4、負載(Load):負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩衝區中,那麼對於一個特定的緩衝區而言,也可能被不同的用戶映射為不同 的內容。與分散性一樣,這種情況也是應當避免的,因此好的哈希演算法應能夠儘量降低緩衝的負荷。

在分佈式集群中,對機器的添加刪除,或者機器故障後自動脫離集群這些操作是分佈式集群管理最基本的功能。如果採用常用的hash(object)%N演算法,那麼在有機器添加或者刪除後,很多原有的資料就無法找到了,這樣嚴重的違反了單調性原則。接下來主要講解一下一致性哈希演算法是如何設計的:

環形Hash空間

按照常用的hash演算法來將對應的key哈希到一個具有2^32次方個桶的空間中,即0~(2^32)-1的數字空間中。現在我們可以將這些數字頭尾相連,想象成一個閉合的環形。如下圖

把資料通過一定的hash演算法處理後映射到環上

現在我們將object1、object2、object3、object4四個物件通過特定的Hash函式計算出對應的key值,然後散列到Hash環上。如下圖:

Hash(object1) = key1;
Hash(object2) = key2;
Hash(object3) = key3;
Hash(object4) = key4;

將機器通過hash演算法映射到環上

在採用一致性哈希演算法的分佈式集群中將新的機器加入,其原理是通過使用與物件儲存一樣的Hash演算法將機器也映射到環中(一般情況下對機器的hash計算是採用機器的IP或者機器唯一的別名作為輸入值),然後以順時針的方向計算,將所有物件儲存到離自己最近的機器中。

假設現在有NODE1,NODE2,NODE3三台機器,通過Hash演算法得到對應的KEY值,映射到環中,其示意圖如下:

Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;

通過上圖可以看出物件與機器處於同一哈希空間中,這樣按順時針轉動object1儲存到了NODE1中,object3儲存到了NODE2中,object2、object4儲存到了NODE3中。在這樣的部署環境中,hash環是不會變更的,因此,通過算出物件的hash值就能快速的定位到對應的機器中,這樣就能找到物件真正的儲存位置了。

機器的刪除與添加

普通hash求餘演算法最為不妥的地方就是在有機器的添加或者刪除之後會照成大量的物件儲存位置失效,這樣就大大的不滿足單調性了。下麵來分析一下一致性哈希演算法是如何處理的。

1.節點(機器)的刪除

以上面的分佈為例,如果NODE2出現故障被刪除了,那麼按照順時針遷移的方法,object3將會被遷移到NODE3中,這樣僅僅是object3的映射位置發生了變化,其它的物件沒有任何的改動。如下圖:

2.節點(機器)的添加

如果往集群中添加一個新的節點NODE4,通過對應的哈希演算法得到KEY4,並映射到環中,如下圖:

通過按順時針遷移的規則,那麼object2被遷移到了NODE4中,其它物件還保持這原有的儲存位置。通過對節點的添加和刪除的分析,一致性哈希演算法在保持了單調性的同時,還是資料的遷移達到了最小,這樣的演算法對分佈式集群來說是非常合適的,避免了大量資料遷移,減小了服務器的的壓力。

平衡性

根據上面的圖解分析,一致性哈希演算法滿足了單調性和負載均衡的特性以及一般hash演算法的分散性,但這還並不能當做其被廣泛應用的原由,因為還缺少了平衡性。下麵將分析一致性哈希演算法是如何滿足平衡性的。hash演算法是不保證平衡的,如上面只部署了NODE1和NODE3的情況(NODE2被刪除的圖),object1儲存到了NODE1中,而object2、object3、object4都儲存到了NODE3中,這樣就照成了非常不平衡的狀態。在一致性哈希演算法中,為了盡可能的滿足平衡性,其引入了虛擬節點。

——“虛擬節點”( virtual node )是實際節點(機器)在 hash 空間的複製品( replica ),一實際個節點(機器)對應了若干個“虛擬節點”,這個對應個數也成為“複製個數”,“虛擬節點”在 hash 空間中以hash值排列。

以上面只部署了NODE1和NODE3的情況(NODE2被刪除的圖)為例,之前的物件在機器上的分佈很不均衡,現在我們以2個副本(複製個數)為例,這樣整個hash環中就存在了4個虛擬節點,最後物件映射的關係圖如下:

根據上圖可知物件的映射關係:object1->NODE1-1,object2->NODE1-2,object3->NODE3-2,object4->NODE3-1。通過虛擬節點的引入,物件的分佈就比較均衡了。那麼在實際操作中,正真的物件查詢是如何工作的呢?物件從hash到虛擬節點到實際節點的轉換如下圖:

“虛擬節點”的hash計算可以採用對應節點的IP地址加數字後綴的方式。例如假設NODE1的IP地址為192.168.1.100。引入“虛擬節點”前,計算 cache A 的 hash 值:

Hash(“192.168.1.100”);

引入“虛擬節點”後,計算“虛擬節”點NODE1-1和NODE1-2的hash值:

Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2

參考:

[1] http://blog.huanghao.me/?p=14

覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂