基于P2P的資源搜索算法探討

趙著堂

摘 要:服務(wù)器的不堪重負(fù)和分布在網(wǎng)絡(luò)中的閑置資源促使了一種新的網(wǎng)絡(luò)范例——對(duì)等計(jì)算(Peer-to-Peer,簡稱P2P)的出現(xiàn)。文章介紹了P2P的三種類型,提出了基于根服務(wù)器的P2P搜索算法的設(shè)計(jì)。

關(guān)鍵詞:P2P 搜索 根服務(wù)器

一、引言

隨著Internet的廣泛普及和網(wǎng)絡(luò)應(yīng)用規(guī)模的不斷擴(kuò)大,客戶機(jī)/服務(wù)器模式的存儲(chǔ)技術(shù)面對(duì)快速增長的網(wǎng)絡(luò)規(guī)模,由于自身模式的原因閑置浪費(fèi)了大量的計(jì)算和存儲(chǔ)資源。更大規(guī)模的網(wǎng)絡(luò)對(duì)存儲(chǔ)服務(wù)器提出了更高的要求。服務(wù)器的不堪重負(fù)和分布在網(wǎng)絡(luò)中的閑置資源促使了一種新的網(wǎng)絡(luò)范例——對(duì)等計(jì)算(Peer-to-Peer,簡稱P2P)的出現(xiàn)。本文就基于P2P的資源搜索算法設(shè)計(jì)進(jìn)行探討。

二、P2P概述

P2P中文稱為對(duì)等網(wǎng)絡(luò),是指分布式系統(tǒng)中的各個(gè)節(jié)點(diǎn)是邏輯對(duì)等的,也就是說,對(duì)等網(wǎng)絡(luò)中每個(gè)IP點(diǎn)的地位是對(duì)等的,既可充當(dāng)服務(wù)器為其他節(jié)點(diǎn)服務(wù),也可充當(dāng)客戶機(jī)消費(fèi)其他IP點(diǎn)提供的服務(wù)。依據(jù)文件的檢索模型和機(jī)制,現(xiàn)有的P2P實(shí)現(xiàn)方式大致可以分為三種類型。它們分別是基于目錄服務(wù)器P2P,非結(jié)構(gòu)化P2P和結(jié)構(gòu)化P2P。

基于目錄服務(wù)器的P2P摒棄了傳統(tǒng)C/S模式由服務(wù)器負(fù)責(zé)一切的方式,用一個(gè)或多個(gè)中央目錄服務(wù)器存儲(chǔ)資源的實(shí)際存儲(chǔ)位置,并響應(yīng)各P2P對(duì)等機(jī)的查詢請(qǐng)求;在非結(jié)構(gòu)化的P2P中,網(wǎng)絡(luò)模型無需特別的設(shè)計(jì),節(jié)點(diǎn)在網(wǎng)絡(luò)中完全對(duì)等,加入和退出網(wǎng)絡(luò)不會(huì)引起大量的維護(hù)消息;結(jié)構(gòu)化的P2P多數(shù)采用基于DHT技術(shù)構(gòu)造,具有明確的搜索目的性,具有較高的搜索效率。

三、基于根服務(wù)器的P2P搜索算法設(shè)計(jì)

1.數(shù)據(jù)結(jié)構(gòu)

(1)根服務(wù)器上保存所有搜索樹根的列表:

structRootlst{

long KEY_Sector;

long ip;

}rootlst[LENGTH];

(2)物理節(jié)點(diǎn)(PN)所保存的本地邏輯節(jié)點(diǎn)列表:

struct LNlst{

longKEY_Sector;

long LNID;

}Inlst[LENGTH];

int LNnum;

(3)邏輯節(jié)點(diǎn)(LN)的路由表:

struct Lnroute{

longfather;

longchildren[4];

intchildren-count;

int Vln;

int Lin;

long Ext;};

struct LN{

long IP;

long KEY;

struct Lnroute Inroute;

}LNnew;

2.搜索樹根發(fā)現(xiàn)機(jī)制

