P2P網(wǎng)絡(luò)搜索技術(shù)

1、本章主要內(nèi)容一、什么是網(wǎng)絡(luò)搜索三、P2P網(wǎng)絡(luò)搜索的分類四、集中式P2P網(wǎng)絡(luò)搜索五、分布式P2P網(wǎng)絡(luò)搜索六、混合式P2P網(wǎng)絡(luò)搜索二、P2P網(wǎng)絡(luò)搜索的評價體系Web 搜索與P2P搜索搜索網(wǎng)頁建立索引數(shù)據(jù)庫在索引數(shù)據(jù)庫中搜索排序P2P搜索發(fā)現(xiàn)P2P網(wǎng)絡(luò)中的活躍點(diǎn)與資源與Web搜索不同與P2P網(wǎng)絡(luò)體系（拓?fù)洌┙Y(jié)構(gòu)緊密相關(guān)P2P搜索評價體系P2P網(wǎng)絡(luò)拓?fù)浞诸怭2P網(wǎng)絡(luò)拓?fù)浞植际椒墙Y(jié)構(gòu)化分布式非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)拓?fù)浞植际浇Y(jié)構(gòu)化分布式結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)拓?fù)浼惺郊惺絇2P網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)拓?fù)浠旌鲜降幕旌鲜降腜2P網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)拓?fù)?.完全集中式完全集中式研究目標(biāo)及重點(diǎn)是應(yīng)用模式從C/S模式向?qū)Φ饶?/p>

2、式的轉(zhuǎn)變優(yōu)點(diǎn)：應(yīng)用模式消除了應(yīng)用服務(wù)器的瓶頸問題并緩解了應(yīng)用流量的不均衡性，在目錄服務(wù)器獲取資源索引信息之后的所有數(shù)據(jù)的交換都是在節(jié)點(diǎn)間完成的。簡單易部署?？梢阅：樵?。缺點(diǎn)：單點(diǎn)失效。盡管可以用并行服務(wù)器解決。拓?fù)浣Y(jié)構(gòu)：非結(jié)構(gòu)化、集中式。典型代表：Napster2、非集中式、非結(jié)構(gòu)化、非集中式、非結(jié)構(gòu)化研究目標(biāo)和重點(diǎn)是去除體系結(jié)構(gòu)上的單點(diǎn)失效問題。對象查詢是分布式的。查詢是逐跳的，泛洪式直到成功或失敗或超時。優(yōu)點(diǎn)：自組織的管理模式使得整個系統(tǒng)的魯棒性得以大幅度增強(qiáng)。可以模糊查詢。缺點(diǎn)：消息傳遞（泛洪、回溯等）的資源定位模式制約了網(wǎng)絡(luò)規(guī)模的可縮放性。查詢效率低。典型代表：Gnutella、Fr

3、eenet、KaZaA拓?fù)浣Y(jié)構(gòu)：非結(jié)構(gòu)化、非集中式、無規(guī)則分布式拓?fù)浣Y(jié)構(gòu)示例e.g. NapsterHybrid P2PdirectoryPure P2Pe.g. Freenet & GnutellaContent Delivery NetworksServerDuplicated Servere.g. Akami3、非集中式且結(jié)構(gòu)化、非集中式且結(jié)構(gòu)化需要解決的問題則是如何增強(qiáng)網(wǎng)絡(luò)規(guī)模的可縮放特性。對象查詢也是分布式的。使用DHT技術(shù)構(gòu)造結(jié)構(gòu)化拓?fù)?。對象的查詢也是逐跳的?zhí)行，經(jīng)過確定的步跳可以確信是成功的。拓?fù)浣Y(jié)構(gòu)：非集中式、結(jié)構(gòu)化。 如：mesh、ring、d-dimension t

