基于Ｐ２Ｐ的數字圖書館分布式搜索關鍵技術

摘要：在對現流行的互操作協議的發展和特征進行比較分析的基礎上，介紹了基于P2P搜索方法的特點及分類。最后在原有OAI－PMH框架的基礎上，提出一種基于P2P技術的數字圖書館分布式搜索模型 (P2P－DL) ，并對系統實現的關鍵技術進行了分析與設計。

關鍵詞：數字圖書館； 對等點； 分布式搜索； OAI－PMH

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

文章編號：1001－3695(2008)04－1240－03

數字圖書館是將多種媒體形態的大量文獻信息以規范的數字方式存儲在計算機中，并將信息的存儲、管理、檢索、發布和產權保護等綜合技術集成在一起，利用現代網絡技術，實現跨地區、跨國家的多個數字圖書館的連接，使讀者能通過統一的界面，在任何地點、任何時間實現自己的信息需求。數字圖書館追求的最終目標是實現聯邦檢索，即將全球的數字化資源連為一體，實現館中數字資源和信息的共享，為用戶提供統一、高效的檢索服務[1]。

數字圖書館的檢索服務實際是一種分布式搜索[2]，它首先要解決系統間的互操作問題，然而現有的數字圖書館分別屬于不同的機構，使用不同格式的元數據，這也構成了形成聯邦數字圖書館的最大障礙。為了克服這一困難，出現了各種數字圖書館之間互操作的方案[3]。然而在分布式環境和用戶數量激增的情況下，原有的互操作方案表現出了各種各樣的局限性。因此本文解決問題的關鍵就是在分布異構環境下的對原有的互操作方案進行擴展，并提出新的檢索方案。

1數字圖書館互操作協議

互操作的目的是跨越組織邊界，為不同的數字圖書館系統之間的客戶端和服務端提供交互。這需要不同的組織遵循一個共同的協議標準。其規范了分布式搜索時檢索信息的組織、訪問檢索服務的機制等。現在廣泛流行以下兩種標準協議[3]：

a)Z39.50協議。它是由圖書館界開發的用于信息搜索和檢索服務的標準協議，已被廣泛應用于不同的計算機系統之間的互操作。Z39．50是一個基于客戶機／服務器結構的網絡應用層協議，并且客戶機與服務器的交互是基于會話的。客戶機程序一旦與服務器建立連接，服務器便進行搜索并建立結果集。客戶機程序對結果集進行檢索，而不需要檢索整個數據庫。在整個會話過程中，客戶機和服務器需要記住各自交互的狀態。Z39．50除了各種檢索服務外，還具有索引瀏覽、訪問控制和資源管理等功能。

b)OAI協議。OAI－PMH(open archives initiative protocol for memdata harvesting)是1999年由美國數字圖書館聯盟、網絡信息聯盟等組織提出的一個應用框架。最初是為了解決電子期刊的預印本的互操作和元數據收割問題。2000年，OAI協議的應用擴展到數字圖書館領域，目的是實現分散的、不同系統平臺之間的元數據交換和共享，提高系統的互操作能力。

OAI為解決數字圖書館之間的互操作問題提出了一種簡單的互操作框架，如圖1所示。該框架區分兩種不同類型的參與者，即數據提供者(data providers，DP)和服務提供者(service providers，SP)。前者要求按照標準的元數據格式(dublin core)建立館藏元數據，后者利用OAI－PMH協議從數據提供者處獲取元數據以實現增值服務(如搜索、瀏覽等)。該結構的代表是Arc[4]，Arc是第一個采用OAI互操作框架實現的聯邦搜索服務，它能夠從遵守OAI協議標準的DLs館藏中提取元數據，經過處理后集中保存在一個關系型數據庫中。

Z39．50與OAI相比，功能比較完善，但是實現起來比較困難，所以通常只能實現其中一個子集。例如，用于對數字圖書館的數字對象進行搜索管理STARTS協議就只實現了Z39．50協議的一個子集。而OAI的元數據采集方案不要求嚴格遵守一組完整的技術協定，只要求做少許支持基本共享服務(如數據訪問)的工作，對聯盟成員的要求很少，因此，許多組織可能會加入這種松散的DLs聯邦。檢索過程中，Z39．50是系統之間的分布式搜索，而OAI是檢索過程的集中式檢索(檢索服務提供者)。

