IMFile

DHT（Distributed Hash Table）分布式哈希表 是分布式计算系统中的一个类别，是一种分布式系统，提供类似于哈希表的查找服务。键值对存储在 DHT 分布式哈希表 中，任何参与的节点都可以有效地检索与给定关联的键值。在 BitTorrent 与 Magnet 的原理与对比 一文中，我们已经介绍了他们的联系和区别，现在我们将单独详细的说明一下，DHT 协议具体是什么。

DHT 的主要优点是可以添加或删除节点，只需最少量的重新分发密钥工作。键值是映射到特定值的唯一标识符，而特定值又可以是从地址到文档到任意数据的任何内容。 维护从键值到数值的映射的责任分布在节点之间，对所涉及的参与者的任何更改对系统或过程的整体功能产生影响降低到最小程度。这允许 DHT 扩展到非常大量的节点，并处理持续的节点到达、离开和故障。

BitTorrent 使用 “分布式松散哈希表”（DHT）来存储基于 Trackerless 协议的种子节点联系信息。实际上，每个节点都变成了一个 Tracker 。该协议基于 Kademila，并通过 UDP 实现。

请注意本文档中使用的术语，以避免混淆。 Peer 节点是在实现 BitTorrent 协议的 TCP 端口上侦听的客户端 / 服务器。 Node 节点是侦听实现分布式哈希表协议的 UDP 端口的 Tracker 客户端 / 服务器。 DHT 由 Node 节点和存储 Peer 的位置节点组成。 BitTorrent 客户端包括一个 DHT 节点，该节点用于联系 DHT 中的其他 Node 节点，以获取使用 BitTorrent 协议下载的 Peer 节点的位置。

Peer 通常是指参与文件共享的用户端，也就是下载或上传特定文件的客户端程序，它们通常都是位于同一层级的。每个 peer 都可以下载和上传文件，这使得整个网络更加去中心化，因为没有任何一个节点掌握了所有的数据。
Node 则通常指的是 Tracker 服务器，也就是通过 Tracker 协议来管理和协调各个 Peer 之间的连接和数据传输。 Tracker 服务器会维护一份记录活跃 Peer 的列表，并将其发送给其他 Peer，以帮助它们建立连接并找到其他可以共享文件的 Peer 。
因此，在 BitTorrent 中，Peer 是指下载和上传文件的客户端程序，而 Node 则指的是 Tracker 服务器，用于协调 Peer 之间的连接和文件共享。

每个 Node 节点都有一个全局唯一标识符，称为 Node ID 。 Node ID 是从与 BitTorrent 信息哈希相同的 160 Bit 空间中随机选择的。距离指标用于比较两个 Node ID ，或 Node ID 和接近度比较的信息哈希。 Node 节点必须维护一个路由表，其中包含少量其他节点的联系信息。随着 ID 越来越接近节点自己的 ID，路由表变得更加详细。节点知道 DHT 中的许多其他节点，这些节点的 ID 与自己的 ID 接近，但只有少数下载方的 ID 离自己的 ID 很远。

在 Kademlia 中，距离度量是 XOR，结果被解释为无符号整数。 distance (A,B) = |A xor B| 值越小越近。

当 Node 节点想要查找种子的 Peer 节点时，它会使用距离指标将种子的信息哈希与其自己的路由表中节点的 ID 进行比较。然后，它使用最接近信息哈希的 ID 联系它所知道的节点，并要求他们提供当前下载种子的 Peer 节点的下载信息。如果联系的节点知道种子的对等节点，则对等节点联系信息将随响应一起返回。否则，联系的节点必须使用其路由表中最接近种子信息哈希的节点的联系信息进行响应。原始节点迭代查询更接近目标信息哈希的节点，直到找不到任何更近的节点。搜索完毕后，客户端将自身的对等下载方信息插入到具有最接近种子信息哈希的 ID 的响应节点上。

infohash 是一个由 40 个十六进制字符表示的唯一标识符，用于标识一个 torrent 文件。这个标识符是通过将 torrent 文件的元数据哈希生成的，它包括了文件名、文件大小、文件数量等信息。
当一个客户端想要下载一个 torrent 文件时，它会向 tracker 发送包含该文件 infohash 的请求。 Tracker 将回复一个包含可用种子和对等方的列表，该列表可以帮助客户端连接到其他客户端并开始下载文件。
因为 infohash 是根据文件的内容生成的，所以即使两个 torrent 文件的名称不同，只要它们包含相同的数据，那么它们的 infohash 就会相同。

