BitTorrent (简称 BT) 协议是一种点对点 (Peer-to-Peer, 或简写为 P2P) 传输协议, 它被设计用来高效地分发文件 (尤其是对于大文件、多人同时下载时效率非常高), 在传统的场景下, 用户希望下载一个文件, 一般都会通过比如 HTTP / FTP 的方式从目标站点的服务器上下载, 服务器的带宽通常都是有限的, 当同时下载的用户过多时, 将超出服务器的带宽限制, 这时大家都会下载地很慢甚至是无法继续下载, 而 BitTorrent 协议便是为了解决这个问题, 它的创新点在于将文件分片, 每个终端用户下载文件分片, 在下载的同时也会互相分发自己已下载的文件分片给其它正在下载的用户, 从而将部分原本应从服务器拉取数据所造成的带宽压力分散给了终端用户, 所有正在同时下载同一文件的终端用户构成一个图结构, 互相点对点式地分发文件片段, 因此对于大文件、多人同时下载时有非常好的文件分发效率, BitTorrent 协议不是 IETF 制定的互联网标准化协议, 因而没有 RFC 文档, 关于 BitTorrent 协议标准《The BitTorrent Protocol Specification》可以从 bittorrent.org 上获得, 本文详细探讨 BitTorrent 协议 (以下简称 BT 协议) 的设计与工作原理

13.1 BitTorrent bencoding 编码

BT 协议使用 .torrent 文件用来描述资源信息, .torrent 文件也就是所说的 BT 种子文件, BT 种子文件使用 BT 协议自定义的一套编码形式来进行信息描述, 本节我们来讨论 BT 协议的编码格式 —— bencoding (B 编码)

bencoding 共有 4 种基本数据类型, 分别是 String, Integer, List 和 Dictionary

• String, 字符串类型, BT 协议的字符串使用形如 length-prefix : string-content 的形式来描述字符串, 其中 length-prefix 是字符串的长度, string-content 是字符串内容, 举例来说, 比如 4:spam 就表示字符串 'spam', 4 是该字符串的长度 (前缀统一都使用十进制表示), 前缀长度和字符串内容使用冒号分割

• Integer, 整数类型, BT 协议的整数类型使用字符 i 作为前缀, 使用字符 e 作为后缀, 在前缀 i 和后缀 e 中间的是整数本身 (整数都使用十进制表达), 例如 i3e 表示整数 3, i-3e 代表整数 -3, 整数类型本身没有大小限制, 特别地, 形如 i-0e 这样的是非法的整数, 包括 i03e 这样的表示方法也是非法的, 但 i0e 是合法的, 它表示整数 0

• List, 列表类型, BT 协议的列表类型使用字符 l 作为前缀, 使用字符 e 作为后缀, 在前缀 i 和后缀 e 之间的是列表的元素 (列表元素也都使用 bencoding 编码方法), 例如 l4:spam4:eggse 表示列表 ['spam', 'eggs']

• Dictionary, 字典类型, BT 协议的字典类型使用字符 d 作为前缀, 使用字符 e 作为后缀, 在前缀 i 和后缀 e 之间的是 k-v 对, 其中字典的键 (key) 必须是 bencoding 编码的 String 形式, 而字典键所对应的值可以是 bencoding 编码的任何一种类型 (String, Integer, List, Dictionary), 举例来说, d3:cow3:moo4:spam4:eggse 表示 {'cow3': 'moo', 'spam':'eggs'}, 再比如 d4:spaml1:a1:bee 表示 {'spam':['a', 'b']}, 另外, bencoding 编码的 Dictionary 类型必须是有序字典, 即它的所有 Key 的出现顺序必须是按字典序升序排列的 (sorted as raw strings, not alphanumerics)

从上面的编码原理可以知道, B 编码的数字都采用十进制, 以 UTF-8 字符串来表示, 这不如二进制编码的效率高, 但 B 编码不会存在字节序的问题, 具有很好的跨平台性

13.2 BitTorrent 种子文件

BT 协议的 metainfo file 用来描述资源的元信息, 如资源的 URL, 资源的 SHA1 哈希等, 它的文件后缀为 .torrent, 也就是常所说的 BT 种子文件 (BT 种子文件中的文本内容统一使用 UTF-8 编码), BT 种子文件使用上一节所描述的 bencoding 编码来描述信息, 整个 BT 种子文件实际上就是一个 bencoding 编码的 Dictionary, 它有两个 Key, 分别是 announce 和 info

