分布式緩存負(fù)載均衡的規(guī)則處理：虛擬節(jié)點對一致性哈希的改進(jìn) 采用固定哈希算法平衡負(fù)載

在大規(guī)模的緩存應(yīng)用中，應(yīng)運而生了分布式緩存系統(tǒng)。key-value如何均勻的分散到集群中？最常規(guī)的方式莫過于hash取模的方式。比如集群中可用機器適量為N，那么key值為K的的數(shù)據(jù)請求很簡單的應(yīng)該路由到hash(K) mod N對應(yīng)的機器。但是在一些高速發(fā)展的web系統(tǒng)中，這樣的解決方案仍有些缺陷。隨著系統(tǒng)訪問壓力的增長，緩存系統(tǒng)不得不通過增加機器節(jié)點的方式提高集群的相應(yīng)速度和數(shù)據(jù)承載量。增加機器意味著按照hash取模的方式，在增加機器節(jié)點的這一時刻，大量的緩存命不中，緩存數(shù)據(jù)需要重新建立，甚至是進(jìn)行整體的緩存數(shù)據(jù)遷移，瞬間會給DB帶來極高的系統(tǒng)負(fù)載，設(shè)置導(dǎo)致DB服務(wù)器宕機。

如果不是緩存數(shù)據(jù)，而是持久化的數(shù)據(jù)，那么當(dāng)擴(kuò)容的時候，絕大部分?jǐn)?shù)據(jù)都要遷移（取模的基數(shù)N變化了），這也是不能忍受的。

一致性哈希平衡負(fù)載

引入一致性哈希，解決以上增減機器導(dǎo)致負(fù)載瞬間整體增大問題

通過在整數(shù)范圍內(nèi)負(fù)責(zé)各區(qū)域的方式，節(jié)點負(fù)責(zé)區(qū)域的負(fù)載不會隨著增減節(jié)點發(fā)生大規(guī)模的遷移

但是最簡單的一致性哈希，在增減物理機的時候，似乎要增加一倍節(jié)點或減去一半節(jié)點才能保證各個節(jié)點的負(fù)載均衡

虛擬節(jié)點對一致性哈希的改進(jìn)

對于一致性哈希的負(fù)載分布不平均問題，所以提出：虛擬節(jié)點對一致性哈希的改進(jìn)

4個物理節(jié)點可以變成很多個虛擬節(jié)點，每個虛擬節(jié)點支持連續(xù)的哈希環(huán)上的一段。而這時如果加入一個物理節(jié)點，就會相應(yīng)加入很多虛擬節(jié)點，這些新的虛擬節(jié)點是相對均勻地插入到整個哈希環(huán)上，這樣，就可以很好的分擔(dān)現(xiàn)有物理節(jié)點的壓力了；如果減少一個物理節(jié)點，對應(yīng)的很多虛擬節(jié)點就會失效，這樣，就會有很多剩余的虛擬節(jié)點來承擔(dān)之前虛擬節(jié)點的工作，但是對于物理節(jié)點來說，增加的負(fù)載相對是均衡的。

所以可以通過一個物理節(jié)點對應(yīng)非常多的虛擬節(jié)點，并且同一個物理節(jié)點的虛擬節(jié)點盡量均勻分布的方式來解決增加或減少節(jié)點時負(fù)載不均衡的問題。

至于一個物理節(jié)點對應(yīng)多少的虛擬節(jié)點才能達(dá)到比較好的均衡效果，有一個圖

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

映射表與規(guī)則自定義計算方式

映射表示根據(jù)分庫分表字段的值的查表法來確定數(shù)據(jù)源的方法，一般用于對熱點數(shù)據(jù)的特殊處理，或者在一些場景下對不完全符合規(guī)律的規(guī)則進(jìn)行補充。

可以通過自定義函數(shù)實現(xiàn)來計算最終的分庫，舉例來說，假設(shè)根據(jù)id取模分成了4個庫，但是對于一些熱點id，我們希望將其獨立到另外的庫，那么通過類似下面的表達(dá)式可以完成：

if (id in hotset) {
return nodes;
}
return hash(id);