1、QFMA: 一種支持負(fù)載均衡的多屬性資源定位方法劉德輝1 周寧2 尹剛1 王懷民1 鄒鵬11 (國防科技大學(xué)計算機(jī)學(xué)院 湖南長沙 410073)2 (中國電子工程系統(tǒng)研究所 北京 100141)摘要: P2P技術(shù)是實現(xiàn)SOA去中心化的有效方法. 在基于元數(shù)據(jù)的P2P系統(tǒng)中, 描述資源屬性的關(guān)鍵字分布和訪問的不均勻性使某些元數(shù)據(jù)存儲節(jié)點極易成為負(fù)載熱點, 嚴(yán)重影響了系統(tǒng)可用性. 在MAAN基礎(chǔ)上給出了一種支持負(fù)載均衡的多屬性資源定位方法QFMA, 將過載節(jié)點狀態(tài)反饋到查詢路徑上, 后續(xù)查詢將根據(jù)反饋信息進(jìn)行查詢目標(biāo)切換. 分析和試驗表明QFMA以O(shè)(logN)的路徑長度實現(xiàn)資源的高效定位, 并能

2、夠通過負(fù)載分流, 有效緩解“熱門”節(jié)點的負(fù)擔(dān), 提高系統(tǒng)的負(fù)載均衡特性.關(guān)鍵詞: SOC; SOA; P2P; QFMA; 負(fù)載均衡; 熱點QFMA: An Approach for Multi-attribute Resource Addressing with Load BalancingLiu De-Hui1 Zhou Ning2 Yin Gang1 Wang Huai-Min1 Zou Peng11 (School of Computer Science, National University of Defense Technology, Hunan Changsha, China,

3、 410073)2 (China Institute of Electronic System Engineering, Beijing China, 100141)Abstract It is an effective way to make SOA uncentralized with P2P. In meta-data based p2p system, hot spot may result due to non-uniform of keywords distribution and load, which will influence the usability of the sy

4、stem seriously. In this paper, we propose QFMA, an algorithm for load balancing in meta-data based P2P systems based on MAAN. The main idea is that, record the status of the high load node along the query path, the other query will change their destination based on the status recorded. Our analysis

5、and simulation result show that QFMA can reduce the load of hot spot and achieve load balance, the query path length is also O(logN).Keywords: SOC; SOA; P2P; QFMA; Load Balance; Hot Spot1引言本文由國家973 重點基礎(chǔ)研究發(fā)展計劃(No.2005CB321804)和國家自然科學(xué)基金(No.90412011)資助. 劉德輝, 男, 1979年生, 博士研究生, 研究領(lǐng)域為分布計算, P2P數(shù)據(jù)管理. 周寧, 女,

6、 1974年生, 碩士, 研究方向為信息安全與軟件工程; 尹剛, 男, 1975年生, 博士, 研究領(lǐng)域為P2P信任管理與信息安全; 王懷民, 男, 1962年生,教授, 博士生導(dǎo)師, 主要研究方向為分布計算與信息安全; 鄒鵬,1957年生, 男, 教授, 博士生導(dǎo)師, 主要研究方向為分布計算. 郵箱: dhliu1997. 地址: 湖南國防科大計算機(jī)學(xué)院博士生隊(410073)SOA(Service Oriented Architecture)以資源服務(wù)化為基礎(chǔ), 通過服務(wù)的發(fā)布、發(fā)現(xiàn)、調(diào)用等相關(guān)機(jī)制19, 為開放環(huán)境下的資源聚合提供強(qiáng)有力的支持. 隨著應(yīng)用規(guī)模的不斷擴(kuò)大,傳統(tǒng)SOA中的集中

7、式注冊中心(如UDDI)最終將成為系統(tǒng)的瓶頸. 研究219等表明P2P技術(shù)是實現(xiàn)SOA去中心化的有效方法, P2P環(huán)境下服務(wù)描述信息(WSDL, OWL-S)的存儲, 服務(wù)資源的定位分別實現(xiàn)了傳統(tǒng)SOA中的服務(wù)發(fā)布和發(fā)現(xiàn)功能, 不同的是注冊中心的角色由分布在網(wǎng)絡(luò)中的大量動態(tài)的P2P節(jié)點承擔(dān). 如何在P2P這樣一個高度動態(tài)和異構(gòu)的網(wǎng)絡(luò)中, 實現(xiàn)高效的服務(wù)發(fā)布和發(fā)現(xiàn)則是需要研究的重要問題. 在P2P網(wǎng)絡(luò)中服務(wù)的發(fā)布和發(fā)現(xiàn)僅需要服務(wù)描述信息, 因此本文研究適用于任意這樣的系統(tǒng)(基于元數(shù)據(jù)的P2P系統(tǒng)): 資源駐留在本地, 資源描述發(fā)布到網(wǎng)絡(luò)中, 資源使用者根據(jù)描述信息進(jìn)行資源定位, 在資源所在節(jié)點獲