4、orus and butterfly。典型P2P網(wǎng)絡(luò)如：CAN、Chord、Oceanstore等。優(yōu)點(diǎn)：在資源管理過程中同時擁有自組織特性、規(guī)模的強(qiáng)可縮放特性以及部署的廉價性等等。為規(guī)模龐大的資源整合及共享提供了可能性。缺點(diǎn)：節(jié)點(diǎn)僅存在局部視圖。缺少權(quán)威第三方的控制。不支持模糊查詢。集中式P2P搜索在集中式P2P網(wǎng)絡(luò)中，節(jié)點(diǎn)以集中式的目錄服務(wù)器為中介，從而發(fā)現(xiàn)對方，集中式的目錄服務(wù)器上，存儲著此網(wǎng)絡(luò)中所有的節(jié)點(diǎn)信息，但不存儲資源。集中目錄模式最流行，Napster使用群組的Peers連接到發(fā)布其能提供共享內(nèi)容的中心目錄上，匹配請求與索引文件直接交換在兩個Peers間進(jìn)行需要一些可管理的設(shè)施（

5、目錄服務(wù)器：記載群組所有參加者的信息）限制了規(guī)模的擴(kuò)大：大量用戶增加大量請求-大服務(wù)器-存儲器然Napster經(jīng)驗(yàn)表明,除開法律問題外,該模式還很有效和強(qiáng)大IndexIndex1 12 23 35 54 4搜索搜索下載下載Napster運(yùn)行原理Napster是眾所周知的音樂交換系統(tǒng)。每個節(jié)點(diǎn)登錄到服務(wù)器上并發(fā)送它們的文件清單，發(fā)布查詢到服務(wù)器上查找哪些節(jié)點(diǎn)是它們擁有的想要的文件，并直接與目標(biāo)節(jié)點(diǎn)連接下載文件。支持模糊匹配Napster原理I have X!Publishinsert(X, ).Napster原理Where is file A?QueryReplyse

6、arch(A)-Fetch分布式結(jié)構(gòu)化P2P搜索結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，每個節(jié)點(diǎn)都有固定的地址，整個網(wǎng)絡(luò)具有相對穩(wěn)定而規(guī)則的拓?fù)浣Y(jié)構(gòu)。依賴拓?fù)浣Y(jié)構(gòu)可以給網(wǎng)絡(luò)的每個節(jié)點(diǎn)指定一個邏輯地址，并把地址和節(jié)點(diǎn)的位置對應(yīng)起來。Pastry網(wǎng)絡(luò)網(wǎng)絡(luò)CAN網(wǎng)絡(luò)網(wǎng)絡(luò)Chord網(wǎng)絡(luò)網(wǎng)絡(luò)Tapestry網(wǎng)絡(luò)網(wǎng)絡(luò)一種機(jī)制，四種網(wǎng)絡(luò)文檔路由模型(Document Routing Model) 這種文件路由模型需要用分布式哈希表(Distributed Hash Tables, DHT) ,這是有結(jié)構(gòu)對等網(wǎng)絡(luò)采用的搜索方法, 也是有結(jié)構(gòu)和無結(jié)構(gòu)對等網(wǎng)絡(luò)的根本區(qū)別。是確定性的算法。在這種模型下,每個

7、對等體都有一個ID,每個文件有一個關(guān)鍵字Key,當(dāng)宣告一個關(guān)鍵字為K1的文件時,先通過哈希映射得到對應(yīng)的K1 ID1 ,然后將該文件存到ID號為ID1 的節(jié)點(diǎn),文件的存放過程需要將文件路由到該節(jié)點(diǎn)ID1。反過來,當(dāng)查找一個關(guān)鍵字為K1 的文件時,先進(jìn)行哈希映射得到K1 ID1 ,然后將該文件從ID號為ID1 的節(jié)點(diǎn)上取到該文件,從該網(wǎng)絡(luò)中取文件需要將請求消息路由到ID1 節(jié)點(diǎn),然后文件從ID1 節(jié)點(diǎn)原路返回。Distributed Hash Table分布式分布式Hash表表分布式應(yīng)用分布式應(yīng)用get (key)datanodenodenode.put(key, data)查找服務(wù)查找服務(wù)lo