Peer 节点查询的返回值包括一个称为 token 的不透明值。要使 Node 节点宣布其控制 Peer 节点正在下载种子，它必须在最近的 Peer 节点查询中提供从同一查询节点收到的 Token 。当节点尝试发行种子时，被查询的节点会根据查询节点的 IP 地址检查 Token 。由于 Token 仅由查询节点返回到它从中接收 Token 的同一节点，Token 必须在分发后的合理时间内被接受。 BitTorrent 实现使用 IP 地址的 SHA1 哈希连接到一个 Token 上，该 Token 每五分钟更改一次，并接受长达 10 分钟的 Token 。

在 BitTorrent 中，”Token” 通常指的是一种通过 Tracker 服务器授权的方式，用于帮助客户端获取其他对等方（Peers）和下载所需文件块的一次性密钥或令牌。
当一个 BitTorrent 客户端想要加入一个特定的 Torrent 下载时，它首先会向 Tracker 发送请求，以获取可用的对等方列表。 如果 Tracker 需要进行身份验证，它可能会返回一个 “Token” 给客户端，作为一次性令牌，该令牌只能用于这个特定的 Torrent 下载。
客户端可以使用这个 Token 向 Tracker 发送更多的请求，包括更新对等方列表和下载文件块的请求。 这个 Token 可以防止未经许可的客户端或对等方试图加入下载，并且增强了整个 BitTorrent 网络的安全性。

路由表
每个节点都维护一个已知良好节点的路由表。路由表中的节点用作 DHT 中查询的起点。返回路由表中的节点以响应来自其他节点的查询。

并非我们了解的所有节点都是平等的。有些是好的，有些则不是。许多使用 DHT 的节点能够发送查询和接收响应，但无法响应来自其他节点的查询。重要的是，每个节点的路由表必须仅包含已知良好的节点。一个好的节点是在过去 15 分钟内响应了我们的一个查询的节点。如果一个节点曾经响应过我们的一个查询，并且在过去 15 分钟内向我们发送了一个查询，那么它也很好。处于非活动状态 15 分钟后，节点变得有问题。当节点无法连续响应多个查询时，它们会变得糟糕。我们知道良好的节点优先于状态未知的节点。

路由表覆盖从 0 到 2160 的整个节点 ID 空间。路由表细分为 buckets，每个 buckets 覆盖一部分空间。空表有一个 bucket，其 ID 空间范围为 min=0, max=2160 。当 ID 为 “N” 的节点插入表中时，该节点将放置在最小值为 <= N < 最大值的存储桶中。空表只有一个 bucket，因此任何节点都必须适合其中。每个 bucket 只能容纳 K 个节点，目前是 8 个节点，然后才能算 “装满” 。当 bucket 充满已知良好的节点时，除非我们自己的节点 ID 在存储桶的范围内，否则不能再添加节点。在这种情况下，bucket 将替换为两个新 buckets，每个 bucket 的范围是旧 bucket 的一半，并且旧 bucket 中的节点分布在两个新 bucket 之间。对于只有一个 bucket 的新表，整个 bucket 始终拆分为两个新 buckets，范围为 0..2159 和 2159..2160 。

在 BitTorrent 协议中，Bucket 是指下载器在下载文件时，将下载任务分成多个子任务，并将每个子任务分配给不同的远程上传者（peers）来下载的数据块。这些数据块被组织成 Bucket，可以看作是一组数据块的集合。
通常情况下，一个 Bucket 包含数百个数据块，每个数据块的大小为 16KB 到 64KB 左右。下载器会尝试从多个上传者处获取不同的 Bucket，以便加速下载。这种方式也被称为多点下载（multi-source downloading），因为下载者从多个源同时下载数据。

当 bucket 中装满了良好节点时，新节点将被简单地丢弃。如果已知 bucket 中的任何节点已损坏，则一个节点将替换为新节点。如果 bucket 中有任何可疑节点在过去 15 分钟内未被查询到，则会对最近最少查询的节点执行 ping 操作。如果 ping 的节点响应，则对下一个最近最少查询的可疑节点进行 ping 操作，直到一个节点无法响应或 bucket 中的所有节点都已知良好。如果 bucket 中的节点无法响应 ping，建议在丢弃该节点并将其替换为新的良好节点之前再试一次。这样，表中就会填充稳定的长时间运行的节点。

