1、分布式哈希表及分布式哈希表及chord一致性哈希(Consistent Hash) 一致性哈希算法在1997年由麻省理工學院提出。指出了在動態變化的Cache環境中，哈希算法應該滿足的4個適應條件： 1、平衡性(Balance) 平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。 2、單調性(Monotonicity) 單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。 一致性

2、哈希(Consistent Hash) 2、單調性(Monotonicity) 續簡單的哈希算法往往不能滿足單調性的要求，如最簡單的線性哈希： x (ax + b) mod (P) 在上式中，P表示全部緩沖的大小。不難看出，當緩沖大小發生變化時(從P1到P2)，原來所有的哈希結果均會發生變化，從而不滿足單調性的要求。 哈希結果的變化意味著當緩沖空間發生變化時，所有的映射關系需要在系統內全部更新。而在P2P系統內，緩沖的變化等價于Peer加入或退出系統，這一情況在P2P系統中會頻繁發生，因此會帶來極大計算和傳輸負荷。單調性就是要求哈希算法能夠避免這一情況的發生。 一致性哈希(Consistent

3、 Hash) 3、分散性(Spread) 在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希 過程將內容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區 中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法 應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。 4、負載(Load) 負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那么

4、對于一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。 一致性哈希(Consistent Hash) 從表面上看，一致性哈希針對的是分布式緩沖的問題，但是如果將緩沖看作P2P系統中的Peer，將映射的內容看作各種共享的資源(數據，文件，媒體流等)，就會發現兩者實際上是在描述同一問題。 例：假定有一個分布式WEB緩存系統，那么其數據緩存的算法可以有兩種。1 1、hashhash模余算法：模余算法： 根據hash(key)% N的結果決定存儲到哪個節點（key:數據的關鍵字鍵值，N:服務器個數），此計算方法簡單

5、，數據的分散性也相當優秀。 其缺點是當添加或移除服務器時，緩存重組的代價相當巨大。添加/刪除服務器后（或者是某臺服務器出現故障之后），余數就會產生巨變，這樣就無法保證獲取時計算的服務器節點與保存時相同，從而影響緩存的命中率造成原有的緩存數據將大規模失效。一致性哈希(Consistent Hash) 2 2、一致性哈希（、一致性哈希（Consistent HashingConsistent Hashing）我們采用了一種新的方式來解決問題，處理服務器的選擇不再僅僅依賴key的hash本身而是將服務實例（節點）的配置也進行hash運算。 1）首先求出每個服務節點的hash，并將其配置到一個0232

6、的圓環（continuum）區間上。2）其次使用同樣的方法求出所需要存儲的key的hash，也將其配置到這個圓環（continuum）上。3）然后從數據映射到的位置開始順時針查找，將數據保存到找到的第一個服務節點上。如果超過232仍然找不到服務節點，就會保存到第一個服務節點上。 一致性哈希(Consistent Hash) 一致性哈希(Consistent Hash) 一致性哈希(Consistent Hash) 為了維護上述路由信息，在節點加入/退出系統時，相鄰的節點必須及時更新路由信息。這就要求節點不僅存儲直接相連的下行節點位置信息，還要知道一定深度 (n跳)的間接下行節點信息，并且動態地

7、維護節點列表。當節點退出系統時，它的上行節點將嘗試直接連接到最近的下行節點，連接成功后，從新的下行節點獲得下行節點列表并更新自身的節點列表。同樣的，當新的節點加入到系統中時，首先根據自身的ID找到下行節點并獲得下行節點列表，然后要求上行節點修改其下行節點列表，這樣就恢復了路由關系。 為了構建查詢所需的路由，一致性哈希要求每個節點存儲其上行節點一致性哈希要求每個節點存儲其上行節點(ID(ID值大于自身的節點中最小的值大于自身的節點中最小的) )和下行節點和下行節點(ID(ID值小于自身的節點中最大值小于自身的節點中最大的的) )的位置信息的位置信息 (IP(IP地址地址) )。當節點需要查找內容

8、時，就可以根據內容的鍵值決定向上行或下行節點發起查詢請求。收到查詢請求的節點如果發現自己擁有被請求的目標，可以直接向發起查詢請求的節點返回確認；如果發現不屬于自身的范圍，可以轉發請求到自己的上行/下行節點。 一致性哈希(Consistent Hash) 路由算法:分布式哈希表(Distributed Hash Table,DHT)分布式哈希表技術(Distributed Hash Table)是一種分布式存儲方法。在不需要服務器的情況下，每個客戶端負責一個小范圍的路由，并負責存儲一小部分數據，從而實現整個DHT 網絡的尋址和存儲。一致性哈希通常被認為是DHT的一種實現。 DHT 的主要思想：

9、首先，每條文件索引被表示成一個(K, V)對，K 稱為關鍵字，可以是文件名（或文件的其他描述信息）的哈希值，V 是實際存儲文件的節點的IP 地址（或節點的其他描述信息）。所有的文件索引條目(即所有的（K, V）對)組成一張大的文件索引哈希表，只要輸入目標文件的K 值，就可以從這張表中查出所有存儲該文件的節點地址。然后，再將上面的大文件哈希表分割成很多局部小塊，按照特定的規則把這些小塊的局部哈希表分布到系統中的所有參與節點上，使得每個節點負責維護其中的一塊。這樣，節點查詢文件時，只要把查詢報文路由到相應的節點即可（該節點維護的哈希表分塊中含有要查找的(K,V)對）。這里面有個很重要的問題，就是節

