通信專業(yè)互聯(lián)網(wǎng)技術考試相容哈希

　　　在線輔導　面授招生　考試大綱　指定教材　試題匯總

　　1.相容哈希（ConsistentHash）
相容哈希算法在1997年由麻省理工學院提出，設計目標是為了解決因特網(wǎng)中的熱點問題,初衷和CARP十分類似。相容哈希修正了CARP使用的簡單哈希算法帶來的問題，使得DHT可以在P2P環(huán)境中真正得到應用。
　?、俟Ｋ惴?br />相容哈希提出了在動態(tài)變化的Cache環(huán)境中，哈希算法應該滿足的4個適應條件：
1）平衡性（Balance）
平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。
2）單調性（Monotonicity）
單調性是指如果已經(jīng)有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加人到系統(tǒng)中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。
簡單的哈希算法往往不能滿足單調性的要求，如最簡單的線性哈希：
在上式中，P表示全部緩沖的大小。不難看出，當緩沖大小發(fā)生變化時（從P1到P2),原來所有的哈希結果均會發(fā)生變化，從而不滿足單調性的要求。
哈希結果的變化意味著當緩沖空間發(fā)生變化時，所有的映射關系需要在系統(tǒng)內全部更新。而在P2P系統(tǒng)內，緩沖的變化等價于Peer加入或退出系統(tǒng)，這一情況在P2P系統(tǒng)中會頻繁發(fā)生，因此會帶來很大的計算和傳輸負荷。單調性就是要求哈希算法能夠避免這一情況的發(fā)生。
3）分散性(Spread）
在分布式環(huán)境中.終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致.最終的結果是相同的內容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統(tǒng)存儲的效率。分散性的定義就是上述情況發(fā)生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發(fā)生，也就是盡攝降低分散性。
4）負載（Load）
負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區(qū)中，那么對于一個特定的緩沖區(qū)而言,也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的，因此，好的哈希算法應能夠盡董降低緩沖的負荷。
從表面上看，相容哈希針對的是分布式緩沖的問題，但是如果將緩沖看做P2P系統(tǒng)中的Peer,將映射的內容看作各種共享的資源（數(shù)據(jù)、文件、媒體流等），就會發(fā)現(xiàn)兩者實際上是在描述同一問題。
②路由算法
在相容哈希算法中，每個節(jié)點（對應P2P系統(tǒng)中的Peer)都有隨機分配的ID。在將內容映射到節(jié)點時,使用內容的關鍵字和節(jié)點的ID進行一致性哈希運算并獲得鍵值。一致性哈希要求鍵值和節(jié)點ID處于同一值域。最簡單的鍵值和ID可以是一維的，比如從0000到9999的整數(shù)集合。
根據(jù)鍵值存儲內容時,內容將被存儲到具有與其鍵值最接近的1D的節(jié)點上。例如，鍵搶為1001的內容，系統(tǒng)中有ID為1000,1010,1100的節(jié)點，該內容將被映射到1000節(jié)點。
為了構建查詢所需的路由，相容哈希要求每個節(jié)點存儲其上行節(jié)點（ID值大于自身的節(jié)點中最小的）和下行節(jié)點（ID值小于自身的節(jié)點中最大的）的位置信息（IP地址>。當節(jié)點需要查找內容時，就可以根據(jù)內容的鍵值決定向上行或下行節(jié)點發(fā)起査詢請求。收到查詢請求的節(jié)點如果發(fā)現(xiàn)自己有被請求的目標,可以直接向發(fā)起査詢請求的節(jié)點返回確認；如果發(fā)現(xiàn)不屬于自身的范圍，可以轉發(fā)請求到自己的上行/下行節(jié)點，為了維護上述路由信息，在節(jié)點加人/退出系統(tǒng)時，相鄰的節(jié)點必須及時更新路由信息。這就要求節(jié)點不僅存儲直接相連的下行節(jié)點位置信息，還要知道一定深度（n跳）的間接下行節(jié)點信息，并且動態(tài)地維護節(jié)點列表。當節(jié)點退出系統(tǒng)時，它的上行節(jié)點將嘗試直接連接到最近的下行節(jié)點，連接成功后，從新的下行節(jié)點獲得下行節(jié)點列表并更新自身的節(jié)點列表。同樣的，當新的節(jié)點加人到系統(tǒng)中時，首先根據(jù)自身的ID找到下行節(jié)點并獲得下行節(jié)點列表,然后要求上行節(jié)點修改其下行節(jié)點列表,這樣就恢復了路由關系。
③優(yōu)缺點分析
相容哈?；窘鉀Q了在P2P環(huán)境中最為關鍵的問題--如何在動態(tài)的網(wǎng)絡拓撲中分布存儲和路由。每個節(jié)點僅需維護少量相鄰節(jié)點的信息，并且在節(jié)點加人/退出系統(tǒng)時，僅有相關的少量節(jié)點參與到拓撲的維護中。所有這一切使得相容哈希成為第一個實用的DHT算法。
但是相容哈希的路由算法尚有不足之處。在查詢過程中，查詢消息要經(jīng)過O(N)步(O(N)表示與N成正比關系，N代表系統(tǒng)內的節(jié)點總數(shù)）才能到達被查詢的節(jié)點。不難想象，當系統(tǒng)規(guī)模非常大時，節(jié)點數(shù)量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。換個角度來看，即使用戶能夠忍受漫長的時延，查詢過程中產(chǎn)生的大量消息也會給網(wǎng)絡帶來不必要的負荷。

返回目錄： 通信工程師互聯(lián)網(wǎng)技術新型網(wǎng)絡體系結構匯總

編輯推薦：

中級通信專業(yè)實務 互聯(lián)網(wǎng)技術教程匯總

中級通信專業(yè)實務傳輸與接入教程匯總

通信專業(yè)實務考試設備與環(huán)境教程匯總

通信專業(yè)實務考試交換技術教程匯總