• announce, 对应的 Value 为 BT Tracker 的 URL (关于 BT Tracker 将在下面讨论)

• announce-list, 可选, 对应的 Value 为备用 BT Tracker 的 URL

• creation date, 可选, 对应的 Value 为种子的创建时间 (UNIX 时间戳), 如 13:creation datei1542799851e

• comment, 可选, 对应的 Value 为种子制作者添加的备注信息

• created by, 可选, 该关键字对应的值为生成种子文件的 BT 客户端软件的信息, 如客户端名、版本号等

• info, 对应的 Value 是一个 dictionary, dictionary 有如下 key

  • name, 对应的值是一个 UTF-8 编码的字符串, 代表资源名称
  • piece length, 对应的值是文件以字节为单位的每个分片的长度 (在 BT 协议中, 文件是以分片 (piece) 的形式分发的, BT 协议将要传输的文件切割为若干个固定长度的 piece, 因为最后一个分片可能是零头, 所以除了最后一个分片, 其它分片的长度都是相等的, 分片的长度通常取 2 的整数次幂, 按照最新版 BT 协议, 分片长度的值为 $2^{18}$ 字节, 即 256 KB, 对应的 B 编码为 i262144e)
  • piece, 对应的值为字节序列, 字节序列的长度为 20 的整数倍, 若该将字节序列按 20 个字节为一组切分开, 则每组都是文件相对应 piece 的 SHA1 哈希值 (哈希值是二进制形式记录的, 因而是 unreadable 的, 使用文本编辑器打开会显示乱码)
  • length / files, 这两个键不能同时存在, 有且仅有其中一个, 若 .torrent 文件描述的文件只有一个, 则 length 键存在, 其值为该文件以字节为单位的长度, 若 .torrent 文件描述的文件有多个, 则 files 键存在, 其值为一个字典的列表, 即列表的每一个元素都是一个字典结构, 每个字典都描述了其中的一个文件, 每个字典结构中包含两个 key, 分别是 length, 代表该文件以字节为单位的长度, path, 代表该文件的相对路径名

bittorrent.org 上的《The BitTorrent Protocol Specification》关于 .torrent 文件中的 Key 讲述的不全, 只提到了 info 和 announce 这两个 Key, 建议读者下载真实的 .torrent 文件使用诸如 Vim / VSCode 之类的文本编辑器自行分析一下实际的种子文件结构

13.3 BitTorrent Tracker

BT Tracker 是一个注册服务, 用来协调 BT 协议的文件分发, 通过 BT Tracker 可以知道当前有哪些终端在同时下载目标资源, 当终端执行下载任务时应首先请求 BT Tracker 服务获取当前正在下载同一资源的对等结点信息, 终端用户通过 Tracker GET 请求 (可以是 HTTP 或 UDP 或其它, 具体使用的协议由 .torrent 文件的 announce 对应的 Value 值给出) BT Tracker 服务, Tracker GET 请求包含如下参数:

• info_hash, 20 字节, 将 .torrent 文件中的 info 键对应的值生成的 SHA1 哈希, 该哈希值可作为所要请求的资源的标识符

• peer_id, 终端生成的 20 个字符的唯一标识符, 每个进行 BT 下载的终端随机生成的 20 个字符的字符串作为其标识符 (终端应在每次开始一个新的下载任务时重新随机生成一个新的 peer_id)

• IP (可选), 该终端的 IP 地址, 一般情况下该参数没有必要, 因为传输层 (Transport Layer, 如 TCP) 本身可以获取 IP 地址, 但比如 BT 下载器通过 Proxy 与 Tracker 交互时, 该在该字段中设置源端的真实 IP

• Port, 该终端正在监听的端口 (因为 BT 协议是 P2P 的, 所以每一个下载终端也都会暴露一个端口, 供其它结点下载), BT 下载器首先尝试监听 6881 端口, 若端口被占用被继续尝试监听 6882 端口, 若仍被占用则继续监听 6883, 6884 ... 直到 6889 端口, 若以上所有端口都被占用了, 则放弃尝试

• uploaded, 当前已经上传的文件的字节数 (十进制数字表示)

• downloaded, 当前已经下载的文件的字节数 (十进制数字表示)

• left, 当前仍需要下载的文件的字节数 (十进制数字表示)

• numwant, 可选, 希望 BT Tracker 返回的 peer 数目, 若不填, 默认返回 50 个 IP 和 Port