8、取和使用資源. 下文涉及的資源不僅限于服務(wù)資源.P2P網(wǎng)絡(luò)主要分為三類：結(jié)構(gòu)化、非結(jié)構(gòu)化以及混合型. 其中基于DHT的結(jié)構(gòu)化P2P網(wǎng)絡(luò)因為其高效性, 高可擴(kuò)展性在學(xué)術(shù)界和應(yīng)用領(lǐng)域得到了廣泛關(guān)注. Chord, CAN, Pastry等具有代表性的結(jié)構(gòu)化P2P網(wǎng)絡(luò)一般只支持基于單個關(guān)鍵字的精確的資源定位方法, 而資源描述中包含多個屬性, 每個屬性包含多個關(guān)鍵字, 基于單個關(guān)鍵字必然嚴(yán)重影響資源定位的效率. 為了克服該局限性, Cai等人提出了多屬性資源定位網(wǎng)絡(luò)MAAN2以支持多屬性查找. 支持多關(guān)鍵字的DHT技術(shù)更加符合互聯(lián)網(wǎng)資源定位的實際需要. 但是,資源描述中的關(guān)鍵字分布和訪問符合Zipf定

9、律, “流行度”往往具有很大差異, 高流行度的關(guān)鍵字(如2008, cpu等)的存儲節(jié)點容易成為系統(tǒng)性能瓶頸, 也就是說引發(fā)負(fù)載均衡問題. 隨著結(jié)構(gòu)化P2P系統(tǒng)研究和應(yīng)用的深入, 其負(fù)載均衡問題引起了廣泛關(guān)注3,4,5,6,7,9, 普遍認(rèn)為導(dǎo)致負(fù)載均衡問題的原因主要有3類: (1) DHT標(biāo)識(標(biāo)識資源和節(jié)點的散列值)分布不均勻4, 基于隨機(jī)hash函數(shù)會產(chǎn)生O(logN)的不平衡因子; (2) 節(jié)點能力異構(gòu)性9, 以同等方式對待所有節(jié)點忽略了節(jié)點能力上的差異; (3) 負(fù)載分布不均勻3, 由于互聯(lián)網(wǎng)中資源分布和訪問符合Zipf定律11,12,13, 即少數(shù)“流行度”高的資源將接受大部分的訪

10、問, 導(dǎo)致了少數(shù)“熱點”的工作負(fù)荷遠(yuǎn)遠(yuǎn)大于普通節(jié)點.第一類問題主要通過改進(jìn)散列算法進(jìn)行解決1,17; 第二類, 文章3,6,9已作相應(yīng)討論; 針對第三類原因產(chǎn)生的問題, 主要有兩種解決方法: (1) 基于復(fù)制和緩存的負(fù)載均衡方法9,14,15, 這種方法通過對資源本身進(jìn)行復(fù)制和緩存, 有效分流“熱點”資源的負(fù)載. (2)基于虛擬服務(wù)器的負(fù)載均衡方法3,4,5,6,9, 其主要思想是在系統(tǒng)中引入新的邏輯概念 - 虛擬服務(wù)器, 每個虛擬服務(wù)器承擔(dān)一段連續(xù)的標(biāo)識, 通過虛擬服務(wù)器在真實節(jié)點之間的遷移實現(xiàn)負(fù)載均衡. 在基于元數(shù)據(jù)的P2P系統(tǒng)中有這樣一類問題：假設(shè)k是一個”熱門”關(guān)鍵字如”2008”,

