本文研究的主要是ConsistentHashing算法代碼。
一致性哈希(Consistent Hash)
協(xié)議簡介
一致性哈希算法在1997年由麻省理工學(xué)院提出(參見0)，設(shè)計目標(biāo)是為了解決因特網(wǎng)中的熱點(Hot pot)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡單哈希算法帶來的問題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。
哈希算法
一致性哈希提出了在動態(tài)變化的Cache環(huán)境中，哈希算法應(yīng)該滿足的4個適應(yīng)條件：
平衡性(Balance)
平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩存中去，這樣可以使得所有的緩存空間都得到利用。很多哈希算法都能夠滿足這一條件。
單調(diào)性(Monotonicity)
單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩存中，又有新的緩存加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩存中去，而不會被映射到舊的緩存集合中的其他緩沖區(qū)。
簡單的哈希算法往往不能滿足單調(diào)性的要求，如最簡單的線性哈希：
x → ax + b mod (P)
在上式中，P表示全部緩存的大小。不難看出，當(dāng)緩存大小發(fā)生變化時(從P1到P2)，原來所有的哈希結(jié)果均會發(fā)生變化，從而不滿足單調(diào)性的要求。
哈希結(jié)果的變化意味著當(dāng)緩存空間發(fā)生變化時，所有的映射關(guān)系需要在系統(tǒng)內(nèi)全部更新。而在P2P系統(tǒng)內(nèi)，緩存的變化等價于Peer加入或退出系統(tǒng)，這一情況在P2P系統(tǒng)中會頻繁發(fā)生，因此會帶來極大計算和傳輸負(fù)荷。單調(diào)性就是要求哈希算法能夠避免這一情況的發(fā)生。
分散性(Spread)
在分布式環(huán)境中，終端有可能看不到所有的緩存，而是只能看到其中的一部分。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩存上時，由于不同終端所見的緩存范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩存區(qū)中。這種情況顯然是應(yīng)該避免的，因為它導(dǎo)致相同內(nèi)容被存儲到不同緩沖中去，降低了系統(tǒng)存儲的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。
負(fù)載(Load)
負(fù)載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對于一個特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。
從表面上看，一致性哈希針對的是分布式緩沖的問題，但是如果將緩沖看作P2P系統(tǒng)中的Peer，將映射的內(nèi)容看作各種共享的資源(數(shù)據(jù)，文件，媒體流等)，就會發(fā)現(xiàn)兩者實際上是在描述同一問題。
路由算法
在一致性哈希算法中，每個節(jié)點(對應(yīng)P2P系統(tǒng)中的Peer)都有隨機(jī)分配的ID。在將內(nèi)容映射到節(jié)點時，使用內(nèi)容的關(guān)鍵字和節(jié)點的ID進(jìn)行一致性哈希運算并獲得鍵值。一致性哈希要求鍵值和節(jié)點ID處于同一值域。最簡單的鍵值和ID可以是一維的，比如從0000到9999的整數(shù)集合。
根據(jù)鍵值存儲內(nèi)容時，內(nèi)容將被存儲到具有與其鍵值最接近的ID的節(jié)點上。例如鍵值為1001的內(nèi)容，系統(tǒng)中有ID為1000，1010，1100的節(jié)點，該內(nèi)容將被映射到1000節(jié)點。
為了構(gòu)建查詢所需的路由，一致性哈希要求每個節(jié)點存儲其上行節(jié)點(ID值大于自身的節(jié)點中最小的)和下行節(jié)點(ID值小于自身的節(jié)點中最大的)的位置信息(IP地址)。當(dāng)節(jié)點需要查找內(nèi)容時，就可以根據(jù)內(nèi)容的鍵值決定向上行或下行節(jié)點發(fā)起查詢請求。收到查詢請求的節(jié)點如果發(fā)現(xiàn)自己擁有被請求的目標(biāo)，可以直接向發(fā)起查詢請求的節(jié)點返回確認(rèn);如果發(fā)現(xiàn)不屬于自身的范圍，可以轉(zhuǎn)發(fā)請求到自己的上行/下行節(jié)點。
為了維護(hù)上述路由信息，在節(jié)點加入/退出系統(tǒng)時，相鄰的節(jié)點必須及時更新路由信息。這就要求節(jié)點不僅存儲直接相連的下行節(jié)點位置信息，還要知道一定深度(n跳)的間接下行節(jié)點信息，并且動態(tài)地維護(hù)節(jié)點列表。當(dāng)節(jié)點退出系統(tǒng)時，它的上行節(jié)點將嘗試直接連接到最近的下行節(jié)點，連接成功后，從新的下行節(jié)點獲得下行節(jié)點列表并更新自身的節(jié)點列表。同樣的，當(dāng)新的節(jié)點加入到系統(tǒng)中時，首先根據(jù)自身的ID找到下行節(jié)點并獲得下行節(jié)點列表，然后要求上行節(jié)點修改其下行節(jié)點列表，這樣就恢復(fù)了路由關(guān)系。
討論
一致性哈希基本解決了在P2P環(huán)境中最為關(guān)鍵的問題——如何在動態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯吐酚伞Ｃ總€節(jié)點僅需維護(hù)少量相鄰節(jié)點的信息，并且在節(jié)點加入/退出系統(tǒng)時，僅有相關(guān)的少量節(jié)點參與到拓?fù)涞木S護(hù)中。所有這一切使得一致性哈希成為第一個實用的DHT算法。
但是一致性哈希的路由算法尚有不足之處。在查詢過程中，查詢消息要經(jīng)過O(N)步(O(N)表示與N成正比關(guān)系，N代表系統(tǒng)內(nèi)的節(jié)點總數(shù))才能到達(dá)被查詢的節(jié)點。不難想象，當(dāng)系統(tǒng)規(guī)模非常大時，節(jié)點數(shù)量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。換個角度來看，即使用戶能夠忍受漫長的時延，查詢過程中產(chǎn)生的大量消息也會給網(wǎng)絡(luò)帶來不必要的負(fù)荷。
源代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
package heritrix;import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;public class ConsistentHash<T> { //哈希算法 private final HashFunction hashFunction; //虛擬節(jié)點數(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; } //計算hash值 int hash = hashFunction.hash(key); //如果不包括這個hash值 if(!circle.containsKey(hash)){ SortedMap<Integer, T> tailMap = circle.tailMap(hash); hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } return circle.get(hash); }} |
總結(jié)
以上就是本文關(guān)于Java語言Consistent Hash算法學(xué)習(xí)筆記（代碼示例）的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/u012965373/article/details/41038191
