簡介

提及去中心化區塊鏈，P2P網路作為區塊鏈系統的核心組件必然是每個區塊鏈開發者應當了解的，本文旨在通過重點介紹以太坊P2P網路的Kademlia協議，拋磚引玉，希望有不同見解的讀者在評論區做更深入的交流，

從中心化到去中心化的網路

傳統的客戶端（Client）-服務器（Server）的模型中，可擴展性的短板與單點故障的問題，是與以服務器為中心的架構分不開的，去中心化的區塊鏈世界中，換個角度又是“人人都是中心”，

對等網路，即對等計算機網路，是一種在對等者（Peer）之間分配任務和作業負載的分布式應用架構，是對等計算模型在應用層形成的一種組網或網路形式，“Peer”在英語里有“對等者、伙伴、對端”的意義，因此，從字面上，P2P可以理解為對等計算或對等網路，其可以定義為：網路的參與者共享他們所擁有的一部分硬體資源（處理能力、存盤能力、網路連接能力、列印機等），這些共享資源通過網路提供服務和內容，能被其它對等節點（Peer）直接訪問而無需經過中間物體，在此網路中的參與者既是資源、服務和內容的提供者（Server），又是資源、服務和內容的獲取者（Client），[^1]

P2P網路完美的服務于區塊鏈去中心化，自組織的平等思想，

從數學的角度上來講，P2P網路可以看做一個有向圖，理想情況下，所有的對等節點間都應該有一條路徑相連，隨著節點的增多，如何在個體有限資源下保證整個圖的連通性就成為我們亟待解決的問題,因此只能保證每個節點對網路拓撲和其他對等節點只有一個不完整的視圖，對每個對等節點來說，圖的連通性通過與其他對等節點的鄰接關系來反映，所以網路覆寫層需要中間節點將訊息轉發至正確目的地，圖的結構為每對節點提供了多條中間路徑，因此如何尋找最優的路徑查找特定網路節點，即節點路由技術，區塊鏈系統對于每個節點如何處理節點與存盤物件之間的映射關系，對等節點的改變（加入與離開網路），鄰接的對等節點可能會持有不正確的鄰接資訊，如何使用網路覆寫層維護機制（Overlay maintenance mechanisms）保存更新的鄰接資訊，使得所有節點間保持連通性，

Kademlia協議

背景

Kademlia是美國紐約大學的 P. Maymounkov 和 D. Mazieres 在2002年發布的一項研究結果，Kademlia是一種分布式哈希表（DHT），是第三代對等網路的節點動態管理和路由協議，

與前兩代協議如 Chord、CAN、Pastry 等相比，Kad以全域唯一id標記對等網路節點，以節點ID異或（XOR）值度量節點之間距離，并通過距離分割子樹構建路由表，建立了一種全新的網路拓撲結構，相比于其他演算法，更簡單，更高效，

網路拓撲的構建

對于每一個節點使用唯一的ID去標識，以太坊使用了256位哈希空間（原始Kad演算法160位）作為NodeId，那么理論上就可容納2^256個節點，每個節點的位置利用其Id值的最短前綴可以唯一確定，那么使用一顆以最短前綴為葉子節點的二叉樹來構建整個網路拓撲是比較合適的，其中每個葉子節點代表一個網路節點，至此一個完整而無冗余的網路拓撲就被構建好了，

構造路由表

正如前文所訴，保證每個節點對網路拓撲和其他對等節點只有一個不完整的視圖，對每個對等節點來說，圖的連通性通過與其他對等節點的鄰接關系來反映，我們需要對整個網路拓撲進行分割，分割出屬于每個節點自己的部分，即對于以每個節點自己的視角完成子樹拆分：根據公共前綴長度將這顆二叉樹分解為一系列不包含自己的子樹，頂層的子樹，由整棵不包含自己的樹的另一半組成，即與節點之間的公共前綴長度為0；下一層子樹由剩下部分不包含自己的一半組成，即公共前綴長度為1；依此類推，直到分割完整棵樹，

