Bittorrent 协议浅析（四）分布式哈希
原创
0. 回顾
前序文章：
- Bittorrent 协议浅析（一）元数据文件 /developer/article/2332701
- Bittorrent 协议浅析（二）Tracker 和 对等节点/developer/article/2333043
- Bittorrent 协议浅析（三）对等数据传输实例/developer/article/2333677
前文内容回顾：
BitTorrent 是一种用于分发文件的协议，元数据文件采用 bencode 编码，分片进行 SHA-1 哈希计算比对，并介绍元数据文件数据结构，通过 HTTP 请求由 Trakcer 交换节点信息，节点直接直接进行通讯
在前面三个部分中所提到的内容基本都是 BEP 0003 的，也就是 BitTorrent 第一版协议，它属于最终版本，几乎不会产生变动，但从这篇文章开始所述的内容，可能随着时间的推移发生改变，可能随着协议的改变文章内容不再准确，之后将会给出完成所依据的协议链接，建议在阅读过程中参考协议进行阅读，以适应内容的变化。
在讨论快速交换，新版本的 BitTorrent 协议之前，分布式哈希表（Distributed Sloppy Hash Table，DHT）是无论如何想要探讨的内容，它在 BitTorrent 协议当中并不是必要的，不依赖它也可以正常使用，甚至有的场合使用者会主动关闭这个功能，但不可否认的是分布式哈希在整个使用过程中起到的关键而重要的作用。
1. 分布式哈希
在前文中说，在 BitTorrent 数据传输过程中 Tracker 具有较为重要的地位，下载器会向 Tracker 发送 GET 请求来宣告自己并获取其他参与下载的下载器的地址和端口，Trakcer 一定需要中心服务器，通常需要支持 HTTP 服务，这是一个较大的不稳定因素，有的资源可能没有 Tracker 地址或其 Tracker 地址已经停止服务，又或者出于各种原因无法访问 Tracker 地址的时，就无法获取到其他下载器的信息。但随着分布式哈希在 BitTorrent 中的使用，让这一问题得到了解决，每一个节点都可以成为一个 Tracker，节点之间相互交换数据，共同维护一个巨大的信息网络，实现了这些资源的连接和传输。
本文的目的不是并且也不打算分析和阐述分布式哈希的原理和实现，仅阐述重要部分，为了方便理解会忽略一些细节和规定，分布式哈希也有很多类型，对原理有兴趣的可以去查看 《Kademlia: A Peer-to-peer Information System Based on the XOR Metric》 ，至于其历史和发展经过，就更不在我们的讨论范围了。
路由表
每一个节点都有一个唯一的 160 位（20字节）节点 ID，每个节点都应该有一个路由表，包括一部分其他节点的信息，具体的，需要包含更多的与自己更近的节点路由，和少量与自己距离较远的路由。
在继续之前，需要先了解 距离 这个概念，在实现过程中，这个距离和实际的物理距离、网络延时等均无关，仅和自身的节点 ID 有关，节点的距离通过 异或 运算进行计算，结算结果视为无符号整数，数值越小表明距离越近。
维护路由表过程中，仅应该保留最近 15 分钟有正确回应的节点信息，需要质疑超过 15 分钟的节点，通过向其发送响应请求来对其进行判断（后文会具体说明），在多次连续请求未能响应的情况下，应该认为节点连接变得糟糕，这些节点不应保留在路由表中，并且其权重应该降低甚至舍弃。
路由表应该覆盖整个节点 ID 空间，即从 0 到 2^160，并通过桶（bucket）来进行划分，每个桶负责管理一部分的空间，节点只会被插入到对应范围的空间桶空间当中，当初始化时，仅有一个对应整个空间的桶。每一个桶都有最大容量限制，在 BEP0005 中给出的当前实现为 8，当一个桶包含了 8 个良好节点时，认为该桶已满。
当一个桶满之后，如果有新的节点出现，需要进行判断，可以选择拆分或丢弃，拆分桶后每个新的桶负责的节点范围是原范围的一半。拆分和丢弃通常可以出于以下几个方面考虑：若自身的节点 ID 位于满足条件的桶的范围内，则需将目前所在的桶进行拆分，同时还需要考虑桶最近是否变化以及考虑系统性能和资源消耗来综合评判。
当出现如下情况时，需要认为桶状态发生了变化：
- 对桶中的节点进行 ping 测试并响应。
- 向桶中添加一个新节点时。
- 桶中的一个节点被替换为另一个节点。
如果一个桶在15分钟内没有发生任何变化，那么应该进行"刷新"操作，即通过在随机选择一个 ID 并对其执行 "find_nodes" 搜索。对于不能接收其他节点查询的节点需要定期刷新所有桶，以便保持良好的连接。
在维护路由表过程中，节点应该尝试通过向离自己越来越近的节点执行 "find_nodes" 来找到距离自己最近的节点。
元数据文件拓展
当一个新节点试图下载一个无 Trakcer 的 BitTorrent 数据时，需要通过元数据文件进行，一个无 Trakcer 的 BitTorrent 元数据文件中可以不包含 Announce 键，取而代之的是 nodes 键值，包含一个 域名或IP，端口号组成的列表的列表。
nodes = [["<host>", <port>], ["<host>", <port>], ...]
nodes = [["127.0.0.1", 6881], ["your.router.node", 4804], ["2001:db8:100:0:d5c8:db3f:995e:c0f7", 1941]]BitTorrent 拓展协议
当节点支持 DHT 拓展，在握手过程中将预留位的最后一字节的最后一位置位，以表示支持该拓展。
当下载器收到该握手信息后，其通讯内容新增：
标记 | 说明 |
|---|---|
0x09 | PORT |
通过 PORT 信息，可告知对方自己 DHT 监听的 UDP 端口。
以前面文章的种子信息为例，通过 Sockit 在 UDP 9000 （0x2328）端口进行监听，发送支持拓展的握手数据，并发送 PORT 信息，可以看到监听的 UDP 端口收到了来自 Transmission 的 DHT 数据，这是一个 KRPC 协议的 ping 查询，将在后面章节进行具体阐述。
所发送的 PORT 信息为：
00 00 00 03 09 23 28信息长度为 3 字节，类型标记为 0x09，有效内容标识了 UDP 端口 0x2328（9000）。
KRPC协议
上述的 UDP 收到的数据即为 KRPC 的 ping 查询，KRPC 协议是一种简单的远程过程调用（RPC），由通过 UDP 发送的编码字典组成，编码方式与BitTorrent 元数据文件编码方式一样为 Becode 编码。
消息类型分为三种：查询、响应和错误。对于本文所探讨的 DHT ，有四个查询：ping、find_node、get_peers和announce_peer，具体将在下文中详细分析。
KRPC 的消息类型是一个字典，通常包含通用键（t，y，v）和其他键，以上文的例子为例：
{
"a": {
"id": b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
},
"q": "ping",
"t": b'pn\x00\x00',
"y": "q"
}每一条消息中包含一个 t，由查询方生成，在响应中回显，以表明响应是针对哪一个查询进行的；y 表示类型，一定为“q”（表示查询）、“r”（表示响应）或“e”（表示错误）；每条带有客户端版本字符串的消息中都应包含键“v”，但显然在这个请求中并没有包含，在很多实现中都不包含这一键，不应假设其一定存在。
a 和 q 则是 q 这一查询的附加键。q 是一个字符串，其中包含查询的方法名称。a 是一个字典，其中包含查询参数。
y 值为 r 或 KRPC 消息字典包含键 r 则表明是成功完成查询后发送响应消息，类型为字典。
y 值为 e 或 KRPC 消息字典包含键 e 则表明是失败完成查询后发送响应消息，类型为列表。
对于错误响应 e，列表第一个元素为错误代码，第二个元素为错误消息字符串，常见的：
错误代码 | 描述 |
|---|---|
201 | 一般错误 |
202 | 服务器错误 |
203 | 协议错误 |
204 | 方法未知 |
例如 d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee 就是一个错误响应，对应
{
"t":"aa",
"y":"e",
"e":[201, "A Generic Error Ocurred"]
}现在来看请求和对应的响应：
所有查询和响应都有一个 id 的键值对，其中包含查询节点或响应节点的节点 ID。
ping 请求：
ping 请求是最基本的请求，只包含 id 参数，例如这是一个请求和返回：
// 请求
d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe
// 返回
d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re对应
// 请求
{
"t":"aa",
"y":"q",
"q":"ping",
"a":{"id":"abcdefghij0123456789"}
}
// 返回
{
"t":"aa",
"y":"r",
"r": {"id":"mnopqrstuvwxyz123456"}
}find_node 请求：
在 find_node 请求中，还要包含 target 参数，target 为目标，当收到 find_node 请求，节点应该从自己的路由表中选择最大桶容量数量的节点进行响应，对 IP 地址和端口使用紧凑型编码（紧凑型编码参考 Tracker 部分）。
以下是一对请求返回的实例：
// 请求
d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe
// 返回
d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re对应
// 请求
{"t":"aa", "y":"q", "q":"find_node", "a": {"id":"abcdefghij0123456789", "target":"mnopqrstuvwxyz123456"}}
// 返回
{"t":"aa", "y":"r", "r": {"id":"0123456789abcdefghij", "nodes": "def456..."}}get_peers 请求：
在 DHT 协议中，get_peers 请求用于获取与特定种子的信息哈希（参见元数据结构相关内容）关联的对等节点。还额外包含 info_hash 参数，即要查找对等节点的种子的 infohash。
节点收到 get_peers 请求后，它会查找与指定信息哈希关联的对等节点。若找到包含请求信息哈希的想一个，则返回带 values 列表的响应，若没有包含请求信息哈希的响应，则返回一个包含 nodes 的响应。
其中：
"token"：token是一个令牌，将用于后续的announce_peer请求。"values"：一个包含对等节点信息字符串的列表，每个字符串包括单个对等节点的紧凑地址端口信息。"nodes": 最大桶容量数量的节点紧凑编码进行响应，与上文一致。
示例：
// 请求
d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe
// 包含结果的响应
d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re
// 更近的节点的响应
d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:t2:aa1:y1:re对应：
// 请求
{
"t": "aa",
"y": "q",
"q": "get_peers",
"a": {
"id": "abcdefghij0123456789",
"info_hash": "mnopqrstuvwxyz123456"
}
}
// 包含结果的响应
{
"t": "aa",
"y": "r",
"r": {
"id": "abcdefghij0123456789",
"token": "aoeusnth",
"values": ["axje.u", "idhtnm"]
}
}
// 更近节点的响应
{
"t": "aa",
"y": "r",
"r": {
"id": "abcdefghij0123456789",
"token": "aoeusnth",
"nodes": "def456..."
}
}announce_peer 请求：
announce_peer 请求用于宣布节点正在下载指定信息哈希的内容。这个请求包括以下参数：
"info_hash"：要宣布下载的种子的 infohash。"port"：下载者正在监听的 UDP 端口。"token"：之前从get_peers请求响应中获取的令牌。"implied_port"：可选参数，一个整数值，如果为 0，则使用"port"参数指定的端口，否则使用传入连接的端口，这通常为了让在 NAT 后的设备可以正确收到相应。
以下是一个 announce_peer 请求的示例：
d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe对应的 JSON 请求示例：
{
"t": "aa",
"y": "q",
"q": "announce_peer",
"a": {
"id": "abcdefghij0123456789",
"info_hash": "mnopqrstuvwxyz123456",
"port": 6881,
"token": "aoeusnth",
"implied_port": 0
}
}其相应为仅包含 ID 的基本相应。
只读 DHT
只读分布式哈希（ReadOnly DHT） 是 BEP43 所提出的，在每一个传出的请求的定级字典中包含一个 ro=1 的键来标明自己的只读（Read Only）状态。
只读状态适用于：
- 位于 NAT 后且尝试穿透的设备或其他由于各种原因无法外部访问的设备；
- 会产生额外成本（如网络流量，电池损耗等）的设备，特别是移动设备；
分布式哈希 完
至此，分布式哈希的内容（BEP5）已经全部分析完毕了，你可能会发现，似乎完成了这部分的阅读，还是不知道如何通过信息哈希来获取一个 BitTorrent 的元数据文件，即无法获取 .torrent 的种子文件。没错，DHT 部分并没有提供元数据的交换，DHT 只帮助找到其他正在下载该内容的对等节点，如果希望通过信息哈希获取元数据，还需要实现 BEP0010 扩展协议和 BEP0009 元数据交换的扩展，将在后续文章中进行阐述，如果进行了更新，链接会放在这里：
在此再次呼吁阅读本文的各位遵循社区规定，做一个良好的参与者，单纯地进行 DHT 查询而不提供任何资源（特别是未标明只读情况下），或者反复向节点发出请求都会被认为是不礼貌的行为。
最后，本文参加的征文活动广告：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。