11、必然在很多資源描述信息和查詢中包含k, 如果n是k的散列值對應(yīng)的節(jié)點, 那么n上必然因為要存儲大量資源描述信息, 接受大量的查詢請求, 而成為”熱點”. 這是因為標(biāo)識(對應(yīng)某關(guān)鍵字)負(fù)載不均勻引起的第三類問題, 但上述兩種解決辦法對此問題并不適用: 第一種方法在節(jié)點頻繁加入和退出網(wǎng)絡(luò)時會導(dǎo)致大量無效的資源元數(shù)據(jù)(資源節(jié)點已經(jīng)退出網(wǎng)絡(luò), 但其元數(shù)據(jù)卻依然存在), 引入較高的副本管理成本; 第二種方法的前提是假設(shè)網(wǎng)絡(luò)中所有標(biāo)識的訪問負(fù)載分布均勻, 即針對不同關(guān)鍵字的訪問量相當(dāng), 這顯然與互聯(lián)網(wǎng)應(yīng)用的特征相違背.針對該問題, 本文提出一種支持負(fù)載均衡的多屬性資源定位方法QFMA (Query-Fee

12、dback based Multi-attribute Addressing). QFMA的主要思想: 以MAAN為基礎(chǔ), 借鑒沿路復(fù)制的思想, 在查詢路由路徑上“捎帶”發(fā)布“熱門”關(guān)鍵字所在節(jié)點的狀態(tài)信息；其它查詢根據(jù)這些狀態(tài), 在路由過程中進(jìn)行查詢目標(biāo)切換, 將“熱門”關(guān)鍵字所在節(jié)點的負(fù)載分流到負(fù)擔(dān)較輕的節(jié)點上, 提高網(wǎng)絡(luò)的負(fù)載均衡特性.本文研究的基本思路是復(fù)制和緩存, 與其它相關(guān)研究9,14,15的區(qū)別在于, 解決負(fù)載均衡問題的同時, 不會產(chǎn)生無效的資源元數(shù)據(jù)和較大的副本管理開銷: (1)資源加入時基于MAAN對其元數(shù)據(jù)進(jìn)行復(fù)制, 因為副本存儲的位置是確定的, 資源發(fā)生變化時資源節(jié)點能夠

13、直接對這些信息進(jìn)行更新, 不會產(chǎn)生無效的資源元數(shù)據(jù); (2)查詢過程中復(fù)制的對象僅僅是狀態(tài)信息, 狀態(tài)信息有存活周期, 資源節(jié)點的加入退出以及資源屬性的更新不會為狀態(tài)管理帶來額外的開銷. 第2節(jié)詳細(xì)闡述QFMA的主要思想；第3節(jié)對QFMA進(jìn)行理論分析；第4節(jié)實驗驗證；第5節(jié)總結(jié)和展望.2 QFMA算法2.1 定義和說明根據(jù)文獻(xiàn)2給出與資源及查詢相關(guān)的形式化定義.定義1 (資源描述) 資源r的描述是一個包含m個屬性的集合, 每個屬性可表示為二元組(a, v), 其中a是屬性名, v是屬性值, 以下屬性值也稱為關(guān)鍵字.定義2 (查詢) 定義查詢q為形如 (a1=v1)Ù(a2=v2) &

14、#217;¼Ù(as=vs) s³1, 的表達(dá)式. 給定任意查詢q, Kq是q中所有關(guān)鍵字組成的集合, r為任意資源, Kr是其描述信息中所有關(guān)鍵字組成的集合, 如果Kq Í Kr, 則稱資源r滿足查詢q.根據(jù)文獻(xiàn)5給出節(jié)點負(fù)載率相關(guān)的定義.節(jié)點接受查詢請求, 執(zhí)行查詢處理, 返回查詢結(jié)果需要消耗一定的計算資源和網(wǎng)絡(luò)帶寬資源. 本文用單位時間內(nèi)接受的查詢請求數(shù)量來衡量節(jié)點的負(fù)載情況, 稱之為節(jié)點負(fù)載. 每個節(jié)點都有計算和帶寬的限制, 定義節(jié)點單位時間內(nèi)能夠接收和處理查詢請求的最大數(shù)量為其能力.定義3 (節(jié)點負(fù)載率) 令節(jié)點n的能力為cn, 負(fù)載為ln,

