在大型web應(yīng)用中，緩存可算是當(dāng)今的一個(gè)標(biāo)準(zhǔn)開(kāi)發(fā)配置了。在大規(guī)模的緩存應(yīng)用中，應(yīng)運(yùn)而生了分布式緩存系統(tǒng)。分布式緩存系統(tǒng)的基本原理，大家也有所耳聞。key-value如何均勻的分散到集群中？說(shuō)到此，最常規(guī)的方式莫過(guò)于hash取模的方式。比如集群中可用機(jī)器適量為N，那么key值為K的的數(shù)據(jù)請(qǐng)求很簡(jiǎn)單的應(yīng)該路由到hash(K) mod N對(duì)應(yīng)的機(jī)器。的確，這種結(jié)構(gòu)是簡(jiǎn)單的，也是實(shí)用的。但是在一些高速發(fā)展的web系統(tǒng)中，這樣的解決方案仍有些缺陷。隨著系統(tǒng)訪問(wèn)壓力的增長(zhǎng)，緩存系統(tǒng)不得不通過(guò)增加機(jī)器節(jié)點(diǎn)的方式提高集群的相應(yīng)速度和數(shù)據(jù)承載量。增加機(jī)器意味著按照hash取模的方式，在增加機(jī)器節(jié)點(diǎn)的這一時(shí)刻，大量的緩存命不中，緩存數(shù)據(jù)需要重新建立，甚至是進(jìn)行整體的緩存數(shù)據(jù)遷移，瞬間會(huì)給DB帶來(lái)極高的系統(tǒng)負(fù)載，設(shè)置導(dǎo)致DB服務(wù)器宕機(jī)。那么就沒(méi)有辦法解決hash取模的方式帶來(lái)的詬病嗎？看下文。

一致性哈希（Consistent Hashing）：

      選擇具體的機(jī)器節(jié)點(diǎn)不在只依賴需要緩存數(shù)據(jù)的key的hash本身了，而是機(jī)器節(jié)點(diǎn)本身也進(jìn)行了hash運(yùn)算。

（1） hash機(jī)器節(jié)點(diǎn)

首先求出機(jī)器節(jié)點(diǎn)的hash值（怎么算機(jī)器節(jié)點(diǎn)的hash？ip可以作為hash的參數(shù)吧。。當(dāng)然還有其他的方法了），然后將其分布到0～2^32的一個(gè)圓環(huán)上（順時(shí)針?lè)植迹Ｈ缦聢D所示：

 

集群中有機(jī)器：A , B, C, D, E五臺(tái)機(jī)器，通過(guò)一定的hash算法我們將其分布到如上圖所示的環(huán)上。

（2）訪問(wèn)方式

如果有一個(gè)寫入緩存的請(qǐng)求，其中Key值為K，計(jì)算器hash值Hash(K)， Hash(K) 對(duì)應(yīng)于圖 – 1環(huán)中的某一個(gè)點(diǎn)，如果該點(diǎn)對(duì)應(yīng)沒(méi)有映射到具體的某一個(gè)機(jī)器節(jié)點(diǎn)，那么順時(shí)針查找，直到第一次找到有映射機(jī)器的節(jié)點(diǎn)，該節(jié)點(diǎn)就是確定的目標(biāo)節(jié)點(diǎn)，如果超過(guò)了2^32仍然找不到節(jié)點(diǎn)，則命中第一個(gè)機(jī)器節(jié)點(diǎn)。比如 Hash(K) 的值介于A~B之間，那么命中的機(jī)器節(jié)點(diǎn)應(yīng)該是B節(jié)點(diǎn)（如上圖 ）。

（3）增加節(jié)點(diǎn)的處理

如上圖 – 1，在原有集群的基礎(chǔ)上欲增加一臺(tái)機(jī)器F，增加過(guò)程如下：

計(jì)算機(jī)器節(jié)點(diǎn)的Hash值，將機(jī)器映射到環(huán)中的一個(gè)節(jié)點(diǎn)，如下圖：

 

增加機(jī)器節(jié)點(diǎn)F之后，訪問(wèn)策略不改變，依然按照（2）中的方式訪問(wèn)，此時(shí)緩存命不中的情況依然不可避免，不能命中的數(shù)據(jù)是hash(K)在增加節(jié)點(diǎn)以前落在C～F之間的數(shù)據(jù)。盡管依然存在節(jié)點(diǎn)增加帶來(lái)的命中問(wèn)題，但是比較傳統(tǒng)的 hash取模的方式，一致性hash已經(jīng)將不命中的數(shù)據(jù)降到了最低。

 

Consistent Hashing最大限度地抑制了hash鍵的重新分布。另外要取得比較好的負(fù)載均衡的效果，往往在服務(wù)器數(shù)量比較少的時(shí)候需要增加虛擬節(jié)點(diǎn)來(lái)保證服務(wù)器能均勻的分布在圓環(huán)上。因?yàn)槭褂靡话愕膆ash方法，服務(wù)器的映射地點(diǎn)的分布非常不均勻。使用虛擬節(jié)點(diǎn)的思想，為每個(gè)物理節(jié)點(diǎn)（服務(wù)器）在圓上分配100～200個(gè)點(diǎn)。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時(shí)的緩存重新分布。用戶數(shù)據(jù)映射在虛擬節(jié)點(diǎn)上，就表示用戶數(shù)據(jù)真正存儲(chǔ)位置是在該虛擬節(jié)點(diǎn)代表的實(shí)際物理服務(wù)器上。
下面有一個(gè)圖描述了需要為每臺(tái)物理服務(wù)器增加的虛擬節(jié)點(diǎn)。

 

x軸表示的是需要為每臺(tái)物理服務(wù)器擴(kuò)展的虛擬節(jié)點(diǎn)倍數(shù)(scale)，y軸是實(shí)際物理服務(wù)器數(shù)，可以看出，當(dāng)物理服務(wù)器的數(shù)量很小時(shí)，需要更大的虛擬節(jié)點(diǎn)，反之則需要更少的節(jié)點(diǎn)，從圖上可以看出，在物理服務(wù)器有10臺(tái)時(shí)，差不多需要為每臺(tái)服務(wù)器增加100~200個(gè)虛擬節(jié)點(diǎn)才能達(dá)到真正的負(fù)載均衡。

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。