一鼎姊、概念

????????常見的P2P網(wǎng)絡(luò)主要分為兩種類型:結(jié)構(gòu)化網(wǎng)絡(luò)和非結(jié)構(gòu)化網(wǎng)絡(luò)屠缭。

? ??????非結(jié)構(gòu)化的P2P網(wǎng)絡(luò)：并不給節(jié)點(diǎn)的連接覆蓋某種特定的架構(gòu)箍鼓，節(jié)點(diǎn)直接隨機(jī)連接。因?yàn)槿鄙俳Y(jié)構(gòu)呵曹，所以網(wǎng)絡(luò)面對(duì)頻繁的動(dòng)態(tài)添加和刪除結(jié)點(diǎn)時(shí)款咖，依然能夠健壯地運(yùn)行，但也正因?yàn)槿鄙俳Y(jié)構(gòu)奄喂，所以當(dāng)某個(gè)結(jié)點(diǎn)想要搜索某些數(shù)據(jù)或文件時(shí)铐殃，查詢必須flood整個(gè)網(wǎng)絡(luò)。

? ??????結(jié)構(gòu)化的P2P網(wǎng)絡(luò)：將網(wǎng)絡(luò)組織成某種特定的擴(kuò)撲結(jié)構(gòu)跨新，并且他們之間的協(xié)議能夠保證任何結(jié)點(diǎn)都能高效地搜索網(wǎng)絡(luò)中的資源富腊，即使是非常冷門的資源。常見的結(jié)構(gòu)化P2P網(wǎng)絡(luò)通常實(shí)現(xiàn)一致性哈嫌蛘剩或者其變種分布式哈希表DHT分配文件的所有權(quán)到特定的結(jié)點(diǎn)

二赘被、P2P中常見的索引方式：

????????中央索引：

????????由一個(gè)中央服務(wù)器統(tǒng)一保存資源與結(jié)點(diǎn)的關(guān)系是整。這種方式搜索效率比較高，因?yàn)榭梢酝ㄟ^中央索引直接定位到目標(biāo)結(jié)點(diǎn)民假，然而這種方式有時(shí)并不可行贰盗，特別是集群規(guī)模特別大時(shí)，無法解決單點(diǎn)故障阳欲。

????????本地索引：

????????每個(gè)結(jié)點(diǎn)保存自己的資源信息，當(dāng)尋找不屬于自己的資源時(shí)陋率，會(huì)flooding整個(gè)網(wǎng)絡(luò)進(jìn)行尋找球化。這種flooding的方式會(huì)在網(wǎng)絡(luò)中引起大量的traffic，并使每個(gè)結(jié)點(diǎn)都要處理查詢請(qǐng)求而導(dǎo)致高CPU和內(nèi)存使用率瓦糟。并且flooding不保證通信質(zhì)量筒愚，所以flooding也無法保證一定能夠找到保存指定數(shù)據(jù)的那個(gè)結(jié)點(diǎn)。因?yàn)闊釘?shù)據(jù)在多個(gè)結(jié)點(diǎn)上存在菩浙，所以比較容易搜索成功巢掺。反之，冷數(shù)據(jù)只在很少的結(jié)點(diǎn)上存在劲蜻，所以搜索很可能會(huì)以失敗告終陆淀。并且搜索效率也很低，也容易導(dǎo)致安全問題先嬉。

????????分布式索引：

????????為了高效地在網(wǎng)絡(luò)中搜索轧苫，結(jié)點(diǎn)需要保存滿足特定條件的鄰居的列表，這使得整個(gè)網(wǎng)絡(luò)在高頻率的添加刪除結(jié)點(diǎn)時(shí)疫蔓，沒有非結(jié)構(gòu)化網(wǎng)絡(luò)那樣健壯含懊。使用DHT路由的結(jié)構(gòu)化P2P網(wǎng)絡(luò)的著名軟件有BitTorrent，Kad Network衅胀，以及各種研究項(xiàng)目Chord等岔乔。基于DHT的網(wǎng)絡(luò)在網(wǎng)絡(luò)計(jì)算系統(tǒng)中也有廣泛的應(yīng)用滚躯，它幫助實(shí)現(xiàn)高效的資源發(fā)現(xiàn)和應(yīng)用程序調(diào)度等