8、okup(key)node IP address(文件共享文件共享)(DHash)(Chord)結(jié)構(gòu)化重疊路由加入：開始時，聯(lián)系一個“bootstrap”節(jié)點(diǎn)，加入分布式數(shù)據(jù)結(jié)構(gòu)，獲得一個節(jié)點(diǎn)id發(fā)布：向數(shù)據(jù)結(jié)構(gòu)中最近的節(jié)點(diǎn)發(fā)布文件id的路由信息搜索：向路由表中最近的節(jié)點(diǎn)查詢文件id，數(shù)據(jù)結(jié)構(gòu)保證查詢會找到發(fā)布節(jié)點(diǎn)獲?。簝蓚€選項(xiàng)查詢到的節(jié)點(diǎn)保存有文件，則從查詢結(jié)束的節(jié)點(diǎn)獲取查詢到的節(jié)點(diǎn)返回結(jié)果：節(jié)點(diǎn)x有文件，則從節(jié)點(diǎn)x獲取DHT示例Chord:在一維空間（環(huán)）中給每個節(jié)點(diǎn)和文件一個唯一的id例如從0.2m中選取通常是文件和IP地址的hash四大結(jié)構(gòu)化模型2001年，SIGCOMM（網(wǎng)絡(luò)通信頂尖

9、會議）- Chord: Ion Stoica等（Berkeley、MIT）- CAN: Ratnasamy等（Berkeley、AT&T）2001年，其它兩個模型- Pastry: Rowstron等（微軟、Rice）- Tapestry: 趙燕斌等（Berkeley）4個算法實(shí)現(xiàn)文件路由Chord/CAN/Tapestry/Pastry目標(biāo)相同減少路由到指定文件的P2P跳數(shù)減少每個Peer必須保持的路由狀態(tài)算法異同都保證算法的跳數(shù)與Peer群組的大小相關(guān)或都指出算法能以高概率完成方法上的差別很小Chord每個Peer保持LogN其他Peer的蹤跡(N是群組的全部Peer數(shù))當(dāng)Peer

10、加入或離開時,高優(yōu)化算法版本僅需關(guān)注LogN個Peers的變化CAN每個Peer保持少于LogN個其他Peers的蹤跡在插入和刪除時僅這些Peers受影響其路由表較小,但到達(dá)的路徑較長可能更適合動態(tài)通信Tapestry與Pastry很相似除減少跳數(shù)外,還積極削減每個P2P跳上的時延Chord 原理實(shí)現(xiàn)了這樣一種操作：給定一個關(guān)鍵字（key），將key映射到某個節(jié)點(diǎn)。如果給對等網(wǎng)絡(luò)應(yīng)用的每個數(shù)據(jù)都分配一個key，那么對等網(wǎng)絡(luò)中的數(shù)據(jù)查詢問題可以用Chord解決。Chord采用了相容哈希的一種變體為節(jié)點(diǎn)分配關(guān)鍵字。相容哈希特點(diǎn)：哈希函數(shù)可以做到負(fù)載平衡（所有的節(jié)點(diǎn)可以接收到基本相同數(shù)量的關(guān)鍵字）當(dāng)

11、第N個節(jié)點(diǎn)加入或者離開網(wǎng)絡(luò)時，只有1/N 的關(guān)鍵字需要移動到另外的位置。Chord 對相容哈希進(jìn)行改善：每個節(jié)點(diǎn)值需要知道關(guān)于其他節(jié)點(diǎn)的少量路由信息。在由N個節(jié)點(diǎn)組成的網(wǎng)絡(luò)中，每個節(jié)點(diǎn)只需要維護(hù)其它O（logN）個節(jié)點(diǎn)的信息，同樣每次查找只需要O（logN）條消息。當(dāng)節(jié)點(diǎn)加入或離開網(wǎng)絡(luò)時，Chord需要更新路由信息，每次加入或離開需要傳遞O（log2N）條消息。當(dāng)節(jié)點(diǎn)n加入網(wǎng)絡(luò)時，為了保持相容哈希映射，某些原來分配給n的后繼結(jié)點(diǎn)的關(guān)鍵字將分配給n。當(dāng)節(jié)點(diǎn)n離開網(wǎng)絡(luò)時，所有分配給他的關(guān)鍵字重新分配給n的后繼節(jié)點(diǎn)。具體實(shí)現(xiàn)：利用相容哈希函數(shù)，為每個節(jié)點(diǎn)和關(guān)鍵字分配m位的標(biāo)識符。此標(biāo)識符可用SHA-