總之，OAI作為一種新發展起來的互操作協議，相對Z39．50而言，吸納了更多新的思想和技術。而Z39．50作為重量級的互操作協議，其協議的復雜性，以及實現的困難性，對互操作的實現和發展帶來了瓶頸。所以OAI代表了互操作技術發展的方向和趨勢。但是由于OAI是集中式的搜索模式，在分布式環境下隨著加入的組織的增多，元數據發現、采集的效率會越來越低，如Arc系統，隨著數據提供者的增多，采集、索引和搜索均在同一個服務器上，它的效率就變得很低，它現在完成一次采集要用4天時間，而在索引中搜索要用約15 min，這對于用戶來說顯然是難以接受的[4]。因此需要新的技術支持OAI協議在分布式環境下的應用。

2基于P2P技術的數字圖書館分布式技術

2.1P2P技術的引入

P2P網絡是一種全新的分布式網絡， 在該網絡中所有主機處于同等地位。基于P2P的搜索方法與目前其他各類傳統搜索方法相比，其最大優勢在于應用了先進的對等搜索理念，網絡中節點之間的動態而又對等的互聯關系使得搜索可以在對等點之間直接地、實時地進行，既可以保證搜索的實時性，又可以達到傳統目錄式搜索引擎無可比擬的深度。為此，本文提出將P2P技術與OAI技術相結合，在原有的OAI－PMH框架之上引入P2P的概念，使OAI原有的集中式搜索適應分布式環境下的搜索，更好地解決了數字圖書館之間資源發現、跨倉儲檢索等問題，實現整個社會范圍內的聯邦數字圖書館。

2．2基于 P2P的分布式搜索技術

根據搜索與資源內容的相關性將基于P2P的搜索技術分為結構化搜索和非結構化搜索[5]。結構化搜索根據資源的內容來存放和定位資源，這類搜索方法通常采用分布式哈希表DHT[6]將整個搜索空間對應到一個散列空間，當一個節點要搜索該資源時，對該資源的惟一標志使用相同的散列函數進行散列得到散列值，通過有效的局部路由，找到負責該資源的節點。但在這類系統中，用戶必須明確知道所搜索資源的惟一標志才能進行散列和找到該資源，且尚未完全支持多個關鍵詞的搜索。

非結構化的搜索方法是目前應用最廣的P2P網絡搜索方法且完全支持多關鍵詞的搜索，它通常采用寬度優先算法（BFS）向所有的鄰居節點發送查找消息，Gnutella是這種算法的代表[7]，但是這種算法的問題是網絡負載過大，為此，筆者采用改進網絡拓撲的方法改進傳統非結構化P2P網絡的搜索性能，引入超級節點super－peer。

如圖2所示，在使用super－peer[8]的系統中，存在一些特殊節點，這些節點各自作為一部分節點的中央服務器，稱做super－peer。各個super－peer也相互連接，構成一個P2P網絡。對于資源的查詢，每一個客戶對等體在某一時刻僅與一個super－peer連接，客戶對等體向其發送自己的資源索引，也向其發出查詢。super－peer在收到查詢后既要根據本地緩存處理，也會在super－peer間傳播查詢。發起查詢傳播的super－peer在收到其他super－peer的回應后，會將這些回應連同本地查詢結果返回給客戶對等體。

這類系統不再依賴惟一的中央服務器，從而解決了中央索引模型中可伸縮性不強、容錯性不夠的問題;另一方面由super－peer來各自負責一部分節點資源的搜索、索引的維護，從而避免了泛洪請求模型中消息泛濫的情形，使搜索效率明顯增強。

3基于P2P技術的數字圖書館分布式搜索框架

由以上分析可知，基于OAI的互操作技術是集中式的搜索模式，已經不能滿足分布式環境下的性能要求，而P2P技術在分布式搜索領域有著獨特的優勢。為此，本文提出一種新的數字圖書館分布式搜索結構模型——P2P－DL， 使OAI原有的集中式搜索適應分布式環境下的搜索，更好地解決了數字圖書館之間的資源發現和檢索問題。

3.1P2P－DL結構模型

如圖3所示，本文提出一種基于super－peer拓撲結構的分層搜索結構模型，即數據資源層data provider、超級節點層SP。在本結構模型中，原OAI框架中的數據提供者對應super－peer結構中的葉子節點，服務提供者對應P2P網絡中的超級節點。具體包括以下核心功能：

a)數據資源層DP。該層由廣域分布的數字圖書館和用戶組成，構成整個P2P－DL的信息提供者，也可以向上層提出查詢請求。該層節點主要有三種服務：

（a） 注冊服務。特定信息的提供者必須在P2P搜索網絡中進行注冊之后，其提供的資源才會被搜索網絡中的SP節點采集。注冊信息包括提供的查詢空間以及對某一特定的查詢作出應答的條件以及提供給查詢者的服務連接端點地址信息，注冊信息被發送到超級對等體后，當有用戶需要瀏覽或下載所需信息，就會被路由到愿意作出應答的信息提供者，由它來作出相應的應答。

