一致性哈希演算法是1997年由麻省理工的幾位學者提出的用於解決分散式緩存中的熱點問題。大家有沒有發現，我們之前介紹的例如快排之類的演算法是更早的六七十年代，此時分散式還沒有發展起來，大家往往還在提高單機性能。但是九十年代開始，逐漸需要用分散式集群來解決大型問題，相應的演算法研究也就應運而生。在說到一致性哈 ...
一致性哈希演算法是1997年由麻省理工的幾位學者提出的用於解決分散式緩存中的熱點問題。大家有沒有發現，我們之前介紹的例如快排之類的演算法是更早的六七十年代，此時分散式還沒有發展起來，
大家往往還在提高單機性能。但是九十年代開始，逐漸需要用分散式集群來解決大型問題，相應的演算法研究也就應運而生。
在說到一致性哈希演算法，我們還是得先從緩存的發展談起：
緩存，我們一般是用來提速的，當規模或者說數據量小時，我們往往用單機來部署一套緩存系統即可，如下圖：
多台客戶端在查詢數據時，只要根據key進入緩存伺服器查詢到自己想要的內容即可。
但是隨著業務的發展，單一的緩存伺服器往往無法支撐住我們的業務需要。比如緩存數據太大，多城多活的網路部署等，
我們就需要多台緩存伺服器來支撐，如下圖：
客戶端需要查詢緩存時，先根據哈希演算法，講key進行計算，得到哈希值。然後通過哈希值對機器數取模（%n）來判定落在哪台機器上。
這個架構很簡單，也很易實現，我們就不多說了。
但是這裡會存在一個緩存伺服器伸縮的問題：什麼意思呢？比如目前是三台，我們由於業務的需要，需要變為四台，或者變為兩台。那麼我們需要調整一遍所有數據所處的伺服器位置，因為他們存在的位置都有可能改變。
分散式緩存本來就是為瞭解決大數據量問題的，此時重新調整，勢必會極度影響可用性。那麼如何解決呢？
來看看一致性哈希演算法的思路：
我們假設存在一個虛擬環，這個環足夠大，上邊存在2^32個節點，三台器機器呢，我們根據id計算出他們在環中所處的位置，如圖所示：
當我們計算數據所處的緩存位置，不再是根據n來取模，而是根據2^32來取模，此時會有相當多的數據並沒有落在緩存伺服器所處的節點上。
那怎麼辦呢？我們按照順時針方向計算，將數據落在下一個最*的順時針節點上。
如下圖所示：
這樣當我們新增或者刪除節點時，只會影響有限的節點上的數據，極大的縮小了受影響的節點和數據。我們只需要重新計算受影響的數據即可，但是這樣還會存在新的問題：
1、緩存伺服器計算出的位置不均勻，導致覆蓋的節點數差異明顯；
2、數據並不均衡：數據經過哈希和取模運算後，可能落在集中的一片區域中，造成對應的緩存伺服器的數據特別大。
以上問題我們稱之為數據傾斜。數據傾斜的程度明顯後，可能會導致所解決的問題再次出現（前文中的紅字部分）。
那如何解決這種問題呢？很簡單，加節點，只要節點足夠多，那麼就會越來越趨*於*均，數據傾斜的情況就會越不突出。但是緩存伺服器是有限的，並不是想加多少都可以的。
那怎麼辦呢？
我們可以採用虛擬緩存節點的形式解決問題。什麼是虛擬緩存節點，就是並不實際存在的緩存節點。只是一個虛擬的點。
每個真實的緩存伺服器對應多個虛擬緩存節點，兩者是一對多的關係，如下圖所示：
虛擬節點--圖中連接在環上的就是虛擬緩存節點。
真實緩存節點--Cache
每個Cache對應若幹的虛擬節點。當增減Cache時，我們只要調整對應的虛擬節點所對應的數據即可。
如果你覺得寫的不錯，歡迎轉載和點贊。 轉載時請保留作者署名jilodream/王若伊_恩賜解脫（博客鏈接：http://www.cnblogs.com/jilodream/
