P數(shù)據(jù)管理系統(tǒng)課件

第九章P2P數(shù)據(jù)管理系統(tǒng)第九章P2P數(shù)據(jù)管理系統(tǒng)主要內(nèi)容P2P系統(tǒng)概述P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)中的數(shù)據(jù)管理資源的定位和路由處理語義異構查詢處理與優(yōu)化主要內(nèi)容P2P系統(tǒng)概述 P2P模型(Peer-to-Peer模型，即對等計算模型)是一種新型的網(wǎng)絡服務體系結(jié)構，是一種通過直接交換的方式來共享計算機資源和服務的互聯(lián)網(wǎng)應用模式。P2P系統(tǒng)具有很多的優(yōu)勢： 第一，P2P系統(tǒng)中的每一個成員具有平等的地位，可同時充當提供者和消費者兩種角色。提供者可以向消費者提供共享的數(shù)據(jù)和計算資源(存儲空間或者是空閑的CPU時間)； 第二，P2P系統(tǒng)具有很好的擴展性。系統(tǒng)成員可以動態(tài)地加入和退出P2P系統(tǒng)，增加了系統(tǒng)的靈活性以及內(nèi)容的豐富性； 第三，在P2P系統(tǒng)中，數(shù)據(jù)是分散存儲的，克服了傳統(tǒng)集中式數(shù)據(jù)存放方法所帶來的性能瓶頸、單點失效等問題，提高了系統(tǒng)的效率，也增加了系統(tǒng)的可用性和可靠性?；靖拍?P2P模型(Peer-to-Peer模型，即對等計算模型) 目前，基于P2P技術的應用是互聯(lián)網(wǎng)上最為活躍的一個部分。統(tǒng)計數(shù)據(jù)表明，P2P應用所產(chǎn)生的網(wǎng)絡流量已經(jīng)占據(jù)了約75%的互聯(lián)網(wǎng)總通信量?；赑2P技術的搜索引擎、文件共享機制、網(wǎng)絡視頻音頻分發(fā)機制為全球用戶提供了更多的資源、更高的帶寬以及更好的服務質(zhì)量。 下面介紹幾個常用的基于P2P技術的互聯(lián)網(wǎng)服務：數(shù)據(jù)共享服務數(shù)據(jù)搜索及查詢服務分布式協(xié)同計算服務數(shù)據(jù)存儲服務流媒體傳輸服務基本概念 目前，基于P2P技術的應用是互聯(lián)網(wǎng)上最為活躍的一個部分。統(tǒng)數(shù)據(jù)共享服務 早期出現(xiàn)的提供此類服務的系統(tǒng)有Napster和Gnutella，現(xiàn)在比較流行的是eMule和BitTorrent。使用者通過運行提供此類服務的軟件加入數(shù)據(jù)共享網(wǎng)絡，然后就可以直接從網(wǎng)絡中已有的其它節(jié)點上下載感興趣文件。與此同時，自己也可以為其它節(jié)點提供下載服務。整個系統(tǒng)中，數(shù)據(jù)被分布地存儲在所有成員節(jié)點上，服務也由全部節(jié)點共同來擔當。需要特別指出的是，雖然數(shù)據(jù)不是集中存儲，但數(shù)據(jù)的目錄信息可能集中存儲，這有利于提高資源的定位效率。數(shù)據(jù)搜索及查詢服務 提供此類服務的系統(tǒng)有Infrasearch、Pointera等等，主要用來在P2P網(wǎng)絡中完成信息檢索。基于P2P網(wǎng)絡的數(shù)據(jù)搜索與基于互聯(lián)網(wǎng)中心服務器的數(shù)據(jù)搜索截然不同，必須要考慮P2P網(wǎng)絡拓撲結(jié)構的動態(tài)性以及節(jié)點的異構性，不同節(jié)點所使用的軟硬件平臺以及數(shù)據(jù)語義也不一定相同?；靖拍顢?shù)據(jù)共享服務基本概念分布式協(xié)同計算服務 如尋找外星人計劃SETI＠HOME。參加者把個人計算機上的空閑CPU時間貢獻出來，去協(xié)同分析和計算來自于位于波多黎各的阿雷西博（Arecibo）射電望遠鏡觀測到的數(shù)據(jù)，從而篩選出可能是地外生物發(fā)出的信號。相類似的項目還有尋找最大質(zhì)數(shù)項目GIMPS和Google的共同搜索項目Folding＠home。需要強調(diào)的是，在這些分布式協(xié)同計算應用中，都采用了一個集中式事務管理器來協(xié)調(diào)節(jié)點的行為，包括任務的分派、同步和結(jié)果匯總。數(shù)據(jù)存儲服務 如Microsoft公司的Farsite和加州大學的OceanStore等軟件。數(shù)據(jù)在P2P網(wǎng)絡上的分散化存放可以減輕服務器負擔，增加數(shù)據(jù)的可靠性和分發(fā)速度。流媒體傳輸服務 主要包括PPLive、CoolStreaming等軟件所提供的視頻音頻文件分發(fā)服務，以及OICQ軟件所提供的即時通信與文件傳輸服務、多人參與的計算機對弈游戲等?；靖拍罘植际絽f(xié)同計算服務基本概念 為了解決數(shù)據(jù)放置和檢索所帶來的巨大挑戰(zhàn)，Gribble等人提出將數(shù)據(jù)庫技術與P2P技術相結(jié)合，其中最重要的是在P2P系統(tǒng)中引入了數(shù)據(jù)模式的概念，出現(xiàn)了基于數(shù)據(jù)模式的P2P數(shù)據(jù)管理系統(tǒng)。有力地解決了不同節(jié)點之間的語義異構問題，提高了數(shù)據(jù)存儲和查詢的效率，并且能夠支持復雜查詢。 總結(jié)來看，基于模式的P2P數(shù)據(jù)管理系統(tǒng)與分布式數(shù)據(jù)庫之間會有很多的相似或相異點： (1)從網(wǎng)絡拓撲結(jié)構上來看，分布式數(shù)據(jù)庫中的節(jié)點相對穩(wěn)定，通常以受控的方式加入或退出網(wǎng)絡；而在P2P系統(tǒng)中，對等節(jié)點即興地加入或離開網(wǎng)絡,網(wǎng)絡拓撲結(jié)構具有很強的動態(tài)性，每個節(jié)點的邏輯位置也可能改變；基本概念 為了解決數(shù)據(jù)放置和檢索所帶來的巨大挑戰(zhàn)，Gribble等 (2)從數(shù)據(jù)的分布性來看，分布式數(shù)據(jù)庫和P2P系統(tǒng)都是將數(shù)據(jù)分布地存儲到地理上分散的節(jié)點上，但是在分布式數(shù)據(jù)庫系統(tǒng)中，全部數(shù)據(jù)首先是一個整體，有一個全部節(jié)點公認的全局模式，全局數(shù)據(jù)經(jīng)過分片和分配被映射到了各個場地上存儲起來，是一個全局與局部之間的映射關系，而且分布存儲的數(shù)據(jù)之間依然要嚴格保證數(shù)據(jù)的一致性；而在P2P系統(tǒng)中，沒有全局數(shù)據(jù)的概念，也不強制要求數(shù)據(jù)必須保持一致性； (3)從查詢處理上來看，在分布式數(shù)據(jù)庫中，存在一個全局的查詢處理器，負責全局查詢的分解和變換，同時還負責事務在不同節(jié)點上執(zhí)行的協(xié)調(diào)工作，由于網(wǎng)絡拓撲相對穩(wěn)定，因此基于分布式數(shù)據(jù)庫的查詢操作可以檢索到所有滿足查詢條件的元組；在P2P系統(tǒng)中，不存在協(xié)調(diào)全局的超級節(jié)點，查詢從發(fā)起場地沿著某一路徑轉(zhuǎn)發(fā)，逐步定位查詢結(jié)果。由于網(wǎng)絡結(jié)構不穩(wěn)定，因此通常不能檢索到全部的滿足查詢條件的結(jié)果。查詢結(jié)果的正確性和完整性極大地依賴于瞬間網(wǎng)絡狀態(tài)和語義映射。

