對等網絡中分布式散列表的研究
2006-12-31 00:00:00袁霖覃征
計算機應用研究 2006年9期
摘要：首先介紹了非結構型對等網絡和結構型對等網絡，歸納了分布式散列表（DHT）的性質與特點；然后對幾種現有的DHT進行了介紹；最后指出DHT現存的主要問題并討論了可能的解決方案。
關鍵詞：分布式散列表；對等網絡；路由性能；定位控制
中圖法分類號：TP393文獻標識碼：A
文章編號：1001－3695(2006)09－0039－02
對等網絡（P2P）是一種Overlay網絡。P2P中每個節點既是服務的提供者，也是服務的消費者，它具有分布式控制、可擴展性、自組織性和自適應性等性質。
當前所研究的P2P可分為無結構型和結構型兩類。Gnutella[1]屬于無結構型P2P，這類P2P不需要維護系統的邏輯拓撲結構視圖，節省了維護結構的開銷；數據的存放在很大程度上不受限制，它采用洪泛式的消息廣播機制進行數據查詢，收到消息的節點將匹配的數據發送給查詢者。正是由于這種洪泛式的消息廣播機制，當系統節點增多時，每個節點的負載隨著查詢總數的增加而迅速增長，從而嚴重影響了系統的可擴展性。而結構型P2P需要維護系統的邏輯拓撲結構視圖，數據被存放到確定的節點，普遍采用分布式散列表（DistributedHashTable，DHT）進行查找、定位及路由。
1分布式散列表（DHT）
現有的DHT的基本設計思想是：在P2P中使用一個足夠大的ID空間，系統中的所有節點和數據（這里的數據對于不同的DHT來說，可能是文件、索引或地址信息等）均具有唯一的ID標志。每個節點和數據的ID是通過散列函數（如SHA1）得到的，即
NodeID=Hash(Node)；DataID=Hash(Data)。
這樣，系統中所有節點就通過NodeID映射到了ID空間，將ID空間分割成若干個子空間，每個節點負責一個子空間；數據保存在負責DataID所在的子空間的節點上。系統中的每個節點需要按照一定的策略維護其他部分節點的信息表（即路由表）以便進行查找、定位和路由。DHT通常為上層應用提供PUT(DataID，Data)和GET(DataID)兩個最基本的接口，前者將數據存到相應的節點上，后者從相應的節點上取出DataID所對應的數據。
在P2P中，DHT應具有如下性質：①一致性（Consistency）。所有節點通過各自維護的路由表構建出的系統邏輯拓撲結構視圖是相容的，也就是說，從系統中任何節點訪問某個特定數據，最終都將定位到相同的節點。②可用性（Availability）。P2P中一個最顯著的特點就是節點動態地加入和離開。DHT能夠自動更新系統狀態變化過程中相關節點的內部路由表，并自動調整相關數據存儲的位置，以保證即使在系統狀態不斷變化的情況下也可以找到存儲特定數據的節點。③鄰近鄰居選擇（ProximityNeighborSelection，PNS），即在路由表中選取適當的鄰居節點以使到達目標節點的延遲最小。將DHT中查找的延遲與底層網絡源節點和目標節點間的RTT之比定義為展寬（Stretch）。展寬越小，PNS越優。④可擴展性（Scalability），即當系統中加入的節點數目增加時，系統正常運行的開銷在可控制的范圍內。⑤負載均衡（LoadBalance），即DHT需要將節點和數據的ID均勻地映射到整個ID空間，以防止某些節點過載。
2幾種常見的DHT
2．1Chord
Chord[1]使用相容散列為每個節點和數據分配m位的ID。節點按照NodeIDmod2m的順序連成一個環型拓撲結構。而數據k存放在第一個滿足NodeID≥DataID的節點上，此節點被稱為該數據的后繼節點，記作successor(k)。在一個節點數為N的系統中，每個節點維護其他O(log(N))個節點的信息，這些信息存儲在一個稱為FingerTable的路由表中。在節點n的FingerTable中，第i項包含節點s的信息，其中s=successor(n+2i-1)，1 2．2Tapestry Tapestry[2]采用Plaxton的變體。每個節點維護鄰近節點表作為路由表，每個路由表按照路由層次組織，其中第i層包含一組ID與該節點ID長度為i的后綴相匹配的最近節點指針。路由時采用的方法類似于CIDRIP地址分配體系結構中的最長前綴匹配。例如一條可能的路由消息的傳遞路徑：***1→**21→*321→4321，其中*為通配符。存儲數據O的節點S發布一條定位消息 2．3CAN CAN[4]使用一個d維笛卡爾坐標空間，系統中每個節點都映射到坐標空間中，每個節點負責一部分子空間。對于待存儲的數據，利用散列函數將其映射到坐標空間中的一點，將數據存儲在負責該點所在子空間的節點上。每個節點維護一個路由表，表中存有與該節點負責子空間相毗鄰的子空間節點的地址信息。當查找數據時，CAN采用貪婪算法，利用這些路由表將查找的消息傳遞給坐標空間中離目標節點最近的鄰居節點。每個節點具有O(d)個鄰居節點，而查找所經過的跳數為O(dN/d)。 2．4Kelips Kelips[3]的設計思想是增加存儲器的使用和固定的后臺通信開銷來減少文件查詢的時間并增加系統的穩定性。Kelips將ID空間分成k個虛擬的親和組，使用散列函數將每個節點映射到各自的親和組。每個節點維護三類狀態信息：①親和組視圖。一組位于相同親和組的節點。②聯系人。對于其他每個親和組所選取的一組（常數）節點。③文件元組。一組記錄文件名和所在節點地址信息的元組，這里文件所在節點與該節點在同一親和組中。Keplips采用心跳機制，周期性地刷新這三類信息。當某一節點要存儲文件時，使用同一個散列函數將文件名映射到相應的親和組；然后從聯系人中找到位于該親合組中且距離最近的節點，向其提出存儲請求，該聯系人從自己的親和組中隨機地選出一個節點作為文件的存儲節點；最后將文件從初始節點直接傳遞給存儲節點。文件的查找機制與之類似。正常情況下，文件的插入或查找只需要一個RPC，消息的復雜度為O(1)，與系統的大小無關。每個節點使用的存儲空間為O(N/2)，其中N為系統中節點的數目。 3需要進一步研究的問題 通過上面的介紹，我們可以看出DHT具有良好的可擴展性，克服了非結構型P2P擴展性差的缺點。但是經過進一步的研究發現，作為P2P中為上層應用提供服務的基礎設施來說，DHT仍然存在一些需要進一步研究解決的問題。 3．1路由性能問題 現有的DHT基本上都是采用散列函數將節點和數據隨機地分布在ID空間中，再按照一定的策略在底層網絡的物理拓撲之上組成特定的邏輯拓撲結構。在路由時，DHT根據各個節點所保存的路由表（而該路由表是按照系統的邏輯拓撲結構動態維護的）選擇最少跳數的路徑來路由消息。這就很可能導致這樣一種情況：一個節點發出請求后，經過橫跨幾個大陸的路由到達目標節點時，卻發現這個節點的物理位置就在自己附近。造成這種情況的根本原因就是DHT在構造自己應用層次的路由表時，沒有考慮底層節點的特性（如節點的處理能力、存儲空間等）和網絡特性（如網絡的帶寬、延遲、物理拓撲結構等）。 因此，當前DHT研究的一個問題就是如何將應用層的路由策略與底層網絡的路由策略相結合，以提高路由性能。解決這一問題的一種方法是，在DHT維護路由表時測量相關的底層網絡拓撲信息和節點特性，并且在DHT的路由表中加以體現。Tapestry和Kelips均是從這方面著手考慮這一問題的，但是通過這種方式勢必帶來額外的開銷，對于可能改善的路由效率與這部分額外開銷之間的關系也有待進一步研究。另外一種解決思路可以從節點ID的分配入手，改變ID隨機分配的方法，引入底層網絡物理布局的因素來為節點分配ID。 3．2定位控制問題 當前所研究的DHT都是通過使用特定的散列函數將數據隨機地定位到ID空間所對應的節點。用戶對于數據的定位沒有任何控制權。這樣做的優點是：①在DHT層次上簡便地實現了負載均衡；②用戶不需要預先知道存儲節點的信息；③在發生故障時，系統具有自恢復的功能，不需要用戶的介入。而該方法也有一定的不足，正如第3．1節所討論的，這種隨機的定位使P2P查找和路由的效率比較低。另外，這種方法的一個隱含前提是假設P2P中所有的節點都是同等的，也就是說所有節點都是可信的，這與實際模型是不相符的。所以DHT定位控制問題是值得研究的，用戶可以對P2P中數據的定位具有一定的控制能力，如用戶可以控制自己的數據定位于本身所在的自治域中。 3．3復雜查詢問題 正如文獻[1]中所提到的，Chord只支持一種操作，即給定一個關鍵字，將該關鍵字映射到一個節點。現有的DHT基本上都是這樣，只能進行單關鍵字的精確查找，這在很大程度上限制了DHT在實際P2P中的應用。如何在DHT中實現多關鍵字的模糊查找是其研究中的一個重要問題。 對于解決多關鍵字查找問題的一種方案，就是以現有的單關鍵字查找為基礎，將多關鍵字的查找分解為多個單關鍵字查找的“疊加”。當然，即使這個直觀的方法也有很多方面需要考慮，例如，對于一個多關鍵字查找所涉及到的節點間如何協調工作來使查詢的開銷最小、查詢到結果的速度最快等相關問題都是需要研究的。 3．4安全問題 正如第3．2節中提到的目前DHT假設所有的節點均是可信的，整個系統是一個統一的信任模型。而在實際應用中，需要考慮惡意節點的加入問題，這些惡意節點可能返回錯誤數據、提供錯誤路由、竄改數據等。如何在DHT中引入身份認證、數據的安全存儲與傳輸等安全機制也是DHT中研究的重要問題。 3．5實現方式問題 考慮到在實際的P2P中，DHT為上層應用提供服務，其具體實現方式同樣也是一個有待研究的問題。傳統上，DHT被作為庫來實現，作為庫來實現的好處是提供了很大的靈活性；而它的一個弊端是不具有通用性，對于每個不同的上層應用都需要開發不同的DHT。 DHT同樣也可以作為服務來實現，這需要為上層應用定義并提供一組嚴格的接口。OpenDHT在這一方面進行了嘗試，它為外界提供了公共的DHT服務。對于客戶端來說，它們不再需要運行DHT節點，而僅僅需要向DHT節點發出PUT和GET操作命令，這些DHT節點就會執行相應的操作。這種DHT的服務模型使客戶端不需要關心DHT的部署和維護，簡化了上層應用的開發和部署。 4總結 DHT是P2P中一類重要的查找、定位和路由的基礎設施，為廣域文件存儲、文件和服務分布索引以及大規模分布計算平臺等大規模分布式的P2P應用提供了重要的服務。本文介紹了非結構型P2P和結構型P2P，歸納了DHT的性質與特點，并對幾種現有的DHT進行了介紹，最后指出DHT現存的主要問題并提出了可能的解決方案。 參考文獻： ［1］GnutellaHomepage[EB/OL].http：//www.gnutella.com. ［2］IonStoica，RobertMorris，DavidLibernNowell，etal.Chord：ASca－lablePeertoPeerLookupProtocolforInternetApplications[J].IEEE/ACMTrans.onNetworking，2003，11(1)：1732. ［3］BenYZhao，JohnKubiatowicz，AnthonyDJoseph.Tapestry：AnInfrastructureforFaulttolerantWideareaLocationandRouting[R].Tech.ReportNo.UCB/CSD011141，2001. ［4］IndranilGupta，KenBirman，PrakashLinga，etal.Kelips：BuildinganEfficientandStableP2PDHTthroughIncreasedMemoryandBackgroundOverhead[C].Berlin：The2ndInternationalWorkshoponPeertoPeerSystems，2003.160169. ［5］RatnasamyS，FrancisP，etal.AScalableContentaddressableNetwork[J].Proc.ofACMSIGCOMM，2001，31(4):161172. 作者簡介： 袁霖(1980)，男，碩士研究生，研究方向為對等網絡、分布式計算； 覃征(1956)，男，教授，博導，博士，研究方向為分布式計算、移動計算、軟件體系結構、計算機系統集成與電子商務。
