基于改進ＤＨＴ算法的分布式資源發現模型的研究

摘要：為了解決大型分布式系統由集中管理導致的擴展性和魯棒性差的問題，利用改進的結構化對等網組織分布式計算資源，構造一個SRDM(scalable resource discovery model，可擴展資源發現模型)。SRDM將邏輯空間中的節點分為主機節點和資源節點。主機節點對應分布式環境中的計算節點，用于存儲peer關聯信息，通過相容性hash映射到邏輯空間上；資源節點對應分布式環境中資源屬性信息，其與邏輯空間的映射通過分段hash再合并的方法得到。通過對屬性值采用位置保留hash方法，使改進后的DHT算法支持有效的資源節點范圍查詢和多屬性范圍查詢。最后通過實驗證明，基于改進DHT算法的資源發現方法比集中式的方法有更好的擴展性，更適用于大規模分布式系統下的資源發現。

關鍵詞：對等網； 分布式哈希表； 資源發現； 相容性哈希； 位置保留哈希

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2007)12-0313-04

0引言

隨著網絡技術的不斷發展和桌面PC機功能的日益強大，接入分布式系統中計算資源的范圍和規模在不斷擴大，使如何有效地管理和發現可用資源成為一個亟待解決的問題。傳統的集中目錄服務方式很容易造成整個系統的性能瓶頸并引起單點故障^[1]，無法滿足分布式系統擴展性和魯棒性的要求。分層管理的策略，即每一層中的目錄服務器對其下層節點仍然是集中式的，仍然無法根本解決集中式的弊端。

一個高可擴展性信息系統應該是非集中式的^[2]，是一個多索引服務器協同組成的分布式信息系統。對等網組織結構符合這一要求。利用對等網的自組織特性，讓分布式系統中的節點均參與到資源索引的存儲和查詢中，可以避免集中式目錄服務引起的擴展性和魯棒性問題。

基于非結構化對等網的資源發現系統^[3，4]，不需要復雜的查詢和信息更新機制，實現較為簡單。但是洪泛或隨機步的路由機制在大規模節點下是不可控的，對資源的范圍查詢會浪費大量的帶寬。這點在請求所有符合條件的資源或查詢稀缺資源時尤為明顯。非結構化覆蓋網的另一個缺點是節點間僅通過連通性來判斷鄰接關系，缺乏有效的組織和監控。

結構化對等網可以有效地解決非結構化的問題，但是其自身也有明顯的欠缺。對于DHT算法來說，主要問題是解決范圍查詢的問題。MAAN^[5]算法將數值類型的資源屬性值直接映射到邏輯節點ID空間上，保證ID與數值具有一致的偏序關系，然后按照Chord算法分別在主機節點上存儲索引，實現了DHT的范圍查詢。文獻[6]是構建于Pastry的資源發現方法，提出按照資源屬性的重要級別，對屬性名和屬性值分段映射，然后合并成邏輯節點ID的方法。屬性值首先被劃分到某一個確定的級別，然后對該級別值進行映射。該方法只能在粗粒度上支持范圍查詢。文獻[7]將資源類型與資源對應索引服務器分別映射。該方法可以縮小資源發現時路由選擇范圍，但是要實現范圍查詢仍然需要遍歷相關主機節點，在節點較多時其對帶寬的浪費是很大的。文獻[8]對三種索引緩存機制作了分析，在本文的資源發現中具有一定借鑒意義。但是其僅提供單點返回。SWORD^[9]方法對DHT算法用于資源發現進行了系統的研究，但是其實驗效果很難體現出支持擴展性的特點。P－Grid^[7]是基于Tries方法的結構化算法，可以有效地進行數值范圍查詢。但是該方法不支持多屬性查找，并且無法實現索引節點的負載均衡。

不同于以上結構化資源發現的研究，本文的SRDM通過資源節點來表示物理空間上的資源屬性信息，將所有屬性信息動態映射到同一個邏輯空間上，構建一個支持有效多屬性資源發現的結構化對等網絡模型。實驗證明該模型在節點組織上具有良好的擴展性，在資源信息查詢時可以在低帶寬消耗下快速準確地找到合適的資源。

1改進DHT算法的分布式資源發現

1．1DHT算法改進

DHT算法只支持精確查找，無法滿足范圍查找的要求。原因在于相容性hash^[10]將所有peer按SHA1算法計算ID。該方法可以使peer均勻地分布在邏輯空間上，卻丟掉了源數據間的關聯關系。

為了構建支持分布式資源范圍查詢的結構化對等網，本文將邏輯節點分為資源節點(resource peer)和主機節點(node peer)兩類；將peerID區分為resourceID和nodeID，分別采取不同的方法將這兩類資源映射到相同的一維邏輯空間上。

