P2P原理與技術(shù)

1、2022-6-111P2P原理與技術(shù)簡(jiǎn)介暨南大學(xué)計(jì)算機(jī)科學(xué)系周繼鵬2022-6-112P2P原理與技術(shù)的內(nèi)容q P2P概念q P2P分類q 構(gòu)件與算法q 關(guān)鍵技術(shù)特性q P2P分析與比較q 研究與未來(lái)2022-6-1131、什么是P2P（Peer-to-Peer）nP2P：對(duì)等(網(wǎng)絡(luò)，計(jì)算);端到端n以非集中方式使用分布式資源來(lái)完成關(guān)鍵任務(wù)的一類系統(tǒng)和應(yīng)用n資源包括計(jì)算能力、數(shù)據(jù)（存儲(chǔ)和內(nèi)容）、網(wǎng)絡(luò)帶寬和場(chǎng)景（計(jì)算機(jī)、人和其它資源）n關(guān)鍵任務(wù)可能是分布式計(jì)算、數(shù)據(jù)/內(nèi)容共享，通信和協(xié)同、或平臺(tái)服務(wù)n節(jié)點(diǎn)是服務(wù)和數(shù)據(jù)的提供者又是需求者n共享資源可被網(wǎng)絡(luò)上其他節(jié)點(diǎn)直接訪問2022-6-114P2P

2、系統(tǒng)特點(diǎn)n可擴(kuò)展性、自組織、容錯(cuò)性、高動(dòng)態(tài)性可擴(kuò)展性、自組織、容錯(cuò)性、高動(dòng)態(tài)性n數(shù)據(jù)的位置往往是不固定的數(shù)據(jù)的位置往往是不固定的n沒有統(tǒng)一的全局模式，查詢基于關(guān)鍵字沒有統(tǒng)一的全局模式，查詢基于關(guān)鍵字n節(jié)點(diǎn)可能不包含完整的數(shù)據(jù)，因此對(duì)于節(jié)點(diǎn)可能不包含完整的數(shù)據(jù)，因此對(duì)于查詢的回答往往不完整查詢的回答往往不完整2022-6-115P2P系統(tǒng)的應(yīng)用n共享文件n流媒體系統(tǒng)n對(duì)等計(jì)算文件共享系統(tǒng)-maze,北京大學(xué)n視頻直播系統(tǒng)AnySee，華中科技大學(xué)n在線電視直播-PPLivenBT下載軟件n(如視頻直播的思想是直播系統(tǒng)中的節(jié)點(diǎn)既下在載數(shù)據(jù)也上傳數(shù)據(jù).)2022-6-116如何找到指定的信息如何找到

3、指定的信息 ? ?ABCDEFE?2022-6-117P2PP2P的網(wǎng)絡(luò)基本構(gòu)成的網(wǎng)絡(luò)基本構(gòu)成LinuxTCP/IPBluetoothHTTPTCP/IPTCP/IPXP2022-6-118P2P覆蓋網(wǎng)絡(luò)的概念（1）覆蓋網(wǎng)絡(luò)的結(jié)點(diǎn)2022-6-119P2P覆蓋網(wǎng)絡(luò)的概念（2）2022-6-1110P2P覆蓋網(wǎng)絡(luò)的路由（1）結(jié)點(diǎn)結(jié)點(diǎn)的完全圖2022-6-1111P2P覆蓋網(wǎng)絡(luò)的路由（2）2022-6-1112覆蓋網(wǎng)絡(luò)n在現(xiàn)有網(wǎng)絡(luò)體系結(jié)構(gòu)上新加一層overlay networksn建立一個(gè)使用已有的Internet傳輸?shù)奶摂M網(wǎng)絡(luò)nInternet也曾經(jīng)被部署為一個(gè)在電話網(wǎng)上的重疊網(wǎng)絡(luò)n也被成為AL

4、NnApplication-Level Network.nFile storage and searchn挑戰(zhàn)n如何創(chuàng)新和部署 at scale2022-6-1113覆蓋網(wǎng)絡(luò)模型 Overlay Network routing table peer 1 Internet: Supporting Netork A Generic Topological Model of P2P Systems routing and locating algorithm Data Storage Data Cache routing table peer 2 routing and locating algor

5、ithm Data Storage Data Cache routing table peer n routing and locating algorithm Data Storage Data Cache 2022-6-1114P2P系統(tǒng)分類n無(wú)結(jié)構(gòu)P2P：文件位置與覆蓋網(wǎng)拓?fù)錈o(wú)關(guān)n有中心的：Napstern無(wú)中心的：Gnutella、Freenetn層次結(jié)構(gòu)：KaZaAn結(jié)構(gòu)化P2P：文件或文件索引的位置與覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)緊密相關(guān)n基于DHT：Chord、CAN、Pastry、Tapestry2022-6-1115Napster原理(1)13245Server2022-6-1116Nap

