IPFS底層技術詳解（2.4）——分布式哈希表（4）

今天我們來說異或算法和Kademlia DHT的二叉樹拓撲結構。

首先我們來介紹一下異或算法。異或算法是二叉樹結構中用來尋址的計算距離的方法。現在網上對異或算法的解釋大都有些晦澀，很多都是說它的計算法則等等，沒有說到重點。

那重點是什麼呢？

說到底，異或算法可以說是為二叉樹的拓撲結構量身打造的距離計算法則，其核心就是二進制。我們都知道，二進制的計算裡只有0和1，這種非此即彼的情況也是異或算法可以產生的前提。異或算法的計算方法就是【相同記為0，不同記為1】。

異或算法計算法則

也就是1100⊕0101=1001

異或算法先說到這兒，我們先轉頭來看Kademlia DHT。

第一點，我們需要強調的是，存儲的內容的哈希算法必須和節點ID的哈希算法有同構性，一般來說用的是同一種算法（例如SHA1），方便節點和存儲的內容聯繫起來。

圓環型的拓撲結構要求內容存儲在順時針方向上的第一個節點內，而二叉樹因為其特殊的拓撲結構，要求內容和節點一一對應。網絡上很多介紹裡都說內容會存儲在和其哈希相同的節點內，但就算全網的節點有百萬的數量級，和所有的哈希值數量2^¹⁶⁰比起來（以SHA1為例，其Bit數有160位，之所以選擇Bit數較多的算法是為了保證安全）也是可以忽略不計的，所以出現內容哈希和節點ID哈希一致的情況可以說很難發生。所以，實際情況是約定一個節點依據其節點ID存儲哈希在某一範圍內的內容，而這個範圍是可以人為規定的。

我二叉樹還會回來的

為了方便理解我們先放上二叉樹的圖。如果我們將節點的哈希換算成二進制數，那麼任意兩個節點的哈希，總會在某一位產生分叉，也就是在某一位時，一個是0，一個是1。所以一個哈希算法可能產生的所有哈希都可以在這一個二叉樹中列出。

接下來的問題就是如何尋址了，這裡我們就要把之前沒說完的異或算法給重新拿出來，來解釋尋址的過程。

Kademlia DHT引入了【K-bucket】的概念，而一個節點所有的K-bucket就是一個節點所維護的路由表。一個K-bucket可以理解為記錄某一距離範圍內的k個節點的通訊錄。而這個距離的計算就是採用了異或算法。

下面的示例會告訴你，按異或距離分層，基本上可以理解為按位數分層。設想以下情景：

以0000110為基礎節點，如果一個節點的ID，前面所有位數都與它相同，只有最後1位不同，這樣的節點只有1個 —— 0000111，與基礎節點的異或值為0000001，即距離為1；對於0000110而言，這樣的節點歸為“k-bucket 1”；

如果一個節點的ID，前面所有位數相同，從倒數第2位開始不同，這樣的節點只有2個：0000101、0000100，與基礎節點的異或值為0000011和0000010，即距離範圍為3和2；對於0000110而言，這樣的節點歸為“k-bucket 2”；

……

如果一個節點的ID，前面所有位數相同，從倒數第n位開始不同，這樣的節點只有2^^(i-1)個，與基礎節點的距離範圍為[ 2^^(i-1),2^ⁱ ）；對於0000110而言，這樣的節點歸為“k-bucket i”；

現在哈希為00000110的節點A想找哈希為00010000的內容。那麼A就知道它需要找到哈希為00010000的節點或者與其相近的，存有00010000的節點B。00010000與節點A（00000110）的異或距離為 00010110，距離範圍在[2^

然後節點A看看自己的K-bucket 5有沒有節點B：

如果有，那就直接跳轉節點B尋找內容；

如果沒有，在K-bucket 5裡隨便找一個節點X（注意任意節點，它的哈希第5位肯定與B相同，即它與節點B的距離會小於2^⁴，相當於比B、A之間的距離縮短了一半以上），請求節點X在它自己的通訊錄裡按同樣的查找方式找一下節點B：

-- 如果X知道節點B位置，那就把節點B的位置告訴A；

-- 如果X也不知道節點B，那X按同樣的搜索方法，可以在自己的通訊錄裡找到一個離B更近的節點Y（B、Y之間距離小於2^³），把節點Y推薦給A；節點A請求節點Y進行下一步查找。

我二叉樹回來了

這樣，在有N位Bit數的哈希來編碼的網絡中，最多隻需要跳轉N次即可查詢到目標所在位置。拿SHA1舉例，假設全網有2^160個節點，實現了哈希的全覆蓋，那麼節點的數量超過了10^48，而最多僅僅需要160次跳轉就可以尋找到目標位置。

另外，一個節點所需要維護的列表最多存有（K*哈希算法Bit數）的節點數。而這個K值也是人為設置的：K值越大，每個節點所需要維護的節點列表越長，節點的進入退出更新越慢，但尋址速度會較快；相反，K值越小，每個節點的列表越短，更新速度越快，但尋址會相對慢一些。這個就需要設計者對整體的網絡的情況進行考量來合理設置K值。

這種二叉樹的DHT結構可以說奠定了至今為止的大多數網絡拓撲結構，連V神創造的以太坊的底層設計中都可以找到Kademlia DHT的蹤跡。

至此，DHT的基礎科普已經完成了。下一次，我們將先簡單介紹IPFS所使用的DSHT並且用一份文件在IPFS網絡內所經歷的一切來介紹IPFS最基本的分片和尋址原理。

References：

《易懂分佈式》，嬸嬸豆奶，簡書：https://www.jianshu.com/p/f2c31e632f1d

https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin

閱讀更多 IPFS點滴資訊 的文章

關鍵字: 技術 簡書 算法