kademlia（卡德米利亞）算法原理介紹

• 前言
• 分布式海量存儲結構
• 邏輯上的結構
• 邏輯上的節點與節點間距
• K bucket
• 如何更新K bucket中的節點信息
• 一個嶄新的節點希望加入Kad網絡
• 如何find_node?
• 如何find_value

前言

感覺碰到這個算法的過程有點莫名其妙？本來是老老實實學習計算機網絡協議的，碰到遇到了應用層的p2p協議，然后就了解了分布式網絡，然后就了解了DHT，最后就到了這個kad算法（其實人家是一個協議，實現了DHT好吧）。開整！

分布式海量存儲結構

我寫這個標題就有點唬人，不過確實這種結構可以適合海量數據的存儲。這是一種去中心化的存儲，在整個網絡中node與node之間的傳輸查詢或者其他操作都是沒有中心服務器的參與的。放張圖可能你就能理解了。

老的p2p協議確實在數據傳輸上是peer to peer的，不需要中心服務器tracker的參與。可是某一peer請求數據的時候，需要先訪問tracker服務器，然后服務器告訴該peer，哪個peer上有你要的資源，然后把對應的ip地址給你。這一操作就差點意思了兄弟，要是tracker服務器壞掉了，那不就直接GG？
于是呢，一種分布式存儲結構就出現了，叫distribute_hash_table，即分布式哈希表，它是用來干啥的呢？反正從我的角度看，DHT直接干掉了tracker服務器，讓網絡中的每一個節點都有著相等的地位，且互相交換數據做到了真正的peer to peer。現在是不是非常好奇，究竟是如何實現的呢？

邏輯上的結構

首先呢，每一個加入網絡的家伙，都會根據哈希算法，生成一個獨特的節點id，長度呢就看你喜歡了，比如說長度是200bit。（長度大家都是固定一樣的）然后呢，邏輯上將所有的節點放在一顆巨大無比的二叉樹中。肯定沒有真的放進去對吧，這就是虛擬出來的，朋友，懂么？就像你的男朋友或者女朋友一樣，都是你虛擬出來的，是不存在的。
OK那怎么虛擬的將節點放到二叉樹中呢？很簡單，將節點的id從最高位開始，同時將虛擬二叉樹從根節點開始，遇到id某bit是0則虛擬二叉樹向左走一步，反之則向右走一步。其實最后就200層的虛擬二叉樹對吧，所有的節點都存放在最下面一層。

OK那個小黑點就是咱自己節點。好了，現在要從自己的角度出發，將這顆虛擬的3二叉樹進行一個模塊劃分（先別管為啥要劃分好吧），本質上講，就是咱們自己節點的父親節點不斷的上升，然后呢，總有一部分是剛剛升上來的，另一部分則不是，于是你看，這個二叉樹就分成了除自己以外的三個部分。（咱們這棵樹的節點層數可是200層，就能分成200個部分）
我不得不說，這種想法是真的棒。

邏輯上的節點與節點間距

咱們到現在為止都還是在說邏輯上，對吧。邏輯上咱們將所有的點都放在一顆虛擬二叉樹的葉子節點上，現在我想求一下兩個葉子節點的虛擬間距，咋搞？簡單啊，把hash得到的節點id異或一下啊！
節點A的ID（010）
節點B的ID（110）
A ⊕ B = 100（二進制） = 4（十進制）
是不是被震驚到了，沒想到吧？所以我才覺得這個虛擬二叉樹的理念是真的棒。
那我為什么要從咱自己這個節點的角度對這顆虛擬二叉樹進行劃分呢？其實是這個原因：對于每個子樹，如果我們分別知道里面的一個節點，就可以利用這個節點遞歸路由到子樹的任意一個節點。聽起來好像很有道理。但是在實際應用中，由于節點是動態增加減少的，如果知道的節點恰好宕機或者下線了就會出現問題，為了保證系統的魯棒性Kad算法又引入了K桶（K-bucket）的機制。

