一致性hash算法是什麼？
一致性hash算法，是麻省理工學院1997年提出的一種算法，目前主要應用於分佈式緩存當中。
一致性hash算法可以有效地解決分佈式存儲結構下動態增加和刪除節點所帶來的問題。
在Memcached、Key-Value Store、Bittorrent DHT、LVS中都採用了一致性hash算法，可以説一致性hash算法是分佈式系統負載均衡的首選算法。
傳統hash算法的弊端
常用的算法是對hash結果取餘數 (hash() mod N)：對機器編號從0到N-1，按照自定義的hash算法，對每個請求的hash值按N取模，得到餘數i，然後將請求分發到編號為i的機器。但這樣的算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法得到正確的處理，這時需要將宕掉的服務器使用算法去除，此時候會有(N-1)/N的服務器的緩存數據需要重新進行計算；如果新增一台機器，會有N /(N+1)的服務器的緩存數據需要進行重新計算。對於系統而言，這通常是不可接受的顛簸（因為這意味着大量緩存的失效或者數據需要轉移）。
傳統求餘做負載均衡算法，緩存節點數由3個變成4個，緩存不命中率為75%。計算方法：窮舉hash值為1-12的12個數字分別對3和4取模，然後比較發現只有前3個緩存節點對應結果和之前相同，所以有75%的節點緩存會失效，可能會引起緩存雪崩。
一致性hash算法
- 首先，我們將hash算法的值域映射成一個具有232 次方個桶的空間中，即0~（232）-1的數字空間。現在我們可以將這些數字頭尾相連，組合成一個閉合的環形。
- 每一個緩存key都可以通過Hash算法轉化為一個32位的二進制數，也就對應着環形空間的某一個緩存區。我們把所有的緩存key映射到環形空間的不同位置。
- 我們的每一個緩存節點也遵循同樣的Hash算法，比如利用IP或者主機名做Hash，映射到環形空間當中，如下圖
- 如何讓key和緩存節點對應起來呢？很簡單，每一個key的順時針方向最近節點，就是key所歸屬的緩存節點。所以圖中key1存儲於node1，key2，key3存儲於node2，key4存儲於node3。
- 當緩存的節點有增加或刪除的時候，一致性哈希的優勢就顯現出來了。讓我們來看看實現的細節：
- 增加節點
當緩存集羣的節點有所增加的時候，整個環形空間的映射仍然會保持一致性哈希的順時針規則，所以有一小部分key的歸屬會受到影響。
有哪些key會受到影響呢？圖中加入了新節點node4，處於node1和node2之間，按照順時針規則，從node1到node4之間的緩存不再歸屬於node2，而是歸屬於新節點node4。因此受影響的key只有key2。
最終把key2的緩存數據從node2遷移到node4，就形成了新的符合一致性哈希規則的緩存結構。
- 刪除節點
當緩存集羣的節點需要刪除的時候（比如節點掛掉），整個環形空間的映射同樣會保持一致性哈希的順時針規則，同樣有一小部分key的歸屬會受到影響。
有哪些key會受到影響呢？圖中刪除了原節點node3，按照順時針規則，原本node3所擁有的緩存數據就需要“託付”給node3的順時針後繼節點node1。因此受影響的key只有key4。
最終把key4的緩存數據從node3遷移到node1，就形成了新的符合一致性哈希規則的緩存結構。
説明：這裏所説的遷移並不是直接的數據遷移，而是在查找時去找順時針的後繼節點，因緩存未命中而刷新緩存。
計算方法：假設節點hash散列均勻（由於hash是散列表，所以並不是很理想），採用一致性hash算法，緩存節點從3個增加到4個時，會有0-33%的緩存失效，此外新增節點不會環節所有原有節點的壓力。
一致性hash算法的結果相比傳統hash求餘算法已經進步很多，但可不可以改進一下呢？或者如果出現分佈不均勻的情況怎麼辦？比如下圖這樣，按順時針規則，所有的key都歸屬於統一個節點。
一致性hash算法+虛擬節點
為了優化這種節點太少而產生的不均衡情況。一致性哈希算法引入了虛擬節點的概念。
所謂虛擬節點，就是基於原來的物理節點映射出N個子節點，最後把所有的子節點映射到環形空間上。
虛擬節點越多，分佈越均勻。使用一致性hash算法+虛擬節點這種情況下，緩存節點從3個變成4個，緩存失效率為25%，而且每個節點都平均的承擔了壓力。
一致性hash算法+虛擬節點的實現
原理理解了，實現並不難，主要是一些細節：
- hash算法的選擇。Java代碼不要使用hashcode函數，這個函數結果不夠散列，而且會有負值需要處理。
這種計算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默認的MemCache推薦的一致性Hash算法，用別的Hash算法也可以，比如FNV1_32_HASH算法的計算效率就會高一些。 - 數據結構的選擇。根據算法原理，我們的算法有幾個要求：
- 要能根據hash值排序存儲
- 排序存儲要被快速查找 （List不行）
- 排序查找還要能方便變更 （Array不行）