12、1（安全哈希算法）等哈希函數(shù)產(chǎn)生。節(jié)點(diǎn)的標(biāo)識符通過哈希節(jié)點(diǎn)的IP地址產(chǎn)生，關(guān)鍵字的標(biāo)識符通過哈希此關(guān)鍵字產(chǎn)生。例如：IP： 通過SHA-1哈希后的標(biāo)識符為123，關(guān)鍵字LetItBe哈希后的關(guān)鍵字為60。標(biāo)識符長度m必須足夠長，這樣才能保證兩個節(jié)點(diǎn)或者關(guān)鍵字哈希到同一個標(biāo)識符上的概率小到可以忽略不計(jì)。相容哈希中，每個關(guān)鍵字都保存到他的后繼節(jié)點(diǎn)（節(jié)點(diǎn)標(biāo)識符大于等于關(guān)鍵字k標(biāo)識符的第一個節(jié)點(diǎn)）中。我們將其記為successor（k）。Chord：逐跳查找N32N90N105N60N10N120K80“Where is key 80?”“N90 has K80”結(jié)點(diǎn)維護(hù)一個有m

13、（ID位數(shù)）項(xiàng)的路由表，也稱“指向表”（finger table），其中第i項(xiàng)指向結(jié)點(diǎn)s，s=successor(n+2i-1)，1im，即s是在順時針方向到n的距離至少為2i-1的第一個結(jié)點(diǎn)，記做n.fingeri.nodeChord路由表的特點(diǎn)：每個結(jié)點(diǎn)只保存很少的其它結(jié)點(diǎn)信息，并且對離它越遠(yuǎn)的結(jié)點(diǎn)所知越少Chord結(jié)點(diǎn)不能從自己的路由表中看出對象k的后繼為確定對象k的后繼（k所在的結(jié)點(diǎn)）,結(jié)點(diǎn)n在自己的路由表中查找在k之前且離k最近的結(jié)點(diǎn)j，讓j去找離k最近的結(jié)點(diǎn)，遞歸查找，最終可以找到對象k的前驅(qū)（在k之前離k最近的結(jié)點(diǎn)，記做predecessor(k)，類似，結(jié)點(diǎn)n的前驅(qū)記做n.pr

14、edecessor）前驅(qū)中必然有后繼的路由表項(xiàng)，定位成功Chord結(jié)點(diǎn)n的路由各項(xiàng)屬性及其定義屬性定義fingerk.start(n+2k-1)mod2m, 1ervalfingerk.start, fingerk+1.start).noden.fingerk.start的第一個結(jié)點(diǎn)successor后繼結(jié)點(diǎn)，即finger1.nodepredecessor前驅(qū)結(jié)點(diǎn)假設(shè)結(jié)點(diǎn)3要找到對象1的后繼在結(jié)點(diǎn)3的路由表中，1屬于3.erval即7,3)結(jié)點(diǎn)3讓3.finger3.node即結(jié)點(diǎn)0去找1結(jié)點(diǎn)0在路由表中發(fā)現(xiàn)自己的后繼1恰好是對象1的后繼，因此將1返回給結(jié)點(diǎn)

