計(jì)算機(jī)網(wǎng)絡(luò)系列博文——目錄
P2P對(duì)等體系結(jié)構(gòu)
對(duì)一直開啟的基礎(chǔ)設(shè)施服務(wù)器有最小程度的依賴，成對(duì)間歇連接的主機(jī)（對(duì)等方）彼此直接通信。
P2P文件分發(fā)與C/S文件分發(fā)的對(duì)比
文件分發(fā)模型
- 將一個(gè)文件分發(fā)給一個(gè)固定的集合。
- 假定因特網(wǎng)核心帶寬充足，網(wǎng)絡(luò)瓶頸在接入網(wǎng)
- 服務(wù)器接入鏈路上載速率
- 對(duì)等方
接入鏈路上載速率
- 對(duì)等方
- 待分發(fā)文件大小
- 要獲得該文件的對(duì)等方數(shù)量
客戶/服務(wù)器文件分發(fā)
服務(wù)器向每個(gè)客戶發(fā)送文件的一個(gè)副本，服務(wù)器負(fù)擔(dān)大余境，服務(wù)器流量消耗大
對(duì)足夠大的N,分發(fā)時(shí)間隨N線性增加
P2P文件分發(fā)
每個(gè)客戶作為對(duì)等方，可重新分發(fā)它所有的文件的任何部分灌诅。
擴(kuò)展性 對(duì)于變量用戶規(guī)模芳来，客戶/服務(wù)器體系的總傳輸時(shí)間是線性的，而P2P體系的總傳輸時(shí)間是亞線性且有上界的猜拾。
BitTorrent協(xié)議
用于文件分發(fā)的流行P2P協(xié)議即舌。
洪流(torrent) 參與一個(gè)特定文件分發(fā)的所有對(duì)等體的集合
文件塊 洪流中的對(duì)等方彼此傳輸?shù)乳L(zhǎng)的文件塊；
追蹤器（tracker） 一個(gè)對(duì)等方加入洪流時(shí)挎袜，向追蹤器注冊(cè)自己顽聂，并周期性地通知追蹤器自己仍在洪流中。追蹤器維護(hù)正在參與洪流的對(duì)等方列表盯仪。
BitTorrent協(xié)議中的追蹤器是分布式的紊搪，即后文中的DHT。
鄰近對(duì)等方 洪流中全景，成功創(chuàng)建TCP連接的一對(duì)對(duì)等方 耀石。
新對(duì)等方A加入洪流時(shí)，追蹤器（隨機(jī)地）將洪流的某個(gè)子集中所有對(duì)等方的ip地址發(fā)送給A;
A持有該對(duì)等方列表蚪燕，并試圖與該列表上的所有對(duì)等方創(chuàng)建并行的TCP連接娶牌；
A的鄰近對(duì)等方不斷變動(dòng)，舊鄰近對(duì)等方可能離開馆纳，新鄰近對(duì)等方可能與A成功創(chuàng)建TCP連接诗良；
A周期性地詢問鄰近對(duì)等方所持有的塊列表，并根據(jù)列表信息鲁驶，對(duì)A自身當(dāng)前未擁有的塊發(fā)出請(qǐng)求鉴裹；
最稀缺優(yōu)先技術(shù) 對(duì)等方A在決定請(qǐng)求哪些塊時(shí)，首先請(qǐng)求那些A的鄰近對(duì)等方中副本最少的塊钥弯，以大致均衡每個(gè)塊在洪流中的副本數(shù)量径荔。
對(duì)換算法 對(duì)等方A決定響應(yīng)鄰近對(duì)等方們的那個(gè)請(qǐng)求。A根據(jù)當(dāng)前向它提供數(shù)據(jù)的鄰居的速率脆霎，給出優(yōu)先權(quán)总处。每個(gè)時(shí)間周期，A根據(jù)優(yōu)先權(quán)決定它向哪些鄰居傳送數(shù)據(jù)睛蛛；每過多個(gè)時(shí)間周期鹦马，A隨機(jī)選出一個(gè)鄰居并向他發(fā)送數(shù)據(jù)。
以上關(guān)于交換的激勵(lì)機(jī)制常被稱為一報(bào)還一報(bào)忆肾。這種激勵(lì)方案能被回避荸频。但事實(shí)上，BitTorrent的生態(tài)比較成功客冈。
分布式P2P體系數(shù)據(jù)庫旭从，DHT
中心式數(shù)據(jù)庫模型
客戶/服務(wù)器體系，中心數(shù)據(jù)庫存儲(chǔ)鍵值對(duì)场仲，客戶可用特定鍵查詢值和悦。
分布式散列表(Distributed Hash Table,DHT)
分布式P2P體系，大量對(duì)等方維護(hù)一個(gè)鍵值對(duì)的表燎窘，每個(gè)對(duì)等方只存儲(chǔ)該表的一個(gè)小子集摹闽。
允許任一對(duì)等方用一個(gè)特定鍵查詢?cè)摲植际綌?shù)據(jù)庫。分布式數(shù)據(jù)庫定位擁有該鍵值對(duì)的對(duì)等方褐健，并返回該鍵值對(duì)付鹿。
允許任一對(duì)等方向數(shù)據(jù)庫中插入新鍵值對(duì)。
樸素設(shè)計(jì)
在所有對(duì)等方中隨機(jī)分布鍵值對(duì)蚜迅，每個(gè)對(duì)等方維護(hù)一個(gè)所有參與對(duì)等方的表舵匾。查詢鍵k時(shí)向所有其他對(duì)等方發(fā)送查詢。維護(hù)鍵k的對(duì)等方向查詢者發(fā)送響應(yīng)谁不。
此方案無擴(kuò)展性坐梯，隨對(duì)等方數(shù)量增多，數(shù)據(jù)庫復(fù)雜性大大增加刹帕。
基于散列的設(shè)計(jì)
為每個(gè)對(duì)等方分配一個(gè)標(biāo)識(shí)符id吵血，id為n比特整數(shù)谎替。
定義將鍵映射到n比特整數(shù)的哈希函數(shù)。
中心問題
定義為對(duì)等方分配鍵的規(guī)則蹋辅。
對(duì)鍵key钱贯，為id最鄰近hash(key)的對(duì)等方分配該鍵值對(duì)。
最鄰近：鍵的最鄰近后繼
插入鍵值對(duì)：確定最鄰近該鍵hash的對(duì)等方侦另，而后向該對(duì)等方發(fā)送查詢報(bào)文秩命。
如何確定最鄰近該鍵hash的對(duì)等方？恰當(dāng)組織數(shù)據(jù)庫結(jié)構(gòu)
DHT結(jié)構(gòu)
將DHT組織為連通圖
連通度過高褒傅，每個(gè)對(duì)等方需維護(hù)的鄰居數(shù)過多
連通度過低弃锐，DHT為解析一個(gè)查詢而需轉(zhuǎn)發(fā)的報(bào)文次數(shù)過多
環(huán)形DHT
將對(duì)等方組織為環(huán)，每個(gè)對(duì)等方僅與其直接后繼和直接前驅(qū)聯(lián)系殿托。
對(duì)等方收到一個(gè)查詢報(bào)文時(shí)霹菊，判斷是否應(yīng)有自己處理該報(bào)文，若不是碌尔，則將報(bào)文轉(zhuǎn)發(fā)給后繼鄰居
捷徑DHT
以環(huán)形DHT為基礎(chǔ)浇辜，為每個(gè)對(duì)等方維護(hù)適量的捷徑對(duì)等方。
對(duì)等方收到一個(gè)查詢報(bào)文時(shí)唾戚，判斷是否應(yīng)有自己處理該報(bào)文柳洋，若不是，則將報(bào)文轉(zhuǎn)發(fā)給最鄰近該鍵hash的鄰居
研究表明叹坦，DHT可被設(shè)計(jì)為每個(gè)對(duì)等方的鄰居數(shù)和每個(gè)請(qǐng)求的報(bào)文轉(zhuǎn)發(fā)次數(shù)都在O(logN)熊镣，N為對(duì)等方總數(shù)
對(duì)等方擾動(dòng)
P2P體系中，對(duì)等方可不加警示地到來或離去募书。
為處理對(duì)等方擾動(dòng)绪囱，每個(gè)對(duì)等方應(yīng)存儲(chǔ)冗余的鄰居信息。如環(huán)形DHT中每個(gè)對(duì)等方可以同時(shí)存儲(chǔ)第一后繼和第二后繼莹捡。
