哈希hash

hash的意思是散列，目的將一組輸入的數(shù)據(jù)均勻的分開、打散，往往用來配合路由算法做負載均衡，多用在分布式系統(tǒng)中。

比如memcached它只提供了K V的存儲、讀取，如果使用了多臺memcache做一個“邏輯集群”，就需要客戶端做“路由算法”，來保證數(shù)據(jù)均勻的進去，然后能“原路”拿出來。

常規(guī)哈希取模

常規(guī)哈希，往往結(jié)合取模運算，以便將請求轉(zhuǎn)發(fā)到后端的服務(wù)器上，如下圖：

第一步使用hash算法，將請求“打散”得到一個整數(shù)（比如傳遞過來一個請求，使用jdk類庫的hash對某個參數(shù)做計算），第二步將得到的參數(shù)對后端的服務(wù)器臺數(shù)取模，以上圖為例，加上有三臺服務(wù)器，那么id分別為1~6的請求會被轉(zhuǎn)發(fā)到1,2,0,1,2,0,上，不管請求id數(shù)是多少，總是這么周而復(fù)始的轉(zhuǎn)發(fā)。

假設(shè)上面是個緩存系統(tǒng)，以上請求為set請求，在服務(wù)器數(shù)量不變的情況下，對同樣的id做get請求，由于采用同樣的hash算法，那么肯定能原路找到對應(yīng)的key值。這個算法簡單，而且數(shù)據(jù)分散的均勻。

如果系統(tǒng)訪問量突增，為了擴容加了一臺機器，編號為3，此時有了4臺機器，采用同樣的算法再去get請求會如何？比如id=6，這個時候 6%4=2，我們知道set時值其實放進了索引為0的機器，這個時候就get不到了。這就是上面算法的弊端，在增減機器時會使舊的數(shù)據(jù)大量“失效”，也就是命中率下降。

不帶虛擬節(jié)點的一致性哈希算法

為了解決以上問題，聰明的人發(fā)明了一致性哈希算法。思路是這樣，hash算法出來的整數(shù)有個范圍，我們在這個范圍內(nèi)布置三臺服務(wù)器（范圍具體是多少看前面的hash算法）。假設(shè)hash的范圍是1~300，每臺負責(zé)一段范圍內(nèi)的請求，比如一臺負責(zé)(1~100]，一臺負責(zé)(100~200]，一臺負責(zé)(200~1]。這三臺server收尾相接覆蓋/閉環(huán)了所有請求，稱為哈希環(huán)，如下圖：

如何實現(xiàn)一臺服務(wù)器接收一個范圍的請求？這個時候不用取模了，而是將server也按照hash算法計算一個id值，比如按照他們的ip+port+name拼成的串計算，假設(shè)正好分別是 1，100，200，將他們放進一個treeMap里，Map<Inetger,Node> ，其中Node代表server節(jié)點，是自定義的數(shù)據(jù)結(jié)構(gòu)，比如是一個類，包含ip，port，name等屬性。我們的例子中，map里包含三個元素。

一個請求過來hash得到的值必屬于這三個server的范圍，比如一個請求id=N，那么從map里get(N)去找server，找到直接轉(zhuǎn)發(fā)，找不到進行如下運算：treemap里有個關(guān)鍵的api，tailMap()，這個接口能夠返回id比N大的map的子集，然后取子集的第一個節(jié)點，就是id=100的節(jié)點，通常稱為順時針查找。

//得到應(yīng)當(dāng)路由到的結(jié)點（示例代碼用String代表的節(jié)點）
private static String getServer(String key) {
	//得到該key的hash值
	int hash = getHash(key);
	//得到大于該Hash值的所有Map
	SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
	if(subMap.isEmpty()){
		//如果沒有比該key的hash值大的，則從第一個node開始
		Integer i = sortedMap.firstKey();
		//返回對應(yīng)的服務(wù)器
		return sortedMap.get(i);
	}else{
		//第一個Key就是順時針過去離node最近的那個結(jié)點
		Integer i = subMap.firstKey();
		//返回對應(yīng)的服務(wù)器
		return subMap.get(i);
	}
}

當(dāng)然如果子集為空，這意味著N>200，就取整個map的第一個節(jié)點，完成閉環(huán)。

分析：從實現(xiàn)可以看出，如果一個節(jié)點掛了，他的流量會順時針（逆時針實現(xiàn)也是一樣的）“導(dǎo)流”到下一個節(jié)點，其他節(jié)點不受影響。假如有100臺服務(wù)器，一臺掛了，其他99臺都能正常命中！這個算法比簡單的取模好了很多。

不過這里仍有個問題，假設(shè)各臺服務(wù)器性能差不多，此時流量突增，一臺server由于流量過載而掛掉，那么它的下一臺因為承載了2倍的流量，很有可能也會掛掉，依此類推，最后所有的節(jié)點都會掛掉，造成“雪崩”！

因此正常情況下，我們往往采用帶虛擬節(jié)點的一致性哈希算法（不特別說明的一致性哈希算法一般都是指的帶虛擬節(jié)點的算法）。

帶虛擬節(jié)點的一致性哈希算法

帶虛擬節(jié)點的一致性哈希算法是為了解決不帶虛擬節(jié)點算法的雪崩問題，虛擬節(jié)點也稱為分片。在上一步的基礎(chǔ)上理解虛擬節(jié)點是非常容易的。“虛擬”節(jié)點是server的副本、分身，每個虛擬節(jié)點存儲的server信息還是后面的物理地址，只不過每個server由一臺變成了多臺，這個時候往treeMap放節(jié)點時往往這么做：

for(i=1  -->  N) // N為每個server對應(yīng)的分片數(shù)量
{
   Map.put(hash(ip+port+name+i)，node) // 所有虛擬節(jié)點放進去
}
這個for循環(huán)外面還會有個循環(huán)，處理所有server node

由于每個server的ip，name不同，所以以上拼串hash后的值碰撞的概率是很小的，這樣所有的虛擬節(jié)點也會離散的分部到環(huán)上，形成的hash環(huán)如下圖，同樣顏色的虛擬節(jié)點同屬于一個server。

這個時候如果紅顏色的server掛了，它的虛擬節(jié)點負責(zé)的范圍會分別導(dǎo)航到下一個虛擬節(jié)點上，這些虛擬節(jié)點分別屬于不同的server，就避免了流量全部導(dǎo)流到一臺機器上。由于流量被均攤了，有效的減少了雪崩發(fā)生的概率。（理論上仍存在虛擬節(jié)點后面的虛擬節(jié)點屬于同一個server的情況，但是當(dāng)虛擬節(jié)點非常多時，這個概率是非常小的，而且這個分片數(shù)量是自定義的，往往設(shè)置幾百個）。

只要是hash算法，就有哈希碰撞的可能性，在增加server時，計算后的虛擬節(jié)點跟其他server的虛擬節(jié)點重復(fù)的話，也會導(dǎo)致部分緩存失效（可以通過算法改良）。

綜上，一致性哈希算法并不是強一致性，也不是高可用方案，如果server掛了數(shù)據(jù)丟了就是丟了，除非有恢復(fù)手段，它只是一種減少由擴縮容引起的命中率下降的手段。

到此這篇關(guān)于Java一致性Hash算法的實現(xiàn)詳解的文章就介紹到這了,更多相關(guān)Java一致性Hash算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論