P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)
拓?fù)浣Y(jié)構(gòu)是指分布式系統(tǒng)中各個(gè)計(jì)算單元之間的物理或邏輯的互聯(lián)關(guān)系，結(jié)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)一直是確定系統(tǒng)類型的重要依據(jù)。目前互聯(lián)網(wǎng)絡(luò)中廣泛使用集中式、層次式等拓?fù)浣Y(jié)構(gòu)。Internet本身是世界上最大的非集中式的互聯(lián)網(wǎng)絡(luò)，但是九十年代所建立的一些網(wǎng)絡(luò)應(yīng)用系統(tǒng)卻是完全的集中式的系統(tǒng)，許多Web應(yīng)用都是運(yùn)行在集中式的服務(wù)器系統(tǒng)上。集中式拓?fù)浣Y(jié)構(gòu)系統(tǒng)目前面臨著過量存儲(chǔ)負(fù)載、DOS（Denial of Service，拒絕服務(wù)）攻擊，網(wǎng)絡(luò)帶寬限制等一些難以解決的問題。Peer-to-Peer (簡稱P2P) 系統(tǒng)主要采用非集中式的拓?fù)浣Y(jié)構(gòu)，一般來說不存在上述這些難題。根據(jù)結(jié)構(gòu)關(guān)系可以將P2P系統(tǒng)細(xì)分為四種拓?fù)湫问剑?/p>
-
中心化拓?fù)?/strong>（Centralized Topology）；
-
全分布式非結(jié)構(gòu)化拓?fù)?/strong>（Decentralized Unstructured Topology）；
-
全分布式結(jié)構(gòu)化拓?fù)?/strong>（Decentralized Structured Topology，也稱作DHT網(wǎng)絡(luò)）；
-
半分布式拓?fù)?/strong>（Partially Decentralized Topology）。
其中，中心化拓?fù)?/strong>最大的優(yōu)點(diǎn)是維護(hù)簡單，資源發(fā)現(xiàn)效率高。由于資源的發(fā)現(xiàn)依賴中心化的目錄系統(tǒng)，發(fā)現(xiàn)算法靈活高效并能夠?qū)崿F(xiàn)復(fù)雜查詢。最大的問題與傳統(tǒng)客戶機(jī)/服務(wù)器結(jié)構(gòu)類似，容易造成單點(diǎn)故障，訪問的“熱點(diǎn)”現(xiàn)象和版權(quán)糾紛等相關(guān)問題，這是第一代P2P網(wǎng)絡(luò)采用的結(jié)構(gòu)模式，經(jīng)典案例就是著名的MP3共享軟件Napster[1].
Napster是最早出現(xiàn)的P2P系統(tǒng)之一，并在短期內(nèi)迅速成長起來。它實(shí)質(zhì)上并非是純粹的P2P系統(tǒng)，而是通過一個(gè)中央索引服務(wù)器保存所有Napster用戶上傳的音樂文件索引和存放位置的信息。它的工作原理如圖1所示。當(dāng)某個(gè)用戶需要某個(gè)音樂文件時(shí)，首先連接到Napster中央索引服務(wù)器，在服務(wù)器上進(jìn)行檢索，服務(wù)器返回存有該文件的用戶信息，再由請求者直接連到文件的所有者傳輸文件。Napster首先實(shí)現(xiàn)了文件查詢與文件傳輸?shù)姆蛛x，有效地節(jié)省了中央服務(wù)器的帶寬消耗，減少了系統(tǒng)的文件傳輸延時(shí)。
圖1 Napster的拓?fù)浣Y(jié)構(gòu)
然而，這種對等網(wǎng)絡(luò)模型存在以下這些問題：
- 中央索引服務(wù)器的癱瘓容易導(dǎo)致整個(gè)網(wǎng)絡(luò)的崩潰，因此可靠性和安全性較低。
- 隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，對中央索引服務(wù)器進(jìn)行維護(hù)和更新的費(fèi)用將急劇增加，所需成本較高。
- 中央索引服務(wù)器的存在常引起版權(quán)問題上的糾紛，服務(wù)提供商容易被追究法律責(zé)任。
綜合上述優(yōu)缺點(diǎn)，對小型網(wǎng)絡(luò)而言，中心化拓?fù)?/strong>模型在管理和控制方面占一定優(yōu)勢。但鑒于其存在的上述缺陷，該模型并不適合大型網(wǎng)絡(luò)應(yīng)用。
全分布式非結(jié)構(gòu)化拓?fù)涞腜2P網(wǎng)絡(luò)是在重疊網(wǎng)絡(luò)（Overlay Network）(見標(biāo)注1)采用了隨機(jī)圖的組織方式，結(jié)點(diǎn)度數(shù)服從Power-law規(guī)律（冪次法則）[2]，從而能夠較快發(fā)現(xiàn)目的結(jié)點(diǎn)，面對網(wǎng)絡(luò)的動(dòng)態(tài)變化體現(xiàn)了較好的容錯(cuò)能力，因此具有較好的可用性。同時(shí)可以支持復(fù)雜查詢，如帶有規(guī)則表達(dá)式的多關(guān)鍵詞查詢，模糊查詢等，采用這種拓?fù)浣Y(jié)構(gòu)最典型的案例便是Gnutella（音譯：紐特拉）。準(zhǔn)確地說，Gnutella不是特指某一款軟件，而是指遵守Gnutella協(xié)議[3]的網(wǎng)絡(luò)以及客戶端軟件的統(tǒng)稱。目前基于Gnutella網(wǎng)絡(luò)的客戶端軟件非常多，著名的有Shareaza、LimeWire和BearShare等。
圖2Gnutella的拓?fù)浣Y(jié)構(gòu)和文件檢索方法
Gnutella和Napster最大的區(qū)別在于Gnutella是更加純粹的P2P系統(tǒng)，因?yàn)樗鼪]有中央索引服務(wù)器，每臺(tái)機(jī)器在Gnutella網(wǎng)絡(luò)中是真正的對等關(guān)系，既是客戶機(jī)同時(shí)又是服務(wù)器，所以被稱為對等機(jī)(Servent，Server+Client的組合)。在文件檢索方面，它與Napster也不相同。在Gnutella網(wǎng)絡(luò)的發(fā)展初期，它主要采用基于完全隨機(jī)圖的Flooding搜索算法。圖2 顯示了Flooding的工作流程：當(dāng)一臺(tái)計(jì)算機(jī)要下載一個(gè)文件，它首先以文件名或者關(guān)鍵字生成一個(gè)查詢，并把這個(gè)查詢發(fā)送給與它相連的所有計(jì)算機(jī)，這些計(jì)算機(jī)如果存在這個(gè)文件，則與查詢的機(jī)器建立連接，如果不存在這個(gè)文件，則繼續(xù)在自己相鄰的計(jì)算機(jī)之間轉(zhuǎn)發(fā)這個(gè)查詢，直到找到文件為止。為了控制搜索消息不至于永遠(yuǎn)這樣傳遞下去，一般通過TTL (Time To Live)的減值來控制查詢的深度。
但是，隨著聯(lián)網(wǎng)節(jié)點(diǎn)的不斷增多，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，通過這種Flooding方式定位對等點(diǎn)的方法將造成網(wǎng)絡(luò)流量急劇增加，從而導(dǎo)致網(wǎng)絡(luò)中部分低帶寬節(jié)點(diǎn)因網(wǎng)絡(luò)資源過載而失效。所以在初期的Gnutella網(wǎng)絡(luò)中，存在比較嚴(yán)重的分區(qū)，斷鏈現(xiàn)象。也就是說，一個(gè)查詢訪問只能在網(wǎng)絡(luò)的很小一部分進(jìn)行，因此網(wǎng)絡(luò)的可擴(kuò)展性不好。所以，后來許多研究人員在Flooding的基礎(chǔ)上作了許多改進(jìn)，例如采用Random work [4]、Dynamic Query[5]等方法。
由于非結(jié)構(gòu)化網(wǎng)絡(luò)將重疊網(wǎng)絡(luò)認(rèn)為是一個(gè)完全隨機(jī)圖，結(jié)點(diǎn)之間的鏈路沒有遵循某些預(yù)先定義的拓?fù)鋪順?gòu)建。這些系統(tǒng)一般不提供性能保證，但容錯(cuò)性好，支持復(fù)雜的查詢，并受結(jié)點(diǎn)頻繁加入和退出系統(tǒng)的影響小。但是查詢的結(jié)果可能不完全，查詢速度較慢，采用Flooding查詢的系統(tǒng)對網(wǎng)絡(luò)帶寬的消耗非常大，并由此帶來可擴(kuò)展性差等問題。
全分布式結(jié)構(gòu)化拓?fù)?/strong>的P2P網(wǎng)絡(luò)主要是采用分布式散列表（Distributed Hash Table, 簡寫成DHT）技術(shù)來組織網(wǎng)絡(luò)中的結(jié)點(diǎn)。DHT是一個(gè)由廣域范圍大量結(jié)點(diǎn)共同維護(hù)的巨大散列表。散列表被分割成不連續(xù)的塊，每個(gè)結(jié)點(diǎn)被分配給一個(gè)屬于自己的散列塊，并成為這個(gè)散列塊的管理者。通過加密散列函數(shù)，一個(gè)對象的名字或關(guān)鍵詞被映射為128位或160位的散列值。分布式散列表起源于SDDS（Scalable Distribute Data Structures）[6]研究，Gribble等實(shí)現(xiàn)了一個(gè)高度可擴(kuò)展，容錯(cuò)的SDDS集群。DHT類結(jié)構(gòu)能夠自適應(yīng)結(jié)點(diǎn)的動(dòng)態(tài)加入/退出，有著良好的可擴(kuò)展性、魯棒性、結(jié)點(diǎn)ID分配的均勻性和自組織能力。由于重疊網(wǎng)絡(luò)采用了確定性拓?fù)浣Y(jié)構(gòu)，DHT可以提供精確的發(fā)現(xiàn)。只要目的結(jié)點(diǎn)存在于網(wǎng)絡(luò)中DHT總能發(fā)現(xiàn)它，發(fā)現(xiàn)的準(zhǔn)確性得到了保證，最經(jīng)典的案例是Tapestry，Pastry，Chord和CAN。
Tapestry [7]提供了一個(gè)分布式容錯(cuò)查找和路由基礎(chǔ)平臺(tái)，在此平臺(tái)基礎(chǔ)之上，可以開發(fā)各種P2P應(yīng)用(OceanStore[8]即是此平臺(tái)上的一個(gè)應(yīng)用)。Tapestry的思想來源于Plaxton。在Plaxton中，結(jié)點(diǎn)使用自己所知道的鄰近結(jié)點(diǎn)表，按照目的ID來逐步傳遞消息。Tapestry基于Plaxton的思想，加入了容錯(cuò)機(jī)制，從而可適應(yīng)P2P的動(dòng)態(tài)變化的特點(diǎn)。OceanStore是以Tapestry為路由和查找基礎(chǔ)設(shè)施的P2P平臺(tái)。它是一個(gè)適合于全球數(shù)據(jù)存儲(chǔ)的P2P應(yīng)用系統(tǒng)。任何用戶均可以加入OceanStore系統(tǒng)，或者共享自己的存儲(chǔ)空間，或者使用該系統(tǒng)中的資源。通過使用復(fù)制和緩存技術(shù)，OceanStore可提高查找的效率。最近，Tapestry為適應(yīng)P2P網(wǎng)絡(luò)的動(dòng)態(tài)特性，作了很多改進(jìn)，增加了額外的機(jī)制實(shí)現(xiàn)了網(wǎng)絡(luò)的軟狀態(tài)（soft state），并提供了自組織、魯棒性、可擴(kuò)展性和動(dòng)態(tài)適應(yīng)性，當(dāng)網(wǎng)絡(luò)高負(fù)載且有失效結(jié)點(diǎn)時(shí)候性能有限降低，消除了對全局信息的依賴、根結(jié)點(diǎn)易失效和彈性差的問題。
Pastry 是微軟研究院提出的可擴(kuò)展的分布式對象定位和路由協(xié)議，可用于構(gòu)建大規(guī)模的P2P系統(tǒng)。如圖3 所示，在Pastry中，每個(gè)結(jié)點(diǎn)分配一個(gè)128位的結(jié)點(diǎn)標(biāo)識符號(nodeID) ，所有的結(jié)點(diǎn)標(biāo)識符形成了一個(gè)環(huán)形的nodeID空間，范圍從0到2128 - 1 ，結(jié)點(diǎn)加入系統(tǒng)時(shí)通過散列結(jié)點(diǎn)IP地址在128位nodeID空間中隨機(jī)分配。網(wǎng)絡(luò)結(jié)點(diǎn)的加入與退出，資源查詢的過程可以參考文獻(xiàn)[9]。
圖3Pastry的消息路由
Chord [10]項(xiàng)目誕生于美國的麻省理工學(xué)院。它的目標(biāo)是提供一個(gè)適合于P2P環(huán)境的分布式資源發(fā)現(xiàn)服務(wù)，它通過使用DHT技術(shù)使得發(fā)現(xiàn)指定對象只需要維護(hù)O(logN)長度的路由表。在DHT技術(shù)中，網(wǎng)絡(luò)結(jié)點(diǎn)按照一定的方式分配一個(gè)唯一結(jié)點(diǎn)標(biāo)識符(Node ID) ，資源對象通過散列運(yùn)算產(chǎn)生一個(gè)唯一的資源標(biāo)識符(Object ID) ，且該資源將存儲(chǔ)在結(jié)點(diǎn)ID與之相等或者相近的結(jié)點(diǎn)上。需要查找該資源時(shí)，采用同樣的方法可定位到存儲(chǔ)該資源的結(jié)點(diǎn)。因此，Chord的主要貢獻(xiàn)是提出了一個(gè)分布式查找協(xié)議，該協(xié)議可將指定的關(guān)鍵字(Key) 映射到對應(yīng)的結(jié)點(diǎn)(Node) 。從算法來看，Chord是相容散列算法的變體。
圖4 Chord的拓?fù)湫螤?/p>
CAN(Content Addressable Networks)[11] 項(xiàng)目采用多維的標(biāo)識符空間來實(shí)現(xiàn)分布式散列算法。CAN將所有結(jié)點(diǎn)映射到一個(gè)n維的笛卡爾空間中，并為每個(gè)結(jié)點(diǎn)盡可能均勻的分配一塊區(qū)域。CAN采用的散列函數(shù)通過對(key, value) 對中的key進(jìn)行散列運(yùn)算，得到笛卡爾空間中的一個(gè)點(diǎn)，并將(key, value) 對存儲(chǔ)在擁有該點(diǎn)所在區(qū)域的結(jié)點(diǎn)內(nèi)。CAN采用的路由算法相當(dāng)直接和簡單，知道目標(biāo)點(diǎn)的坐標(biāo)后，就將請求傳給當(dāng)前結(jié)點(diǎn)四鄰中坐標(biāo)最接近目標(biāo)點(diǎn)的結(jié)點(diǎn)。CAN是一個(gè)具有良好可擴(kuò)展性的系統(tǒng)，給定N個(gè)結(jié)點(diǎn)，系統(tǒng)維數(shù)為d，則路由路徑長度為O(n1/d) ，每結(jié)點(diǎn)維護(hù)的路由表信息和網(wǎng)絡(luò)規(guī)模無關(guān)為O(d) 。
上述四種基于DHT的P2P系統(tǒng)的性能比較可以參照[12]。DHT這類結(jié)構(gòu)最大的問題是DHT的維護(hù)機(jī)制較為復(fù)雜，尤其是結(jié)點(diǎn)頻繁加入退出造成的網(wǎng)絡(luò)波動(dòng)（Churn）會(huì)極大增加DHT的維護(hù)代價(jià)。DHT所面臨的另外一個(gè)問題是DHT僅支持精確關(guān)鍵詞匹配查詢，無法支持內(nèi)容/語義等復(fù)雜查詢。
半分布式拓?fù)浣Y(jié)構(gòu)（有的文獻(xiàn)亦稱作混雜模式，英文表達(dá)為Hybrid Structure）吸取了中心化結(jié)構(gòu)和全分布式非結(jié)構(gòu)化拓?fù)涞膬?yōu)點(diǎn)，選擇性能較高（處理、存儲(chǔ)、帶寬等方面性能）的結(jié)點(diǎn)作為超級結(jié)點(diǎn)（英文表達(dá)為SuperNodes或者Hubs），在各個(gè)超級結(jié)點(diǎn)上存儲(chǔ)了系統(tǒng)中其他部分結(jié)點(diǎn)的信息，發(fā)現(xiàn)算法僅在超級結(jié)點(diǎn)之間轉(zhuǎn)發(fā)，超級結(jié)點(diǎn)再將查詢請求轉(zhuǎn)發(fā)給適當(dāng)?shù)娜~子結(jié)點(diǎn)。半分布式結(jié)構(gòu)也是一個(gè)層次式結(jié)構(gòu)，超級結(jié)點(diǎn)之間構(gòu)成一個(gè)高速轉(zhuǎn)發(fā)層，超級結(jié)點(diǎn)和所負(fù)責(zé)的普通結(jié)點(diǎn)構(gòu)成若干層次。采用這種結(jié)構(gòu)的最典型的案例就是KaZaa。
圖5 半分布式拓?fù)浣Y(jié)構(gòu)（網(wǎng)絡(luò)中包含Super Node）
KaZaa是當(dāng)前世界最流行的幾款P2P文件共享軟件之一。根據(jù)CA公司統(tǒng)計(jì)，全球KaZaa的下載量超過2.5億次。使用KaZaa軟件進(jìn)行文件傳輸消耗了互聯(lián)網(wǎng)40%的帶寬。之所以它如此的成功，是因?yàn)樗Y(jié)合了Napster和Gnutella共同的優(yōu)點(diǎn)。從結(jié)構(gòu)上來說，它使用了Gnutella的全分布式的結(jié)構(gòu)，這樣可以是系統(tǒng)更好的擴(kuò)展，因?yàn)樗鼰o需中央索引服務(wù)器存儲(chǔ)文件名，它是自動(dòng)的把性能好的機(jī)器成為SuperNode，它存儲(chǔ)著離它最近的葉子節(jié)點(diǎn)的文件信息，這些SuperNode,再連通起來形成一個(gè)Overlay Network. 由于SuperNode的索引功能，使搜索效率大大提高。
圖6 KaZaa的軟件界面
半分布式結(jié)構(gòu)的優(yōu)點(diǎn)是性能、可擴(kuò)展性較好，較容易管理，但對超級點(diǎn)依賴性大，易于受到攻擊，容錯(cuò)性也受到影響。
在實(shí)際應(yīng)用中，每種拓?fù)浣Y(jié)構(gòu)的P2P網(wǎng)絡(luò)都有其優(yōu)缺點(diǎn)，下表從可擴(kuò)展性、可靠性、可維護(hù)性、發(fā)現(xiàn)算法的效率、復(fù)雜查詢等方面比較了這四種拓?fù)浣Y(jié)構(gòu)的綜合性能。
|
比較標(biāo)準(zhǔn)／拓?fù)浣Y(jié)構(gòu)
|
中心化拓?fù)?/p>
|
全分布式非結(jié)構(gòu)化拓?fù)?/p>
|
全分布式結(jié)構(gòu)化拓?fù)?/p>
|
半分布式拓?fù)?/p>
|
|
可擴(kuò)展性
|
差
|
差
|
好
|
中
|
|
可靠性
|
差
|
好
|
好
|
中
|
|
可維護(hù)性
|
最好
|
最好
|
好
|
中
|
|
發(fā)現(xiàn)算法效率
|
最高
|
中
|
高
|
中
|
|
復(fù)雜查詢
|
支持
|
支持
|
不支持
|
支持
|
我還是比較看好chord...雖然目前還有不少問題沒有解決....
順便附上一篇經(jīng)典的chord論文: Chord: A Scalable Peertopeer Lookup Service for Internet Applications
http://www.aygfsteel.com/Files/heiyuchuanxia/chord_sigcomm.rar
posted on 2006-11-15 15:28
Stefanie 閱讀(3469)
評論(0) 編輯 收藏 所屬分類:
網(wǎng)絡(luò)相關(guān)