一.歷史：
一致哈希由MIT的Karger及其合作者提出肖揣，現(xiàn)在這一思想已經擴展到其它領域理疙。在這篇1997年發(fā)表的學術論文中介紹了“一致哈洗用模”如何應用于用戶易變的分布式Web服務中痹扇。哈希表中的每一個代表分布式系統(tǒng)中一個節(jié)點，在系統(tǒng)添加或刪除節(jié)點只需要移動K/n項担租。
二.需求：
在使用n臺緩存服務器時砸民，一種常用的負載均衡方式是，對資源o的請求使用hash(o)=o mod n來映射到某一臺緩存服務器。當增加或減少一臺緩存服務器時這種方式可能會改變所有資源對應的hash值岭参，也就是所有的緩存都失效了反惕，這會使得緩存服務器大量集中地向原始內容服務器更新緩存。因此需要一致哈希算法來避免這樣的問題演侯。 一致哈希盡可能使同一個資源映射到同一臺緩存服務器姿染。這種方式要求增加一臺緩存服務器時，新的服務器盡量分擔存儲其他所有服務器的緩存資源秒际。減少一臺緩存服務器時悬赏，其他所有服務器也可以盡量分擔存儲它的緩存資源。 一致哈希算法的主要思想是將每個緩存服務器與一個或多個哈希值域區(qū)間關聯(lián)起來娄徊，其中區(qū)間邊界通過計算緩存服務器對應的哈希值來決定舷嗡。（定義區(qū)間的哈希函數不一定和計算緩存服務器哈希值的函數相同，但是兩個函數的返回值的范圍需要匹配嵌莉。）如果一個緩存服務器被移除，則它所對應的區(qū)間會被并入到鄰近的區(qū)間捻脖，其他的緩存服務器不需要任何改變锐峭。
三.實現(xiàn)：
一致性哈希將每個對象映射到圓環(huán)邊上的一個點，系統(tǒng)再將可用的節(jié)點機器映射到圓環(huán)的不同位置可婶。查找某個對象對應的機器時沿癞，需要用一致哈希算法計算得到對象對應圓環(huán)邊上位置，沿著圓環(huán)邊上查找直到遇到某個節(jié)點機器矛渴，這臺機器即為對象應該保存的位置椎扬。 當刪除一臺節(jié)點機器時，這臺機器上保存的所有對象都要移動到下一臺機器具温。添加一臺機器到圓環(huán)邊上某個點時蚕涤，這個點的下一臺機器需要將這個節(jié)點前對應的對象移動到新機器上。 更改對象在節(jié)點機器上的分布可以通過調整節(jié)點機器的位置來實現(xiàn)铣猩。
1.按照常用的hash算法來將對應的key哈希到一個具有2^32次方個桶的空間中揖铜，即0~(2^32)-1的數字空間中。現(xiàn)在我們可以將這些數字頭尾相連达皿，想象成一個閉合的環(huán)形天吓。如下圖
2.把數據通過一定的hash算法處理后映射到環(huán)上
現(xiàn)在我們將object1、object2峦椰、object3龄寞、object4四個對象通過特定的Hash函數計算出對應的key值，然后散列到Hash環(huán)上汤功。如下圖：
? ? Hash(object1) = key1物邑；
? ? Hash(object2) = key2；
? ? Hash(object3) = key3；
? ? Hash(object4) = key4拂封；
3.將機器通過hash算法映射到環(huán)上
在采用一致性哈希算法的分布式集群中將新的機器加入茬射，其原理是通過使用與對象存儲一樣的Hash算法將機器也映射到環(huán)中（一般情況下對機器的hash計算是采用機器的IP或者機器唯一的別名作為輸入值），然后以順時針的方向計算冒签，將所有對象存儲到離自己最近的機器中在抛。
假設現(xiàn)在有NODE1，NODE2萧恕，NODE3三臺機器刚梭，通過Hash算法得到對應的KEY值，映射到環(huán)中票唆，其示意圖如下：
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
通過上圖可以看出對象與機器處于同一哈掀佣粒空間中，這樣按順時針轉動object1存儲到了NODE1中走趋，object3存儲到了NODE2中衅金，object2、object4存儲到了NODE3中簿煌。在這樣的部署環(huán)境中氮唯，hash環(huán)是不會變更的，因此姨伟，通過算出對象的hash值就能快速的定位到對應的機器中惩琉，這樣就能找到對象真正的存儲位置了。
4.機器的刪除與添加
普通hash求余算法最為不妥的地方就是在有機器的添加或者刪除之后會照成大量的對象存儲位置失效夺荒，這樣就大大的不滿足單調性了瞒渠。下面來分析一下一致性哈希算法是如何處理的。
1. 節(jié)點（機器）的刪除
? ? 以上面的分布為例技扼，如果NODE2出現(xiàn)故障被刪除了伍玖，那么按照順時針遷移的方法，object3將會被遷移到NODE3中剿吻，這樣僅僅是object3的映射位置發(fā)生了變化私沮，其它的對象沒有任何的改動。如下圖：
如果往集群中添加一個新的節(jié)點NODE4和橙，通過對應的哈希算法得到KEY4仔燕，并映射到環(huán)中，如下圖：
通過按順時針遷移的規(guī)則魔招，那么object2被遷移到了NODE4中晰搀，其它對象還保持這原有的存儲位置。通過對節(jié)點的添加和刪除的分析办斑，一致性哈希算法在保持了單調性的同時外恕，還是數據的遷移達到了最小杆逗，這樣的算法對分布式集群來說是非常合適的，避免了大量數據遷移鳞疲，減小了服務器的的壓力罪郊。
5.數據節(jié)點分布平衡調整
根據上面的圖解分析，一致性哈希算法滿足了單調性和負載均衡的特性以及一般hash算法的分散性尚洽，但這還并不能當做其被廣泛應用的原由悔橄，因為還缺少了平衡性。下面將分析一致性哈希算法是如何滿足平衡性的腺毫。hash算法是不保證平衡的癣疟，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖），object1存儲到了NODE1中潮酒，而object2睛挚、object3、object4都存儲到了NODE3中急黎，這樣就照成了非常不平衡的狀態(tài)扎狱。在一致性哈希算法中，為了盡可能的滿足平衡性勃教，其引入了虛擬節(jié)點淤击。
? ? ——“虛擬節(jié)點”（ virtual node ）是實際節(jié)點（機器）在 hash 空間的復制品（ replica ），一實際個節(jié)點（機器）對應了若干個“虛擬節(jié)點”荣回，這個對應個數也成為“復制個數”，“虛擬節(jié)點”在 hash 空間中以hash值排列戈咳。
以上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例心软，之前的對象在機器上的分布很不均衡，現(xiàn)在我們以2個副本（復制個數）為例著蛙，這樣整個hash環(huán)中就存在了4個虛擬節(jié)點删铃，最后對象映射的關系圖如下：
根據上圖可知對象的映射關系：object1->NODE1-1，object2->NODE1-2踏堡，object3->NODE3-2猎唁，object4->NODE3-1。通過虛擬節(jié)點的引入顷蟆，對象的分布就比較均衡了诫隅。那么在實際操作中，正真的對象查詢是如何工作的呢帐偎？對象從hash到虛擬節(jié)點到實際節(jié)點的轉換如下圖：
虛擬節(jié)點”的hash計算可以采用對應節(jié)點的IP地址加數字后綴的方式逐纬。例如假設NODE1的IP地址為192.168.1.100。引入“虛擬節(jié)點”前削樊，計算 cache A 的 hash 值：
Hash(“192.168.1.100”);
引入“虛擬節(jié)點”后豁生，計算“虛擬節(jié)”點NODE1-1和NODE1-2的hash值：
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2
四.特性
致哈希在互聯(lián)網分布式緩存中非常有用的幾個特性：
1.冗余少
2.負載均衡
3.過渡平滑
4.存儲均衡
5.關鍵詞單調
5.使用
1.一致哈希也可用于實現(xiàn)健壯緩存來減少大型Web應用中系統(tǒng)部分失效帶來的負面影響兔毒。
2.一致哈希的概念還被應用于分布式散列表（DHT）的設計。DHT使用一致哈希來劃分分布式系統(tǒng)的節(jié)點甸箱。所有關鍵字都可以通過一個連接所有節(jié)點的覆蓋網絡高效地定位到某個節(jié)點育叁。
本文整合維基百科和每天進步一點點——五分鐘理解一致性哈希算法(consistent hashing) - Cynric 的博客 - CSDN博客兩篇文章