每個節點在完成子樹拆分后，僅需保證每個子樹中至少一個節點可達，經過迭代的查找是能夠遍歷整個網路的每一個節點的，但因為分布式下節點是動態更新的，所以要記錄每個子樹里面的 K 個節點，這里所說的 K 值是一個系統級的常量，通常是偶數，以太坊的K值設定為16，協議中定義這樣的每一個子樹為K-Bucket，K-桶；那么構造的路由表Routing-Table就是一個K-Bucket List，

路由查找

對于特定網路節點的查找，Kad演算法的核心思想是逐步迭代，遞進查找，首先是計算XOR距離，這是一個邏輯上的距離，
由之前子樹拆分的圖及其劃分可以得出根據目標節點與本地節點XOR距離能夠找到對應層的K-Bucket，從層中獲取α個節點，不足則從附近的桶中獲取（幸運的是此情況大多數是目標節點已經非常接近本地節點了），

每次迭代查找的距離至少減半，可以看出整個查詢是收斂的，且時間復雜度為O（log N），

節點通信

Kademlia 協議包括四種遠程 RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE，

1. PING ：探測一個節點，用以判斷其是否仍然在線，
2. STORE : 通知一個節點存盤一個 <key,value> 對，以便以后查詢需要，
3. FIND_NODE : 操作使用一個 160 bit 的 ID 作為引數，本操作的接受者回傳它所知道的更接近目標 ID 的 K 個節點的 (IP address, UDP port, Node ID) 資訊，
4. FIND_VALUE : 回傳一個節點的 (IP address, UDP port, Node ID) 資訊，如果本操作的接受者收到同一個 key 的 STORE 操作，則會直接回傳存盤的 value 值，

GETH中Kad的UDP通信

1. PING: 校驗節點是否存活
2. PONG: 對PING事件的回復
3. FIND_NODE: 向節點查詢某個與目標節點ID距離接近的節點
4. NEIGHBORS: 對FIND_NODE命令回應，發送與目標節點ID距離接近的K桶中的節點

K-Bucket更新

K-Bucket即K-桶，以前文所述的子樹的劃分來定義每個K-桶，每個K-桶內維護的節點數存在上限，節點的離開與加入則使我們需要一定的演算法來進行更新K-桶，
當節點 x 收到一個 PRC 訊息時，發送者 y 的 IP 地址就被用來更新對應的 K 桶

這樣就高效的實作了一種把最近看到的節點更新的策略，這種更新策略由節點的在線時長與繼續在線的概率關系決定，

Gnutella showed that the longer a node is up,the more likely it is to remain up for one more hour.

除非在線節點一直未從 K 桶中移出過，也就是說在線時間長的節點具有較高的可能性繼續保留在 K 桶串列中，對 Kad 網路的穩定性和減少網路維護成本（不需要頻繁構建節點的路由表）帶來很大好處，

這種機制的另一個好處是能在一定程度上防御 DOS 攻擊，因為只有當老節點失效后，Kad 才會更新 K 桶的資訊，這就避免了通過新節點的加入來泛洪路由資訊，

為了防止 K 桶老化，所有在一定時間之內無更新操作的 K 桶，都會分別從自己的 K 桶中隨機選擇一些節點執行 RPC_PING 操作，

上述這些 K 桶機制使 Kad 緩和了流量瓶頸（所有節點不會同時進行大量的更新操作），同時也能對節點的失效進行迅速回應，

物件與節點的映射（資料存盤）

使用Kademlia網路構建大規模分布式存盤系統，需要解決以下兩個核心問題：

1. 建立物件與網路節點之間的映射
2. 節點動態變化時保證物件的可訪問

建立物件與節點的映射，一般有兩種方法：

1. 查表：維護全域<物件，節點>映射表
2. 計算：直接根據物件特征，通過數學運算得到目標節點

很明顯我們只能選擇第二種方法，但是又導致了下列問題

• 物件<key, value>被存盤在與key距離最接近的?K個節點，如果? K個節點全部離線，那么物件便不可達，
• 物件<key, value>被存盤在與key距離最接近的K個節點，如果網路新加入節點N且?N距離key更接近，物件也需要進行一次遷移，因為下次去查找的時候，會直接定位到N，如果資料不遷移至?N，那物件雖然資料存在，但也是不可達，

解決上述問題有兩種解決方案：