基本概念 (2)從數(shù)據(jù)的分布性來看，分布式數(shù)據(jù)庫和P2P系統(tǒng)都P2P系統(tǒng)的體系結(jié)構

P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。集中式P2P網(wǎng)絡

在集中式P2P網(wǎng)絡中，維護著一個全局的目錄服務器，它負責記錄節(jié)點的共享信息并回答對于這些信息的查詢請求。提供者節(jié)點把共享信息發(fā)布到目錄服務器上，消費者節(jié)點首先在目錄服務器上查找所需資源的準確節(jié)點位置，然后連接節(jié)點完成數(shù)據(jù)交換。 集中式P2P網(wǎng)絡與傳統(tǒng)的client/server模式下的集中式系統(tǒng)雖然有相似之處（都維護著一個中心服務器）但兩者有著本質(zhì)的區(qū)別：傳統(tǒng)的集中式系統(tǒng)的中心服務器不僅保存資源的目錄信息，更為關鍵的是保存全部的共享資源，客戶端只能連接中心服務器并下載所需要的數(shù)據(jù)；而集中式P2P網(wǎng)絡的中心服務器只保留共享信息的目錄，所有共享信息依然保存在局部節(jié)點上。消費者節(jié)點在中心服務器上查找到資源提供者節(jié)點后，完成節(jié)點之間的連接，并進行數(shù)據(jù)交換。P2P系統(tǒng)的體系結(jié)構 P2P系統(tǒng)的體系結(jié)構分為三種：集中P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。集中式P2P網(wǎng)絡