15、那么n的負(fù)載率為un = ln/cn. 令節(jié)點n的負(fù)載率閾值為tn, 當(dāng)un ³ tn時, 稱節(jié)點n過載, 否則稱節(jié)點n欠載. 如果負(fù)責(zé)H(k)的節(jié)點n處于過載狀態(tài), 則稱k為過載關(guān)鍵字.在此基礎(chǔ)上給出其它相關(guān)定義. 定義4 (路由路徑) 令節(jié)點ns到節(jié)點nt的路由過程為ns, n1, ¼, np, nt, 其中np為nt的直接前驅(qū)節(jié)點. 稱n1, ¼, np為從ns到nt的路由路徑, 簡稱路徑. 任意一條以nt為目標(biāo)的路徑p, 如果p中任意節(jié)點記錄有nt的狀態(tài), 則稱p命中nt的狀態(tài). 定義5 (節(jié)點狀態(tài)): 節(jié)點n的狀態(tài)sn可以表示為三元組(start-idn

16、, end-idn, idn, un), 其中start-idn, end-idn是節(jié)點n負(fù)責(zé)的標(biāo)識區(qū)間, idn.是節(jié)點n的標(biāo)識, un表示節(jié)點的負(fù)載率. 定義6 (查詢消息): 查詢消息表示為三元組(q, C, k), 其中q表示查詢, 令Kq為q中所有關(guān)鍵字組成的集合, CÍKq是候選關(guān)鍵字集合, 由查詢發(fā)起者進(jìn)行初始化, 在查詢路由過程中演化, k表示當(dāng)前用于定位資源的關(guān)鍵字. 本文網(wǎng)絡(luò)的構(gòu)造和演化過程遵循Chord協(xié)議. 節(jié)點在加入網(wǎng)絡(luò)時將本節(jié)點的資源描述存儲到相應(yīng)節(jié)點: 給定資源r及其屬性序列(ai, vi), iÎ1, m, 對每個關(guān)鍵字vi, 采用一致性ha

17、sh算法H將vi映射為一個屬性標(biāo)識H(vi), 并將資源描述存儲到H(vi)對應(yīng)的節(jié)點.網(wǎng)絡(luò)中的每個節(jié)點既可以是查詢的發(fā)起者, 也可以是接受者, 另外還可以作為查詢路由的中間節(jié)點; 節(jié)點定期根據(jù)接受的查詢負(fù)載情況更新負(fù)載率; 每個節(jié)點需要維護(hù)一個狀態(tài)列表, 用于記錄途徑本節(jié)點的查詢反饋的過載節(jié)點的狀態(tài)信息. 2.2狀態(tài)管理算法從任意節(jié)點ns發(fā)起的查詢q, 其路徑為n1, ¼, np, nt為目標(biāo)節(jié)點, nt執(zhí)行完查詢操作后會沿路徑反向返回結(jié)果, 如果nt處于過載狀態(tài), 在結(jié)果中“捎帶”nt的狀態(tài). 路徑上的節(jié)點(np除外)在接收到帶有狀態(tài)的結(jié)果時, 調(diào)用State_Manager算法

18、對本節(jié)點的狀態(tài)列表進(jìn)行維護(hù). 在本節(jié)點狀態(tài)列表state_list中增加狀態(tài)項時需要為其設(shè)置時間戳; 如果本節(jié)點已經(jīng)存在nt的狀態(tài)項時需重新設(shè)置其時間戳. 因為每個節(jié)點負(fù)責(zé)的標(biāo)識區(qū)間不相交, 所以可以根據(jù)狀態(tài)項中的start-idn對狀態(tài)列表中的項進(jìn)行排序, 以提高匹配速度; 為了提高狀態(tài)命中概率, 在路徑上各節(jié)點(np除外)的前驅(qū)節(jié)點和k(與系統(tǒng)設(shè)置相關(guān))個后繼節(jié)點上都記錄相應(yīng)的狀態(tài); 每個節(jié)點定期檢查自己的state_list刪除過時的狀態(tài)項. 假設(shè)n為路徑上的任意節(jié)點, state為結(jié)果消息中“捎帶”的狀態(tài)信息, 狀態(tài)管理算法描述如下:算法1: 狀態(tài)管理算法State_Manager(

19、n, state )在節(jié)點n的上記錄該狀態(tài)1. n.Add_State( state ) 在n的前驅(qū)節(jié)點上記錄該狀態(tài)2. n.precessor.Add_State ( state )在n的k個后繼節(jié)點上記錄該狀態(tài)3.fori1 to k 4. n.successorj. add_state(state)Add_State( state )根據(jù)idn判斷該狀態(tài)項是否已存在1.if exist( state )更新節(jié)點狀態(tài)中的負(fù)載率和時間戳2. updata( state ) 3.else將state插入state_list4. insert( state ) 2.3路由算法令ns, n1, &