15、3結(jié)點(diǎn)3由此知道對象1放在結(jié)點(diǎn)1中Chord：插入N32N90N105K80K20K5Circular ID spaceKey 5Node 105Chord結(jié)點(diǎn)加入算法Chord的自適應(yīng)需要保持兩個不變的屬性每個結(jié)點(diǎn)的后繼始終正確對每個對象k，結(jié)點(diǎn)successor(k)始終負(fù)責(zé)k的索引為此，新結(jié)點(diǎn)n的加入需要完成幾個任務(wù)初始化n的前驅(qū)和路由表項(xiàng)更新網(wǎng)絡(luò)其他結(jié)點(diǎn)的前驅(qū)和路由表項(xiàng)告訴其后繼將應(yīng)該由n負(fù)責(zé)的數(shù)據(jù)對象索引傳遞給n新結(jié)點(diǎn)n連接到某個眾所周知結(jié)點(diǎn)n，通過調(diào)用join(n)初始化自己的狀態(tài)信息，并將自己加入到Chord網(wǎng)絡(luò)節(jié)點(diǎn)失效當(dāng)節(jié)點(diǎn)n失效時，所有在指針表中包括n的節(jié)點(diǎn)都把n替換成n的后

16、繼結(jié)點(diǎn)。為了便于維護(hù)正確的后繼指針，每個節(jié)點(diǎn)都維護(hù)一張包括r個最近后繼的后繼列表，如果節(jié)點(diǎn)n的后繼節(jié)點(diǎn)失效了，就從后繼列表中第一個正常節(jié)點(diǎn)替換失效節(jié)點(diǎn)。Content-Addressable NetworkCAN內(nèi)容尋址網(wǎng)絡(luò)可以在Internet規(guī)模的大型對等網(wǎng)絡(luò)上提供類似哈希表的功能，CAN 的設(shè)計(jì)是完全分布式的，不需要任何形式的中央控制點(diǎn)。CAN 具有很好的可擴(kuò)展性，結(jié)點(diǎn)只需要維護(hù)少量的控制狀態(tài)而且狀態(tài)數(shù)量與系統(tǒng)中的結(jié)點(diǎn)數(shù)量無關(guān)；CAN 支持容錯特性，結(jié)點(diǎn)可以繞過錯誤結(jié)點(diǎn)進(jìn)行路由。CAN 基于虛擬的d 維笛卡兒坐標(biāo)空間實(shí)現(xiàn)其數(shù)據(jù)的組織和查找功能，它將整個坐標(biāo)空間動態(tài)地分配給系統(tǒng)中的所有結(jié)點(diǎn)

17、，每個結(jié)點(diǎn)都擁有獨(dú)立的互不相交的一塊區(qū)域?？梢园颜麄€CAN 系統(tǒng)看成一張保存（ key，value）對的大哈希表。CAN 的基本操作包括插入、查找和刪除（ key，value）對。其中key 是對被搜索資源的關(guān)鍵字（如文件名）哈希后的值，而value 則是資源的存儲位置（ 如IP 地址和目錄）。整個CAN 系統(tǒng)由許多獨(dú)立的結(jié)點(diǎn)組成，每個結(jié)點(diǎn)保存哈希表的一部分，稱之為一個區(qū)。此外，每個結(jié)點(diǎn)在鄰接表中還保存了少量鄰接區(qū)的信息。對指定關(guān)鍵字的插入（ 或者查找、刪除）請求被中間的CAN 結(jié)點(diǎn)路由到區(qū)里含有該關(guān)鍵字的CAN 結(jié)點(diǎn)。下圖給出了一個2 維的0，10，1的笛卡兒坐標(biāo)空間劃分成五個結(jié)點(diǎn)區(qū)域的情況

18、。從圖1 中可以看到，虛擬坐標(biāo)空間中的每個區(qū)被動態(tài)地分配給CAN 中的某個結(jié)點(diǎn)，如坐標(biāo)空間（0. 5 - 1，0. 0 - 0. 5）被分配給結(jié)點(diǎn)B。CAN 中的路由實(shí)際上就是穿過笛卡兒空間從源坐標(biāo)到目的坐標(biāo)的一條直線段路徑。在CAN 中，每個結(jié)點(diǎn)都維護(hù)一張坐標(biāo)路由表，此表用來存放該結(jié)點(diǎn)所有鄰居的IP 地址和虛擬坐標(biāo)區(qū)。在d 維坐標(biāo)空間中，如果兩個結(jié)點(diǎn)的坐標(biāo)在d - 1維上重疊而在另一維上相鄰接，則稱這兩個結(jié)點(diǎn)是鄰居關(guān)系。CAN 的路由機(jī)制 由此，不難看出，對于d 維的坐標(biāo)空間，每個結(jié)點(diǎn)有2d 個鄰居結(jié)點(diǎn)，因此每個結(jié)點(diǎn)的坐標(biāo)路由表會維護(hù)2d 個鄰居的IP 地址和坐標(biāo)信息。如2 維的坐標(biāo)空間，每