每个 bucket 都应维护一个 “上次更改” 属性，以指示内容的 “新鲜” 程度。当 bucket 中的节点被 ping 并响应时，或者将节点添加到 bucket ，或者 bucket 中的节点替换为另一个节点时，应更新 bucket 的上次更改属性。 15 分钟内未更改的 bucket 应 “刷新” 。这是通过在 bucket 范围内选择一个随机 ID 并对其执行 find_nodes 搜索来完成的。能够接收来自其他节点的查询的节点通常不需要经常刷新 bucket 。无法从其他节点接收查询的节点通常需要定期刷新所有 bucket ，以确保在需要 DHT 时其表中有良好的节点。

将第一个节点插入其路由表后以及此后启动时，节点应尝试在 DHT 中查找与自身最近的节点。它通过向越来越近的节点发出 find_node 消息来实现这一点，直到它找不到更近的节点。路由表应在客户端软件的调用之间保存。

BitTorrent 协议扩展#

BitTorrent 协议已扩展到在 Tracker 引入的 Peer 节点之间交换节点 UDP 端口号。通过这种方式，客户端可以通过下载常规种子来自动做种他们的路由表。在第一次尝试下载 trackerless 种子的新安装客户端的路由表中将没有任何节点，种子文件中也需要节点信息。

支持 DHT 的 Peer 节点设置在 BitTorrent 协议握手中交换的 8 字节保留标志的最后一位。 Peer 节点收到指示远程 Peer 节点支持 DHT 的握手时，应发送 PORT 消息。它以字节 0x09 开头，并具有两个字节的有效负载，其中包含按网络字节顺序排列的 DHT 节点的 UDP 端口。收到此消息的 Peer 节点应尝试在远程 Peer 节点的接收端口和 IP 地址上 ping 节点。如果收到对 ping 的响应，节点应尝试根据常规规则将新的联系信息插入其路由表中。

Torrent 文件扩展名#

一个 Trackerless 种子词典没有 “发行” 键值。相反，Trackerless 的种子有一个 “节点” 键值。此键值应设置为种子生成客户端路由表中的 K 个最近的节点。或者，可以将密钥设置为已知良好的节点，例如由生成种子的人操作的节点。请不要自动添加 “Router.Bittorrent.Com” 到种子文件或自动将此节点添加到客户端路由表中。

nodes = [["<host>", <port>], ["<host>", <port>], ...]
nodes = [["127.0.0.1", 6881], ["your.router.node", 4804], ["2001:db8:100:0:d5c8:db3f:995e:c0f7", 1941]]

KRPC 协议#

KRPC 协议是一个简单的 RPC 机制，由通过 UDP 发送的编码字典组成。发送单个查询数据包，并发送单个数据包作为响应，没有重试。有三种消息类型：查询、响应和错误。对于 DHT 协议，有四个查询：ping 、 find_node 、 get_peers 和 announce_peer 。

每个 KRPC 消息是单个哈希表，每个消息具有三个通用键，并根据消息类型提供其他键值。每条消息都有一个键 “t”，其字符串值表示事务 ID 。此事务 ID 由查询节点生成，并在响应中回显，因此响应可能与对同一节点的多个查询相关联。事务 ID 应编码为一小串二进制数字，通常 2 个字符就足够了，因为它们涵盖 2^16 个未完成的查询。每条消息还有一个键 “y”，其中包含描述消息类型的单个字符值。 “y” 键的值是 “q” 表示查询，“r” 表示响应，“e” 表示错误。在具有客户端版本字符串的每条消息中都应包含一个键 “v” 。并非所有实现都包含 “v” 键，因此客户端不应假定它的存在。

Contact Encoding 联系人编码#

一种紧凑型表示 Peer 节点联系信息的编码方式，也被称为 “压缩 IP 地址 / 端口信息” 。在这种编码方式下，一个 Peer 节点的联系信息被表示成 6 个字节的字符串。其中前 4 个字节表示该 Peer 节点的 IP 地址，并且采用网络字节序（即大端序）进行编码；后两个字节则表示该 Peer 节点的端口号，同样采用网络字节序进行编码。具体地，这 6 个字节的排列顺序是先表示 IP 地址，再表示端口号，因此拼接成的字符串就是 IP 地址 + 端口号 的形式。