6、ster原理(2)Where is file A?QueryReplysearch(A)Fetch目錄服務(wù)器2022-6-1117Napster優(yōu)缺點(diǎn)n優(yōu)點(diǎn)：只維護(hù)目錄，結(jié)構(gòu)簡(jiǎn)單，效率高n缺點(diǎn)：?jiǎn)吸c(diǎn)失效，存在瓶頸，法律問題2022-6-1118洪泛請(qǐng)求模式n過程n每個(gè)Peer的請(qǐng)求直接廣播到連接的Peersn各Peers又廣播到各自的Peersn直到收到應(yīng)答或 達(dá)到最大洪泛步數(shù)n特點(diǎn)n無(wú)廣告性共享資源nGnutella 使用該算法,限于公司內(nèi)通信有效n大量請(qǐng)求占用網(wǎng)絡(luò)帶寬,可擴(kuò)展性并不一定最好n改進(jìn)nKazaa 設(shè)立Super-Peer客戶軟件,以集中大量請(qǐng)求n文件

7、分塊nCache最近請(qǐng)求2022-6-1119Gnutella原理 (1)Flooding: Loop Prevention2022-6-1120Gnutella原理(2)I have file A.I have file A.Where is file A?QueryReply2022-6-1121Gnutella優(yōu)缺點(diǎn)n容錯(cuò)性和健壯性好n覆蓋網(wǎng)拓?fù)渚S護(hù)簡(jiǎn)單n查詢代價(jià)高，可擴(kuò)展性差，flooding2022-6-1122KaZaA原理n介于Napster和Gnutella之間n無(wú)中心，但有中心簇集n層次結(jié)構(gòu)，一個(gè)節(jié)點(diǎn)是超級(jí)節(jié)點(diǎn)或?qū)儆谀吵?jí)節(jié)點(diǎn)的子節(jié)點(diǎn)n超級(jí)節(jié)點(diǎn)間采用flooding機(jī)制搜索2

8、022-6-1123KaZaA原理132Super Nodes:1,2,32022-6-1124KaZaA原理Where is file A?Querysearch(A)-8search(A)-0Replies802022-6-1125有結(jié)構(gòu)系統(tǒng)的文件路由模式n過程n每個(gè)網(wǎng)上Peer分配一個(gè)隨機(jī)ID,并知道其他Peers的給定號(hào)碼n當(dāng)共享文件發(fā)布到系統(tǒng)上時(shí),根據(jù)文件名字和內(nèi)容Hash成為IDn每個(gè)Peer將根據(jù)該ID向該文件路由n該過程重復(fù)執(zhí)行,直到最近的PeerID是現(xiàn)行Peer的IDn每個(gè)路由操作還保持文件副本在本

9、地n當(dāng)Peer請(qǐng)求某文件時(shí),該請(qǐng)求將用該文件的ID到達(dá)Peer,過程重復(fù)直到發(fā)現(xiàn)文件副本,最終文件下載到請(qǐng)求源端2022-6-1126實(shí)現(xiàn)文件路由算法nChord/CAN/Tapestry/Pastryn目標(biāo)相同n減少路由到指定文件的P2P跳數(shù)n減少每個(gè)Peer必須保持的路由狀態(tài)n算法異同n都保證算法的跳數(shù)與Peer群組的大小相關(guān)n或都指出算法能以高概率完成n方法上的差別很小2022-6-1127四個(gè)算法的比較nChordn每個(gè)Peer保持LogN其他Peer的蹤跡(N是群組的全部Peer數(shù))n當(dāng)Peer加入或離開時(shí),高優(yōu)化算法版本僅需關(guān)注LogN個(gè)Peers的變化nCANn每個(gè)Peer保持少

10、于LogN個(gè)其他Peers的蹤跡n在插入和刪除時(shí)僅這些Peers受影響n其路由表較小,但到達(dá)的路徑較長(zhǎng)n可能更適合動(dòng)態(tài)通信nTapestry與Pastry很相似n除減少跳數(shù)外,還積極削減每個(gè)P2P跳上的時(shí)延2022-6-1128路由表n路由表內(nèi)容nid文件標(biāo)識(shí)符nnext_hop存儲(chǔ)文件id的另一個(gè)節(jié)點(diǎn)nfile保存在本地的文件標(biāo)識(shí)符為id的文件n搜索過程n如果文件id存儲(chǔ)在本地，停止搜索，上傳文件n如果不在本地，搜索路由表中最接近的id，將請(qǐng)求轉(zhuǎn)到next_hopn如果所有節(jié)點(diǎn)都沒有找到，返回失敗，返回路由表中下一個(gè)最接近的idIDNext_hopfile2022-6-1129文件路由原理

