淺談基于p2p網(wǎng)絡(luò)的搜索引擎技術(shù)

吳兆立

【摘 要】隨著互聯(lián)網(wǎng)的迅速發(fā)展，網(wǎng)上的信息資源海量增加，在給用戶提供共享的同時(shí)也給用戶搜索、定位和獲取信息資源帶來了巨大的困難。傳統(tǒng)的搜索技術(shù)采用集中式架構(gòu)，存在很多問題，對(duì)搜索性能產(chǎn)生了很大的影響。P2P作為一種新的網(wǎng)絡(luò)模式，具有自組織、分布式、可擴(kuò)展性的特點(diǎn)。它的出現(xiàn)給搜索引擎技術(shù)的發(fā)展帶來了新的機(jī)遇。本文首先介紹課題的研究背景，闡述當(dāng)前P2P搜索引擎的國內(nèi)外研究現(xiàn)狀。然后介紹搜索引擎的發(fā)展歷史、原理以及未來的發(fā)展趨勢(shì)以及P2P技術(shù)的基本概念并分析其主要優(yōu)點(diǎn)。最后介紹一種新的基于Chord協(xié)議的P2P網(wǎng)絡(luò)模型。

【關(guān)鍵詞】P2P網(wǎng)絡(luò) 搜索模型 Group Chord協(xié)議

隨著網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)上的資源海量增加。互聯(lián)網(wǎng)的出現(xiàn)，開創(chuàng)了文類文化信息化的新時(shí)代。它向公眾開放的信息資源比世界上任何一個(gè)圖書館或任何一個(gè)信息存儲(chǔ)機(jī)構(gòu)都要多。人類的生活、學(xué)習(xí)、工作都離不開網(wǎng)絡(luò)。因此，如何在這海量的信息資源之中獲取對(duì)自身有價(jià)值的信息已成為人們?nèi)找骊P(guān)注的問題。搜索引擎技術(shù)是一種幫助網(wǎng)絡(luò)用戶查詢所需信息的搜索工具，是為論文解決網(wǎng)上信息查詢困難的難題應(yīng)用而生的，它可以有效地幫助用戶在網(wǎng)絡(luò)上查找到自己所需要的信息。如果說絡(luò)改變了人類的生活，那么搜索引擎正是改變?nèi)祟惿畹墓ぞ摺?/p>

一、基于Chord協(xié)議的P2P網(wǎng)絡(luò)

（一）Chord的拓?fù)浣Y(jié)構(gòu)

Chord將整個(gè)網(wǎng)絡(luò)抽象為一個(gè)環(huán)形的拓?fù)浣Y(jié)構(gòu)，通過一致性哈希變換（Consistent Hashing），通常使用哈希函數(shù)SHA-1，給每一個(gè)節(jié)點(diǎn)和文檔都賦予一個(gè)m位的標(biāo)識(shí)符key，節(jié)點(diǎn)的標(biāo)識(shí)符是通過對(duì)節(jié)點(diǎn)的IP地址進(jìn)行哈希變換得到的，文檔的標(biāo)識(shí)符是通過對(duì)文檔的內(nèi)容進(jìn)行哈希變換得到的①。標(biāo)識(shí)符的長(zhǎng)度m應(yīng)該足夠大，使得Chord環(huán)能夠容納最大可能的參與節(jié)點(diǎn)數(shù)，并且使得任意兩個(gè)節(jié)點(diǎn)或者文檔經(jīng)過哈希變換后得到相同標(biāo)識(shí)符的概率可以忽略不計(jì)。Chord網(wǎng)絡(luò)中所有的節(jié)點(diǎn)根據(jù)標(biāo)識(shí)符從小到大的順序以順時(shí)針的方向構(gòu)成一個(gè)邏輯環(huán)形的拓?fù)浣Y(jié)構(gòu)，文檔保存在后繼節(jié)點(diǎn)上。后繼節(jié)點(diǎn)（Successor）是節(jié)點(diǎn)標(biāo)識(shí)符大于或者等于當(dāng)前節(jié)點(diǎn)標(biāo)識(shí)符的最小的一個(gè)節(jié)點(diǎn)，形象說后繼節(jié)點(diǎn)就是邏輯環(huán)中順時(shí)針方向第一個(gè)跟著當(dāng)前節(jié)點(diǎn)的實(shí)際存在的節(jié)點(diǎn)；前置節(jié)點(diǎn)（Predecessor）與后繼節(jié)點(diǎn)正相反，是邏輯環(huán)中逆時(shí)針方向第一個(gè)跟著當(dāng)前節(jié)點(diǎn)的實(shí)際存在的節(jié)點(diǎn)，方便節(jié)點(diǎn)逆時(shí)針方向的查找，節(jié)點(diǎn)m的后繼節(jié)點(diǎn)和前置節(jié)點(diǎn)分別記為Successor（m）和Predecessor（m）。