例如，如果一个 Peer 的 IP 地址是 192.168.1.100，端口号是 6881，那么它的联系信息就可以被表示成一个 6 个字节的字符串：
c0 a8 01 64 1a e1
其中，前 4 个字节 c0 a8 01 64 表示了 IP 地址 192.168.1.100，后 2 个字节 1a e1 则表示了端口号 6881，两部分按照 IP 地址在前、端口号在后的顺序拼接起来，就得到了这个 6 个字节的字符串。

节点信息采用的是不同的编码方式。联系节点的信息被编码为一个 26 字节的字符串，其中包含了 20 字节的节点 ID 和 6 字节的 IP 地址和端口号信息。这种编码方式也被称为” 紧凑型节点信息” 。节点可以使用这些信息来连接其他对等方并进行文件共享。

Queries 查询#

当发送一个请求时，消息字典的”y” 键设置为”q”，表示这是一个查询请求。此外，消息字典还需要包含”q” 和”a” 两个键。其中”q” 键指定具体的查询类型，”a” 键则包含了查询所需的参数。

Responses 反应#

根据 KRPC 协议规定，消息字典中包含一个”y” 键，表示消息类型，如果其值为”r”，则表示这是一个响应消息。在这种情况下，消息字典还必须包含一个额外的”r” 键，其值为一个字典，其中包含了命名的返回值。

当节点收到请求消息并成功处理后，它将发送一个响应消息来回复请求方。这个响应消息采用相同的格式，但”y” 键的值为”r”，同时包含一个额外的”r” 键，其值为一个字典，包含了响应的返回值。通过这种方式，节点之间可以进行查询和回复，实现基本的通信和交互。

Errors 错误#

在 KRPC 协议中，当消息字典中的”y” 键值为”e” 时，表示这是一个错误消息。这种情况下，消息字典会包含一个额外的”e” 键，其值为一个列表。该列表的第一个元素是一个整数，表示错误代码，第二个元素是一个字符串，包含了错误信息。这种情况通常会出现在节点收到请求消息但无法处理时，或者由于某些原因导致请求无法完成。通过发送错误消息，请求方可以了解到错误的具体原因，从而采取相应的措施。

下表描述了可能的错误代码：

错误数据包示例：

generic error = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]}
bencoded = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee

DHT 查询#

所有的查询和响应消息都包含一个”ID” 键，并且该键的值包含了发出查询或响应的节点的 ID 。对于查询消息，请求方会将自己的节点 ID 作为 “ID” 键的值附加到消息字典中。当接收方节点收到查询消息后，它会将自己的节点 ID 作为 “ID” 键的值附加到响应消息中，以便请求方在接收到响应后可以确定响应来自哪个节点。

通过使用 “ID” 键，节点之间可以建立起基本的通信和交互，使得每个节点都可以识别和跟踪来自其他节点的查询和响应消息。

Ping#

The most basic query is a ping. “q” = “ping” A ping query has a single argument, “id” the value is a 20-byte string containing the senders node ID in network byte order. The appropriate response to a ping has a single key “id” containing the node ID of the responding node.
最基本的查询是 ping 。 “q” = “ping” ping 查询具有单个参数，“id” 该值是一个 20 字节的字符串，包含按网络字节顺序排列的发送方节点 ID 。对 ping 的相应响应具有包含响应节点的节点 ID 的单个键 “id” 。

在 KRPC 协议中，“ping” 是最基本的查询类型之一，用于检测目标节点是否在线和响应正常。 “ping” 查询包含一个参数 “ID”，其值为 20 字节的字符串，在网络字节顺序下表示发送方节点的 ID 。当接收到 “ping” 查询消息后，节点会简单地回复一个带有节点 ID 的响应消息作为确认。该响应消息仅包含一个键 “ID”，其值为响应方节点的 ID 。

通过发送”ping” 查询消息和接收响应消息，节点可以确定目标节点是否处于在线状态，并且与之建立连接的准备情况。这是建立 P2P 网络中最基本的通信方式之一。

arguments:  {"id" : "<querying nodes id>"}

response: {"id" : "<queried nodes id>"}

示例数据包

ping Query = {"t":"aa", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}}
bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe

Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

Find_node#

在 KRPC 协议中，“find_node” 用于查找给定节点 ID 的联系信息。 “find_node” 查询包含两个参数：“ID” 代表请求方节点的 ID，“target” 代表查询目标节点的 ID 。