10、點要按照一定的規則來分割整體的哈希表，進而也就決定了節點要維護特定的鄰居節點，以便路由能順利進行。 這個規則因具體系統的不同而不同，CAN，Chord，Pastry和Tapestry 都有自己的規則，也就呈現出不同的特性有查找可確定性、簡單性和分布性等優點，正成為國際上結構化P2P 網絡研究和應用的熱點。分布式哈希表(Distributed Hash Table,DHT)1.將內容索引抽象為對:K是內容關鍵字的Hash摘要K = Hash(key)V是存放內容的實際位置，例如節點IP地址等2. 所有的對組成一張大的Hash表，因此該表存儲了所有內容的信息3.每個節點都隨機生成一個標識(ID)，

11、把Hash表分割成許多小塊，按特定規則(即K和節點ID之間的映射關系)分布到網絡中去，節點按這個規則在應用層上形成一個結構化的重疊網絡4.給定查詢內容的K值，可以根據K和節點ID之間的映射關系在重疊網絡上找到相應的V值，從而獲得存儲文件的節點IP地址DHT 的主要思想：分布式哈希表(Distributed Hash Table,DHT)DHT 的主要思想：內容內容內容關鍵字內容關鍵字key內容存儲位置等信息內容存儲位置等信息value內容索引內容索引K=Hash(key)提取提取k vHash表表電影電影夜宴夜宴電影、夜宴電影、夜宴http:/ 夜宴夜宴)V = http:/ va. Hash

12、表表b. 分布式分布式Hash表表規則規則? ?K VN1N48N16N32N8K VK VK VK VChord、CAN、Tapestry、Pastry在許多情況下在許多情況下,節點節點ID為節點為節點IP地址的地址的Hash摘要摘要DHT 的主要思想：插入插入(K1,V1)K VK VK VK VK VK VK VK VK VK VK V(K1,V1)查詢查詢(K1)ABK1=Hash(xyz.mp3)V1=xyz.mp3C索引發布和內容定位DHT 的主要思想：定位(Locating)l節點ID和其存放的對中的K存在著映射關系，因此可以由K獲得存放該對的

13、節點ID路由(Routing)l在重疊網上根據節點ID進行路由，將查詢消息最終發送到目的節點。每個節點需要有到其鄰近節點的路由信息，包括節點ID、IP等網絡拓撲l拓撲結構由節點ID和其存放的對中的K之間的映射關系決定l拓撲動態變化，需要處理節點加入/退出/失效的情況在重疊網上節點始終由節點在重疊網上節點始終由節點ID標識，并且根據標識，并且根據ID進行路由進行路由DHT 的主要思想：1. 哈希算法哈希算法Chord使用一致性哈希作為哈希算法。在一致性哈希協議中并沒有定義具體的算法，在Chord協議中將其規定為SHA-1。2. 路由算法路由算法Chord在一致性哈希的基礎上提供了優化的路由算法：

14、 經過Chord的優化后，查詢需要的跳數由O(N)減少到O(log(N)。這樣即使在大規模的P2P網絡中，查詢的跳數也較少。 Chord還考慮到多個節點同時加入系統的情況并對節點加入/退出算法作了優化。 Chord在2001年由麻省理工學院提出，其核心思想就是要解決在P2P應用中遇到的基本問題：如何在P2P網絡中找到存有特定數據的節點。 Chordl采用環形拓撲(Chord環)l應用程序接口nInsert(K, V)n將對存放到節點ID為Successor(K)上nLookup(K)n根據K查詢相應的VnUpdate(K, new_V)n根據K更新相應的VnJoin(NID)n節點加入nLea

15、ve()n節點主動退出3.3.基本原理基本原理: :ChordChord：Hash表分布規則lHash節點IP地址m位節點ID(表示為NID)lHash內容關鍵字m位K(表示為KID)l節點按ID從小到大順序排列在一個邏輯環上l存儲在后繼節點上Successor (K)：從K開始順時針方向距離K最近的節點 ID=hash (IP)=14N56K=hash (key)=54N1N8N14N21N32N42N48N51m=6N38Chord：簡單查詢過程l每個節點僅維護其后繼節點ID、IP地址等信息l查詢消息通過后繼節點指針在圓環上傳遞l直到查詢消息中包含的K落在某節點ID和它的后繼節點ID之間l

16、速度太慢 O(N)，N為網絡中節點數N56K54Lookup(K54)N56N1N8N14N21N32N38N42N48N51m=6Chord：查詢表(Finger Table) N56指針表指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42節點節點S的第的第i個指針個指針successorn+2(i-1), 1im Chord：基于查找表的擴展查找過程n指針表中有指針表中有O (log N)個節點個節點n查詢經過大約查詢經過大約O (log N)跳跳N56K54指針表指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21

17、N32N42Lookup(K54)指針表指針表N42+1N42+2N42+4N42+8N42+16N42+32N48N48N48N51N1N14nChurn由節點的加入、退出或者失效所引起。n每個節點都周期性地運行探測協議來檢測新加入節點或退出/失效節點，從而更新自己的指針表和指向后繼節點的指針。4.4.網絡波動網絡波動(Churn)(Churn)Chordn新節點N事先知道某個或者某些結點，并且通過這些節點初始化自己的指針表。也就是說，新節點N將要求已知的系統中某節點為它查找指針表中的各個表項。n在其它節點運行探測協議后，新節點N將被反映到相關節點的指針表和后繼節點指針中。 n新結點N的第一個后繼結點將其維護的小于N節點的ID的所有K交給該節點維護。節點加入節點加入Chordn當Chord中某個結點M退出/失效時，所有在指針表中包含該結點的結點將相應指針指向大于M結點ID的第一個有效結點即節點M的后繼節點。n為了保證節點M