DHT方法

背景

原始BT协议是使用Tracker来追踪用户的信息，但是这种方法违背去中心化的思想。万一Tracker挂了，种子文件就会失效，即便有其他用户有着这个文件，也不能下载，所以需要一个改进的协议，能够从网络中去寻找自己需要的其他用户。

一种方法是广播方式，但容易引发广播风暴，pass。另一种方法是DHT。

DHT结构

参考链接：https://blog.csdn.net/vincent_hbl/article/details/79339462

参考链接：http://www.bittorrent.org/beps/bep_0005.html

DHT= Distributed Hash Table 中文：分布式哈希表

一句话说明DHT的作用：代替Tracker服务器，通过分布式存储的方式将原本存储在Tracker中的信息存储到各个用户中。

有了DHT以后，下载种子文件的过程变成了：首先，从DHT中查询种子对应的活跃用户。然后，根据获得的用户信息开始p2p下载。和原始BT协议不同的地方只是在于改变了获取活跃用户的方式。

因而DHT可以说是一个分布式数据库。网络中的所有用户构成的DHT网络是一个大的数据库。每个用户都存储一小部分数据。

要说明一下，DHT是一个概念性的方法，具体实现有许多种，这里仅说明Kademlia方法，该方法是BT协议中使用的方法。

• DHT, distributed sloppy hash tabl.
  1. BT 协议像 TCP/IP 协议一样是一个协议簇
  2. DHT 协议是在 UDP 通信协议的基础上使用 Kademila（俗称 Kad 算法）算法实现
  3. Tracker 服务器保存和 torrent 文件相关的 peer 的信息
  4. 一个 peer 节点是一个实现了 BT 协议并且开启了 TCP 监听端口的 BT 客户端或者服务器
  5. 一个 node 节点是一个实现了 DHT 协议并且开启了 UDP 监听端口的 BT 客户端或者服务器
  6. DHT 由很多 node 节点以及这些 node 节点保存的 peer 地址信息组成
  7. 一个 BT 客户端包括了一个 DHT node 节点，通过这些节点来和 DHT 网络中的其它节点通信来获取 peer 节点的信息，然后再通过 BT 协议从 peer 节点下载文件
  8. DHT 协议通过从附近的 node 节点获取 peer 信息，而不是从 tracker 服务器获取 peer 信息，这就是所谓的 trackerless.

DHT中数据的分配方式

DHT中的数据是按键值对的方式存储的。在BT协议的应用中，key是种子文件的ID，value是该种子文件的活跃用户（peers）信息。这里种子的ID是160bit的infohash，就是每个种子文件hash生成的独一无二的字符串。

DHT中的每个存储单元，其实也是用户，叫做节点（node），注意和peer区分。每个node也有一个ID，是一个随机生成的160bit 字符串。如此以来，数据ID和nodeID都是160bit字符串了。

接下来再引入一个概念做为铺垫——距离。node和node之间，node和数据之间都有距离，距离的计算方法，是做两个160bit ID的异或运算。注意，node ID是随机生成的，因而这里的距离是与实际网络连接情况无关的。

在 Kademlia 网络中，距离是通过异或(XOR)计算的，结果为无符号整数。distance(A, B) = |A xor B|，值越小表示越近。

DHT中数据存储的基本想是把数据存放在离它最近的node中，也就是说，把数据存放在ID和数据ID最接近的node中。准确说是最接近的几个node中。

DHT中的路由

知道DHT中数据和node的距离计算和存储原则，我们可以知道只要查找和数据ID最接近的几个node，就能够找到目标数据了。但是有个问题，一个node中，可以存储部分其他node的ID以及对应的IP地址端口号。但是无法存储所有的节点的信息。要连接到目标node，需要询问其他节点，慢慢的接近目标节点。

1、bucket

存储node ID、ip地址、端口号列表叫做路由表。简单说，这个路由表中，离自己所在node距离越近的node越多，越远的越少。具体讲，用到了叫做bucket的结构。

bucket结构是路由表中其他节点信息的集合，一个bucket中最多只能存放8个node。node初始情况下只有一个bucket，范围是160bit ID的整个空间。如果一个bucket满了，而且这个bucket的范围包含了自己的node ID，那么就允许将这个bucket平均一分为二。如果bucket的范围不包括自己的nodeID，那么就不能够分裂。可以看出，持续的分裂下去，新的bucket范围会越来越小，而且离nodeID越来越近。由于每个bucket都只能存8个node，这么以来就确保了距离近的node信息多，距离远的node信息少。

2、查询过程

DHT中数据的查询过程是：发起查询的节点（node）首先计算自己路由表中的节点到目标数据的距离，然后对最近的k个节点发起数据查询。收到数据查询请求的节点如果有数据直接返回，没有则在自己的路由表中查询距离数据最近的节点，并返回。发起查询的节点收到了返回的节点，则继续查询这些节点，知道返回了需要的数据。

这个持续的查询过程会一步步接近存在数据的节点。

3、路由表的更新

DHT中用户在持续的变化，所以需要一些机制保证路由表信息不会过时。

路由表中的node有三种状态：good、questionable、bad。简单说，good就是活跃的节点。如果长期没有一个节点的信息，这个节点就变成了questionable，如果对某个节点多次发送请求都没有回复，那么这个节点就是bad的，会从路由表中去除。

questionable节点暂时不会被去除，只有当需要加入新节点但该bucket已经满了之后，才会对该bucket中的questionable节点进行测试，并删除没有回应的节点。

另外，每个bucket中，至少需要维持一个good节点（这样才能保证整个网络中的任意点都是可达的），如果一个bucket里的所有点都长期没有动静，就需要对整个bucket进行刷新，刷新方法是发起一个在该bucket范围内的查询。

4、新节点初始化路由表

新节点进入DHT网络时，必须至少已知一个节点。然后对该节点发起查询，查询的是自己的ID。这样以来，会返回越来越接近自己的Node信息。查询的过程中存储这些node信息。查询结束后，就完成了路由表的初始化。（牛蛙）

数据的读写和数据的保持

1、增删改查

前面已经说到了数据的查询过程。修改数据方法类似，也是首先查询数据ID，最后可以得到几个node，修改这些node上的数据。

2、应对节点变化

节点会不断变化，存储数据的k个节点都可能全部下线从而导致数据丢失。

刷新机制可以应对这个问题，刷新机制很简单，就是每隔一段时间，所有节点将自己拥有的数据重新进行一次存储。就是重新查询数据ID，将自己有的数据存储到返回的那几个node中去。这个方法不能百分之百保证数据不丢失，只是丢失概率比较低而已。

新加入节点如何处理呢？新节点在加入过程中会初始化路由表，这个过程中其他节点会发现该节点。其他节点会判断新节点到自己存储的数据之间的距离，如果新节点够近，就将数据存储到新节点上。