• PULL：如果新增一個節點?N，且?距離某物件?O更為接近，此時某節點訪問物件?內容，根據演算法很可能被定位至節點N?上，?此時再去?當前所在的節點上Pull資料回傳給物件訪問者；
• PUSH: 如果新增一個節點N，且?距離某物件?O的更為接近，一旦物件?所在的節點探測到N的存在，會主動地將?資料推至N，這也可以保證下次訪問?時無需中轉而直接獲取到資料，

對比兩種方案:

• PULL：新增節點?需要了解物件?此時所在節點位置，這是做不到的，?可以根據自身路由表計算出當前距離?最接近的節點，但是沒法知道前一個時刻距離?最接近的節點；而且該方案沒法處理節點批量離線導致的物件不可訪問問題，
• PUSH: 探測到新節點?加入，然后計算本地存盤的物件中有哪些距離?更為接近，將這些接近的物件push至此?，當然，這種做法也無法時刻都在做，因為在大量節點的P2P網路中，節點變更是常態，一種比較合理的方式是定期做檢查，但是該方案依賴于?能夠感知到新增?的存在，好在，?需要遷移物件的一定是距離?很接近的節點，在我們前面新增節點流程描述中可以知道一個新增節點上線時，演算法會偏向于將該新增節點通知到距離其更近的節點中，因此，一旦一個新節點上線，那么距離其接近的節點就會更快地了解到該節點資訊，從而將其本地存盤的資料可以push至新增節點，

通過對比可確認PUSH才是切實可行的，而且符合P2P網路的松耦合的設計，但是該方案也并非完美：一旦有新增節點可能就會帶來大量的資料拷貝，消耗大量資源，萬事萬物總是這樣，在識訓好處的同時總得付出代價，在論文中，作者提出了按照小時為單位執行Re-Publishing：每個小時，每個節點?對本地存盤的每一個物件?進行Re-Publishing，每一次Re-Publishing包括下面兩個步驟:

1. 首先查詢?當前最近的K個節點資訊
2. 節點?向1中獲得的節點發送資料存盤訊息，從而完成資料更新

針對每個節點的每個物件都執行類似操作，會導致P2P網路出現突激的網路流量，仔細分析上面的行為，我們可以發現，其實很多的Re-Publishing是無用的：

• 如果在一個小時的周期內，網路拓撲沒有發生變化，那根本不需要進行Re-Publishing；

• 對于不同的節點、?，如果物件?在節點、?上均已存盤，那其實在一個Re-Publishing周期內，只需要一個節點(?或者?)來更新?即可，沒必要大家同時一起上，浪費資源；

• 步驟1中的查詢當前最近是否有必要：因為根據上面的表述，對于新增節點，其實是可以很快速地反映到最近節點路由表，所以一般情況下，查詢本地節點路由表即可，

最終存放<key,value>對資料的解決方案為：

1. 發起者首先定位 K個ID值最接近key的節點
2. 發起者對這K個節點發起STORE操作
3. 執行 STORE 操作的K個節點每小時重發布自己所有的 <key,value>對資料
4. 為了限制失效資訊，所有<key,value>對資料在初始發布24小時后過期
5. 另外，為了保證資料發布、搜尋的一致性，規定在任何時候，當節點 O發現新節點N比O上的某些<key,value>物件資料更接近，則O把這些<key,value>物件資料復制到N上，但是并不會從O上洗掉，
6. 最后，一旦有節點 FIND_VALUE 操作成功執行，則 <key,value>物件資料會快取在沒有回傳value值的最接近的節點上，這樣下一次查詢相同的key時就會更加快速的得到結果，通過這樣的方式，熱門 <key,value> 對資料的快取范圍就逐步擴大，使系統具有極佳的回應速度(cache為存活24小時，但是目標節點上的內容時每1小時向其他最近節點重新發布<key, value>使得資料的超時時間得以重繪，而遠離目標節點的節點的資料存活時間當然就可能不會被重新發布到，所以也就是資料快取的超時時間和節點的距離成反比)，

參考

《Peer-To-Peer綜述》—中科院計算技術研究所
https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf
https://zhuanlan.zhihu.com/p/38425656
https://www.cnblogs.com/1314xf/p/14019453.html