• event, 可选, 该参数的值可以是 started, completed, stopped, empty 其中的一个, 该参数的值为 empty 与该参数不存在是等价的, 当开始下载时, 该参数的值设置为 started, 当下载完成时, 该参数的值设置为 completed, 当下载停止时, 该参数的值设置为 stopped

在向 BT Tracker 发送包含以上参数的 GET 请求后, 正常情况下, BT Tracker 会返回一个 bencoding 编码的字典, 如果字典中含有 failure reason 的 Key, 则说明此次请求失败, 同时该 Key 对应的值是一个可读性的字符串, 用于向终端用户展示此次请求失败的原因, 在请求失败的情况下, BT Tracker 返回的字典里有且仅有这个一个 Key, 请求成功时, BT Tracker 返回的字典中应含有以下 Key

• warnging message, 当发生非致命性错误时, Tracker 返回的可读的警告信息

• interval, 对应的 Value 是终端在下一次请求 BT Tracker 前应等待的时间 (以秒为单位)

• min interval, 对应的 Value 是终端在下一次请求 BT Tracker 前的最短等待时间 (以秒为单位)

• complete, 对应的 Value 表明当前已完成整个资源下载的 peer 的数量

• incomplete, 对应的 Value 表明当前未完成整个资源下载的 peer 的数量

• peers, 对应的 Value 是一个字典的列表, 即列表的每一个元素都是一个字典, 每个字典包含有两个 Key, 分别为:

  • peer id, peer 结点的 Id
  • IP, peer 结点的 IP 地址
  • Port, peer 结点的端口

13.4 BitTorrent Peer Protocol

Peer Protocol 是当前正在下载同一资源的对等结点 (peer) 之间进行数据传输使用的协议, BT 协议的 Peer Protocol 基于 TCP 或 uTP (关于 uTP 我将在以后的博客中单独讨论), 在使用 BT 协议下载时, 所有正在下载同一资源的结点都是对等的, 结点之间相互建立的连接也是对等的, 对等结点建立的连接的数据传输方向是双向的, 数据可以由任何一端发往另一端, 对等结点每接收到一个完整的 piece 之后, 接收方便计算该 piece 的 SHA1 哈希并与 .torrent 文件中的 info 对应的字典的 piece 对应的 Value 的相应分段做对比, 若哈希值相等, 则说明该分片传输成功, 此时这两个对等结点都拥有了资源文件关于该 piece 的数据, 在实际的传输过程中, piece 会进一步分为固定大小的 slice, 对等结点使用 slice 作为最基本的数据传输单位, 接收到一个 piece 的所有 slice 之后便计算 SHA1 哈希进行对比

对等结点在建立完传输层连接 (如 TCP) 之后, 便开始进行 Peer Protocol 的握手, 握手消息依次含有如下数据:

• pstrlen, 该值固定为 19 (十进制格式, 使用 4 字节大端字节序)

• pstr, 该值为 "BitTorrent protocol" (BitTorrent 协议的关键字)

• reserved, BT 协议的保留字段, 用于以后扩展用, 一般将这 8 字节全部设置为 0, 某些 BT 客户端没有正确实现协议或者使用了某种扩展而发送了不全为 0 的握手信息, 此时忽略即可

• info_hash, 与请求 BT Tracker 时发送的 info_hash 参数值相同

• peer_id, 与请求 BT Tracker 时发送的 peer_id 参数值相同

即握手消息的格式为 <pstrlen><pstr><reserved><info_hash><peer_id>, 对等结点一方在传输层连接建立以后便发送握手信息, 另一方收到握手信息后也回复一个握手信息, 任何一方当收到非法的握手信息 (如 pstrlen 不等于 19, pstr 缺失或其值不是 "BitTorrent protocol", info_hash 不相等, peer_id 与预期值不同等) 应立即断开连接

若校验没有问题, 则握手成功, 之后对等双方开始进行数据传输, 数据的通用格式为 <length prefix><type id><payload>, 其中 length prefix 顾名思义是消息的长度 (即 len(type id) + len(payload)), type id (十进制整数) 指示消息的类型, 特别地, length prefix 为 0 (此时消息没有 type id 也没有 payload) 代表 Keep Alive 消息, BT 协议标准规定 Keep Alive 消息每 2 min 发送一次, 接收端忽略该消息即可, 对于其它类型的消息, 其对应的 type id 如下

• type id = 0, 代表 choke 消息, choke 消息没有 payload, 其 length prefix 等于 1

