一致性哈希算法是1997年由麻省理工的幾位學者提出的用于解決分布式緩存中的熱點問題。大家有沒有發(fā)現(xiàn)，我們之前介紹的例如快排之類的算法是更早的六七十年代，此時分布式還沒有發(fā)展起來，
大家往往還在提高單機性能。但是九十年代開始，逐漸需要用分布式集群來解決大型問題，相應(yīng)的算法研究也就應(yīng)運而生。
在說到一致性哈希算法，我們還是得先從緩存的發(fā)展談起：
緩存，我們一般是用來提速的，當規(guī)模或者說數(shù)據(jù)量小時，我們往往用單機來部署一套緩存系統(tǒng)即可，如下圖：

多臺客戶端在查詢數(shù)據(jù)時，只要根據(jù)key進入緩存服務(wù)器查詢到自己想要的內(nèi)容即可。
但是隨著業(yè)務(wù)的發(fā)展，單一的緩存服務(wù)器往往無法支撐住我們的業(yè)務(wù)需要。比如緩存數(shù)據(jù)太大，多城多活的網(wǎng)絡(luò)部署等，
我們就需要多臺緩存服務(wù)器來支撐，如下圖：

客戶端需要查詢緩存時，先根據(jù)哈希算法，講key進行計算，得到哈希值。然后通過哈希值對機器數(shù)取模（%n）來判定落在哪臺機器上。
這個架構(gòu)很簡單，也很易實現(xiàn)，我們就不多說了。(防盜連接：本文首發(fā)自http://www.cnblogs.com/jilodream/ )
但是這里會存在一個緩存服務(wù)器伸縮的問題：什么意思呢？比如目前是三臺，我們由于業(yè)務(wù)的需要，需要變?yōu)樗呐_，或者變?yōu)閮膳_。那么我們需要調(diào)整一遍所有數(shù)據(jù)所處的服務(wù)器位置，因為他們存在的位置都有可能改變。

分布式緩存本來就是為了解決大數(shù)據(jù)量問題的，此時重新調(diào)整，勢必會極度影響可用性。那么如何解決呢？
來看看一致性哈希算法的思路：
我們假設(shè)存在一個虛擬環(huán)，這個環(huán)足夠大，上邊存在2^32個節(jié)點，三臺器機器呢，我們根據(jù)id計算出他們在環(huán)中所處的位置，如圖所示：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-468555.html

當我們計算數(shù)據(jù)所處的緩存位置，不再是根據(jù)n來取模，而是根據(jù)2^32來取模，此時會有相當多的數(shù)據(jù)并沒有落在緩存服務(wù)器所處的節(jié)點上。
那怎么辦呢？我們按照順時針方向計算，將數(shù)據(jù)落在下一個最近的順時針節(jié)點上。
如下圖所示：

這樣當我們新增或者刪除節(jié)點時，只會影響有限的節(jié)點上的數(shù)據(jù)，極大的縮小了受影響的節(jié)點和數(shù)據(jù)。我們只需要重新計算受影響的數(shù)據(jù)即可，但是這樣還會存在新的問題：
1、緩存服務(wù)器計算出的位置不均勻，導致覆蓋的節(jié)點數(shù)差異明顯；(防盜連接：本文首發(fā)自http://www.cnblogs.com/jilodream/ )
2、數(shù)據(jù)并不均衡：數(shù)據(jù)經(jīng)過哈希和取模運算后，可能落在集中的一片區(qū)域中，造成對應(yīng)的緩存服務(wù)器的數(shù)據(jù)特別大。
以上問題我們稱之為數(shù)據(jù)傾斜。數(shù)據(jù)傾斜的程度明顯后，可能會導致所解決的問題再次出現(xiàn)（前文中的紅字部分）。
那如何解決這種問題呢？很簡單，加節(jié)點，只要節(jié)點足夠多，那么就會越來越趨于平均，數(shù)據(jù)傾斜的情況就會越不突出。但是緩存服務(wù)器是有限的，并不是想加多少都可以的。
那怎么辦呢？

我們可以采用虛擬緩存節(jié)點的形式解決問題。什么是虛擬緩存節(jié)點，就是并不實際存在的緩存節(jié)點。只是一個虛擬的點。
每個真實的緩存服務(wù)器對應(yīng)多個虛擬緩存節(jié)點，兩者是一對多的關(guān)系，如下圖所示：

虛擬節(jié)點--圖中連接在環(huán)上的就是虛擬緩存節(jié)點。
真實緩存節(jié)點--Cache
每個Cache對應(yīng)若干的虛擬節(jié)點。當增減Cache時，我們只要調(diào)整對應(yīng)的虛擬節(jié)點所對應(yīng)的數(shù)據(jù)即可。

?

到了這里，關(guān)于談?wù)勔恢滦怨Ｋ惴ǖ奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！