（b）查詢服務。查詢請求由用戶向與之相連的SP發出，它包含在規定格式的XML文檔中，當SP收到查詢請求消息時，它將在本地索引中進行匹配查找。在SP發現了足夠的查詢結果時(該數目可以由SP設定，也可由用戶設定)，就立即向用戶返回結果。如果不能發現足夠的查詢結果數目，本地超級對等點將根據具體的實現策略，在由超級對等體構成的網絡中轉發查詢，以嘗試獲得用戶所需要的結果數。

（c）數據傳輸服務。傳輸服務包括上傳和下載兩個部分。注冊成功后，DP就連接到一個特定的SP，并共享準備上傳的資源索引，接收SP的元數據采集。下載發生在用戶檢查返回的查詢結果，并決定需要使用的資源，然后該用戶可以直接同持有資源的用戶建立連接并使用資源，下載/上傳動作的執行均會引起用戶資源狀態的變化，此時用戶應向其本地SP發送資源更新信息。

b）超級節點層SP。超級對等體一般由網絡中擁有相對較大的帶寬，較強的計算能力，以及較大的存儲空間的對等體承擔，因此可以提供搜索網絡中更多的服務。在搜索網絡中，超級對等體起到與其他普通對等體之間交流通信的紐帶作用，通過與其他的超級對等體的連接，將整個搜索網絡擴展到更廣闊的區域。

（a）查詢路由服務。該服務管理由查詢發起者發送到搜索網絡中的查詢請求信息，并將其路由到滿足查詢條件的搜索服務器，隨后收集返回的查詢響應消息，并將結果返回給查詢發起對等體。

（b）查詢解析服務。解析由數據提供者發送來的注冊消息，并將查詢請求消息與注冊消息進行匹配，以此提供高效率的路由匹配信息。

3．2各種服務之間的關系

各種服務之間的關系如圖4所示，運行在超級對等點上的路由服務將收到由查詢服務傳來的查詢消息并轉發出去，并且將搜索網絡中返回的查詢響應消息合并在一起返回給查詢發起節點。注冊服務發送注冊信息到運行的超級對等點上，對等點上的解析服務解析注冊消息成路由服務可以利用的索引結構。用戶獲得查詢結果后可以利用傳輸服務瀏覽或下載所需資源。



4P2P－DL關鍵技術及其實現策略

根據P2P－DL結構模型，筆者利用JXTA[9]平臺搭建了系統的實驗環境，希望利用實驗驗證系統的可行性，在此過程中，發現了系統實現的幾個關鍵問題。

4．1應用程序層次結構

設計的搜索引擎的層次結構如圖5所示，處于最底層的是各個參與的數據提供者。JXTA核心層處于其上層，需要實現的有JXTA的六個協議，該層奠定了創建對等點、創立對等組、對等點的監控、標志對等點、發布資源廣告、保證安全性等功能的基礎。位于JXTA核心層之上的是服務層，提供了信息查詢服務、查詢提供者服務、資源注冊服務、查詢信息路由服務、查詢信息解析服務等P2P－DL必需的服務。處于最上層的是P2P搜索引擎應用程序界面，提供了用戶與P2P搜索引擎交換的用戶圖形界面。



4．2JXTA核心層實現

JXTA核心層是對等搜索網絡實現的基礎，是搜索網絡對等點的解析、查找，實現相互之間通信的端點路由服務，以及通過管道之間通信等功能得以實現的基礎。對等網絡中的所有對等點，包括普通對等點和超級對等點，均應該首先實現JXTA六個標準協議，即集合點協議(RVP)、端點路由協議(ERP)、對等機解析協議(PRP)、對等機信息協議(PIP)、管道綁定協議(PBP)和對等機發現協議(PDP)。

4．3查詢消息轉發優化

通常的P2P搜索系統在進行消息轉發時，往往對查詢消息接收者不加區別，要么向全部相鄰節點發出查詢，要么隨機選擇部分相鄰節點發出查詢；對消息的傳播，一般以最大地滿足用戶需要的查詢結果數為目標，進行經常性的大范圍深度搜索。而用戶進行搜索的使用習慣表明，對于產生的大量結果，只有較少部分被用戶瀏覽，因此僅在用戶真正需要大量結果時才擴大搜索范圍的處理方法，將產生既符合查詢要求又降低總體查詢代價的效果。這里，擬使用以下兩種查詢優化技術：

a) 迭代深入[10，11]。這是一種逐步進行深度搜索的方法。在實現中，每一次搜索比上一次搜索擴大一層搜索范圍，已經執行過搜索的super－peer僅轉發查詢消息和結果消息，只有在最大深度處的super－peer才實際執行搜索。采用這種方法，要求查詢的初始發起者在需要更多結果時，多次發出同一查詢，并調整每一次查詢的要求結果數。