第一代P2P網(wǎng)絡均采用集中式結(jié)構，其中典型的代表是Napster。Napster是一種可以在網(wǎng)絡中下載自己想要的MP3音樂文件的軟件。安裝了Napster系統(tǒng)的機器將成為一臺服務器，可為其它用戶提供音樂下載服務。Napster系統(tǒng)本身并不存儲和提供MP3文件下載，它實際上提供的是整個網(wǎng)絡中包含的MP3音樂文件“目錄”，即MP3音樂文件的地址，這個目錄存放在一個集中的服務器上，而MP3音樂文件本身則分布在網(wǎng)絡中的每一臺機器上。使用者在目錄服務器上找到想要的MP3音樂文件的位置，然后到指定的位置完成下載。2002年，Napster由于違反了知識產(chǎn)權保護法而被迫關閉。

P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。(2)全分布的P2P網(wǎng)絡

集中式P2P網(wǎng)絡雖然有利于內(nèi)容查找，但位于系統(tǒng)中心的目錄服務器依然是整個系統(tǒng)的瓶頸，而且依然存在著單點失效、負載不均衡、目錄更新代價大等問題。 第二代P2P網(wǎng)絡則完全向全分布式方向發(fā)展，這也為內(nèi)容的存儲和查詢提出了挑戰(zhàn)。根據(jù)內(nèi)容的組織方法來劃分，有兩種形式的全分布式P2P網(wǎng)絡：結(jié)構化全分布式P2P網(wǎng)絡非結(jié)構化全分布式P2P網(wǎng)絡P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。(2)全分布的P2P網(wǎng)絡

結(jié)構化全分布式P2P網(wǎng)絡是一種維護節(jié)點之間在應用層上互聯(lián)的組織方法。它按照一定的邏輯拓撲結(jié)構將系統(tǒng)中的節(jié)點互連起來，內(nèi)容的存放也相對有序，通過路由消息實現(xiàn)系統(tǒng)中任意兩個節(jié)點的互通。結(jié)構化的P2P網(wǎng)絡比較適合于拓撲結(jié)構相對固定的應用環(huán)境。通常使用分布式哈希表(DHT)來實現(xiàn)文件到節(jié)點的映射。目前已有的結(jié)構化全分布式P2P網(wǎng)絡有Pastry、Tapestry、Chord和CAN等。P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。(2)全分布的P2P網(wǎng)絡