11、4 n1 f412 n2 f12 5 n3 9 n3 f9 3 n1 f314 n4 f14 5 n314 n5 f1413 n2 f13 3 n6n1n2n3n4 4 n1 f410 n5 f10 8 n6n5query(10)1234452022-6-1130Distributed Hash Table（DHT）分布式分布式Hash表表分布式應(yīng)用分布式應(yīng)用get (key)datanodenodenode.put(key, data)查找服務(wù)查找服務(wù)lookup(key)node IP address(文件共享文件共享)(DHash)(Chord)2022-6-1131結(jié)構(gòu)化覆蓋網(wǎng)的路由q

12、加入：開始時(shí)，聯(lián)系一個(gè)“bootstrap”節(jié)點(diǎn)，加入分布式數(shù)據(jù)結(jié)構(gòu)，獲得一個(gè)節(jié)點(diǎn)idq發(fā)布：向數(shù)據(jù)結(jié)構(gòu)中最近的節(jié)點(diǎn)發(fā)布文件id的路由信息q搜索：向路由表中最近的節(jié)點(diǎn)查詢文件id，數(shù)據(jù)結(jié)構(gòu)保證查詢會(huì)找到發(fā)布節(jié)點(diǎn)q獲?。簝蓚€(gè)選項(xiàng)n查詢到的節(jié)點(diǎn)保存有文件，則從查詢結(jié)束的節(jié)點(diǎn)獲取n查詢到的節(jié)點(diǎn)返回結(jié)果：節(jié)點(diǎn)x有文件，則從節(jié)點(diǎn)x獲取q DHT示例Chord:在一維空間（環(huán)）中給每個(gè)節(jié)點(diǎn)和文件一個(gè)唯一的idn例如從0.2m中選取n通常是文件和IP地址的hash2022-6-1132ChordnChord系統(tǒng)提出了一個(gè)利用一致性的Hash函數(shù)將所有結(jié)點(diǎn)和文件對(duì)應(yīng)到一個(gè)N個(gè)整數(shù)形成的邏輯環(huán)上的P2P系統(tǒng)。n

13、每一個(gè)結(jié)點(diǎn)有一個(gè)代碼（node ID）表示在邏輯環(huán)上的位置。結(jié)點(diǎn)代碼是利用結(jié)點(diǎn)IP通過一個(gè)Hash函數(shù)（node hash function）計(jì)算得到。n每一個(gè)文件用一個(gè)文件代碼（File ID）表示，文件代碼是文件名通過一個(gè)Hash函數(shù)（file hash function）計(jì)算得到。2022-6-1133Chord環(huán)定義n在一個(gè)穩(wěn)定狀態(tài)下，在有N個(gè)結(jié)點(diǎn)（peer）的系統(tǒng)中，每一個(gè)結(jié)點(diǎn)維護(hù)一個(gè)O（logN）個(gè)結(jié)點(diǎn)的路由狀態(tài)表。nVertex Set: 0N-1 : N is a power of 2nEdge Set: (u, v) | v-u is a power of 2nex: N=6

