笔者寄语
本来这一篇是直接将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點滴資訊 的文章