• type id = 1, 代表 unchoke 消息, unchoke 消息没有 payload, 其 length prefix 等于 1

• type id = 2, 代表 interested 消息, interested 消息没有 payload, 其 length prefix 等于 1

• type id = 3, 代表 not interested 消息, not interested 消息没有 payload, 其 length prefix 等于 1

• type id = 4, 代表 have 消息, have 消息的 paylod 只包含一个整数, 该整数对应的是该终端刚刚接收完成并校验通过 SHA1 哈希的 piece 索引 (终端在接收到并校验完一个 piece 后, 就向它所知道的所有 peer 都发送 have 消息以宣示它拥有了这个 piece, 其它终端接收到 have 消息之后便可以知道对方已经有该 piece 的文件数据了, 因而可以向其发送 request 消息来获取该 piece)

• type id = 5, 代表 bitfield 消息, bitfield 消息只作为对等结点进行通信时所发送的第一个消息 (即在握手完成之后, 其它类型消息发送之前), 若文件没有分片, 则不发送该消息, 它的 Payload 是一个字节序列, 逻辑上是一个 bitmap 结构, 指示当前该终端已下载的文件分片, 其中第一个字节的 8 位分别表示文件的前 8 个分片, 第二个字节的 8 位分别表示文件的第 9 至 16 个分片, 以此类推, 已下载的分片对应的位的值为 1, 否则为 0, 由于文件分片数不一定是 8 的整数倍, 所以最后一个分片可能有冗余的比特位, 对于这些冗余的比特位都设置为 0

• type id = 6, 代表 request 消息, request 消息用于一方向另一方请求文件数据, 它的 Payload 含有 3 个字段, 分别是 index, begin 和 length. 其中 index 指示文件分片的索引 (索引从 0 开始), begin 指示 index 对应的 piece 内的字节索引 (索引从 0 开始), length 指定请求的长度, length 一般都取 2 的整数次幂, 现在所有的 BitTorrent 实现中, length 的值都取 $2^{14}$, 即 16 KB, BitTorrent 协议规定结点通过随机的顺序请求下载文件 piece

• type id = 7, 代表 piece 消息, piece 消息是对 request 消息的响应, 即返回对应的文件片段, 它的 Payload 含有 3 个字段, 分别是 index, begin 和 piece, 其中 index 和 begin 字段与 request 消息中的 index 与 begin 含义相同, 而 piece 是所请求的文件片段

• type id = 8, 代表 cancel 消息, cancel 消息与 request 消息的 Payload 字段完全相同, 但作用相反, 用于取消对应的下载请求

从逻辑上讲, 在进行 BT 下载时, 建立了 P2P 连接的对等结点两端各维护一个状态机, 状态机的状态可以用四个比特位来表征, 这两个比特位分别代表以下 4 个状态:

• am_chocking, 该值若为 1 代表当前终端将另一端阻塞 (通过向对端发送 choke 消息), 将另一端阻塞期间将不再接受对方的请求, 对方无法从当前终端下载数据, 反之, 则没有阻塞对方, 则允许对方下载数据

• am_interested, 该值若为 1 代表当前终端对另一端 "感兴趣" (通过向对方发送 interested 消息), 所谓 "感兴趣" 即是对方拥有自己所没有的文件 piece, 因此当前终端希望从对方下载对应的数据

• peer_chocking, 该值为 1 代表对方将当前终端阻塞 (收到了对端发来的 choke 消息), 此时当前终端无法继续向对方请求数据

• peer_interested, 该值为 1 代表对方对自己感兴趣 (收到了对端发来的 interested 消息), 即当前终端拥有另一端所没有的文件片段

当前终端从另一端下载数据当且仅当当前终端对另一端感兴趣且另一端没有将当前终端阻塞, 反过来, 另一端从当前终端下载数据当且仅当另一端对当前终端感兴趣且当前终端没有将另一端阻塞, 初始化状态下, BT 客户端对所有其它的 peer 结点都是 choked 状态, BitTorrent 设计的初衷是希望结点之间公平地进行文件分发, 保证所有结点的对等性, 为了避免某些结点只下载而不上传, BitTorrent 协议采用特定的 choke 算法来维护平衡, BT 终端每 10s 统计一次将当前下载速度最快并且对其感兴趣的 4 个 peer 结点, 向它们发送 unchoke 消息, 解除对其的阻塞, choke 算法将直接决定 BT 下载的公平性与效率, 可以阅读相应的 BitTorrent 客户端代码了解更多关于 choke 算法的实现