1. 首页
  2. 技术分享

IPFS底层技术详解:分布式哈希表(4)

今天我们来说异或算法和Kademlia DHT的二叉树拓扑结构。

首先我们来介绍一下异或算法。异或算法是二叉树结构中用来寻址的计算距离的方法。现在网上对异或算法的解释大都有些晦涩,很多都是说它的计算法则等等,没有说到重点。

那重点是什么呢?

说到底,异或算法可以说是为二叉树的拓扑结构量身打造的距离计算法则,其核心就是二进制。我们都知道,二进制的计算里只有0和1,这种非此即彼的情况也是异或算法可以产生的前提。异或算法的计算方法就是【相同记为0,不同记为1】。

IPFS底层技术详解:分布式哈希表(4)

也就是1100⊕0101=1001

异或算法先说到这儿,我们先转头来看Kademlia DHT。

第一点,我们需要强调的是,存储的内容的哈希算法必须和节点ID的哈希算法有同构性,一般来说用的是同一种算法(例如SHA1),方便节点和存储的内容联系起来。

圆环型的拓扑结构要求内容存储在顺时针方向上的第一个节点内,而二叉树因为其特殊的拓扑结构,要求内容和节点一一对应。网络上很多介绍里都说内容会存储在和其哈希相同的节点内,但就算全网的节点有百万的数量级,和所有的哈希值数量2160比起来(以SHA1为例,其Bit数有160位,之所以选择Bit数较多的算法是为了保证安全)也是可以忽略不计的,所以出现内容哈希和节点ID哈希一致的情况可以说很难发生。所以,实际情况是约定一个节点依据其节点ID存储哈希在某一范围内的内容,而这个范围是可以人为规定的。

IPFS底层技术详解:分布式哈希表(4)

为了方便理解我们先放上二叉树的图。如果我们将节点的哈希换算成二进制数,那么任意两个节点的哈希,总会在某一位产生分叉,也就是在某一位时,一个是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”;

IPFS底层技术详解:分布式哈希表(4)

现在哈希为00000110的节点A想找哈希为00010000的内容。那么A就知道它需要找到哈希为00010000的节点或者与其相近的,存有00010000的节点B。00010000与节点A(00000110)的异或距离为 00010110,距离范围在[24, 25),所以节点B可能在k-bucket 5中(或者说,B节点的哈希与A节点的哈希从第5位开始不同,所以节点B可能在K-bucket 5中)。然后节点A看看自己的K-bucket 5有没有节点B:如果有,那就直接跳转节点B寻找内容;如果没有,在K-bucket 5里随便找一个节点X(注意任意节点,它的哈希第5位肯定与B相同,即它与节点B的距离会小于24,相当于比B、A之间的距离缩短了一半以上),请求节点X在它自己的通讯录里按同样的查找方式找一下节点B:— 如果X知道节点B位置,那就把节点B的位置告诉A;— 如果X也不知道节点B,那X按同样的搜索方法,可以在自己的通讯录里找到一个离B更近的节点Y(B、Y之间距离小于23),把节点Y推荐给A;节点A请求节点Y进行下一步查找。

IPFS底层技术详解:分布式哈希表(4)

这样,在有N位Bit数的哈希来编码的网络中,最多只需要   即可查询到目标所在位置。拿SHA1举例,假设全网有  个节点,实现了哈希的全覆盖,那么节点的数量超过了  ,而最多仅仅需要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底层技术详解:分布式哈希表(4)

原创文章,作者:点对点资讯,如若转载,请注明出处:https://ipfsdrop.com/tech/ipfsdicengjishuxiangjiefenbushihaxibiao4/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

联系我们

(+86)18301922335

在线咨询:点击这里给我发消息

邮件:haskell@freechains.cn

工作时间:7×24小时

QR code