純分布式P2P網(wǎng)絡(luò)結(jié)構(gòu)淺析

劉凱 張華

摘要：P2P（Peer-to-Peer）是現(xiàn)今廣泛使用的一種網(wǎng)絡(luò)模型，非結(jié)構(gòu)化P2P模型和結(jié)構(gòu)化P2P模型是其中兩種基本拓?fù)浣Y(jié)構(gòu)。非結(jié)構(gòu)化模型一般使用洪泛方法實現(xiàn)，結(jié)構(gòu)化P2P網(wǎng)絡(luò)一般使用分布式哈希表構(gòu)建。該文在分析兩種P2P網(wǎng)絡(luò)的基礎(chǔ)上，對比了結(jié)構(gòu)化P2P模型和非結(jié)構(gòu)化P2P模型中的典型案例的實現(xiàn)過程，并對其優(yōu)缺點(diǎn)進(jìn)行了總結(jié)。

關(guān)鍵詞：P2P；洪泛；分布式哈希表

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044（2012）36-8631-03

1研究背景

二十一世紀(jì)以來，信息技術(shù)迅速發(fā)展，互聯(lián)網(wǎng)上的信息量快速增長，根據(jù)Google公司的報道，到2005年，Google已經(jīng)索引了80.6億個頁面和10億以上的圖片，如何有效管理這些信息是一個熱點(diǎn)和難點(diǎn)問題。當(dāng)前，互聯(lián)網(wǎng)程序主要使用客戶機(jī)/服務(wù)器（C/S）和瀏覽器/服務(wù)器（B/S）模式，這兩種模式都以服務(wù)器為中心，由服務(wù)器負(fù)責(zé)存儲資源和提供服務(wù)。但隨著互聯(lián)網(wǎng)的發(fā)展，兩種模式中服務(wù)器的負(fù)載越來越重，服務(wù)器成了發(fā)展的瓶頸，同時應(yīng)用程序?qū)Ψ?wù)器依賴性較大，一旦服務(wù)器出現(xiàn)故障，整個系統(tǒng)都面臨崩潰。

P2P的出現(xiàn)，使得消除服務(wù)器為中心的網(wǎng)絡(luò)瓶頸成為了可能。最近幾年，P2P計算已稱為計算機(jī)中的熱門話題之一。P2P網(wǎng)絡(luò)是一種分布式的網(wǎng)絡(luò)，它打破了傳統(tǒng)的C/S和B/S模式，在網(wǎng)絡(luò)中每個計算機(jī)的功能和地位都是對等的，每個計算機(jī)既為其他用戶提供服務(wù)，也想用其他用戶所提供的服務(wù)，在P2P中，所有的運(yùn)算、存儲等都分布在各個計算機(jī)上，這樣就減少了對服務(wù)器的依賴，減輕了服務(wù)器的負(fù)載。

2P2P網(wǎng)絡(luò)結(jié)構(gòu)

P2P系統(tǒng)一般要構(gòu)造一個拓?fù)浣Y(jié)構(gòu)，在這個結(jié)構(gòu)中需要解決節(jié)點(diǎn)命名，出錯恢復(fù)和數(shù)據(jù)查詢等問題，現(xiàn)有的P2P網(wǎng)絡(luò)結(jié)構(gòu)有以下幾種：

2.1混合型的P2P結(jié)構(gòu)

這種結(jié)構(gòu)并不是完全的分布式P2P，這種結(jié)構(gòu)中仍然有服務(wù)器的存在，不過服務(wù)器的作用發(fā)生了改變，和傳統(tǒng)的C/S相比，此時服務(wù)器僅祈禱促成各種節(jié)點(diǎn)協(xié)調(diào)和擴(kuò)展的功能，一般這種服務(wù)器我們稱為索引服務(wù)器。在這種結(jié)構(gòu)下，資源并不存儲在服務(wù)器上，而是存儲在各個計算機(jī)上，這樣一來可以大大降低服務(wù)器的負(fù)載壓力，但是對服務(wù)器的依賴性依然存在。比如著名的MP3共享軟件Napster就是使用混合型的P2P結(jié)構(gòu)。

2.2純分布式的P2P結(jié)構(gòu)

純分布式的P2P結(jié)構(gòu)又分為非結(jié)構(gòu)模型和結(jié)構(gòu)化模型兩種，其中非結(jié)構(gòu)模型采用隨機(jī)圖的組織方式，各個計算機(jī)間的關(guān)系以及數(shù)據(jù)的放置方式?jīng)]有嚴(yán)格的控制，才用洪返的方式來定位數(shù)據(jù)，該模型的主要優(yōu)點(diǎn)是穩(wěn)定性好，主要缺點(diǎn)是查詢效率比較低；結(jié)構(gòu)化模型中主要基于分布式哈希表來控制計算機(jī)的分布和數(shù)據(jù)的放置，該模型的優(yōu)點(diǎn)是查詢效率高，主要缺點(diǎn)是穩(wěn)定性比較低。

3非結(jié)構(gòu)化P2P模型

非結(jié)構(gòu)化P2P模型采用了基于完全隨機(jī)圖的洪泛發(fā)現(xiàn)和隨機(jī)轉(zhuǎn)發(fā)機(jī)制。解決了網(wǎng)絡(luò)結(jié)構(gòu)中心化的問題，擴(kuò)展性和容錯性較好，但是它采用應(yīng)用程廣播的協(xié)議導(dǎo)致消息量過大，網(wǎng)絡(luò)負(fù)擔(dān)過重，無法得知整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或組成網(wǎng)絡(luò)的各計算機(jī)的身份，另外這類系統(tǒng)更容易受到垃圾信息甚至是病毒的惡意攻擊，而且由于采用洪泛方法，查詢的直徑也不可控，查詢效率比較低下。下面我們來看一種典型的使用非結(jié)構(gòu)模型的軟件，Gnutella。