所有LN維護(hù)一個(gè)僅存儲(chǔ)自己的父節(jié)點(diǎn)、所有子節(jié)點(diǎn)的位置信息的鄰居表,所有根節(jié)點(diǎn)的子節(jié)點(diǎn)均設(shè)置父節(jié)點(diǎn)為根節(jié)點(diǎn)的標(biāo)識(shí)符口當(dāng)一個(gè)LN需要獲得根節(jié)點(diǎn)的位置時(shí),將發(fā)送一個(gè)根節(jié)點(diǎn)發(fā)現(xiàn)消息給自己的父節(jié)點(diǎn),并逐級(jí)向上轉(zhuǎn)發(fā),直到父節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí),返回響應(yīng)消息。

3.空余度路由更新算法

子LN節(jié)點(diǎn)的空余度Vin或者空余度距離Lin發(fā)生改變時(shí),將二者的值發(fā)給父LN,通知父節(jié)點(diǎn)執(zhí)行空余度路由更新。

父節(jié)點(diǎn)更新自己存儲(chǔ)的該子節(jié)點(diǎn)的Vln和Lin,并根據(jù)新的子節(jié)點(diǎn)空余度路。

由狀況重新設(shè)置自己的空余度路由出口。

Vin為空余度,Lin為空余度距離,Ext為空余度路由出口。LN6下接4個(gè)節(jié)點(diǎn)之后,LN6的空余度路由發(fā)生改變,同時(shí)通知其父節(jié)點(diǎn)LN2,LN2將選擇Lin最小的子節(jié)點(diǎn),而LN7.LN8.LN9的Lin均為0,因此LN6選擇這三個(gè)子節(jié)點(diǎn)中Vin最大者,即LN9作為自己的空余度路由出口。而LNl及其他兄弟節(jié)點(diǎn)并為受此拓?fù)渥兓挠绊憽?/p>

偽碼如下:

Route-update(child_Vln, child_Lln){

if (LN.Inroute.children_count<4){

LN.Inroute.Vln=4-LN.Inroute.children_count;

LN.Inroute.Lln=0;

LN.Inroute.Ext=localhost;}

else{

LN.Inroute.Ext=max_Lln(LN.children)

LN.Inroute.Vln=GetRemoteLN(LN.Inroute.Ext).InrouteVln;

LN.Inroute.tln=GetRemoteLN(LN.Inroute.Ext).InrouteLin+1}}

4.搜索樹創(chuàng)建算法

當(dāng)一個(gè)物理節(jié)點(diǎn)上存儲(chǔ)的文件加入PZP網(wǎng)絡(luò)時(shí),將執(zhí)行一下步驟:

(1)計(jì)算出該文件各個(gè)關(guān)鍵字對(duì)應(yīng)的哈希鍵值

(2)檢查本節(jié)點(diǎn)上是否已經(jīng)存在包含該哈希鍵值的LN,如果沒有,則創(chuàng)建該LNnew.

(3)檢查該物理節(jié)點(diǎn)上是否已存在的其他LN,如果不存在,則向根服務(wù)器發(fā)送新LN消息:如果存在則利用該LN的根LN發(fā)現(xiàn)消息找到其所對(duì)應(yīng)的根LN,即對(duì)應(yīng)另一哈希數(shù)值區(qū)間的搜索樹根,并由此確定LNnew本身所屬的哈希數(shù)值區(qū)間的搜索樹是否存在(步驟d確保每個(gè)搜索樹根LN均保有所有搜索樹根LN的信息),若存在,則轉(zhuǎn)向LN加入算法;若不存在,則向根服務(wù)器發(fā)送新LN消息。

(4)根服務(wù)器接收到新LN消息,在LNnew所對(duì)應(yīng)的哈希數(shù)值區(qū)間上新建一棵搜索樹,即將該物理節(jié)點(diǎn)上的這個(gè)新創(chuàng)建的LN定義為該搜索樹的根添加到本地搜索樹根表中的對(duì)應(yīng)行,隨即將這張搜索樹根表發(fā)給所有根LN進(jìn)行更新。

新加入的邏輯節(jié)點(diǎn)LNnew僅在本地不存在其他LN的時(shí)候才向根服務(wù)器發(fā)起查詢請(qǐng)求,而根服務(wù)器也僅需返回對(duì)應(yīng)于LNnew所在哈希值區(qū)段的搜索樹樹根地址即可。

偽碼如下:

