Java語(yǔ)言ConsistentHash算法怎么用-創(chuàng)新互聯(lián)

這篇文章主要為大家展示了“Java語(yǔ)言Consistent Hash算法怎么用”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“Java語(yǔ)言Consistent Hash算法怎么用”這篇文章吧。

成都創(chuàng)新互聯(lián)從2013年創(chuàng)立，是專(zhuān)業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站建設(shè)、網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元漢陰做網(wǎng)站,已為上家服務(wù),為漢陰各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話(huà):13518219792一致性哈希(Consistent Hash)協(xié)議簡(jiǎn)介

一致性哈希算法在1997年由麻省理工學(xué)院提出(參見(jiàn)0)，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot pot)問(wèn)題，初衷和CARP十分類(lèi)似。一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來(lái)的問(wèn)題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。

哈希算法

一致性哈希提出了在動(dòng)態(tài)變化的Cache環(huán)境中，哈希算法應(yīng)該滿(mǎn)足的4個(gè)適應(yīng)條件：

平衡性(Balance)

平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩存中去，這樣可以使得所有的緩存空間都得到利用。很多哈希算法都能夠滿(mǎn)足這一條件。

單調(diào)性(Monotonicity)

單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩存中，又有新的緩存加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩存中去，而不會(huì)被映射到舊的緩存集合中的其他緩沖區(qū)。

簡(jiǎn)單的哈希算法往往不能滿(mǎn)足單調(diào)性的要求，如最簡(jiǎn)單的線性哈希：

x → ax + b mod (P)

在上式中，P表示全部緩存的大小。不難看出，當(dāng)緩存大小發(fā)生變化時(shí)(從P1到P2)，原來(lái)所有的哈希結(jié)果均會(huì)發(fā)生變化，從而不滿(mǎn)足單調(diào)性的要求。

哈希結(jié)果的變化意味著當(dāng)緩存空間發(fā)生變化時(shí)，所有的映射關(guān)系需要在系統(tǒng)內(nèi)全部更新。而在P2P系統(tǒng)內(nèi)，緩存的變化等價(jià)于Peer加入或退出系統(tǒng)，這一情況在P2P系統(tǒng)中會(huì)頻繁發(fā)生，因此會(huì)帶來(lái)極大計(jì)算和傳輸負(fù)荷。單調(diào)性就是要求哈希算法能夠避免這一情況的發(fā)生。

分散性(Spread)

在分布式環(huán)境中，終端有可能看不到所有的緩存，而是只能看到其中的一部分。當(dāng)終端希望通過(guò)哈希過(guò)程將內(nèi)容映射到緩存上時(shí)，由于不同終端所見(jiàn)的緩存范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩存區(qū)中。這種情況顯然是應(yīng)該避免的，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不同緩沖中去，降低了系統(tǒng)存儲(chǔ)的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。

負(fù)載(Load)

負(fù)載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶(hù)映射為不同的內(nèi)容。與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

從表面上看，一致性哈希針對(duì)的是分布式緩沖的問(wèn)題，但是如果將緩沖看作P2P系統(tǒng)中的Peer，將映射的內(nèi)容看作各種共享的資源(數(shù)據(jù)，文件，媒體流等)，就會(huì)發(fā)現(xiàn)兩者實(shí)際上是在描述同一問(wèn)題。

路由算法

在一致性哈希算法中，每個(gè)節(jié)點(diǎn)(對(duì)應(yīng)P2P系統(tǒng)中的Peer)都有隨機(jī)分配的ID。在將內(nèi)容映射到節(jié)點(diǎn)時(shí)，使用內(nèi)容的關(guān)鍵字和節(jié)點(diǎn)的ID進(jìn)行一致性哈希運(yùn)算并獲得鍵值。一致性哈希要求鍵值和節(jié)點(diǎn)ID處于同一值域。最簡(jiǎn)單的鍵值和ID可以是一維的，比如從0000到9999的整數(shù)集合。

根據(jù)鍵值存儲(chǔ)內(nèi)容時(shí)，內(nèi)容將被存儲(chǔ)到具有與其鍵值最接近的ID的節(jié)點(diǎn)上。例如鍵值為1001的內(nèi)容，系統(tǒng)中有ID為1000，1010，1100的節(jié)點(diǎn)，該內(nèi)容將被映射到1000節(jié)點(diǎn)。