結(jié)構化全分布式P2P網(wǎng)絡是一種維護節(jié)點之間在應用層上互聯(lián)的組織方法。它按照一定的邏輯拓撲結(jié)構將系統(tǒng)中的節(jié)點互連起來，內(nèi)容的存放也相對有序，通過路由消息實現(xiàn)系統(tǒng)中任意兩個節(jié)點的互通。結(jié)構化的P2P網(wǎng)絡比較適合于拓撲結(jié)構相對固定的應用環(huán)境。通常使用分布式哈希表(DHT)來實現(xiàn)文件到節(jié)點的映射。目前已有的結(jié)構化全分布式P2P網(wǎng)絡有Pastry、Tapestry、Chord和CAN等。P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。(2)全分布的P2P網(wǎng)絡

在非結(jié)構化全分布式P2P網(wǎng)絡中，節(jié)點通過一些松散的規(guī)則組織在一起，文件也是隨機存放的。非結(jié)構化P2P網(wǎng)絡擴展性和容錯性較好，但是它采用應用層的廣播協(xié)議，消息量過大，網(wǎng)絡負擔過重，節(jié)點無法得知整個網(wǎng)絡的拓撲結(jié)構或組成網(wǎng)絡的其它對等節(jié)點的信息。新節(jié)點加入網(wǎng)絡時，系統(tǒng)必須向這個對等節(jié)點提供一個對等節(jié)點的列表，但P2P網(wǎng)絡的強動態(tài)性，即節(jié)點可隨時加入和退出，限制了這個對等節(jié)點列表的有效性。 Gnutella是應用最為廣泛的非結(jié)構化P2P網(wǎng)絡。它沒有所謂的中心索引服務器，不需要在目錄服務器上注冊共享信息。當對等節(jié)點進行查詢的時候，查詢請求通過flooding方式廣播發(fā)送給直接相連的鄰居，并由近及遠依次轉(zhuǎn)發(fā)直到收到響應，或者達到了最大的泛洪步數(shù)。P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分布式和混合式。(3)混合型的P2P網(wǎng)絡在混合型的P2P網(wǎng)絡中，節(jié)點以簇的形式組織，某些具有較高性能(如計算能力、存儲容量和通信帶寬)的節(jié)點被選擇擔當簇頭節(jié)點，簇內(nèi)節(jié)點把共享信息的目錄發(fā)布到簇頭節(jié)點上，簇頭節(jié)點負責進行搜索和查詢處理。普通節(jié)點加入網(wǎng)絡后，可以選擇多個簇頭節(jié)點作為它的父親節(jié)點，得到簇頭節(jié)點的允許后，該節(jié)點加入簇頭節(jié)點所領導的域，并把自己共享資源的目錄發(fā)布到簇頭節(jié)點上。簇頭節(jié)點向查詢提供匹配的資源所在的地址，而不是資源本身。如果在本領域不能找到與查詢匹配的資源，查詢將被轉(zhuǎn)發(fā)給其它的簇頭節(jié)點。P2P系統(tǒng)的體系結(jié)構P2P系統(tǒng)的體系結(jié)構分為三種：集中式、分P2P系統(tǒng)中的數(shù)據(jù)管理