19、個結(jié)點(diǎn)有4個鄰居結(jié)點(diǎn)，因此每個結(jié)點(diǎn)將維護(hù)4 個鄰居結(jié)點(diǎn)的IP 地址和坐標(biāo)空間。因?yàn)槊織lCAN 消息都包含目的坐標(biāo)，結(jié)點(diǎn)在路由時會將該消息轉(zhuǎn)發(fā)給坐標(biāo)路由表中距目的坐標(biāo)最近的結(jié)點(diǎn)，直到目的坐標(biāo)。虛擬坐標(biāo)空間采用下面的方法來保存（key，value）對：當(dāng)要保存（K1，V1）時，首先通過統(tǒng)一的哈希函數(shù)把關(guān)鍵字K1映射成坐標(biāo)空間中的某個點(diǎn)P 的坐標(biāo)，相應(yīng)的（key，value）對即存放在點(diǎn)P 所在區(qū)的結(jié)點(diǎn)內(nèi)。當(dāng)需要查詢關(guān)鍵字K1 對應(yīng)的值時，任何結(jié)點(diǎn)都可以使用同樣的哈希函數(shù)找到K1 對應(yīng)的點(diǎn)P，并從點(diǎn)P 所在區(qū)的結(jié)點(diǎn)取出相應(yīng)的值。如果點(diǎn)P 所在區(qū)的結(jié)點(diǎn)不是發(fā)起查詢請求的結(jié)點(diǎn)或其鄰居，則CAN 負(fù)責(zé)將此

20、查詢請求路由到點(diǎn)P 所在區(qū)的結(jié)點(diǎn)。因此，在CAN 中，有效的路由機(jī)制是一個關(guān)鍵問題。圖2 給出了一個路由例子，虛線是點(diǎn)1 到點(diǎn)（x，y）的路由，圖2 中還標(biāo)明了在結(jié)點(diǎn)7 加入系統(tǒng)前結(jié)點(diǎn)1 的鄰居結(jié)點(diǎn)集為2，3，4，5。新結(jié)點(diǎn)的加入整個CAN 空間是由當(dāng)前系統(tǒng)里所有的結(jié)點(diǎn)來動態(tài)劃分的。每當(dāng)新的結(jié)點(diǎn)加入時，系統(tǒng)必須為它分配相應(yīng)的坐標(biāo)空間。一般的做法是：系統(tǒng)中某個現(xiàn)有的結(jié)點(diǎn)將自己的區(qū)域一分為二，自己保留一半，將另一半分配給新的結(jié)點(diǎn)。整個過程包括：1）新的結(jié)點(diǎn)必須找到一個在CAN 中已經(jīng)存在的結(jié)點(diǎn)；2）通過CAN 的路由機(jī)制，新結(jié)點(diǎn)必須找到一個區(qū)域?qū)⒁环指畹慕Y(jié)點(diǎn)；3）進(jìn)行區(qū)域劃分操作，并通知被分割區(qū)

