筆者寄語

本來這一篇是直接將IPFS所使用的DHT技術的，但後來一想，為了能讓真正想通過這一個系列文章搞懂IPFS究竟是什麼的讀者去慢慢理解，筆者還是決定慢下腳步，說一下白皮書裡提到的Kademlia DHT，幫助我們更好的理解IPFS所真正用到的DSHT（也借鑑了Kademlia DHT裡的一些思想）。

基礎邏輯有一些晦澀，請讀者耐心讀完。

首先，筆者先修改一下上一篇中出現的表述錯誤：

DHT偏愛公網固定IP是因為固定IP不會改變其在DHT拓撲結構裡的位置，前一篇介紹的是第一代DHT中比較有代表性的Chord DHT，其拓撲結構是圓環結構。其實無論是什麼結構，都存在【位置】這個概念，所以固定IP是必須的。

如果有讀者並沒有看的太明白，想要自己多研究研究，請看：

https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf

好了，我們來說正題。

上一期說完有人和我說沒有介紹路由的問題。

這裡需要道個歉，沒錯，存儲和尋址都是DHT存在的必要理由，之前介紹了存儲，沒有說尋址的方式，我們先補充一下。

所謂路由，簡單理解就是找到你要的信息的方式。在圓環的結構裡，最初的尋址方式是順時針方向依次尋找，在節點量級很大的時候，這樣的方式顯然是相當低效的，所以之後，出現了Finger Table，也就是Kademlia DHT的路由方式的基礎。

這裡筆者簡單介紹一下Finger Table，這項技術的實現以圓環結構為基礎。

Finger Table的尋址方式是讓每一個節點存儲一個數量為哈希算法Bit數（例如SHA1有160位，每個節點就會存儲160個位置信息）的節點ID的List。每次開始尋址時某一節點會獲得一個Key（內容特徵值哈希），如果自己這個恰好有這個Key就直接返回Value；如果不存在這個Key，節點將從自己存儲的List裡去找【不大於Key的最大的哈希所代表的節點】。

我們拿圖來說明為什麼要這樣做。

依據上一次科普的內容，每一個進入環型網絡的內容都是按照順時針方向尋找距離其最近的節點的，所以節點的哈希一定大於其所存儲Value的Key的哈希，在這個前提之下，我們規定每次跳轉的節點哈希都不大於Key的哈希。

可以說利用Finger Table進行尋址依然沒有逃脫順序這個變量，我們依然還是要按照順時針方向尋找存儲鍵值對的節點，但不是依靠一次尋找，而是直接在自己存儲的列表中去尋找哈希不大於Key的節點，再重複進行指導找出節點為止。

當經過數次跳轉之後，哈希值足夠接近以至於節點內的List內不大於Key的最大哈希對應的節點哈希大於Key的哈希時，下一個節點就是我們要找的節點。

至於這個List上存儲的位置，是按照本節點哈希值（m）+2^(i-1) 來計算的，這個i就是所選哈希算法的Bit數，例如SHA1有160位，List裡存儲的位置哈希就是m+2^0，m+2^1，……，m+2^159。

看到這裡

你是不是想說

我們來舉個例子

盜一張別人博客裡的圖，假設現在網絡被請求尋找一個文件，而這個文件哈希（十進制）為83，在哈希為96的位置有一個節點，文件存在這裡。

現在我們從頭看，這個哈希環是當n=7，也就是哈希的Bit數為7的時候。

首先，尋址信息來到哈希（十進制）為20的節點，這個節點裡存著的不大於文件哈希的最大的位置哈希是20+2^5=52，而52位置對應的節點就是80。

尋址信息來到了80這裡，經過計算，i=0,1,2,3,4時（位置哈希十進制分別為80,82,84,88,96），位置都在80和96節點之間，也就代表了96節點。此時，不大於83的最大位置哈希為82，這個位置歸屬96節點。於是尋址信息就按照順時針來到了96這裡。該節點尋找之後發現這個文件就存在自己這裡。

可以看到，這樣的尋址方式就直接跳過了32和45兩個節點，效率大大提高。

不知不覺說了這麼多，今天先到此為止，大家可以當做睡前催眠讀物，下一篇我們來說Kademlia DHT的二叉樹拓撲結構和用於定位的異或算法。

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

關鍵字: 尋址 位置 筆者