點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)是區(qū)塊鏈中核心的技術(shù)之一，主要關(guān)注的方面是為區(qū)塊鏈提供一個(gè)穩(wěn)定的網(wǎng)絡(luò)結(jié)構(gòu)，用于廣播未被打包的交易（交易池中的交易）以及共識(shí)過(guò)的區(qū)塊，部分共識(shí)算法也需要點(diǎn)對(duì)點(diǎn)的網(wǎng)絡(luò)支撐（如PBFT），另外一個(gè)輔助功能，如以太坊的消息網(wǎng)絡(luò)，也需要點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的支持。

分類

P2P網(wǎng)絡(luò)分為結(jié)構(gòu)化和非結(jié)構(gòu)化網(wǎng)絡(luò)兩類。結(jié)構(gòu)化網(wǎng)絡(luò)采用類似DHT算法來(lái)構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)；非結(jié)構(gòu)化網(wǎng)絡(luò)是一種扁平的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)都有一些鄰居節(jié)點(diǎn)的地址。

點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)職責(zé)

點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的主要職責(zé)有維護(hù)網(wǎng)絡(luò)結(jié)構(gòu)和發(fā)送信息這兩個(gè)方面。網(wǎng)絡(luò)結(jié)構(gòu)要關(guān)注的是新節(jié)點(diǎn)的加入和網(wǎng)絡(luò)更新這兩個(gè)方面，而發(fā)送信息包括廣播和單播兩個(gè)方面

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

如何建立并維護(hù)點(diǎn)對(duì)點(diǎn)的整個(gè)網(wǎng)絡(luò)？節(jié)點(diǎn)如何加入、退出？
網(wǎng)絡(luò)結(jié)構(gòu)的建立有兩個(gè)核心的參數(shù)，一個(gè)是每個(gè)節(jié)點(diǎn)向外連接的節(jié)點(diǎn)數(shù)，第二個(gè)是最大轉(zhuǎn)發(fā)數(shù)。

新節(jié)點(diǎn)

新節(jié)點(diǎn)對(duì)于整個(gè)網(wǎng)絡(luò)一無(wú)所知，要么通過(guò)一個(gè)中心的服務(wù)獲取網(wǎng)絡(luò)中的一些節(jié)點(diǎn)去連接，要么去連接網(wǎng)絡(luò)中的“種子”節(jié)點(diǎn)。

網(wǎng)絡(luò)更新