需要進行范圍查詢的資源屬性信息對應資源節點，使用保持鄰近性關系的函數映射得到resourceID。主機節點即索引服務器采用相容性hash映射為nodeID，使節點能夠均勻地分布在邏輯空間上。

peerID

nodeID=NodeHash(nodeAddress)

resourceID=ResourceHash(〈attributeName， attributeVale〉)

NodeHash: Consistent－Hash－Function(1)

ResourceHash: ResourceInfo－Hash－Function

其中：nodeID標記索引服務器的位置。每個索引服務器根據DHT算法維護一組以resourceID為標記的資源屬性信息。該信息用一個三元組{resourceID，resourceInfo，nodeIP}表示。ResourceID標記資源屬性信息在邏輯空間上的位置。它是該資源屬性的詳細信息。NodeIP用于資源定位。本文使用的是資源節點對應主機的IP地址。

一個主機節點對應多種屬性，如硬件性能指標、負載情況等。每個屬性信息對應一個資源節點。主機節點與資源節點在隸屬關系上是一對多的，在存儲關系上主機節點與資源節點是多對多的關系。

根據式(1)的映射思路，本文基于算法Chord^[11]實現了一個資源發現模型，即SRDM。圖1為SRDM的體系結構。

1）資源信息服務SRDM針對上層應用提供的接口。其對上層服務提供的支持有資源查詢、發布、更新，節點的發布以及SRDM shell。Shell功能支持上層用戶通過telnet命令監控管理SRDM節點。

2)邏輯空間映射接口將物理空間的計算資源及其屬性映射為邏輯空間上的主機節點和資源節點。將分布式系統中的節點動作映射為SRDM邏輯空間上的動作。

3)SRDM節點功能目錄服務用于管理本地和全局索引信息；路由服務用于指導消息轉發、拓撲結構的維護和優化，路由選擇算法和拓撲維護算法直接決定著SRDM的功能；消息服務負責節點間消息的接收、發送和處理。SRDM通過分布式資源基礎設施與外部節點進行通信。基礎設施主要功能是保證節點間的連通性，使底層消息通信對上層消息服務是透明的。本模型采用TCP協議進行節點間的通信。

1．2分布式資源映射及發布

資源的屬性可以分為數值類型和字符串類型。數值類型的屬性，主要是指整型(如memory、磁盤容量、CPU性能等)或浮點型(CPU主頻、memory、帶寬或CPU空閑率等)的屬性信息。這些屬性值是比較選擇資源的重要依據，是資源查詢中最關鍵的部分，需要提供模糊查詢。字符串類型的屬性主要是指軟資源的屬性信息，如操作系統的規格、輔助軟件是否安裝等。這類信息的查詢往往需要進行精確匹配。資源發現中的范圍查詢主要是指數值型屬性的查詢。為了實現數值型屬性的范圍查找，本文引入位置保留hash^[5]的方法。通過該方法使資源節點在邏輯空間上仍保持物理空間中屬性值間的鄰近性關系。對于字符型屬性的映射則使用相容性hash。

以下是關于位置保留hash的定義和性質分析：

2實驗

2．1實驗說明

SRDM基于overlay weaver的DHT框架，通過修改ID生成模塊和消息路由與發現模塊實現了多屬性范圍查詢的模擬，并且添加了log記錄和分析模塊以實現實驗結果的記錄和分析。表1是模型的節點動作及其發生頻率。SRDM每個域上可以運行的最大節點數為10 000個，分別在10個集群節點上進行模擬，每個節點共有五類屬性信息。詳細信息如表2所示。為了與集中式資源發現方法比較，本文構造了一個集中式的資源發現模型，除了路由規則外，該模型與SRDM具有相同環境和設置。

2．2實驗結果

圖4給出的是SRDM模型與相同環境下集中式發現模型在50個查詢下的響應時間比較。其中SRDM模型的查詢分為等概率隨機范圍查詢和全局性查詢。從圖中可以看到，在600個節點時，集中式查詢和SRDM方法的延遲有個交點。600個節點前，集中式發現方法的性能優于SRDM方法。但是隨著節點的增加，集中式的增長斜率呈現增大的趨勢，而SRDM方法的增長相對緩慢。因此當節點數＞600時，集中式的性能越來越差，而SRDM的性能卻不會有太大的下降。由此可以認為，在大規模分布式環境下，SRDM方法具有比集中式方法更好的性能。

從圖4關于隨機范圍查詢和全局范圍查詢的比較可以看到，關于全局范圍的屬性值遍歷的響應時間變化率要高于隨機范圍查詢。主要原因在于位置保留hash函數將相鄰的資源節點映射到連續的弧段上。隨著節點的增加，需要遍歷的節點數會增加，查詢消息的傳遞延遲將大大影響查詢響應時間。但是對于規模較大且連通性較好的網絡環境，SRDM還是具有較高性能的。