三雏门、分布式索引--- KAD算法：

????????KAD算法全程Kademlia，在實(shí)際的DHT路由中哀九，大部分都是采用KAD這種變種來實(shí)現(xiàn)的剿配，BT、eDonkey/電驢阅束、eMule/電騾呼胚， I2P 暗網(wǎng)等等，其中以太坊中也采用KAD算法來實(shí)現(xiàn)路由的息裸。

(一)蝇更、"最短距離"的概念

????????當(dāng)從P2P網(wǎng)絡(luò)中查詢某一條數(shù)據(jù)時(shí)沪编，為了避免泛洪查找，首先要定位到離數(shù)據(jù)的KEY最近的一個(gè)節(jié)點(diǎn)年扩，然后從該節(jié)點(diǎn)上提取所需要的數(shù)據(jù)蚁廓。那么這個(gè)最短距離如何確定呢？

????????首先厨幻，我們獲取到P2P中所有節(jié)點(diǎn)的nodeId相嵌，經(jīng)過hash算法，表示成某一固定長度的二進(jìn)制接口况脆。同理饭宾，用同樣的hash對(duì)數(shù)據(jù)key進(jìn)行hash并表示為二進(jìn)制。然后對(duì)數(shù)據(jù)key和nodeId計(jì)算其異或距離格了，找到其中距離最小值就是我們的最短距離看铆。

????????假如hash完后的數(shù)據(jù)二進(jìn)制長度為3位，并且存在4臺(tái)服務(wù)器盛末。 data key的值為101弹惦，按照data key 和node id的同構(gòu)原理，應(yīng)該是尋找節(jié)點(diǎn)101悄但， 但是該節(jié)點(diǎn)不存在棠隐，故需要尋找距離最短的節(jié)點(diǎn)，也就是100節(jié)點(diǎn)檐嚣。故應(yīng)該從nodeId = 100這臺(tái)機(jī)器上查詢當(dāng)前的數(shù)據(jù)宵荒。

注意：這里的距離并非真實(shí)的距離，而是邏輯距離净嘀。

(二)报咳、邏輯拓?fù)浣Y(jié)構(gòu) 和 K-Buckets K桶

????????在P2P的網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都保存了其他節(jié)點(diǎn)的信息挖藏。當(dāng)我請(qǐng)求其中一個(gè)節(jié)點(diǎn)時(shí)暑刃，該節(jié)點(diǎn)如何快速的定位到數(shù)據(jù)是位于哪個(gè)節(jié)點(diǎn)上呢？那么其他節(jié)點(diǎn)信息在當(dāng)前節(jié)點(diǎn)中如何存儲(chǔ)膜眠，這就是邏輯拓?fù)浣Y(jié)構(gòu)要解決的問題了岩臣。

????????現(xiàn)在假如 nodeId 經(jīng)過hash后 的位數(shù)還是3位，那么理論上整個(gè)網(wǎng)絡(luò)中就可以存在2^3 = 8 個(gè)節(jié)點(diǎn)宵膨。節(jié)點(diǎn)包括：

001架谎，010，011辟躏，000谷扣，100，101捎琐，110会涎，111

????????我們將每個(gè)節(jié)點(diǎn)的表示為二進(jìn)制后裹匙，按照左0右1構(gòu)建如下二叉樹。其中不難發(fā)現(xiàn)末秃，所有的葉子節(jié)點(diǎn)就是我們的服務(wù)器節(jié)點(diǎn)概页。如下圖

????????如圖，當(dāng)前節(jié)點(diǎn)為101练慕， 那么該節(jié)點(diǎn)如何存儲(chǔ)其他節(jié)點(diǎn)惰匙，以方便快速定位呢？ 這里采用分層铃将。

????????首先計(jì)算每個(gè)節(jié)點(diǎn)與 當(dāng)前節(jié)點(diǎn)101的距離徽曲， 按照一定距離進(jìn)行分層。

? ??????分層規(guī)則: 定義從最右位開始麸塞，第一次開始出現(xiàn)不同位時(shí)，則表示為同一層涧衙。