核心問題包括：數(shù)據(jù)的存儲策略、索引的構造策略、語義異構性的調(diào)整策略和查詢傳播與查詢處理策略。P2P數(shù)據(jù)管理的性能指標有：可擴展性：即允許節(jié)點自由地加入和離開網(wǎng)絡，查詢處理的性能不能過分依賴網(wǎng)絡規(guī)模，不能因為網(wǎng)絡規(guī)模擴大而顯著下降；自治性：P2P節(jié)點在系統(tǒng)結(jié)構、軟件與功能配置，通信方式上均有很強的自治性，查詢處理算法應當充分尊重節(jié)點的自治性；健壯性：對故障的健壯性和對攻擊的健壯性，在面臨節(jié)點故障、離開、攻擊時，系統(tǒng)應該保持可用性、保持一定的服務質(zhì)量和效率；支持語義異構：peer節(jié)點各自使用自己的數(shù)據(jù)模式來表達和組織數(shù)據(jù)。為了節(jié)點之間的數(shù)據(jù)交換，需要解決語義異構問題。查詢處理能力：P2P網(wǎng)絡中的查詢處理涉及到數(shù)據(jù)存儲、語義異構、索引組織、查詢請求分發(fā)和結(jié)果匯聚等方面。查詢的準確性、查全性、響應時間和通信量是表現(xiàn)P2P系統(tǒng)查詢處理能力的重要指標。P2P系統(tǒng)中的數(shù)據(jù)管理 核心問題包括：數(shù)據(jù)的存儲策略、索引的資源的定位和路由

在P2P網(wǎng)絡中進行信息檢索，第一步是要進行資源定位。目前主要有兩種P2P資源定位策略：面向非結(jié)構化P2P網(wǎng)絡的資源定位方法；面向結(jié)構化P2P網(wǎng)絡的資源定位方法；資源的定位和路由 在P2P網(wǎng)絡中進行信息檢索，第一步是要進資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法 在非結(jié)構化P2P網(wǎng)絡中，節(jié)點沒有相對固定的邏輯地址，采用隨機的方法或者啟發(fā)式的方法加入網(wǎng)絡，網(wǎng)絡拓撲隨著節(jié)點的變遷隨時發(fā)生演變。泛洪（Flooding）搜索算法k遍歷隨機游走算法(k-walkerrandomwalk)基于移動代理(MobileAgent)的搜索算法

資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法 泛洪（Flooding）搜索算法

泛洪算法在搜索時向所有的鄰居節(jié)點轉(zhuǎn)發(fā)查詢消息，因此又叫寬度優(yōu)先搜索。在網(wǎng)絡中，一個節(jié)點向所有鄰居節(jié)點廣播查詢消息，鄰居節(jié)點再向自己的鄰居節(jié)點廣播，這個過程不斷進行下去，像洪水在網(wǎng)絡中各個節(jié)點流動一樣，所以叫做Flooding搜索。搜索的節(jié)點預先設定消息生命周期TTL(Time-to-live)并賦以初值。查詢在節(jié)點間每傳播一次TTL減1，如果TTL減到0，則丟棄查詢。如果搜索到資源則返回目標機器的信息用來建立連接。

泛洪算法的特點：路由算法比較簡單，易于實現(xiàn)。缺點是查詢消息數(shù)量大，耗費大量通信帶寬。

資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法

k遍歷隨機游走算法(k-walkerrandomwalk)

k遍歷隨機游走算法是盲目搜索算法中采用漫游策略的典范。它進一步加強了對節(jié)點路由消息的擴散程度的控制。該算法中，請求者發(fā)出K個查詢請求給隨機挑選的K個相鄰節(jié)點。然后每個查詢信息在以后的漫游過程中直接與請求者保持聯(lián)系，詢問查詢結(jié)果的有效性并判斷是否還要繼續(xù)漫游。如果請求者同意繼續(xù)漫游，則又開始隨機選擇下一個轉(zhuǎn)發(fā)節(jié)點，否則終止搜索。 k遍歷隨機游走算法的特點：提高了查詢信息的傳播速度，減少了路由消息量，一定意義上實現(xiàn)了節(jié)點的負載均衡。但是，查詢結(jié)果的準確性非常依賴于隨機漫步的路徑，因此結(jié)果準確性不穩(wěn)定。資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法

基于移動代理(MobileAgent)的搜索算法

