劉凱 張華

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

關鍵詞：P2P；洪泛；分布式哈希表

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044（2012）36-8631-03

1研究背景

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

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

2P2P網(wǎng)絡結構

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

2.1混合型的P2P結構

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

2.2純分布式的P2P結構

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

3非結構化P2P模型

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

4結構化P2P模型

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

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

5兩種模型的對比

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

6小結

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

參考文獻：

[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)絡中資源搜索算法的研究[D].南京：南京郵電大學，2011.