支持多關(guān)鍵字查詢(xún)的改進(jìn)Chord算法.pdf

1、支持多關(guān)鍵字查詢(xún)的改進(jìn)Chd算法重慶大學(xué)碩士學(xué)位論文（學(xué)術(shù)學(xué)位）學(xué)生姓名：王興芹指導(dǎo)教師：符云清教授專(zhuān)業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)學(xué)科門(mén)類(lèi)：工學(xué)重慶大學(xué)計(jì)算機(jī)學(xué)院學(xué)院二O一二年十月重慶大學(xué)碩士學(xué)位論文中文摘要I摘要P2P網(wǎng)絡(luò)的應(yīng)用越來(lái)越多地受到了人們的關(guān)注?，F(xiàn)在，P2P網(wǎng)絡(luò)面臨的關(guān)鍵問(wèn)題就是如何準(zhǔn)確快速并且全面地定位共享資源。不同的P2P網(wǎng)絡(luò)采用的拓?fù)浣Y(jié)構(gòu)也各不相同，它們的查詢(xún)效率也各不一樣。本文分析了一種完全分布式結(jié)構(gòu)化拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)模型—Chd

2、模型。Chd模型采用了一致性哈希算法，以分布式散列表為查找策略。在Chd模型中，每個(gè)節(jié)點(diǎn)只需維護(hù)O(logN)條節(jié)點(diǎn)路由信息便可快速地定位共享資源。Chd算法在很多方面體現(xiàn)出了一定的優(yōu)勢(shì)，如：很好的負(fù)載均衡、高可靠性、高可擴(kuò)展性等。但是，由于哈希算法的使用，Chd算法不支持多關(guān)鍵字查詢(xún)，因此也不能全面地定位到共享資源。針對(duì)Chd算法的不足，本文提出了一種改進(jìn)Chd算法。在改進(jìn)的Chd算法中，放棄了通過(guò)一致性哈希算法得到共享資源標(biāo)識(shí)的機(jī)制

3、，采用了BloomFilter算法來(lái)獲取資源標(biāo)識(shí)，但是仍然使用一致性哈希函數(shù)來(lái)獲得節(jié)點(diǎn)標(biāo)識(shí)。各個(gè)節(jié)點(diǎn)和資源不是按照各自標(biāo)識(shí)的大小順時(shí)針排列在Chd環(huán)上。在本文中，首先把Chd環(huán)分段，其次把各個(gè)節(jié)點(diǎn)和資源根據(jù)標(biāo)識(shí)中1bit的個(gè)數(shù)映射到Chd環(huán)中的不同段內(nèi)，然后按照整數(shù)標(biāo)識(shí)的大小，由小到大順時(shí)針地排列在Chd環(huán)的段內(nèi)。當(dāng)查找共享資源時(shí)，首先跳轉(zhuǎn)到對(duì)應(yīng)的Chd環(huán)段內(nèi)，然后根據(jù)資源標(biāo)識(shí)的最長(zhǎng)后綴匹配進(jìn)行查找。為了更加快速地定位到共享資源，每個(gè)節(jié)

4、點(diǎn)存儲(chǔ)了更多節(jié)點(diǎn)的路由信息。首先，論文假設(shè)改進(jìn)Chd算法中各個(gè)節(jié)點(diǎn)都存在，不存在的節(jié)點(diǎn)標(biāo)志為虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)只負(fù)責(zé)路由信息的轉(zhuǎn)發(fā)。各個(gè)節(jié)點(diǎn)根據(jù)自身的二進(jìn)制向量標(biāo)識(shí)就可推測(cè)出自己的路由表信息。路由表信息獲取機(jī)制是通過(guò)自身的二進(jìn)制向量標(biāo)識(shí)，交換二進(jìn)制向量標(biāo)識(shí)中高位的0bit和低位的1bit。改進(jìn)Chd模型不僅僅支持多關(guān)鍵字查詢(xún)，本文還理論證明了改進(jìn)Chd算法的最大查詢(xún)跳數(shù)為m–21，平均查詢(xún)跳數(shù)為m21，其中m為二進(jìn)制標(biāo)識(shí)的長(zhǎng)度，遠(yuǎn)遠(yuǎn)地優(yōu)