網(wǎng)絡(luò)更新處理當(dāng)有新節(jié)點(diǎn)加入或者節(jié)點(diǎn)退出，甚至原來(lái)一些節(jié)點(diǎn)網(wǎng)絡(luò)不好，無(wú)法連接，過(guò)一段時(shí)間又活了，等等這些情況。一般通過(guò)節(jié)點(diǎn)已有的連接來(lái)廣播這些路由表的變化。需要注意的是，因?yàn)辄c(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的特殊性，每個(gè)節(jié)點(diǎn)的路由表是不一樣的（也叫partial view）

消息收發(fā)

廣播

廣播一般采用泛洪協(xié)議，即收到轉(zhuǎn)發(fā)方式，使的消息在網(wǎng)絡(luò)中擴(kuò)散，一般要采用一些限制條件，比如一條消息要設(shè)置最大的轉(zhuǎn)發(fā)數(shù)，避免網(wǎng)絡(luò)的過(guò)渡負(fù)載。

單播

單播需要結(jié)構(gòu)化網(wǎng)絡(luò)結(jié)構(gòu)支持，一般是DHT，類似于DNS解析的方式，逐跳尋找目標(biāo)節(jié)點(diǎn)地址，之后進(jìn)行傳輸，并且更新本地路由表。

DHT-分布式hash表

要想快速檢索信息，有兩種數(shù)據(jù)結(jié)構(gòu)可以使用，一種是樹(shù)類型，如AVL樹(shù)、紅黑樹(shù)、B樹(shù)等；另外一類是hash表。
哈希表的效率比樹(shù)更高，但是需要占用更多的內(nèi)存。
信息的表示采用鍵值對(duì)的方式，即一個(gè)鍵對(duì)應(yīng)一個(gè)值，我們要查找的是key，值是附著的信息。
哈希表要解決的問(wèn)題是如何均勻地為每一個(gè)key分配一個(gè)存儲(chǔ)位置。
這里面有兩個(gè)重點(diǎn)：1.是為key分配一個(gè)存儲(chǔ)地點(diǎn)，這個(gè)分配算法是固定的，保證存儲(chǔ)的時(shí)候和查找的時(shí)候使用同一個(gè)算法，不然存進(jìn)去之后會(huì)找不到；2.是均勻地分配，不能有點(diǎn)地方存放數(shù)據(jù)多，有點(diǎn)放存放數(shù)據(jù)少。

本地hash表

一般語(yǔ)言里面的hashtable、map等結(jié)構(gòu)使用這個(gè)技術(shù)來(lái)實(shí)現(xiàn)，哈希函數(shù)可以直接使用取模函數(shù)，key%n，這種方式，n代表有多少個(gè)地方，key是整數(shù)，如果key是其他類型，需要先進(jìn)行一次哈希，將key轉(zhuǎn)為整數(shù)。這種方式可以解決上面的兩個(gè)需求，但是當(dāng)n不夠大的時(shí)候（小于要存儲(chǔ)的數(shù)據(jù)），會(huì)產(chǎn)生沖突，一個(gè)地方一定會(huì)有兩個(gè)key要存儲(chǔ)，這時(shí)候，需要在這個(gè)地方放一個(gè)鏈表，將分配到同一地點(diǎn)、不同key，順序擺放。當(dāng)一個(gè)地點(diǎn)放的key太多后，鏈表的查找速度太慢，要轉(zhuǎn)化為樹(shù)類型結(jié)構(gòu)（紅黑樹(shù)或者AVL樹(shù)）。

分布式哈希表

上面說(shuō)過(guò)，哈希表效率很高，但是占用內(nèi)容，使用多臺(tái)機(jī)器就可以解決這個(gè)限制。在分布式環(huán)境中，可以將上述的地點(diǎn)理解為計(jì)算機(jī)（后面成為節(jié)點(diǎn)），即如何將一個(gè)key映射到一個(gè)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)有一個(gè)節(jié)點(diǎn)ID，即key->node id的映射，這個(gè)映射算法也要固定。
這個(gè)算法還有一個(gè)非常重要的要求，即scalebility,當(dāng)新節(jié)點(diǎn)加入和退出時(shí)候，需要遷移的key要盡量少。

這個(gè)映射算法有兩種典型結(jié)構(gòu)，一個(gè)是環(huán)形，一個(gè)是樹(shù)形；環(huán)形的叫一致性哈希算法，樹(shù)形的典型叫kademlia算法。

選點(diǎn)算法

選點(diǎn)算法就是解決key->node id的映射算法，形象的來(lái)說(shuō)就是為一個(gè)key選擇它生命中的她（節(jié)點(diǎn)）。

一致性哈希(chod)

假設(shè)我們使用32哈希，那么總共能容納的key的數(shù)據(jù)量是2**32，稱之為hash空間，把節(jié)點(diǎn)的ID映射成整數(shù)，key也映射成整數(shù)。把key哈希和節(jié)點(diǎn)哈希值接的差值的叫做距離（負(fù)數(shù)的話要取模，不用絕對(duì)值），比如一個(gè)key的哈希是100（整數(shù)表示），一個(gè)節(jié)點(diǎn)的哈希是105，則這兩個(gè)的距離是105-100=5。當(dāng)然使用其他距離表示也可以，比如反過(guò)來(lái)減，但是算法要固定。我們把key映射（放到）距離他最近的節(jié)點(diǎn)上。距離取模的話，看起來(lái)就是把節(jié)點(diǎn)和key放到一個(gè)環(huán)上，key歸屬到從順時(shí)針角度離它最近的節(jié)點(diǎn)上。

kademlia