21、域的鄰居有新的結(jié)點(diǎn)加入以便在鄰居的坐標(biāo)路由表中包含新的結(jié)點(diǎn)。在結(jié)點(diǎn)7 加入系統(tǒng)前結(jié)點(diǎn)1的鄰居結(jié)點(diǎn)集為2，3，4，5。首先結(jié)點(diǎn)7 找到要劃分區(qū)域的結(jié)點(diǎn)，即結(jié)點(diǎn)1；然后，結(jié)點(diǎn)1 將自己的區(qū)域一分為二，自己保留一半，并將另一半?yún)^(qū)域分配給結(jié)點(diǎn)7；區(qū)域重新分割后，結(jié)點(diǎn)1 的鄰居集變?yōu)?，3，4，7，結(jié)點(diǎn)7 的鄰居集為1，2，4，5。結(jié)點(diǎn)離開，恢復(fù)當(dāng)結(jié)點(diǎn)離開CAN 系統(tǒng)時，要保證空出的區(qū)能移交給剩下的結(jié)點(diǎn)。正常的過程是結(jié)點(diǎn)明確地將它的區(qū)和相關(guān)的（ key，value）數(shù)據(jù)庫移交給其中的一個鄰居。如果某個鄰居的區(qū)可以合并該區(qū)并產(chǎn)生單個有效的區(qū)，那么任務(wù)就完成了；如果不行，那么就將該區(qū)移交給區(qū)最小的鄰居結(jié)點(diǎn)，

22、該結(jié)點(diǎn)將暫時負(fù)責(zé)兩個區(qū)。正常情況下，結(jié)點(diǎn)周期性地發(fā)布更新消息給它的每個鄰居，更新消息中包含自己和鄰居的區(qū)坐標(biāo)列表。如果某個結(jié)點(diǎn)在給定時間內(nèi)未收到鄰居結(jié)點(diǎn)的更新消息，則說明該鄰居結(jié)點(diǎn)失效。一旦某個結(jié)點(diǎn)失效，則它的每個鄰居結(jié)點(diǎn)會分別初始化接管算法并啟動接管定時器，定時器的大小和該結(jié)點(diǎn)擁有的區(qū)大小成比例。當(dāng)定時器超時，每個鄰居結(jié)點(diǎn)向其他所有鄰居結(jié)點(diǎn)發(fā)送TAKEOVER 消息，消息中含有自己的區(qū)信息。每當(dāng)收到一條TAKEOVER 消息時，每個鄰居結(jié)點(diǎn)都會做同樣的操作：比較自己的區(qū)和消息中的區(qū)，當(dāng)消息中的區(qū)小于自己的區(qū)時，結(jié)點(diǎn)會取消自己的定時器，反之則回應(yīng)自己的TAKEOVER 消息。用這種方法，可以有

23、效地選擇區(qū)小的存活鄰居結(jié)點(diǎn)，由這個鄰居結(jié)點(diǎn)接管失效結(jié)點(diǎn)的區(qū)。Pastry 原理功能：Pastry網(wǎng)絡(luò)中每個節(jié)點(diǎn)都有一個唯一的節(jié)點(diǎn)號（nodeId）。當(dāng)給定一條消息和一個關(guān)鍵字時，Pastry節(jié)點(diǎn)將會把這條信息路由到當(dāng)前所有的Pastry節(jié)點(diǎn)中nodeId和關(guān)鍵字最接近的那個節(jié)點(diǎn)。路由過程的復(fù)雜度是O（logN），這里N是網(wǎng)絡(luò)中Pastry節(jié)點(diǎn)的總數(shù)。目標(biāo):Pastry考慮了網(wǎng)絡(luò)的位置信息，使消息傳遞的距離最短。距離采用類似于IP路由的hop數(shù)的標(biāo)量距離度量。 采用了啟發(fā)式的算法，可以使關(guān)鍵字首先路由到在節(jié)點(diǎn)空間中與消息產(chǎn)生的節(jié)點(diǎn)距離最近的包括查找關(guān)鍵字的節(jié)點(diǎn)。Pastry原理節(jié)點(diǎn)分配制度Pas