移動代理技術非常適合在網(wǎng)絡環(huán)境中完成信息檢索的任務。代理是一個能在異構網(wǎng)絡中自主遷移的服務程序，它可與其他代理和資源進行交互。源節(jié)點發(fā)送一個包含了查詢信息的代理給它的鄰居節(jié)點，當這個代理到達一臺新的機器上后，就在這臺機器上進行資源搜索。如果這臺機器上沒有它想要的資源，則它自主向下一個鄰居節(jié)點遷移，如果找到資源，則將結(jié)果或者包含結(jié)果的節(jié)點IP返回給源節(jié)點。 優(yōu)點：具有很好的用戶個性化管理能力，支持離線查詢，支持更加智能的代理遷移機制，從而獲得更好的查詢效率； 缺點：代理的運行增加了節(jié)點的負載，而且會帶來安全性、隱私保護等多方面問題。資源的定位和路由面向非結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法

結(jié)構化P2P網(wǎng)絡是指像Chord、Tapestry、CAN之類的點對點的網(wǎng)絡。在結(jié)構化P2P網(wǎng)絡中，每個節(jié)點都有固定的地址，整個網(wǎng)絡具有相對穩(wěn)定和規(guī)則的拓撲結(jié)構。依賴拓撲結(jié)構，可以給網(wǎng)絡的每一個節(jié)點指定一個邏輯地址，并把地址和節(jié)點的位置對應起來。對于給定的某個地址，拓撲結(jié)構保證只需要通過跳就能路由到相應地址的節(jié)點上去(n是網(wǎng)絡中的節(jié)點數(shù))。P2P網(wǎng)絡中節(jié)點的邏輯地址通常是由散列函數(shù)得到的，即每個節(jié)點都保存一張分布式散列表(DHT，DistributedHashTable)進行路由。因此，結(jié)構化P2P網(wǎng)絡也叫作DHT網(wǎng)絡。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法

在DHT網(wǎng)絡中，主機稱為節(jié)點，共享資源稱為對象。節(jié)點擁有名字，并且一個節(jié)點可以在多個興趣維度下?lián)碛卸鄠€名字。對于一個節(jié)點來說，最為典型的名字就是它的IP地址。系統(tǒng)擁有一個標識符空間，它是一個整數(shù)域，每個標識符就是一個來自該整數(shù)域的唯一整數(shù)。散列函數(shù)將節(jié)點的名字轉(zhuǎn)換為節(jié)點的標識符，節(jié)點的標識符相當于節(jié)點的虛擬地址(VID)，例如VID=hash(IP)。同時，共享資源也有自己的對象名。散列函數(shù)將對象名轉(zhuǎn)換為對象的關鍵字(KEY)，即kEY=hash(ObjectName)。在DHTP2P網(wǎng)絡中，散列值相鄰的節(jié)點定義為鄰居節(jié)點。系統(tǒng)中的每個節(jié)點都擁有一部分散列空間，它負責保存某個范圍的對象關鍵字。共享資源被發(fā)布到具有和KEY相近虛擬地址的節(jié)點上去。資源定位的時候，就可以快速根據(jù)KEY到相近的節(jié)點上獲取二元組（KEY,VID），從而獲得文檔的實際存儲位置。目前典型的DHT網(wǎng)絡有Chord、Tapestry、CAN等，它們的主要區(qū)別在于采用了不同的DHT路由算法，因此它們具有不同的邏輯拓撲結(jié)構。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(1)chord協(xié)議

Chord是一個環(huán)形拓撲結(jié)構，Chord協(xié)議使用的散列函數(shù)是SHA-1。在Chord中，每個節(jié)點Ni有2個鄰居：以順時針為正方向排列在Ni之前的第1個節(jié)點稱為Ni的前繼(predecessor)，在Ni之后的第1個節(jié)點稱為Ni的后繼(successor)。資源存放于其關鍵字為KEY的后繼節(jié)點上。為了路由的需要，節(jié)點保存前繼和后繼信息，并維護一張最多m項的路由表，稱為查詢表，m稱為查詢表級數(shù)。其中，第k項(k為查詢表數(shù)組的下標)保存鍵值(Node_VID+2k-1)mod2m的后繼節(jié)點VID。由此可見，表中節(jié)點之間的間距以2k-1的關系排列，這實際上是折半查找算法需要的排列關系。網(wǎng)絡的最大容量為n=2m個節(jié)點。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(1)chord協(xié)議

