劉凱 張華

摘要：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)化模型一般使用洪泛方法實(shí)現(xiàn)，結(jié)構(gòu)化P2P網(wǎng)絡(luò)一般使用分布式哈希表構(gòu)建。該文在分析兩種P2P網(wǎng)絡(luò)的基礎(chǔ)上，對(duì)比了結(jié)構(gòu)化P2P模型和非結(jié)構(gòu)化P2P模型中的典型案例的實(shí)現(xiàn)過程，并對(duì)其優(yōu)缺點(diǎn)進(jìn)行了總結(jié)。

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

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

1研究背景

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

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

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

P2P系統(tǒng)一般要構(gòu)造一個(gè)拓?fù)浣Y(jié)構(gòu)，在這個(gè)結(jié)構(gòu)中需要解決節(jié)點(diǎn)命名，出錯(cuò)恢復(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相比，此時(shí)服務(wù)器僅祈禱促成各種節(jié)點(diǎn)協(xié)調(diào)和擴(kuò)展的功能，一般這種服務(wù)器我們稱為索引服務(wù)器。在這種結(jié)構(gòu)下，資源并不存儲(chǔ)在服務(wù)器上，而是存儲(chǔ)在各個(gè)計(jì)算機(jī)上，這樣一來可以大大降低服務(wù)器的負(fù)載壓力，但是對(duì)服務(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ī)圖的組織方式，各個(gè)計(jì)算機(jī)間的關(guān)系以及數(shù)據(jù)的放置方式?jīng)]有嚴(yán)格的控制，才用洪返的方式來定位數(shù)據(jù)，該模型的主要優(yōu)點(diǎn)是穩(wěn)定性好，主要缺點(diǎn)是查詢效率比較低；結(jié)構(gòu)化模型中主要基于分布式哈希表來控制計(jì)算機(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ò)展性和容錯(cuò)性較好，但是它采用應(yīng)用程廣播的協(xié)議導(dǎo)致消息量過大，網(wǎng)絡(luò)負(fù)擔(dān)過重，無法得知整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或組成網(wǎng)絡(luò)的各計(jì)算機(jī)的身份，另外這類系統(tǒng)更容易受到垃圾信息甚至是病毒的惡意攻擊，而且由于采用洪泛方法，查詢的直徑也不可控，查詢效率比較低下。下面我們來看一種典型的使用非結(jié)構(gòu)模型的軟件，Gnutella。

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

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

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

5兩種模型的對(duì)比

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

6小結(jié)

該文主要介紹了P2P的概念、特點(diǎn)和分類，其中重點(diǎn)介紹了純分布式P2P中的兩個(gè)典型：非結(jié)構(gòu)化的Chord和結(jié)構(gòu)化的Gnutella，并對(duì)比了兩種模型的在時(shí)間復(fù)雜度、空間復(fù)雜度度、穩(wěn)定性、可擴(kuò)展性等方面的優(yōu)缺點(diǎn)，揚(yáng)長(zhǎ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.