当一个节点接收到 “find_node” 查询消息后，它会根据自己的路由表和查询目标节点的 ID 来确定响应内容。如果该节点具有查询目标节点的联系信息，则会将其作为字符串格式的紧凑节点信息附加到响应消息的 “nodes” 键值中返回。如果该节点没有查询目标节点的联系信息，则会返回其自身路由表中与查询目标节点 ID 距离最近的 K（通常为 8）个节点的紧凑节点信息。

通过使用 “find_node” 查询消息和接收响应，节点可以了解到其他节点的联系信息，并且进行网络拓扑结构的构建和维护。

arguments:  {"id" : "<querying nodes id>", "target" : "<id of target node>"}

response: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}

示例数据包

find_node Query = {"t":"aa", "y":"q", "q":"find_node", "a": {"id":"abcdefghij0123456789", "target":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe

Response = {"t":"aa", "y":"r", "r": {"id":"0123456789abcdefghij", "nodes": "def456..."}}
bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re

Get_peers#

在 KRPC 协议中，“get_peers” 用于获取与特定 Torrent 的 infohash 相关联的节点列表。 “get_peers” 查询包含两个参数：“ID” 代表请求方节点的 ID，“info_hash” 代表要查询的 Torrent 文件的 infohash 。

当一个节点接收到 “get_peers” 查询消息后，它会根据自己存储的信息确定响应内容。如果该节点本身有与所查询 Torrent 的 infohash 相关联的 peer，则它会将这些 peer 的紧凑格式信息作为字符串附加到响应消息的 “values” 键中返回。每个字符串表示一个 peer 的紧凑格式信息。

如果该节点没有与所查询 Torrent 的 infohash 相关联的 peer，则它将返回其自身路由表中与 infohash 距离最近的 K（通常为 8）个节点的紧凑节点信息，其作为字符串格式的联系信息附加到响应消息的 “nodes” 键值中返回。无论是哪种情况，响应消息都包含了一个 “token” 键，其值是一个短的二进制字符串。这个 TOKEN 键可以用作未来 “announce_peer” 查询的必需参数。

通过使用”get_peers” 查询消息和接收响应，节点可以了解到与特定 Torrent 的 infohash 相关联的节点列表，并进行相应的连接和交互。

arguments:  {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>"}

response: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "values" : ["<peer 1 info string>", "<peer 2 info string>"]}

or: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "nodes" : "<compact node info>"}

示例数据包：

get_peers Query = {"t":"aa", "y":"q", "q":"get_peers", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe

Response with peers = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "values": ["axje.u", "idhtnm"]}}
bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re

Response with closest nodes = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "nodes": "def456..."}}
bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:t2:aa1:y1:re

Announce_peer#

宣布控制查询节点的对等方正在端口上下载种子。 announce_peer 有四个参数：“id” 包含查询节点的节点 ID，“info_hash” 包含种子的信息哈希，“port” 包含端口作为整数，以及响应上一个 get_peers 查询而收到的 “token” 。

一个节点可以向其他节点查询特定种子文件的 peer 列表，并通过 announce_peer 请求告知其他节点它正在下载该特定种子文件，并提供其端口号和之前收到的 token 以验证其身份。被查询的节点需要验证令牌是否来自相同的 IP 地址，并将查询节点的 IP 地址和端口号存储在其 peer 联系信息的相应 infohash 下。这样其他节点就可以向该节点连接来下载该特定种子文件。

一个可选参数 implied_port，其取值为 0 或 1 。若该参数存在且非零，则应忽略 port 参数，并使用 UDP 数据包的源端口作为对等方的端口。这对于位于 NAT 后面的对等方很有用，因为他们可能不知道自己的外部端口，同时支持 uTP 协议，它们在与 DHT 端口相同的端口上接受传入连接。

arguments:  {"id" : "<querying nodes id>",
  "implied_port": <0 or 1>,
  "info_hash" : "<20-byte infohash of target torrent>",
  "port" : <port number>,
  "token" : "<opaque token>"}

response: {"id" : "<queried nodes id>"}

示例数据包：

announce_peers Query = {"t":"aa", "y":"q", "q":"announce_peer", "a": {"id":"abcdefghij0123456789", "implied_port": 1, "info_hash":"mnopqrstuvwxyz123456", "port": 6881, "token": "aoeusnth"}}
bencoded = d1:ad2:id20:abcdefghij012345678912:implied_porti1e9:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe

Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

参考链接#

http://bittorrent.org/beps/bep_0005.html
https://hazelcast.com/glossary/distributed-hash-table/
https://en.wikipedia.org/wiki/Distributed_hash_table