（二）Chord的資源搜索機(jī)制

在Chord網(wǎng)絡(luò)中，簡(jiǎn)單的資源搜索機(jī)制是每個(gè)節(jié)點(diǎn)只需要保存其后繼節(jié)點(diǎn)的信息，這樣查詢消息就可以沿著Chord環(huán)以順時(shí)針的方向一步一跳的傳遞，直到找到匹配的節(jié)點(diǎn)②。這種通過節(jié)點(diǎn)的鄰接關(guān)系進(jìn)行消息順序傳遞的方法雖然簡(jiǎn)單可行，但是效率非常低，網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)為了找到對(duì)方很可能將消息繞環(huán)傳遞一周。為了提高查詢效率，減少定位開銷，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)保存一個(gè)具有n個(gè)表項(xiàng)的Finger表（Finger Table，鄰居表），這樣網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)只需要維護(hù)自身Finger表中的小部分節(jié)點(diǎn)，無需掌握網(wǎng)絡(luò)中其他節(jié)點(diǎn)的信息，就可以通過節(jié)點(diǎn)之間的通信，找到任一節(jié)點(diǎn)。

二、新的P2P網(wǎng)絡(luò)模型的基本思想

Chord通過把網(wǎng)絡(luò)虛擬成環(huán)形的拓?fù)浣Y(jié)構(gòu)，完成了信息的快速搜索，提高了查詢效率，但是存在以下兩方面的問題：

（1）以Chord為代表的結(jié)構(gòu)化P2P網(wǎng)絡(luò)在構(gòu)建網(wǎng)絡(luò)的時(shí)候沒有考慮節(jié)點(diǎn)的實(shí)際物理拓?fù)浣Y(jié)構(gòu)，都忽視了覆蓋網(wǎng)絡(luò)與底層網(wǎng)絡(luò)的差異，這樣將會(huì)導(dǎo)致在實(shí)際網(wǎng)絡(luò)中相距很近的兩個(gè)節(jié)點(diǎn)通過函數(shù)映射在覆蓋網(wǎng)絡(luò)上卻相距很遠(yuǎn)，而在覆蓋網(wǎng)絡(luò)中距離很遠(yuǎn)的節(jié)點(diǎn)卻可能成為實(shí)際網(wǎng)絡(luò)中的臨近節(jié)點(diǎn)，即Chord網(wǎng)絡(luò)的繞路（Detouring）問題。這樣的底層網(wǎng)絡(luò)與覆蓋網(wǎng)絡(luò)的不一致，將致使覆蓋網(wǎng)絡(luò)上的兩個(gè)臨近節(jié)點(diǎn)理論上看似距離很近，但實(shí)際上要想找到對(duì)方卻要經(jīng)過很長(zhǎng)的路徑，使得基于這種覆蓋網(wǎng)絡(luò)所做的評(píng)測(cè)的不可靠；相反實(shí)際距離很近的兩個(gè)節(jié)點(diǎn)，因?yàn)楸挥成涞搅烁采w網(wǎng)絡(luò)上距離很遠(yuǎn)的位置，卻要在網(wǎng)絡(luò)中白白的繞一圈才能找到對(duì)方，致使走了大量重復(fù)路徑，增加網(wǎng)絡(luò)流量，浪費(fèi)帶寬。