20、#188;, np, nt為查詢q路由過程涉及的所有節(jié)點(ns為查詢發(fā)起節(jié)點, n1, ¼, np為路由路徑, nt為目標(biāo)節(jié)點), 查詢路由過程中的每個節(jié)點都調(diào)用Query_Rout算法執(zhí)行路由操作. (1) ns首先從查詢q中提取出所有關(guān)鍵字, 初始化候選關(guān)鍵字集合C; 依據(jù)本地狀態(tài)列表從C中刪除過載關(guān)鍵字(如果C中僅剩一個關(guān)鍵字, 則保留); 從C中隨機(jī)選擇一個關(guān)鍵字賦予當(dāng)前關(guān)鍵字k, 初始化路由消息; 根據(jù)H(k)選擇下一跳節(jié)點, 并向其轉(zhuǎn)發(fā)查詢消息. (2) 路徑上的節(jié)點則根據(jù)本節(jié)點狀態(tài)列表從C中刪除過載關(guān)鍵字; 如果本節(jié)點記錄有路由消息中當(dāng)前關(guān)鍵字所在節(jié)點的狀態(tài)信息, 則執(zhí)

21、行目標(biāo)切換, 否則直接選擇下一跳節(jié)點轉(zhuǎn)發(fā)查詢消息; (3) 到達(dá)目標(biāo)節(jié)點, 路由過程結(jié)束, 執(zhí)行查詢操作, 返回查詢結(jié)果. 假設(shè)n是查詢q路由過程中的任意節(jié)點, msg是對應(yīng)的查詢消息, 路由算法描述如下: 算法2: 路由算法Query_Rout(n, msg)判斷是否為目標(biāo)節(jié)點1.if is_dest_node(n) 執(zhí)行查詢操作2. n.excute(msg.q) 3. return 查詢發(fā)起節(jié)點4.if is_init_node(n) 5. init_msg( msg )6. else n上存在與k相關(guān)狀態(tài), C不為空.7. remove_overload (msg C)8. if (h

22、as_state(n, msg k)&&( msg C) 9.msg krandom_sel(msg C) 10.msg CC- msg k 選擇下跳節(jié)點, 轉(zhuǎn)發(fā)送查詢消息11. foword(msg) 初始化查詢消息init_msg(msg)初始化C1.msg Cextract(msg q) 根據(jù)本節(jié)點狀態(tài)列表, 刪除C中過載關(guān)鍵字2.remove_overload(msg C)從C中隨機(jī)選擇一個作為當(dāng)前關(guān)鍵字3.msg krandom_sel(msg C) 將該關(guān)鍵字從C中刪除4.msg Cmsg C-msg k檢查節(jié)點n上是否有負(fù)責(zé)k的節(jié)點的狀態(tài)記錄has_state(n

23、, k)1.for i0 to n.stata_list.length 1 2. if (n.stata_listi. start-idn H(k) && (H(k) n.stata_listi. end-idn)3.if is_intime(n.stata_listi)4.return true 5.return false 3算法分析3.1路由算法分析定理1 QFMA路由算法是收斂且完備的證明(1) 如果當(dāng)前關(guān)鍵字所在節(jié)點處于非過載狀態(tài), 則查詢路由過程不需要進(jìn)行查詢目標(biāo)切換, 根據(jù)Chord路由算法知, 經(jīng)過O(logN)跳后, 路由過程一定會結(jié)束. (2) 否則, 需要

24、進(jìn)行查詢目標(biāo)切換, 執(zhí)行切換的條件是當(dāng)前關(guān)鍵字為過載關(guān)鍵字且候選關(guān)鍵字集合不為空. 因為候選關(guān)鍵字集合中元素個數(shù)是有限的, 假設(shè)其個數(shù)為x, 所以最多再執(zhí)行x次切換, 每次切換之前經(jīng)過的跳數(shù)最多為O(logN), 即最多經(jīng)過O(xlogN)跳后要么當(dāng)前關(guān)鍵字為非過載關(guān)鍵字, 要么候選關(guān)鍵字集合為空, 令此時的當(dāng)前關(guān)鍵字為k, 那么之后的路由過程是以k為當(dāng)前關(guān)鍵字, 不會執(zhí)行切換操作, 路由過程再經(jīng)過O(logN)步后結(jié)束. 根據(jù)(1), (2)知QFMA路由算法是收斂的. (3) 設(shè)r為任意滿足查詢q的資源, Kr為r包含的所有關(guān)鍵字組成集合, Kq為q包含的所有關(guān)鍵字組成的集合, 則Kq &

25、#205; Kr. 對任意關(guān)鍵字k ( kKq ), 顯然kKr, 令n為負(fù)責(zé)H(k)的節(jié)點, 則n一定存有資源r的描述, 所以根據(jù)k一定可以定位到資源r. 因為k為Kq中任意關(guān)鍵字, 只要存在滿足查詢的資源就一定可以被定位. 即QFMA路由算法是完備的.綜上所述, QFMA路由算法是收斂且完備的. 證畢.3.2節(jié)點負(fù)載分析假設(shè)任意節(jié)點n處于過載狀態(tài), 任一以n為目標(biāo)的查詢q, 路由過程中能否有效地進(jìn)行查詢目標(biāo)切換, 與其路徑能否命中的狀態(tài)有關(guān). 如果在n的直接前驅(qū)上記錄狀態(tài), 后續(xù)以n為目標(biāo)的查詢路徑都一定會命中該狀態(tài), 在狀態(tài)有效時n將接受不到查詢處于0負(fù)載情況, 狀態(tài)失效后又將很快處于過

26、載狀態(tài), n的負(fù)載處于震蕩狀態(tài), 所以我們不在n的直接前驅(qū)上記錄其狀態(tài). 本文在路徑上每個節(jié)點(n的直接前驅(qū)除外)的前驅(qū)節(jié)點和k個后繼節(jié)點上記錄其狀態(tài), 使得以n為目標(biāo)的查詢路徑命中其狀態(tài)的概率大大增加. 在n剛處于過載狀態(tài)時, 發(fā)布到網(wǎng)絡(luò)上的狀態(tài)的數(shù)量很少, 其狀態(tài)被命中的概率相對較小, 隨著發(fā)布到網(wǎng)絡(luò)上的狀態(tài)增多時, 被命中的概率會大大提高. 狀態(tài)存在有效期, 當(dāng)狀態(tài)失效后命中該狀態(tài)的查詢不會進(jìn)行查詢切換, 由于到達(dá)n的查詢是有先后順序的, 所以只要選擇合適的狀態(tài)有效期, 保證網(wǎng)絡(luò)中存在相對穩(wěn)定的狀態(tài)數(shù)量, 那么狀態(tài)命中概率將趨于穩(wěn)定. 我們用Zipf定律描述關(guān)鍵字訪問頻度的分布, Zip

27、f定律一般表達(dá)式為: Fi=/ia, 為常數(shù), i為該對象的流行度排列位次, Fi為其訪問頻度. 一般來講1.6>a>0可以涵蓋目前對互聯(lián)網(wǎng)應(yīng)用的分析結(jié)果7,為了簡化問題本文取a=1, 用概率Pi代替頻度, Pi=C/i, 其中C=(Mi=11/i)-1 1/lnM, M為關(guān)鍵字的總數(shù), 則Pi 1/(lnM*i). 令系統(tǒng)中一共有N個關(guān)鍵字, 關(guān)鍵字k的流行度排行位次為i, 包含k的查詢中涉及的關(guān)鍵字個數(shù)平均為M個. 那么在MAAN中任意查詢以k所在節(jié)點為目標(biāo)的概率約為1/(i*M*lnN). 設(shè)單位時間內(nèi)的總訪問量為A, 那么n的負(fù)載約為A/(i*M*lnN); 在QFMA中,

28、假設(shè)n的狀態(tài)命中概率為p (穩(wěn)定后), 那么n的負(fù)載約為A(1-p)/(i*M*lnN). 3.3平均路由長度定理2：QFMA的路由路徑長度為O(logN)證明：令q為從ns發(fā)起的查詢, Kq為q中包含的關(guān)鍵字組成的集合, |Kq|=M, k為查詢消息中的當(dāng)前關(guān)鍵字.如果k為非過載關(guān)鍵字, QFMA算法的查詢路由過程與Chord一致, 所以路徑長度也為O(logN). 如果k為過載關(guān)鍵字, 在查詢路由過程中要進(jìn)行查詢目標(biāo)切換, 路徑長度會相應(yīng)增加.因為|Kq|=M, 那么查詢路由過程最多執(zhí)行次M-1切換. 顯然以某一關(guān)鍵字為當(dāng)前關(guān)鍵字的路由過程在切換之前的路徑長度最多為O(logN), 令整個

29、查詢的路由路徑長度為L,很顯然LO(MlogN). 因為M是一個常數(shù), 而且值一般都比較小, 所以QFMA路由路徑長度為O(logN) . 證畢.4實驗驗證PeerSim16是歐洲BISON, DELIS項目的一部分, 它是由博洛尼亞大學(xué)基于JAVA語言開發(fā)的基于組件的通用P2P仿真平臺, 該平臺支持步長和事件兩種模式. Trento大學(xué)在該平臺上實現(xiàn)了標(biāo)準(zhǔn)Chord協(xié)議, 本文對Chord協(xié)議進(jìn)行擴(kuò)充實現(xiàn)了MAAN和QFMA, 并進(jìn)行仿真比較. 環(huán)境設(shè)置: 網(wǎng)絡(luò)節(jié)點數(shù)目1000, 網(wǎng)絡(luò)拓?fù)渫ㄟ^PeerSim自動生成. 資源數(shù)目100000, 每個資源的屬性為5個, 每個屬性用一個關(guān)鍵字來表示

30、(在DHT中關(guān)鍵字和字符串是沒有區(qū)別的), 關(guān)鍵字是從文獻(xiàn)3中提取, 形成一個關(guān)鍵字集合. 從集合中隨機(jī)選擇5個不相同的關(guān)鍵字分配給一個資源, 作為其屬性值. 文獻(xiàn)中單詞總數(shù)為12810, 有1793個不同的單詞, 單詞的出現(xiàn)情況如圖1-a; 對文獻(xiàn)中出現(xiàn)的關(guān)鍵字按照詞頻進(jìn)行排序(詞頻相同名次相同), 分布情況如圖1-b, 從圖中可以看出, 關(guān)鍵字服從a1的zipf分布. 本文實驗的工作負(fù)載將基于這些關(guān)鍵字形成.圖1-a 單詞出現(xiàn)情況圖1-b 關(guān)鍵字分布4.1“熱點”狀態(tài)命中情況首先任取n個節(jié)點, 從這些節(jié)點發(fā)起僅包含同一關(guān)鍵字的查詢, 在返回結(jié)果時沿路徑(直接前驅(qū)除外)記錄其所在節(jié)點的狀態(tài);

31、 然后任取10個節(jié)點發(fā)起僅包含該關(guān)鍵字的查詢, 第一次命中該關(guān)鍵字所在節(jié)點狀態(tài)時記錄經(jīng)過的跳數(shù). 對每一個n模擬一次, 取步長的平均值得到曲線A. 從圖中可以看出當(dāng)n大于10時, 其它以該關(guān)鍵字為目標(biāo)的查詢, 平均三到四步可以命中其狀態(tài); 當(dāng)n大于30以后一般經(jīng)過兩跳可以命中其狀態(tài). 圖2 狀態(tài)命中需要跳數(shù)其它設(shè)置相同, 返回結(jié)果時除了路徑上的節(jié)點, 還在這些節(jié)點的前驅(qū)節(jié)點、k(取12)個后繼節(jié)點上記錄相應(yīng)的狀態(tài), 根據(jù)實驗結(jié)果得到曲線B. 從圖中可以看出: n=0時, 跳數(shù)實際上表示在1000個節(jié)點的網(wǎng)絡(luò)中路由路徑長度, 為5.7; 當(dāng)n大于10時, 命中狀態(tài)的跳數(shù)稍大于1, 這明顯好于僅在

32、路徑上記錄節(jié)點狀態(tài)的情況. 4.2節(jié)點負(fù)載每個節(jié)點每10秒鐘(時間點隨機(jī)選擇)從關(guān)鍵字集合中任取3個不同的關(guān)鍵字構(gòu)成形如(a1=v1)Ù(a2=v2)Ù(a3=v)的查詢, 在MAAN中運行, 每個節(jié)點記錄自己接受查詢的頻度(以分鐘為單位, 系統(tǒng)運行10分鐘后取均值); 節(jié)點接受查詢頻度的閾值取每分鐘20次, 狀態(tài)有效期設(shè)為20秒, 其它設(shè)置同上, 對QFMA進(jìn)行模擬. 從圖3中可以看出在MAAN中, 有很少一部分節(jié)點負(fù)載遠(yuǎn)遠(yuǎn)高于普通節(jié)點, 大于100, 絕大部分節(jié)點的負(fù)載在05之間; 采用QFMA算法, 節(jié)點負(fù)載主要集中在310之間, 分布比MAAN均勻. 圖3節(jié)點負(fù)載分

33、布對頻度最高的關(guān)鍵字“the”所在節(jié)點的負(fù)載進(jìn)行采樣, 采樣時間間隔為1分鐘, 該節(jié)點1小時內(nèi)的負(fù)載狀況如圖4所示. 從圖中可以看出該節(jié)點的負(fù)載在20左右, 并且一旦超過20很快就會調(diào)整到20以下. 圖4節(jié)點負(fù)載4.3平均路由長度對查詢消息進(jìn)行擴(kuò)充(q, C, k, H), 增加參數(shù)H記錄消息已經(jīng)過的跳數(shù), 查詢發(fā)起者將其初始化為0, 每一跳加1, 到達(dá)目標(biāo)節(jié)點時, 記錄該消息經(jīng)過的跳數(shù). 在上述設(shè)置下模擬10分鐘, 一共產(chǎn)生60000個查詢, 查詢路由跳數(shù)分布如圖5所示. 從圖中可以看出查詢路由跳數(shù)主要集中在4, 5, 6, 7, 8. 圖5 QFMA路由路徑長度分布 同樣的設(shè)置對MAAN協(xié)

34、議進(jìn)行模擬, 路由跳數(shù)均值為5.3, QFMA路由跳數(shù)均值為5.88, 這表明我們在實現(xiàn)負(fù)載均衡時, 路由路徑長度并沒有明顯增加. 5總結(jié)本文針對DHT中由于關(guān)鍵字負(fù)載分布不均勻引起的“熱點”問題, 提出了一種支持負(fù)載均衡的多屬性資源定位方法QFMA, 并在通用P2P仿真平臺PeerSim上進(jìn)行驗證, 實驗結(jié)果表明QFMA能夠有效減輕“熱門”關(guān)鍵字所在節(jié)點的負(fù)載, 提高系統(tǒng)的負(fù)載均衡性, 而且不會使網(wǎng)絡(luò)中產(chǎn)生無效元數(shù)據(jù), 不會帶來額外的副本管理成本, 同時查詢路徑長度同樣是O(logN). 本文沒有考慮查詢發(fā)起節(jié)點的分布特性, 針對查詢分布的特點對相關(guān)算法進(jìn)行改進(jìn)是下一步研究的重點.參考文獻(xiàn)1

35、 I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In : Proceedings of ACM SIGCOMM, San Diego, CA, 2001, 149160. 2 M. Cai, M. Frank, J. Chen, and P. Szekely. MAAN: A multi-attribute addressable network for grid

36、 information services. In : 4th Intl Workshop on Grid Computing, Phoenix, AZ, 2003, 184191.3 Bharambe.A, Agrawal.M, Seshan. Mercury: Suppporting Scalable Multi-Attribute Range Queries, In: Proceedings of ACM SIGCOMM, Portland, Oregon, 2004, 353366. 4 Ananth Rao, Karthik Lakshminarayanan, Sonesh Sura

37、na, Richard Karp, and Ion Stoica. Load Balancing in Structured P2P Systems, In: Proceedings of IPTPS, Berkeley, CA, 2003, 6879.5 Godfrey. B., Lakshminarayanan. K., Surana.S., Karp.R., and Stoica.I. Load balancing in dynamic structured P2P systems. In: Proceedings of IEEE INFOCOM, Hong Kong, China, 2

38、004.6 P. Brighten Godfrey, I . Stoica. Heterogeneity and Load Balance in Distributed Hash Tables. In: IEEE INFOCOM, Miami, FL, USA ,2005, 596606.7 Theoni Pitoura, Peter Triantafillou. Load Distribution Fairness in P2P Data Management Systems, In: Proceedings of ICDE, Istanbul, Turkey, 2007, 396405.8

39、 Saroiu S, Gummadi KP, Dunn RJ, Gribble SD, Levy HM. An analysis of Internet content delivery systems. In: Proceedings of OSDI. Boston: USENIX Association, 2002, 3153279 Dabek F, Kaashoek F, Karger D, Morris R, Stoica I. Wide-Area cooperative storage with CFS. In: Proceedings of SOSP. New York: ACM Press, 2001, 202215.10 Cai.M, Fran