為了構(gòu)建查詢(xún)所需的路由，一致性哈希要求每個(gè)節(jié)點(diǎn)存儲(chǔ)其上行節(jié)點(diǎn)(ID值大于自身的節(jié)點(diǎn)中最小的)和下行節(jié)點(diǎn)(ID值小于自身的節(jié)點(diǎn)中大的)的位置信息(IP地址)。當(dāng)節(jié)點(diǎn)需要查找內(nèi)容時(shí)，就可以根據(jù)內(nèi)容的鍵值決定向上行或下行節(jié)點(diǎn)發(fā)起查詢(xún)請(qǐng)求。收到查詢(xún)請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自己擁有被請(qǐng)求的目標(biāo)，可以直接向發(fā)起查詢(xún)請(qǐng)求的節(jié)點(diǎn)返回確認(rèn);如果發(fā)現(xiàn)不屬于自身的范圍，可以轉(zhuǎn)發(fā)請(qǐng)求到自己的上行/下行節(jié)點(diǎn)。

為了維護(hù)上述路由信息，在節(jié)點(diǎn)加入/退出系統(tǒng)時(shí)，相鄰的節(jié)點(diǎn)必須及時(shí)更新路由信息。這就要求節(jié)點(diǎn)不僅存儲(chǔ)直接相連的下行節(jié)點(diǎn)位置信息，還要知道一定深度(n跳)的間接下行節(jié)點(diǎn)信息，并且動(dòng)態(tài)地維護(hù)節(jié)點(diǎn)列表。當(dāng)節(jié)點(diǎn)退出系統(tǒng)時(shí)，它的上行節(jié)點(diǎn)將嘗試直接連接到最近的下行節(jié)點(diǎn)，連接成功后，從新的下行節(jié)點(diǎn)獲得下行節(jié)點(diǎn)列表并更新自身的節(jié)點(diǎn)列表。同樣的，當(dāng)新的節(jié)點(diǎn)加入到系統(tǒng)中時(shí)，首先根據(jù)自身的ID找到下行節(jié)點(diǎn)并獲得下行節(jié)點(diǎn)列表，然后要求上行節(jié)點(diǎn)修改其下行節(jié)點(diǎn)列表，這樣就恢復(fù)了路由關(guān)系。

討論

一致性哈?；窘鉀Q了在P2P環(huán)境中最為關(guān)鍵的問(wèn)題——如何在動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯?chǔ)和路由。每個(gè)節(jié)點(diǎn)僅需維護(hù)少量相鄰節(jié)點(diǎn)的信息，并且在節(jié)點(diǎn)加入/退出系統(tǒng)時(shí)，僅有相關(guān)的少量節(jié)點(diǎn)參與到拓?fù)涞木S護(hù)中。所有這一切使得一致性哈希成為第一個(gè)實(shí)用的DHT算法。

但是一致性哈希的路由算法尚有不足之處。在查詢(xún)過(guò)程中，查詢(xún)消息要經(jīng)過(guò)O(N)步(O(N)表示與N成正比關(guān)系，N代表系統(tǒng)內(nèi)的節(jié)點(diǎn)總數(shù))才能到達(dá)被查詢(xún)的節(jié)點(diǎn)。不難想象，當(dāng)系統(tǒng)規(guī)模非常大時(shí)，節(jié)點(diǎn)數(shù)量可能超過(guò)百萬(wàn)，這樣的查詢(xún)效率顯然難以滿(mǎn)足使用的需要。換個(gè)角度來(lái)看，即使用戶(hù)能夠忍受漫長(zhǎng)的時(shí)延，查詢(xún)過(guò)程中產(chǎn)生的大量消息也會(huì)給網(wǎng)絡(luò)帶來(lái)不必要的負(fù)荷。

源代碼：

package heritrix;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
	//哈希算法
	private final HashFunction hashFunction;
	//虛擬節(jié)點(diǎn)數(shù)目
	private final int numberOfReplicas;
	private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
	public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes){
		this.hashFunction = hashFunction;
		this.numberOfReplicas = numberOfReplicas;
		for (T node : nodes){
			add(node);
		}
	}
	public void add(T node){
		for (int i = 0; i < numberOfReplicas; i++){
			circle.put(hashFunction.hash(node.toString() + i), node);
		}
	}
	public void remove(T node){
		for (int i = 0; i < numberOfReplicas; i++){
			circle.remove(hashFunction.hash(node.toString() + i));
		}
	}
	//關(guān)鍵算法
	public T get(Object key){
		if(circle.isEmpty()){
			return null;
		}
		//計(jì)算hash值
		int hash = hashFunction.hash(key);
		//如果不包括這個(gè)hash值
		if(!circle.containsKey(hash)){
			SortedMap<Integer, T> tailMap = circle.tailMap(hash);
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}
}

以上是“Java語(yǔ)言Consistent Hash算法怎么用”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)站名稱(chēng)：Java語(yǔ)言ConsistentHash算法怎么用-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://bm7419.com/article46/hcoeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、做網(wǎng)站、網(wǎng)站排名、網(wǎng)站設(shè)計(jì)、面包屑導(dǎo)航、動(dòng)態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)