24、try系統(tǒng)中的每個節(jié)點(diǎn)都被分配一個128位的節(jié)點(diǎn)號。節(jié)點(diǎn)號用于在節(jié)點(diǎn)空間中標(biāo)識節(jié)點(diǎn)的位置。節(jié)點(diǎn)號是在節(jié)點(diǎn)加入系統(tǒng)時隨機(jī)分配的。分配策略是在節(jié)點(diǎn)空間中均勻分布。節(jié)點(diǎn)號的獲?。和ㄟ^計(jì)算節(jié)點(diǎn)公鑰或者IP地址的哈希函數(shù)值來獲得。為了進(jìn)行路由，把節(jié)點(diǎn)號和關(guān)鍵字表示為一串以2b 為基的數(shù)。Pastry把消息路由到節(jié)點(diǎn)號從數(shù)值上最接近關(guān)鍵字的節(jié)點(diǎn)。具體過程如下：l在每個路由步驟中，當(dāng)前節(jié)點(diǎn)將把消息路由給節(jié)點(diǎn)號和消息關(guān)鍵字的共同前綴長度至少比當(dāng)前值長一個數(shù)位（b個二進(jìn)制位）的節(jié)點(diǎn)。l如果不存在這樣的節(jié)點(diǎn)，消息將傳遞給前綴長度相同但是節(jié)點(diǎn)號更接近的關(guān)鍵字的節(jié)點(diǎn)。為了支持這樣的路由過程，每個節(jié)點(diǎn)必須維護(hù)一定的路由

25、狀態(tài)。Pastry的路由過程當(dāng)收到一條消息時，節(jié)點(diǎn)首先檢查消息的關(guān)鍵字是否落在葉子節(jié)點(diǎn)的集合中。 是，直接把消息轉(zhuǎn)發(fā)給對應(yīng)的節(jié)點(diǎn)，也就是說葉子節(jié)點(diǎn)的集合中節(jié)點(diǎn)號和關(guān)鍵字最接近的節(jié)點(diǎn)。 否，使用路由表進(jìn)行路由。當(dāng)前節(jié)點(diǎn)把消息發(fā)送給節(jié)點(diǎn)號和關(guān)鍵字直接的共同前綴至少比現(xiàn)在節(jié)點(diǎn)長一個數(shù)位的節(jié)點(diǎn)。如果路由表對應(yīng)表項(xiàng)為空，或者路由表對應(yīng)的節(jié)點(diǎn)不可達(dá)。這時消息會被轉(zhuǎn)發(fā)給共同前綴一樣長的某個節(jié)點(diǎn)。這個節(jié)點(diǎn)從數(shù)值上比當(dāng)前節(jié)點(diǎn)更接近關(guān)鍵字。Tapestry原理Tapestry是用于覆蓋網(wǎng)絡(luò)的定位和路由機(jī)制，它可以對消息進(jìn)行位置無關(guān)的路由，把消息傳遞到最近的存放所要求的對象拷貝的節(jié)點(diǎn)。特點(diǎn)：自我管理、容錯和靈活平衡

26、負(fù)載等特點(diǎn)。Tapestry是基于Plaxton提出的定位和路由機(jī)制進(jìn)行優(yōu)化的。表5-2基于哈希表的路由機(jī)制有無法解決的問題。經(jīng)過哈希后，節(jié)點(diǎn)的位置信息破壞了，來自同一個子網(wǎng)的站點(diǎn)很可能節(jié)點(diǎn)號相距甚遠(yuǎn)，這不利用查詢性能的優(yōu)化基于哈希表的系統(tǒng)不能利用應(yīng)用本身的信息，許多應(yīng)用（文件系統(tǒng)）的數(shù)據(jù)本身是按照層次結(jié)構(gòu)組織的，使用哈希函數(shù)后，層次信息丟失了TerraDir提出了一種面向?qū)哟谓Y(jié)構(gòu)的查詢機(jī)制。該機(jī)制通過緩存機(jī)制可以進(jìn)一步提高查詢性能。Chord每個Peer保持LogN其他Peer的蹤跡(N是群組的全部Peer數(shù))當(dāng)Peer加入或離開時,高優(yōu)化算法版本僅需關(guān)注LogN個Peers的變化CAN每個Peer保持少于LogN個其他Peers的蹤跡在插入和刪除時僅這些Peers受影響其路由表較小,但到達(dá)的路徑較長可能更適合動態(tài)通信Tapestry與Pastry很相似除減少跳數(shù)外,還積極削減每個P2P跳上的時延4個算法實(shí)