b) 分布式資源定位協議(DRLP)[12]。該算法將查詢請求以一定的概率發送到各個鄰居節點(屬于盲目搜索階段)。如果得到某個查詢結果，那么結果會在返回路徑的每個節點上記錄目標數據的位置，在以后的查詢中，這些節點可以直接與請求節點聯系，通告目標數據的位置。

4．4Super－peer間資源索引復制機制

當super－peer僅保存自己本地客戶對等體的資源索引時，為了獲得足夠數量的查詢結果，super－peer只能進行查詢轉發，這使得查詢轉發的次數偏多、網絡負載加重。因此如果部分復制客戶資源索引，則搜索可以直接在本地進行，從而能夠減少查詢轉發的次數，并加快搜索的處理速度。部分復制是指每一個super－peer除了保存自己本地客戶的資源索引外，還保存了部分遠程客戶的資源索引。在恰當的時候，super－peer間可以通過某種方式相互發送自己本地客戶的資源索引，并且被復制的索引能夠以合理的方式保存和刪除。實現中，利用從其他super－peer返回的查詢結果消息，將消息中那些本super－peer尚未擁有的索引保存下來，間接地完成了資源索引復制。

5結束語

搜索性能是數字圖書館最重要的性能指標，現有數字圖書館已經開發出了許多在互操作協議方案之上的分布式搜索方法，取得了一些成果，但這些方法在實現Internet上大規模的數字圖書館分布式搜索方面有一定的局限性。本文采用P2P的搜索理念來構建搜索網絡，在原有OAI－PMH框架的基礎上構建數字圖書館分布式搜索框架模型P2P－DL，而設計中采用的JXTA是一個P2P網絡應用開發的統一平臺，徹底獨立于操作系統和程序設計語言，真正實現了跨平臺，使得基于JXTA的P2P系統的擴展性、兼容性大為提高。利用P2P技術改進OAI中集中式檢索為分布式搜索，順應了搜索引擎技術的分布化發展趨勢，實現了數字圖書館信息資源共享和跨倉儲無縫查找。

參考文獻：

［1］LU Jie ，CALLAN， JAMIE . Federated search oftext－based digital libraries in hierarchical peer－to－peer networks: Lecture Notes in Computer Science， v 3408[C]//Proc of the 27th European Conference on IR Research. 2005: 52－66.

[2］BENDEY M B， MICHEL S M，ZIMMER C，et al.Challenges of distributed search across digital libraries[C]//Proc ofDELOS workshop:System Architecture Information Access.2005: 14－26.

[3］張付志，孔令富. 幾種典型的數字圖書館互操作協議分析比較 [J].情報學報， 2003，22(4): 476－481.

[4］MALY K， ZUBAIR M， LI Xue－mei.A high performance implementation of an OAI－based federation service[C]//Proc of the 11th International Conference on Parallel and Distributed Systems Workshops－ ICPADS. 2005: 769－774.

[5］馮國富，毛鶯池，陸桑璐，等.PeerRank:一種無結構P2P資源發現策略[J]. 軟件學報，2006，17(5): 1098－1106.

[6］ZEINALIPOUR－YAZTI D， KALOGERAKI V， GUNOPULOS D. Information retrieval techniques for peer－to－peer networks[J].Computing in Science and Engineering，2004，6(4)：20－26.

[7］TSOUMAKOS D， ROUSSOPOULOS N. A comparison of peer－to－peer search methods[C]//Proc of International Workshop on the Web and Databases (WebDB). San Diego， California:[s.n.]，2003.

[8］LEIBOWITZ N， RIPEANU M， WIERZBICKI A.Deconstructing the kazza Network[C]//Proc of the3rd IEEE Workshop on Internet Applications(WIAPP’03).2003: 23－24.

[9］SANNA A， ZUNINO C， CIMINIERA L. A distributed JXTA－based architecture for searching and retrieving solar data[J].Future Generation Computer Systems，Special Issues:P2P Computing and Interaction with Grids，2005，21(3): 349－359.

[10］LV C， CAO P， COHEN E，et al. Search and replication in unstrunctured peer－to－peer networks[C]//Proc ofICS. 2002.

[11］YANG B， GARCIA－MOLINA H. Improving search in peer－to－peer networks[C]//Proc ofInternational Conference on Distributed Computing Systems.2002: 5-14.

[12］MENASC’E D， KANCHANAPALLI L. Probabilistic scalable p2p resource location services[J]. ACM Sigmetrics Perfor mance Evaluation Rev， 2002，30(2)：48－58.

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