CreatTree(KEY){

if(!existed(GetLocalLN)(KEY))

PN.CreateLN(KEY);

if(LNnum>0){

oot=getRoot(anotherLN);

if(Root=getRootLRoot,KEY)==null){

LNnew.send(Sever,msg_NEWLN,LNnew.KEY,LNnew.IP);

Server.Add(Server.getSector(KEY),LNnew.lP);

Server.Broadcast(Server.getRootListQ);}

else

LNnew.send(Root,msgNEWLN,LNnew.KEY,LNnew.IP);}

else

LNnew.send(Sever,msg_NEWLN, LNnew.KEY,LNnew.IP);}}

建立搜索樹的目的即是將同在一個(gè)關(guān)鍵字哈希值區(qū)間內(nèi)的文件邏輯上聚合在一起,當(dāng)產(chǎn)生搜索請(qǐng)求時(shí),搜索消息即可在某個(gè)搜索樹內(nèi)部進(jìn)行,消除了盲目性,而搜索樹的結(jié)構(gòu)也保證了不會(huì)有消息循環(huán)和冗余。每個(gè)節(jié)點(diǎn)僅需負(fù)責(zé)簡單的轉(zhuǎn)發(fā)消息和查找自己的文件列表,負(fù)載分布合理,具有很高的效率。

5.邏輯節(jié)點(diǎn)加入算法

當(dāng)一個(gè)新的LN:LNnew加入網(wǎng)絡(luò),并且由算法A中的c)步驟轉(zhuǎn)向LN加入算法時(shí):

(1)LNnew通過同一PN的其他搜索樹節(jié)點(diǎn)獲得自己所在搜索樹的根LN節(jié)點(diǎn)。若該P(yáng)N沒有其他的LN時(shí),則向根服務(wù)器查詢根LN。

(2)LNnew向根節(jié)點(diǎn)LN發(fā)送新LN消息。

(3)從根節(jié)點(diǎn)開始,依照空余度路由轉(zhuǎn)發(fā)LN加入消息,直到到達(dá)路由出口指向自身的節(jié)點(diǎn)LNi,即完成搜索。

(4)LN將LNi作為LNnew的父節(jié)點(diǎn),并通知該當(dāng)前節(jié)點(diǎn)和LNnew,二者隨后更新自己的空余度路由表。

LNnew向其所屬的搜索樹的根節(jié)點(diǎn)LN1發(fā)出加入請(qǐng)求,根節(jié)點(diǎn)沿著空余度路由進(jìn)行搜索,直到找到出u指向自己的邏輯節(jié)點(diǎn)LN9。

LNnew接入搜索樹,成為LN9的子節(jié)點(diǎn),則LN9更新其空余度路由,并向父節(jié)點(diǎn)LN2發(fā)出更新消息,以此類推,LN2和根節(jié)點(diǎn)LNI均更新空余度路由,LNnew加入過程完畢。

偽碼如下:

Root.OnNEWLN(KEY, IP)

Node=Root;

while(node.Inroute.Ext!=node.IP){

node=GetRemoteLN(node.Inroute.Ext);}

LNi=node;

LNi.children[LNi.lnroute.children_count] =LNnew.IP;

LNnew.father=LNi.IP;}

采用空余度路由的理由是盡可能將新加入的節(jié)點(diǎn)往靠近根LN的地方放置,并且盡可能將各LN的子節(jié)點(diǎn)排滿,避免在搜索樹的各個(gè)LN間廣播空余度查詢消息時(shí),造成對(duì)搜索樹的大面積遍歷,浪費(fèi)網(wǎng)絡(luò)資源。

參考文獻(xiàn):

1.詹春華,陳曉蘇.對(duì)等網(wǎng)絡(luò)搜索方法比較與分析.湖北工學(xué)院學(xué)報(bào),2004.

2.陳志琦,蘇德富.基于P2P技術(shù)的Gnutella網(wǎng)絡(luò)搜索路由機(jī)制的改進(jìn).計(jì)算機(jī)工程與設(shè)計(jì),2005.

3.周晉,路海明,盧增祥,李衍達(dá).基于部分匹配方式的可擴(kuò)展P2P搜索算法.清華大學(xué)學(xué)報(bào):自然科學(xué)版,2004,44(10).

作者單位:山東安丘市第三中學(xué)