圖5是對SRDM查詢平均路由跳數的比較。從實驗結果看，隨著節點增加，雖然除了最小路由跳數外均有增加，但是其增幅低于節點的增加數量。在節點數為4 000時，平均查詢路由跳數大約為32，最大路由跳數也小于60，而全局范圍的查詢跳數大約為48。從路由跳數可以看到，SRDM具有較好的擴展性。

從圖5中還可以看到，在大約800個節點時，平均路由跳數曲線和O(log n)曲線有交叉。本文認為少于800個節點時，平均路由跳數小于O(log n)的值是合理的。本實驗采取了盡量讓節點保持全網拓撲的策略，因此消息路由時尋找后繼節點的時間復雜度遠小于O(log n)。本實驗的路由跳數主要開銷在遍歷對應屬性弧段的連續節點上。因此隨著節點數的增加，平均路由跳數的增長率要高于O(log n)的變化率。這個趨勢在最大跳數和遍歷全局范圍的跳數變化率上更為明顯。同時圖6中路由跳數的變化率小于節點增加的變化率，說明在索引分布。

從實驗數據上可以看到，基于改進DHT算法的資源發現方法具有比集中式發現方法更短的響應時間，并且隨著節點的增加，響應時間的增長率要遠遠低于集中式的發現方法。查詢路由跳數的增加原因來自于資源節點索引信息被分布到了更多的主機節點上，從而提高了資源發現方法的擴展性。

3結束語

用對等網的思路組織分布式資源的注冊和發現，可以有效解決大規模系統集中管理引起的性能瓶頸、單點故障等問題。本文通過修改DHT算法，將資源屬性信息作為資源節點映射到對等網邏輯空間上，實現一個支持資源節點范圍查詢和多屬性查詢的模型——可擴展分布式資源發現模型。通過實驗證明該方法可以有效地支持大規模分布式系統下的資源發現。考慮到分布式系統中對外提供服務的主機節點具有較高的穩定性，SRDM并未考慮DHT算法抖動性的問題。在接下來的

研究中筆者的重點將是解決由于屬性值本身的不均勻性導致

主機節點負載不均衡問題以及如何提高分布式自治域間的資源發現。

參考文獻：

[1]ZHANG Xue－hai， FRESCHL J L， SCHOPF J M. A performance study of monitoring and information services for distributed systems[C]//Proc of HPDC. 2003.

[2]BERMAN F.網格計算:支持全球化資源共享與協作的關鍵技術[M].都志輝，譯.武漢:華中科技大學出版社， 2005.

[3]UPPULURI P， JABISETTI N， JOSHI U，et al. P2P grid:service oriented framework for distributed resource management[C]//Proc of the 2005 IEEE International Conference on Services Computing.[S.l.]: IEEE， 2005:347-350.

[4]RENESSE R van， BIRMAN K P， VOGELS W. Astrolabe: a robust and scalable technology for distributed system monitoring management， and data mining[J]. ACM Transactions on Computer Systems， 2003，21(2):164-206.

[5]CAI Min. MAAN: a multi－attribute addressable network for grid information services[J]. Journal of Grid Computing， 2004，2(1):3－14.

[6]CHEEMA A S， MUHAMMAD M， GUPTA I. Peer－to－peer discovery of computational resources for grid applications[C]//Proc of Grid Computing Workshop 2005. Washington D C:[s.n.]， 2005:179－185.

[7]DATTA A， HAUSWIRTH M， JOHN R， et al. Range queries in trie－structured overlays[C]//Proc of the 5th IEEE International Confe－rence on Peer－to－Peer Computing(P2P’05). Washington D C: IEEE Computer Society， 2005:57-66.

[8]CHEN Li－ping，CANDAN K S.On overlay schemes to support poin－tin－range queries for scalable grid resource discovery[C]//Proc of the 5th IEEE International Conference on Peer－to－Peer Computing(P2P’05). Washington D C: IEEE Computer Society， 2005:57-66.

[9]OPPENHEIMER D， ALBRECHT J， PATTERSON D， et al. Scalable wide－area resource discovery， UCB//CSD－04－1334[R]. Berkeley: UC Berkeley， 2004.

[10]LEWIN D. Consistent hashing and random trees: algorithms for caching in distributed networks[D].[S.l.]: Department of EECS， MIT， 1998.

[11]STOICA I， MORRIS R， KARGER D， et al. Chord: a scalable peer－to－peer lookup service for Internet applications[C]//Proc of the 2001 Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications. New York: ACM Press， 2001:149.

[12]MENG Yong， WANG Xian－bing. A DHT－based grid resource indexing and discovery scheme[C]//Singapore－MIT Alliance Symposium. 2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”