引言

 

DHT全称叫分布式哈希表(Distributed Hash Table),是一种分布式存储方法,一类可由键值来唯一标示的信息按照某种约定/协议被分散地存储在多个节点上,这样也可以有效地避免“中央集权式”的服务器(比如:tracker)的单一故障而带来的整个网络瘫痪。实现DHT的技术/算法有很多种,常用的有:Chord, Pastry, Kademlia等。

 

总述

 

dht网络中每一个node节点有一个全局的唯一标识,叫node ID(节点id),节点id是随机从文件中的160位的hash中随机抽取的。distance metric(距离度量)用来比较两个节点id或者节点id和hash之间的距离。所有的节点(必须保存一个routing table(路由表)保存它和dht网络中一小部分节点交流的信息。离节点id越近的其它节点id的信息越详细。所有的节点必须知道很多离它们很近的其它节点,离它们很远的节点只需要有足够的握手信息就行了。

在Kad算法中,距离度量是对两个hash值进行XOR(异或)运算,并且把结果转换成无符号整数。distance(A,B)=|A xor B|,结果值越小,距离越近。

当一个节点想找到一个文件的peer节点信息时,就使用距离算法把文件的hash字段和它自己路由表中的节点id进行比较,然后和距离最近的节点进行通信,向它们发送请求获取正在下载这个文件的peer节点列表的信息。如果它请求的节点知道这个文件的peer节点列表,则把peer节点列表返回给发送请求的节点。如果不知道,它必须返回自己路由表中离文件hash最近的节点列表给请求者。原始节点不断迭代的发送请求直到找到离目标文件hash更近的节点。搜索结束之后,下载节点把peer节点的信息保存在自己的路由表里面。

 

原理

 

每一个节点都维护一个路由表保存一些已知的通信好的节点。路由表中的节点通常用来作为起始节点,当其它节点向这个节点发送请求时,路由表中的这些节点就会被返回给发送请求的结点。

路由表覆盖从0到2的160次完整的nodeID空间。路由表又被划分为buckets(简称K桶),每一个bucket包含一个子部分的nodeID空间。一个空的路由表只有一个bucket,它的ID范围从min=0到max=2的160次。K桶结构如下:

当一个nodeID为“N”的node插入到表中时,它将被放到ID范围在min< N < max的bucket中。一个空的路由表只有一个bucket所以所有的node都将被放到这个bucket中。每一个bucket最多只能保存K个nodes,当前K=8。当一个bucket放满了好的nodes之后,将不再允许新的节点加入,除非我们自身的nodeID在这个bucket的范围内。在这样的情况下,这个bucket将被分裂为2个新的buckets,每一个新桶的范围都是原来旧桶的一半。原来旧桶中的nodes将被重新分配到这两个新的buckets中。如果是一个只有一个bucket的新表,这个包含整个范围的bucket将总被分裂为2个新的buckets,第一个的覆盖范围从0..2的159,第二个的范围从2的159次..2的160次。

当bucket装满了好的nodes,那么新的node将被丢弃。一旦bucket中的某一个node变为了坏的node,那么我们就用新的node来替换这个坏的node。如果bucket中有规定时间(例如120秒)内都没有活跃过的节点,我们将这样的节点视为可疑的节点,这时我们向最久没有联系的节点发送ping。如果被pinged的节点给出了回复,那么我们向下一个可疑的节点发送ping,不断这样循环下去,直到有某一个node没有给出ping的回复,或者当前bucket中的所有nodes都是好的。如果bucket中的某个node没有对我们的ping给出回复,我们最好再试一次(再发送一次ping,因为这个node也许仍然是活跃的,但由于网络拥塞,所以发生了丢包现象,注意DHT的包都是UDP的,而不是立即丢弃这个node或者直接用新node来替代它。这样,我们得路由表将充满稳定的长时间在线的nodes。

 

DSP对DHT的改进

在DSP的协议架构下,我们将DHT做了扩展。利用Discovery算法,可以通过peer之间互相交换nodeUDP端口号。同时,下载节点可以通过下载普通的任意文件来自动扩展DHT路由表。当新启动的节点第一次试着下载一个无tracker的文件时,它的路由表中将没有任何nodes,这时它需要在bootstrap节点中找到其它节点的联系信息。

 

本文链接:https://www.8btc.com/media/635187
转载请注明文章出处

文章标签: DHT DSP
评论
登录 账号发表你的看法,还没有账号?立即免费 注册