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