Hash環
我們把2~32次方想成一個環，比如鐘錶上有60個分針點組成一個圓，那麼hash環就是由2~32個點組成的圓。第一個點是0，最後一個點是2~32-1,我們把這2~32個點組成的環稱之為HASH環。
一致性Hash算法
將memcached物理機節點通過Hash算法虛擬到一個虛擬閉環上（由0到2~32構成），key請求的時候通過Hash算法計算出Hash值然後對2~32取模，定位到環上順時針方向最接近的虛擬物理節點就是要找到的緩存伺服器。
假設有ABC三台緩存伺服器：
我們使用這三台伺服器各自的IP進行hash計算然後對2~32取模即：
***Hash(伺服器IP)%2~32***
複製代碼
計算出來的結果是0到2~32-1的一個整數，那麼Hash環上必有一個點與之對應。比如：
現在緩存伺服器已經落到了Hash環上，接下來我們就看我們的數據是怎麼放到緩存伺服器的？
我們可以同樣對Object取Hash值然後對2~32取模，比如落到了接近A的一個點上：
那麼這個數據理應存到A這個緩存伺服器節點上
所以，在緩存伺服器節點數量不變的情況下，緩存的落點是不會變的。
但是如果B掛掉了呢？
按照hash且取模的算法，圖中3這個Object理應就分配到了C這個節點上去了，所以就會到C上找緩存數據，結果當然是找不到，進而從DB讀取數據重新放到了C上。
但是對於編號為1,2的Object還是落到A，編號為4的Object還是落到C，B宕機所影響的僅僅是3這個Object。這就是一致性Hash算法的優點。
Hash環的傾斜
前面我們理想化的把三台memcache機器均勻分到了Hash環上：
但是現實情況可能是：
如果Hash環傾斜，即緩存伺服器過於集中將會導致大量緩存數據被分配到了同一個伺服器上。比如編號1,2,3,4,6的Object都被存到了A，5被存到B，而C上竟然一個數據都沒有，這將造成內存空間的浪費。
為了解決這個問題，一致性Hash算法中使用「虛擬節點」解決。
虛擬節點解決Hash環傾斜
「虛擬節點」是「實際節點」在hash環上的複製品，一個實際節點可能對應多個虛擬節點。這樣就可以將ABC三台伺服器相對均勻分配到Hash環上，以減少Hash環傾斜的影響，使得緩存被均勻分配到hash環上。
Hash算法平衡性
平衡性指的是hash的結果儘可能分布到所有的緩存中去，這樣可以使得所有的緩存空間都可以得到利用。但是hash算法不保證絕對的平衡性，為了解決這個問題一致性hash引入了「虛擬節點」的概念。虛擬節點」（ virtual node ）是實際節點在 hash 空間的複製品（ replica ），一實際個節點對應了若干個「虛擬節點」，這個對應個數也成為「複製個數」，「虛擬節點」在 hash 空間中以 hash 值排列。「虛擬節點」的hash計算可以採用對應節點的IP位址加數字後綴的方式。
例如假設 cache A 的 IP 地址為202.168.14.241 。
複製代碼
引入「虛擬節點」前，計算 cache A 的 hash 值：
Hash(「202.168.14.241」);
複製代碼
引入「虛擬節點」後，計算「虛擬節」點 cache A1 和 cache A2 的 hash 值：
Hash(「202.168.14.241#1」); // cache A1
複製代碼
Hash(「202.168.14.241#2」); // cache A2
複製代碼
這樣只要是命中cacheA1和cacheA2節點，就相當於命中了cacheA的緩存。這樣平衡性就得到了提高。
各位老鐵，覺得可以麻煩點個讚謝謝了！！！
作者：Java2B
連結：https://juejin.im/post/5e21244fe51d453cee48d0f0