kademlia算法的距離采用的是key哈希與節(jié)點(diǎn)哈希異或計(jì)算之后的數(shù)值來(lái)表示（整數(shù)），從左往右，擁有越多的“相同前綴”，則距離越近，越在左邊位置不一樣，距離越遠(yuǎn)。
樹(shù)結(jié)構(gòu)的體現(xiàn)是，將節(jié)點(diǎn)和key看成樹(shù)的節(jié)點(diǎn)，這個(gè)算法支持的位數(shù)是160bit，即20個(gè)8字節(jié)，樹(shù)的高度為160，每個(gè)邊表示一位。
選點(diǎn)的算法和一致性哈希相同，從所有節(jié)點(diǎn)中，選擇一個(gè)距離key距離最小的節(jié)點(diǎn)作為這個(gè)key的歸宿。

路由算法

由于是在分布式環(huán)境中，為了保證高可用，我們假設(shè)沒(méi)有一個(gè)中心的路由表，沒(méi)有這個(gè)可以看到全貌的路由表，帶來(lái)了一些挑戰(zhàn)，比如如何發(fā)現(xiàn)節(jié)點(diǎn)、查找節(jié)點(diǎn)？
在P2P網(wǎng)絡(luò)中，常用的方法是每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)部分路由表，即只包含部分節(jié)點(diǎn)的路由信息。在泛洪算法中，這些節(jié)點(diǎn)上隨機(jī)的；在DHT算法中，這個(gè)路由表是有結(jié)構(gòu)的，維護(hù)的節(jié)點(diǎn)也是有選擇性的。那么如何合理的選擇需要維護(hù)路由信息的節(jié)點(diǎn)呢？

一致性哈希(chod)

一個(gè)樸素的做法是，每一個(gè)節(jié)點(diǎn)保存比他大的節(jié)點(diǎn)的信息，這樣可以組成一個(gè)環(huán)，但是這樣做的話，有一個(gè)大問(wèn)題和一個(gè)小問(wèn)題。大問(wèn)題是，每個(gè)節(jié)點(diǎn)知道的信息太少(只有下一個(gè)節(jié)點(diǎn)的哈希和地址)，當(dāng)給出一個(gè)key時(shí)，它不知道網(wǎng)絡(luò)中還有沒(méi)有比它距離這個(gè)key距離還短的節(jié)點(diǎn)，所以它首先判斷key是否屬于自己和下一個(gè)節(jié)點(diǎn),如果是，那么這個(gè)key就屬于下一個(gè)節(jié)點(diǎn)，如果不是就調(diào)用下一個(gè)節(jié)點(diǎn)同樣的方法，這個(gè)復(fù)雜度是N(節(jié)點(diǎn)數(shù))。一個(gè)優(yōu)化的方法是，每個(gè)節(jié)點(diǎn)i維護(hù)的其他節(jié)點(diǎn)有：i+21, i+22,…i+2**31,通過(guò)觀察這個(gè)數(shù)據(jù)，發(fā)現(xiàn)由近到遠(yuǎn)，節(jié)點(diǎn)越來(lái)越稀疏。這樣可以把復(fù)雜度降低到lgN

kademlia

每個(gè)節(jié)點(diǎn)保存的其他節(jié)點(diǎn)的信息，包括，從左到右，每一位上與本節(jié)點(diǎn)不同的節(jié)點(diǎn)，最多選擇k個(gè)（算法的超參數(shù)）。比如在節(jié)點(diǎn)00110上（為演示起見(jiàn)，選擇5位），在要保存的節(jié)點(diǎn)路由信息是：
1****: xxx,…,xxx(k個(gè))
01***: xxx,…,xxx(k個(gè))
000**: xxx,…,xxx(k個(gè))
0010*: xxx,…,xxx(k個(gè))
00111: xxx,…,xxx(k個(gè))
以上為一行稱為k-bucket。形象的來(lái)看，也是距離自己越近，節(jié)點(diǎn)越密集，越遠(yuǎn)，節(jié)點(diǎn)越稀疏。這個(gè)路由查找、節(jié)點(diǎn)查找的算法也是lgN復(fù)雜度。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-416238.html

到了這里，關(guān)于區(qū)塊鏈核心技術(shù)-P2P網(wǎng)絡(luò)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！