14、4, u=0, then the neighbors of u are 1, 2, 4, 8, 16, 322022-6-1134Chord環(huán)定義qHash函數(shù): node InodeID, data DdataIDqnodeID, dataID in 0, ., N -1 where N =2mqPut data D on node I, so that nodeID(I) is smallest nodeID larger than or equal to dataID(D)qGiven key=dataID(D), how to find successor(key) ? Lookup(

15、key)=successor(key), find the first live nodeID which is key.qFinger table: node k stores pointers to k+1, k+2, k+4 ., k +2m -1 (mod N) qFind node for every data in O(log(N) steps; O(log(N) storage per node0 1 2 3 4 . 7 8 9 . 14 15 16 . . . n-2 n-12022-6-1135Chord環(huán)Chord環(huán)的 finger表12131417181920222330

16、2928272625211516240123456783191011Actual nodeNode identifier24345791217205767812121220201315141516202020281Node 1s finger tableNode 4s finger tableNode 12s finger tableStart = k + 2i (modulo 2m) IP addr of successor (start )A ring of 25 node Ids. m =5, i = 0m-1 .2022-6-1137Chord環(huán)：路由算法When node k rec

17、eives the lookup(key),If k key next(k), return next(k) elseif key k at intermediate node k, return kelse forward to f such that f=MAXfingers|fingerskeyChord環(huán)：路由實(shí)例12131417181920222330292827262521151624012345678319101124345791217205767812121220201315141516202020281Node 1s finger tableNode 4s finger ta

18、bleNode 12s finger tableStart = k + 2i (modulo 2m) IP addr of successor (start )Look up key=14,15,16,17 at node 1.2022-6-1139CANn基于虛擬的d維笛卡爾坐標(biāo)空間實(shí)現(xiàn)數(shù)據(jù)組織和查找功能。n利用類似網(wǎng)絡(luò)路由的方式來(lái)尋找文件所在的位置。n在CAN系統(tǒng)中，每一個(gè)結(jié)點(diǎn)利用一個(gè)坐標(biāo)路由表(coordinate routing table)記錄在坐標(biāo)空間中相鄰結(jié)點(diǎn)的IP地址和空間位置。n當(dāng)收到一個(gè)文檔查詢的請(qǐng)求時(shí)，起始結(jié)點(diǎn)先利用Hash函數(shù)計(jì)算出此文件所在的坐標(biāo)，并附在查詢請(qǐng)求中。n

19、當(dāng)一個(gè)結(jié)點(diǎn)收到此文件的查詢請(qǐng)求時(shí)，先看查詢文件是否存在，若存在，則返回此文件；否則，利用查找路由表找出一個(gè)與查找文件位置最近的結(jié)點(diǎn)；以此繼續(xù)下去。2022-6-1140CAN2022-6-1141P2P的關(guān)鍵技術(shù)特性（的關(guān)鍵技術(shù)特性（1）（1）非集中化）非集中化:置疑置疑 C/S 模式模式n集中化n在訪問權(quán)限和安全上容易管理n但不可避免導(dǎo)致:低效/瓶頸/資源浪費(fèi)n盡管硬件性能和成本有了改進(jìn),但建立和維護(hù)集中化知識(shí)庫(kù)成本高昂,需要人員智能化地建立,保持信息的相關(guān)和更新n非集中化:更強(qiáng)有力的思想n強(qiáng)調(diào)用戶端所有權(quán),對(duì)數(shù)據(jù)和資源的控制n每個(gè)Peer都是平等的參與者n實(shí)現(xiàn)更困難(無(wú)全局服務(wù)器,看不到全

20、局Peers及其文件)n這也是當(dāng)前混合模式存在的原因2022-6-1142（2）可擴(kuò)展性）可擴(kuò)展性n可擴(kuò)展性受限的主要原因n需要完成大量的集中化操作:如同步與一致n需要維護(hù)許多狀態(tài)n固有的并行性應(yīng)用展開n用來(lái)表示計(jì)算的編程模式nP2P解決可擴(kuò)展性問題nNapster在其服務(wù)的高峰用戶達(dá)到 600萬(wàn)n然SETIhone2002年止用戶 僅接近350萬(wàn).因?yàn)樗性诓⑿卸扔邢薜娜蝿?wù)上,依靠因特網(wǎng)上的可用計(jì)算力來(lái)分析從天文望遠(yuǎn)鏡收集來(lái)的數(shù)據(jù),搜索外星生命nAvaki通過提供分布式對(duì)象模型來(lái)解決可擴(kuò)展性問題2022-6-1143（3）匿名n目的目的n重要目的是讓人們使用系統(tǒng)時(shí)不用關(guān)心法律問題和其他節(jié)外

21、重要目的是讓人們使用系統(tǒng)時(shí)不用關(guān)心法律問題和其他節(jié)外生枝的問題生枝的問題n進(jìn)一步目的可能使數(shù)字內(nèi)容的審查制度形同虛設(shè)進(jìn)一步目的可能使數(shù)字內(nèi)容的審查制度形同虛設(shè)n匿名形式匿名形式n作者作者:可以不標(biāo)識(shí)文件的作者或創(chuàng)建者可以不標(biāo)識(shí)文件的作者或創(chuàng)建者n發(fā)布者發(fā)布者:可以不標(biāo)識(shí)對(duì)系統(tǒng)而言的文件發(fā)行者可以不標(biāo)識(shí)對(duì)系統(tǒng)而言的文件發(fā)行者n讀者讀者:可以不標(biāo)識(shí)文件的讀者或其他消費(fèi)數(shù)據(jù)者可以不標(biāo)識(shí)文件的讀者或其他消費(fèi)數(shù)據(jù)者n服務(wù)器服務(wù)器:可以不標(biāo)識(shí)含有未被標(biāo)識(shí)文件的服務(wù)器可以不標(biāo)識(shí)含有未被標(biāo)識(shí)文件的服務(wù)器n文件文件:服務(wù)器并不知道它存儲(chǔ)的是什么文件服務(wù)器并不知道它存儲(chǔ)的是什么文件n查詢查詢:服務(wù)器并不告訴它正用何文件在響應(yīng)用戶的查詢服務(wù)器并不告訴它正用何文件在響應(yīng)用戶的查詢2022-6-11446種不同技術(shù)-適合不同匿名方式n多播使接收者