????????按照入上規(guī)則進(jìn)行分層哪工，可以看出，第一層與當(dāng)前節(jié)點(diǎn)的距離是最短的弧哎，層數(shù)越高雁比，節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離越遠(yuǎn)。

????????此時(shí)撤嫩，如果當(dāng)前節(jié)點(diǎn)接收到查詢請(qǐng)求偎捎，先將數(shù)據(jù)的key 按照同樣的hash算法，然后表示為二進(jìn)制序攘， 假如data key = 100 茴她。 首先將data key 與當(dāng)前節(jié)點(diǎn) nodeId = 101 進(jìn)行距離計(jì)算(異或)， 其中異或結(jié)果就代表了當(dāng)前數(shù)據(jù)節(jié)點(diǎn)所在的層程奠。 100 ^101 = 1 丈牢， 故存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)在第一層，然后定位到100節(jié)點(diǎn)瞄沙，向100節(jié)點(diǎn)發(fā)送查詢請(qǐng)求己沛。

????????此時(shí)可以發(fā)現(xiàn)，不用利用泛洪式查找就能快速定位到資源所在的位置距境。加入現(xiàn)在資源定位在第3層申尼，那么我只要遍歷二叉樹中的左面四個(gè)節(jié)點(diǎn)就可以，避免了遍歷整個(gè)子樹的問題垫桂。

? ??????K-Buckets:

????????由于我們舉例中的節(jié)點(diǎn)只有三位师幕，但是現(xiàn)實(shí)中龐大的集群網(wǎng)絡(luò)節(jié)點(diǎn)可能會(huì)存在上萬個(gè)節(jié)點(diǎn)。比如以太坊中的位數(shù)為256位诬滩，那么網(wǎng)絡(luò)中理論上就可以存在2^256個(gè)節(jié)點(diǎn)们衙。

????????當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量不斷擴(kuò)張時(shí)钾怔，不可能在每個(gè)節(jié)點(diǎn)上都存儲(chǔ)所有其他節(jié)點(diǎn)的信息。 從上例也可以看出蒙挑，位數(shù)的增加宗侦，層數(shù)也不斷增加，而越高層存儲(chǔ)的信息也就越多忆蚀。

? ??????所以 Kad 論文中給出了一個(gè)“K-桶(K-bucket)”的概念矾利。也就是說：每個(gè)節(jié)點(diǎn)在完成子樹拆分后，要記錄每個(gè)子樹里面的 K 個(gè)節(jié)點(diǎn)馋袜。這里所說的 K 值是一個(gè)【系統(tǒng)級(jí)】的常量男旗。

????????也就是說每一層，我們最多存儲(chǔ)K個(gè)節(jié)點(diǎn)欣鳖。因?yàn)橹灰喇?dāng)前子樹的一個(gè)節(jié)點(diǎn)察皇，理論上我們就可以知道并能夠遍歷當(dāng)前子樹的所有節(jié)點(diǎn)。那為什么不存儲(chǔ)一個(gè)呢泽台？ 因?yàn)榉植际较碌墓?jié)點(diǎn)的動(dòng)態(tài)變化的什荣，如果當(dāng)前節(jié)點(diǎn)宕機(jī)，就會(huì)影響該子樹怀酷。故可以根據(jù)系統(tǒng)自身的特性來調(diào)整K值的大小稻爬。比如BT設(shè)定K = 8, 以太坊中設(shè)定為16.

????????其中，每層中存儲(chǔ)的節(jié)點(diǎn)的順序是按照與當(dāng)前節(jié)點(diǎn)的由近及遠(yuǎn)來存儲(chǔ)的蜕依。

(三)桅锄、KAD節(jié)點(diǎn)的更新機(jī)制

????????當(dāng)節(jié)點(diǎn) 收到一個(gè) PRC 消息時(shí)，發(fā)送者B的節(jié)點(diǎn)信息就被用來更新對(duì)應(yīng)的 K 桶样眠，具體步驟如下：

????????1友瘤、計(jì)算發(fā)送者節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離。

????????2檐束、根據(jù)距離選擇位于K桶第幾層