Node7Node15Node22Node33Node39Node48Node42Node51Node63+1+2+4+8+16+32例：m=6，具有9個節(jié)點的Chord網(wǎng)絡中的資源存儲定位Node33節(jié)點的查詢表(FigureTable)kNode_VID+2k-1(Node_VID+2k-1)mod2m的后繼節(jié)點VID133+1Node39233+2Node39333+4Node39433+8Node42533+16Node51633+32Node7資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法Node7資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(1)chord協(xié)議Node15Node7Node15Node22Node33Node39Node48Node42Node51Node63①：由Node_VID+2k-1=33+16=48最接近54，得第一跳找到Node51節(jié)點；②：在Node51節(jié)點上，由于Node_VID+2k-1=51+2=53，可找到Node63節(jié)點；③：在Node63上找到Key=54的共享資源，Node63給Node33發(fā)出回饋；從node33節(jié)點發(fā)起的查詢鍵值為54的共享資源的搜索過程：資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法Node1資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(2)PastryPastry從邏輯上是一個網(wǎng)狀的拓撲。Pastry中沒有規(guī)定具體應該采用的散列函數(shù)，但是定義了一個128bit的整數(shù)空間作為鍵值的域。每個節(jié)點擁有一個128bit的邏輯地址(Node_VID)。為了保證Node_VID的唯一性，一般由節(jié)點的IP地址通過散列計算獲得。Node_VID在域內(nèi)均勻分布，因此邏輯地址相鄰的節(jié)點地理位置不同的概率很大。節(jié)點的邏輯地址和關鍵字均表示為一串以2b為基的數(shù)。Pastry把消息路由到節(jié)點邏輯地址最接近關鍵字的節(jié)點上。每個節(jié)點都維護一個路由表(RoutingTable)、一個鄰居節(jié)點集合(NeighborSet)和一個葉子節(jié)點集合(LeafSet)，三者共同構成了節(jié)點的狀態(tài)表。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(2)Pastry

