引言

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节点中找到其它节点的联系信息。