????????3商佑、如果發(fā)送者B已經(jīng)存在于K桶中，則移動(dòng)B節(jié)點(diǎn)到最前面

????????4厢塘、如果B不在K桶中茶没，且桶中數(shù)量小于K個(gè)，則添加B節(jié)點(diǎn)信息到K桶末尾

????????5晚碾、如果B不在K桶中抓半，且桶中的數(shù)據(jù)量大于K個(gè)，先給桶中末尾節(jié)點(diǎn)發(fā)送PING消息：

????????????????????????????????如果收到回復(fù)格嘁，則忽略B節(jié)點(diǎn)笛求。

????????????????????????????????如果未收到回復(fù)，則刪除末尾節(jié)點(diǎn)，加入B節(jié)點(diǎn)探入。

????????原因如下:?

?????????????K 桶的更新機(jī)制的實(shí)現(xiàn)依賴于一個(gè)理論：用戶在線時(shí)間越長狡孔，它在下一時(shí)段繼續(xù)在線的可能性就越高。? ??? ??這種機(jī)制的另一個(gè)好處是能在一定程度上防御 DOS 攻擊蜂嗽，因?yàn)橹挥挟?dāng)老節(jié)點(diǎn)失效后苗膝，Kad 才會(huì)更新 K 桶的信息，這就避免了通過新節(jié)點(diǎn)的加入來泛洪路由信息植旧。

(四)辱揭、KAD的UDP通信協(xié)議：

? ? ? ? 1、PING事件:? 校驗(yàn)節(jié)點(diǎn)是否存活

? ? ? ? 2病附、PONG事件：對(duì)PING事件的回復(fù)

????????3问窃、FIND_NODE事件：向節(jié)點(diǎn)查詢某個(gè)與目標(biāo)節(jié)點(diǎn)ID距離接近的節(jié)點(diǎn)

????????4、NEIGHBORS事件：對(duì)FIND_NODE命令響應(yīng)完沪，發(fā)送與目標(biāo)節(jié)點(diǎn)ID距離接近的K桶中的節(jié)點(diǎn)域庇。

(五)、KAD的路由查詢機(jī)制：

????????假如集群中的某個(gè)節(jié)點(diǎn)A收到一個(gè)FIND_NODE請(qǐng)求覆积，要求查詢 與ID為m的節(jié)點(diǎn)最近的節(jié)點(diǎn)信息,具體的步驟如下：

????????1听皿、計(jì)算當(dāng)前A節(jié)點(diǎn)ID與M的距離：

????????2、鎖定到K桶的層技健，并從中獲取aplha個(gè)節(jié)點(diǎn)，如果節(jié)點(diǎn)數(shù)不足alpha惰拱，則從附近的桶中獲取節(jié)點(diǎn)雌贱。

????????3、同時(shí)向alpha個(gè)節(jié)點(diǎn)發(fā)送FIND_NODE請(qǐng)求偿短。

????????4欣孤、接收到FIND_NODE的節(jié)點(diǎn)，如果發(fā)現(xiàn)自己的ID是m則返回昔逗。從自己K桶中選擇距離最近的alpha個(gè)節(jié)點(diǎn)返回降传。

????????5、當(dāng)節(jié)點(diǎn)A接收到返回的數(shù)據(jù)時(shí)勾怒，如果有m則返回婆排，如果沒有m，則再次向返回的alpha個(gè)節(jié)點(diǎn)發(fā)送FIND_NODE請(qǐng)求繼續(xù)查找笔链，如此循環(huán)段只，直至遍歷完所有的節(jié)點(diǎn)。

????????其中在BitTorrent和以太坊中設(shè)定alpha = 3鉴扫。

????????原因如下：

????????????????由于每次查詢都能從更接近 m 的 K 桶中獲取信息赞枕，這樣的機(jī)制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少 1 bit）的效果，從而保證整個(gè)查詢過程的收斂速度為?O(logN)?，這里 N 為網(wǎng)絡(luò)全部節(jié)點(diǎn)的數(shù)量炕婶。

? ??????????????借用網(wǎng)絡(luò)上一張圖描述其查找的過程: