一緻性雜湊演算法的應用及實作

一緻性雜湊演算法(consistent hashing algorithm)是一種分布式算法，

由mit的karger及其合作者提出，現在這一思想已經擴充到其它領域。

1997年發表的學術論文中介紹了“一緻性哈希”如何應用于使用者易變的分布式web服務中。

一緻性哈希可用于實作健壯緩存來減少大型web應用中系統部分失效帶來的負面影響。（維基百科）

hash 算法的一個衡量名額是單調性（ monotonicity ），定義如下：

單調性是指如果已經有一些内容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已配置設定的内容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

一緻性哈希是一種特殊的雜湊演算法。在使用一緻性雜湊演算法後，哈希表槽位數（大小）的改變平均隻需要對k/n 個關鍵字重新映射，

其中 k是關鍵字的數量，n是槽位數量。然而在傳統的哈希表中，添加或删除一個槽位的幾乎需要對所有關鍵字進行重新映射。（維基百科）

一緻性雜湊演算法是分布式系統中常用的算法。一個分布式的存儲系統，要将資料存儲到具體的節點上，如果采用普通的hash方法，将資料映射到具體的節點上，如key%n，key是資料的key，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中，其它對象還保持這原有的存儲位置。通過對節點的添加和删除的分析，一緻性雜湊演算法在保持了單調性的同時，還是資料的遷移達到了最小，這樣的算法對分布式叢集來說是非常合适的，避免了大量資料遷移，減小了伺服器的的壓力。

可以看出，一緻性哈希實際上是對資料和節點同時做了哈希，

然後通過一個環形的位址空間找到對應的映射，避免了節點增删時的大量的位址變動。

一緻性雜湊演算法解決了取模操作無法應對增删memcached server的問題，

增删server會導緻同一個key,在get操作時配置設定不到資料真正存儲的server，命中率會急劇下降。

目前使用較多的是稱為ketama的hash算法，通過虛拟節點的思想，解決memcached的分布式問題。