bt协议详解 DHT篇（上）
最近开发了一个免费教程的网站，突然产生了仔细了解bt协议的想法，这篇文章是bt协议详解系列的第三篇，后续还会写一些关于搜索和索引的东西，都是在开发这个网站的过程中学习到的技术，敬请期待。
文章主要内容来自于对DHT Protocol的翻译，如果大家感兴趣的话，可以阅读一下英文原版。
为了大家阅读的方便，把文章分成了上下篇，两篇加在一起快1w字了，确实看的比较累。
1 简介
前面讲到BT协议像tcp/ip协议一样是一个协议簇，dht协议在这个协议簇中出现的比较晚，但是它所发挥的作用却不容小视。dht协议提出的一些新的想法让我们能够推翻基础篇中的设计，得到一个更简单更高效的bt服务器和bt客户端。
在dht协议中，bt客户端使用“distributed sloppy hash table”（DHT的全称）来存储没有tracker地址的种子文件所对应的peer节点的信息，在这种情况下，每一个peer节点变成了一个tracker服务器，dht协议是在udp通信协议的基础上使用Kademila（俗称Kad算法）算法实现。
重要:注意这里使用的术语，一个peer节点是一个实现了bt协议并且开启了tcp监听端口的bt客户端或者服务器。一个node节点是一个实现了dht协议并且开启了udp监听端口的bt客户端或者服务器，这两者非常容易混淆。
dht由很多node节点以及这些node节点保存的peer地址信息组成，一个bt客户端包括了一个dht node节点，通过这些节点来和dht网络中的其它节点通信来获取peer节点的信息，然后再通过bt协议从peer节点下载文件。
看到这里大家应该明白了，dht协议并不能取代bt协议，它只是bt协议的一个强有力的补充，在一些禁止运行bt tracker服务器的国家，通过使用dht协议，用户照样可以下载想要的内容。tracker服务器本来也不保存真正的文件，只是保存和torren文件相关的peer的信息，
dht协议通过从附近的node节点获取peer信息，而不是从tracker服务器获取peer信息，这就是所谓的trackerless。
2 概述
dht网络中每一个node节点有一个全局的唯一标识，叫node ID（节点id），节点id是随机从torrent种子文件中的160位的infohashes中随机抽取的。distance metric（距离度量）用来比较两个节点id或者节点id和infohash之间的距离。所有的节点（注意后面所有提到的node节点都简称节点，peer节点不作简写）必须保存一个routing table（路由表）保存它和dht网络中一小部分节点交流的信息。离节点id越近的其它节点id的信息越详细。所有的节点必须知道很多离它们很近的其它节点，离它们很远的节点只需要有足够的握手信息就行了。
在Kad算法中，距离度量是对两个hash值进行XOR（异或）运算，并且把结果转换成无符号整数。distance(A,B)=|A xor B|，结果值越小，距离越近。
当一个节点想找到一个种子文件的peer节点信息时，就使用距离算法把种子文件的infohash字段和它自己路由表中的节点id进行比较，然后和距离最近的节点进行通信，向它们发送请求获取正在下载这个种子文件的peer节点列表的信息。如果它请求的节点知道这个种子文件的peer节点列表，则把peer节点列表返回给发送请求的节点。如果不知道，它必须返回自己路由表中离infohash最近的节点列表给请求者。原始节点不断迭代的发送请求直到找到离目标infohash更近的节点。搜索结束之后，bt客户端把peer节点的信息保存在自己的路由表里面。
请求peer节点列表的返回值中包含了一个可选“token”，当一个节点声明它控制的peer节点正在下载一个种子文件时，它必须把它最近发送请求中获取的token返回向它发送请求的节点。当一个节点尝试“声明”一个种子时，被询问的节点把token和ip进行检查，这样做是为了防止冒充其它主机下载文件。因为token只是在查询节点和它获取token的节点之间发送，具体的实现没有任何限制。tokens在发布之后的一段时间之内是生效的。bittorrent客户端使用秘钥对ip进行sha1哈希，秘钥每5分钟改变一次，生成的token在10分钟内是有效的。
3 路由表
每一个节点都维护一个路由表保存一些已知的通信好的节点。路由表中的节点通常用来作为起始节点，当其它节点向这个节点发送请求时，路由表中的这些节点就会被返回给发送请求的几点。
并不是每一个已知的节点都是对等的。一些节点是活跃的（原文是“good”）的，另外一些不是。dht中的许多节点可以发送请求和接受返回，但是不会响应dht网络中其它节点的请求。每一个节点的路由表中都只保存好的节点，这一点非常重要。一个活跃的节点就是能在15分钟之内响应过请求或者在15分钟之内发送过请求的节点。15分钟之内没有活动的话，这个节点变成问题节点。当一个节点响应请求失败的话，它就变成坏的节点。活跃的节点比状态不明的节点的优先级要高（这不是显然吗？）。
路由表覆盖从0到2160完整的nodeID空间。路由表又被划分为buckets(桶)，每一个bucket包含一个子部分的nodeID空间。一个空的路由表只有一个bucket，它的ID范围从min=0到max=2160。当一个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..2159，第二个的范围从2159..2160。
当bucket装满了好的nodes，那么新的node将被丢弃。一旦bucket中的某一个node变为了坏的node，那么我们就用新的node来替换这个坏的node。如果bucket中有在15分钟内都没有活跃过的节点，我们将这样的节点视为可疑的节点，这时我们向最久没有联系的节点发送ping。如果被pinged的节点给出了回复，那么我们向下一个可疑的节点发送ping，不断这样循环下去，直到有某一个node没有给出ping的回复，或者当前bucket中的所有nodes都是好的(也就是所有nodes都不是可疑nodes，他们在过去15分钟内都有活动)。如果bucket中的某个node没有对我们的ping给出回复，我们最好再试一次(再发送一次ping，因为这个node也许仍然是活跃的，但由于网络拥塞，所以发生了丢包现象，注意DHT的包都是UDP的)，而不是立即丢弃这个node或者直接用新node来替代它。这样，我们得路由表将充满稳定的长时间在线的nodes。
每一个bucket都应该维持一个“lastchange”字段来表明bucket中的nodes有多新鲜。当一个bucket中的node被ping并给出了回复，或者一个node被加入到了bucket，或者一个node被一个新的node所替代，bucket的“lastchanged”字段都应当被更新。如果一个bucket的“lastchange”在过去的15分钟内都没有变化，那么我们将更新它。这个更新bucket操作是这样完成的：从这个bucket所覆盖的范围中随机选择一个ID，并对这个ID执行find_nodes查找操作。常常收到请求的nodes通常不需要常常更新自己的buckets，反之，不常常收到请求的nodes常常需要周期性的执行更新所有buckets的操作，这样才能保证当我们用到DHT的时候，里面有足够多的好的nodes。
在第一个node插入路由表并开始服务后，这个node应该试着查找离自身更近的node，这个查找工作是通过不断的发布find_node消息给越来越近的nodes来完成的，当不能找到更近的节点时，这个扩散工作就结束了。路由表应当被启动工作和客户端软件保存（也就是启动的时候从客户端中读取路由表信息，结束的时候客户端软件记录到文件中）。
4 bt协议扩展
BitTorrent协议已经被扩展为可以在通过tracker得到的peer之间互相交换nodeUDP端口号(也就是告诉对方我们的DHT服务端口号)，在这样的方式下，客户端可以通过下载普通的种子文件来自动扩展DHT路由表。新安装的客户端第一次试着下载一个无tracker的种子时，它的路由表中将没有任何nodes，这是它需要在torrent文件中找到联系信息。
peers如果支持DHT协议就将BitTorrent协议握手消息的保留位的第八字节的最后一位置为1。这时如果peer收到一个handshake表明对方支持DHT协议，就应该发送PORT消息。它由字节0x09开始，payload的长度是2个字节，包含了这个peer的DHT服务使用的网络字节序的UDP端口号。当peer收到这样的消息是应当向对方的IP和消息中指定的端口号的node发送ping。如果收到了ping的回复，那么应当使用上述的方法将新node的联系信息加入到路由表中。
本文来自 免费教程网