Pastry路由的具體過程是：當收到一條搜索請求時，節(jié)點首先檢查共享資源的關鍵字是否落在葉子節(jié)點集合中。如果是，則直接把消息轉(zhuǎn)發(fā)給對應的節(jié)點，也就是葉子節(jié)點集合中邏輯地址和關鍵字最接近的節(jié)點。如果關鍵字沒有落在葉子節(jié)點集合中，那么就將使用路由表進行路由。當前節(jié)點會把消息發(fā)送給節(jié)點號和關鍵字直接的共同前綴至少比現(xiàn)在節(jié)點長一個數(shù)位的節(jié)點。當然，會出現(xiàn)路由表對應表項為空或路由表表項對應的節(jié)點不可達的情況。此時，路由消息將會被轉(zhuǎn)發(fā)給共同前綴一樣長的節(jié)點，但是該節(jié)點和當前節(jié)點相比，其節(jié)點邏輯地址在數(shù)值上將更接近關鍵字。這樣的節(jié)點一定位于葉子結(jié)點集合中。因此，只要葉子節(jié)點集合中不會出現(xiàn)一半以上的節(jié)點同時失效，路由過程就可以繼續(xù)。從上述過程中可以看出，路由的每一步和上一步相比都向目標節(jié)點前進了一步，因此這個過程是收斂的。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由邏輯地址值<10233200邏輯地址值>1023320010233133102331211023320310233213102331101023310310233221102332300-221210212-23012033-120320301-1-3012331-2-2302031-3-02102210-0-3120310-1-32102210-3-23302102-0-0230102-1-1302102-2-230231023-0-3221023-1-0001023-2-121310233-0-0110233-1-0020102332-2-00面向結(jié)構化P2P網(wǎng)絡的資源定位方法(2)Pastry1302102210200230113012333130123302232120223012033120320333213321Node_VID:10233200Key:10233102LeafSetRoutingTableNeighborSet例：在Pastry網(wǎng)絡中節(jié)點10233102的路由表信息。b取值為2，即所有的數(shù)均是4進制數(shù)。其中路由表的最上面一行是第0行。路由表中每行的陰影項表示當前節(jié)點邏輯地址對應的位。路由表中每項表示為“和10233102的共同前綴--下一數(shù)位--節(jié)點邏輯地址的剩余位”。資源的定位和路由邏輯地址值<10233200邏輯地址值資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(3)CAN(內(nèi)容尋址網(wǎng)絡，Content-AddressableNetwork)CAN基于虛擬的d維笛卡兒坐標空間來實現(xiàn)其數(shù)據(jù)組織和查找，因此CAN中的散列函數(shù)的結(jié)果是一個d維笛卡兒空間，其中d是根據(jù)系統(tǒng)規(guī)模大小而確定的常量。整個P2P網(wǎng)絡被映射成為一個d維的笛卡兒空間，節(jié)點的邏輯地址是由散列函數(shù)計算出的一個d維的向量。因此，每個節(jié)點都對應于d維笛卡兒空間中的一點。整個坐標空間動態(tài)地分配給系統(tǒng)中的所有節(jié)點，每個節(jié)點都擁有獨立的互不相交的一塊區(qū)域。共享資源也經(jīng)散列函數(shù)對應于d維笛卡兒空間中的一點，這樣共享資源就找到了它相應的存儲位置。每一個CAN網(wǎng)絡中的節(jié)點都維護著一個相鄰節(jié)點表。相鄰節(jié)點的定義是，在d維笛卡兒坐標空間中，如果兩個節(jié)點的坐標在其中的d-1維上均相等，在剩余的1維上坐標值相鄰，則這樣的兩個節(jié)點成為相鄰節(jié)點。因此，d維空間中的節(jié)點共有2d個鄰居節(jié)點。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法(3)CAN(內(nèi)容尋址網(wǎng)絡，Content-AddressableNetwork)B5N1B4N4N2N5B3N6N3B2N9N8N7B1例：在2維CAN網(wǎng)絡中進行資源查找的過程：查詢從N2節(jié)點發(fā)起，資源的關鍵字是(a,b)，假設0≤a≤A1，0≤b≤B1。N2節(jié)點負責存儲的關鍵字區(qū)間是(A3~A4,B3~B4)。N2首先判斷(a,b)是否屬于(A3~A4,B3~B4)：如果屬于，說明待查找的資源在本地；否則，則可沿著A維或者B維向包含(a,b)的關鍵字區(qū)間轉(zhuǎn)發(fā)查詢請求，直到找到N9節(jié)點，查找完成。資源的定位和路由面向結(jié)構化P2P網(wǎng)絡的資源定位方法B5N1B處理語義異構性 在P2P網(wǎng)絡中，peer節(jié)點之間是松散耦合的，每個節(jié)點都具有充分的自治性，具體體現(xiàn)在：每個節(jié)點可以自由地加入和退出網(wǎng)絡；加入網(wǎng)絡的節(jié)點可以具有不同的組件結(jié)構，可以使用不同的操作系統(tǒng)和數(shù)據(jù)管理系統(tǒng)。peer節(jié)點的自治性使得不同的數(shù)據(jù)源具有多層次的語義異構性：模式級異構：數(shù)據(jù)在關系名、屬性名、屬性的值域、屬性之間的依賴關系、以及屬性到值域的映射方面不同。數(shù)據(jù)級異構：現(xiàn)實世界的相同實體使用不同的表示形式。處理語義異構性 在P2P網(wǎng)絡中，peer節(jié)點之間是松散耦合的處理語義異構性 當前，解決語義異構的主要方法是在peer間建立模式或者數(shù)據(jù)映射，其中存在著巨大的局限性：多數(shù)映射就是簡單的相等或者包含關系，某些研究提出使用更為復雜的映射，如合取、析取等，但這些映射關系尚不能處理大數(shù)據(jù)源的情況；無論是查詢發(fā)生前預先確定語義映射關系，還是在查詢提出后根據(jù)關鍵字匹配確定映射關系，都不能依據(jù)查詢來解