K bucket

這個桶長啥樣子呢？其實就是個鏈表，表示在一定的偏移量范圍內的K個節點的ip地址信息。這么多個桶串聯起來成了一張表，這個表其實就是路由表！

如何更新K bucket中的節點信息

為什么要更新呢？因為每時每刻都會有一些節點永久消失掉。這當然很好理解，比如某個人很長時間都沒上線了，它把某個BT軟件卸載了，都是很可能發生的對吧，所以咱們要更新這個K bucket。
以下三種方式用來更新k bucket：
1.周期性的發起PING請求，判斷K桶中某個節點是否在線，然后清理K桶中哪些下線的節點。
2.主動收集節點，主動發起FIND_NODE查詢節點的請求，從而更新K桶的節點信息
3.被動收集節點，當收到其他節點發送過來的請求（如：FIND_NODE、FIND_VALUE），會把對方的節點ID加入到某個K桶中
當確定某個節點ID需要被加入到K bucket中時，怎么搞呢？
1.計算自己和目標節點ID的距離d
2.通過距離d找到對應的K桶，如果ID已經在K桶中了則把對應項移到K桶的末尾
3.如果不在K桶中則有兩種情況
3.1.如果該K桶存儲的節點小于K個，則直接把目標節點插入到K-桶尾部；
3.2.如果該K桶存儲節點大于等于K個，則選擇K-桶中的頭部節點進行PING操作，檢測節點是否存活。如果頭部節點沒有響應，則移除該頭部節點，并將目標節點插入到隊列尾部；如果頭部節點有響應，則把頭部節點移到隊列尾部，同時忽略目標節點。

一個嶄新的節點希望加入Kad網絡

一個新節點需要加入Kad網絡有如下的步驟：
1.新節點A生成一個隨機的節點ID，直到離開網絡一直使用。
2.新節點A需要一個種子節點B作為引導，并把該種子節點加入到K桶中。
3.向節點B發送FIND_NODE請求。
4.節點B在收到節點A的FIND_NODE請求后，會根據FIND_NODE請求的約定，找到K個距離A最近的節點，并返回給A節點，A收到這些節點以后，就把它們加入到自己的K桶中
5.然后節點A會繼續向這些剛拿到節點發起FIND_NODE請求，如此往復，直到A建立了足夠詳細的路由表。

如何find_node?

1.確定目標ID對應路由表中的K桶位置，然后從自己的K-桶中篩選出K個距離目標ID最近的節點，并同時向這些節點發起FIND_NODE的查詢請求。
2.被查詢節點收到FIND_NODE請求后，從對應的K桶中找出自己所知道的最近的K個節點，并返回給發起者。
3.發起者在收到這些節點后，更新自己的結果列表，并再次從其中K個距離目標節點ID最近的節點，挑選未發送請求的節點重復第一步
4.不斷重復上面的步驟直到找到目標節點為止

如何find_value

其實吧，不僅僅是節點是hash后的一串id，就連文件都是哈希后的id（對文件名稱字符串進行哈希，當然可以呀，而且那些MD5或者SHA不都可以么？）有這么個規定，就是說，節點id和文件id相同的話，那么這個節點以及節點的鄰近K個節點都有責任知道，這個文件所在的節點id。其實只要這件事情能辦到，那么find_value不就等同于find_node么？？？
可是這件事情真的好實現么？
其實鄰里之間互幫互助從一開始就搞起來的話，還真不叫什么事兒。總共你就160個分組，里面都有你的眼線（K個），想維護這樣的關系確實不難。比如我舉個例子哈，當某個節點貢獻一份新的文件，那么將這個文件計算得到hash值之后，直接讓這個文件所在節點去find_node，找這個哈希值的節點，不就完了么。找不到的話就找附近K個節點，不就完了么？
這樣一來，這個關系不就搞起來了么！

總結

以上是生活随笔為你收集整理的kademlia（卡德米利亚）算法原理介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。