4結(jié)構(gòu)化P2P模型

非結(jié)構(gòu)化P2P系統(tǒng)中存在著缺乏有效的可擴(kuò)展的查找機(jī)制的問題。近年很多研究人員在設(shè)計可擴(kuò)展的查找機(jī)制方面做了很多工作，重要成果就是分布式哈希表（DHT，DistributedHashTable），基于分布式哈希表的P2P是結(jié)構(gòu)化的P2P。與一般的哈希表累死，分布式哈希表提供三個基本操作：插入，查找和刪除，操作對象仍然是鍵值對，與傳統(tǒng)哈希表不同的是，分布式哈希表的各項是分布在網(wǎng)絡(luò)的各個計算機(jī)上，因此每個計算機(jī)都要具備這樣的功能：給定一個鍵，消息必須能夠被傳遞到保存該鍵的計算機(jī)上。典型的DHT協(xié)議有：Chord，CAN等。

Chord在2001年由麻省理工學(xué)院提出，其核心思想就是要解決在P2P應(yīng)用中遇到的基本問題：如何在P2P網(wǎng)絡(luò)中找到存有特定數(shù)據(jù)的節(jié)點(diǎn)。Chord實現(xiàn)了這樣的一種操作：給定一個關(guān)鍵詞Key，將其映射到某個計算機(jī)上。為此，Chord中使用了DHT為每個計算機(jī)和關(guān)鍵詞產(chǎn)生了一個n位的標(biāo)識，并按照標(biāo)識大小形成環(huán)形結(jié)構(gòu)。標(biāo)識的長度n必須足夠長，這樣可以忽略不同計算機(jī)或關(guān)鍵詞哈希結(jié)果相同的情況。在Chord中，每個關(guān)鍵詞都保存在它的后繼中，后繼指的是計算機(jī)標(biāo)示大于等于關(guān)鍵詞標(biāo)示的第一個計算機(jī)在Chord中，如果n表示關(guān)鍵詞和計算機(jī)標(biāo)識的位數(shù)（二進(jìn)制），那么每個計算機(jī)需要存儲n個其他計算機(jī)的信息，這些信息叫做查詢表（FingerTable），或者叫做指針表，而且這些表格中存儲的不再是直接相鄰的計算機(jī)。在查詢的時候，查詢計算機(jī)將請求發(fā)送到與所查詢關(guān)鍵詞的標(biāo)識最接近的計算機(jī)上。收到查詢請求的計算機(jī)如果發(fā)現(xiàn)自身存儲了被查詢的關(guān)鍵詞，可以直接回應(yīng)查詢計算機(jī)；如果被查詢的關(guān)鍵詞不在本地，就根據(jù)查詢表將請求轉(zhuǎn)發(fā)到與標(biāo)識最接近的計算機(jī)上。這樣的過程一直持續(xù)到找到相應(yīng)的計算機(jī)為止。不難看出，查詢過程實際上就是折半查找的過程。

5兩種模型的對比

而在負(fù)載平衡方面，首先Gnutella中的計算機(jī)之間的關(guān)系是隨機(jī)的，未考慮負(fù)載平衡，Chord中使用了相容哈希，可以在全網(wǎng)范圍內(nèi)實現(xiàn)負(fù)載平衡；在穩(wěn)定性方面，Gnutella中的計算機(jī)的加入和退出只對鄰近計算機(jī)有影響，所以計算機(jī)的加入退出對整個網(wǎng)絡(luò)影響不大，所以其穩(wěn)定性較高，Chord中計算機(jī)的加入退出時間復(fù)雜度較高，如果計算機(jī)頻繁加入退出可能引起整個網(wǎng)絡(luò)的癱瘓，所以其穩(wěn)定性比較差；在可擴(kuò)展性方面，Gnutella中計算機(jī)加入退出方面，但由于Gnutella使用洪泛的方式通信，大量的帶寬占用使得一些帶寬少性能差的計算機(jī)被孤立，導(dǎo)致網(wǎng)絡(luò)可用性降低，因此Guntella的可擴(kuò)展性一般，Chord中因為具有O（logN）的空間和時間復(fù)雜度，所以能夠容納大量的計算機(jī)，所以其可擴(kuò)展性很好。

6小結(jié)

該文主要介紹了P2P的概念、特點(diǎn)和分類，其中重點(diǎn)介紹了純分布式P2P中的兩個典型：非結(jié)構(gòu)化的Chord和結(jié)構(gòu)化的Gnutella，并對比了兩種模型的在時間復(fù)雜度、空間復(fù)雜度度、穩(wěn)定性、可擴(kuò)展性等方面的優(yōu)缺點(diǎn)，揚(yáng)長避短，以便于讀者選擇合適的P2P模型進(jìn)行開發(fā)和使用。

參考文獻(xiàn)：

[1]GallaugherJM，RamanathanSC.ChoosingaClient/ServerArchitecture[J].InformationSystemsManagement，1996，13（2）：7-13.

[2]ClayShirky.WhatisP2Pandwhatisn't[C].O'Reilly'sEmergingTechnologyConference，2002.

[3]Gnutella[EB/OL].Http：//www.Gnutella.com.

[4]PEER-TO-PEER.ORG[EB/OL].http：//www.peer-to-peer.org/.

[5]徐玉.P2P網(wǎng)絡(luò)中資源搜索算法的研究[D].南京：南京郵電大學(xué)，2011.