（2）目前的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)已經(jīng)充分的考慮了節(jié)點(diǎn)性能（包括計(jì)算能力、存儲(chǔ)能力、網(wǎng)絡(luò)帶寬等性能）的差異，但是傳統(tǒng)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)尚沒有考慮這一點(diǎn)，不加區(qū)分的賦予網(wǎng)絡(luò)中的所有節(jié)點(diǎn)以同一的責(zé)任，這將造成高性能的節(jié)點(diǎn)沒有充分發(fā)揮其能力的空間，而相對(duì)性能較差的節(jié)點(diǎn)卻擔(dān)負(fù)著無法負(fù)擔(dān)的責(zé)任，嚴(yán)重影響了網(wǎng)絡(luò)的穩(wěn)定性和搜索信息的速度。

三、新模型的體系結(jié)構(gòu)

模型與Chord網(wǎng)絡(luò)不同的是，它改變了Chord協(xié)議的單一環(huán)形空間的拓?fù)浣Y(jié)構(gòu)，而引入了分層分布式的模型結(jié)構(gòu)。整個(gè)網(wǎng)絡(luò)是由多個(gè)Chord環(huán)彼此互連構(gòu)成的，每個(gè)Chord環(huán)是根據(jù)節(jié)點(diǎn)的實(shí)際物理地址劃分的，是相對(duì)獨(dú)立的，Chord環(huán)中的節(jié)點(diǎn)依然按照Chord協(xié)議的規(guī)則組成結(jié)構(gòu)化的P2P網(wǎng)絡(luò)，而每個(gè)Chord環(huán)之間則是以完全分布式的方式連接的。

四、新模型介紹

新模型繼承了Chord網(wǎng)絡(luò)在可擴(kuò)展性和魯棒性等方面的優(yōu)點(diǎn)，同時(shí)考慮了節(jié)點(diǎn)的實(shí)際物理地址和節(jié)點(diǎn)性能的差異，它是一個(gè)將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照實(shí)際物理地址的鄰近性劃分群組的分層分布式結(jié)構(gòu)的網(wǎng)絡(luò)模型。網(wǎng)絡(luò)中實(shí)際鄰近的節(jié)點(diǎn)在覆蓋網(wǎng)絡(luò)模型中也相距很近，使得網(wǎng)絡(luò)拓?fù)浜蛯?shí)際物理地址相對(duì)一致。

五、結(jié)論

P2P技術(shù)在網(wǎng)絡(luò)應(yīng)用領(lǐng)域顯示出很強(qiáng)的技術(shù)優(yōu)勢(shì)，最近幾年的迅速發(fā)展，受到廣泛、關(guān)注。由于網(wǎng)絡(luò)用戶以及網(wǎng)絡(luò)資源的增加，C/S模式下的網(wǎng)絡(luò)對(duì)服務(wù)器要求很高，越來越難提供滿意的服務(wù)性能。P2P技術(shù)的分散特性⑤與因特網(wǎng)的協(xié)議和結(jié)構(gòu)完全相適應(yīng)，具有極強(qiáng)的適應(yīng)性和網(wǎng)絡(luò)服務(wù)能力。因此，設(shè)計(jì)高效的搜索機(jī)制，快速而準(zhǔn)確地找到所需要的資源，才能使P2P網(wǎng)絡(luò)得以廣泛應(yīng)用。本文在分析了現(xiàn)有P2P搜索方法的優(yōu)缺點(diǎn)基礎(chǔ)上介紹了一種搜索模型，該模型能夠以很小的開銷獲得很高的性能。

參考文獻(xiàn)：

[1]毛薇，姚青，李濤.基于P2P的高效搜索引擎的研究[J].武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2002，24（4）：43.

[2]呂建明，劉悅，丁林，等.P2P與信息檢索[J].信息技術(shù)快報(bào)，2005，（2）.