关于 BitTorrent 的 Fast Extension 你必须要知道的

Fast Extension 协议扩展的开启方式，需要在 BitTorrent 握手协议中设置一位特定的二进制位来开启。在 BitTorrent 握手协议中的保留字节（reserved byte）的第三个最低有效位（third least significant bit）设置为 1，即将其与 0x04 进行按位或运算，来启用 Fast Extension 。例如：

reserved[7] |= 0x04

如果连接的两端都设置了这一位，那么 Fast Extension 就会被启用，并且可以使用其中的四个扩展功能：Have None/Have All 、 Reject Requests 、 Suggestions 和 Allowed Fast 。

需要注意的是，Fast Extension 只有在支持该协议扩展的两个 BitTorrent 客户端之间建立连接时才能生效。否则，即使设置了这一位，也无法启用 Fast Extension 。

BitTorrent 协议中消息的语法指定所有整数都是四个字节的大端序，并且所有消息都以一个整数的消息长度开始。此外，它还指定除 Keep-Alive 外的所有消息将具有单个字节的操作码和零个或多个依赖于操作码的参数。声明应按照 IETF RFC 2119 中所述的方式解释某些关键词（MUST 、 MUST NOT 、 REQUIRED 、 SHALL 、 SHALL NOT 、 SHOULD 、 SHOULD NOT 、 RECOMMENDED 、 MAY 和 OPTIONAL）。这意味着这些单词具有在 RFC 中定义的特定含义，它们用于指示对特定动作或行为的要求或建议水平。例如，“MUST” 表示必须遵循某项要求，“SHOULD” 则表示应该遵循某项建议，除非存在充分理由不这样做。

现有消息语义的修改

Fast Extension 对请求（Request）、阻塞（Choke）、取消阻塞（Unchoke）和取消请求（Cancel）消息的语义进行修改，并添加了一个拒绝请求（Reject Request）消息。现在，每个请求都保证只会收到一个响应，即相应的拒绝或相应的 piece 消息。即使请求被取消，接收到取消请求的节点也应该发送相应的拒绝或相应的 piece ：正在处理中的请求仍然允许完成。阻塞不再隐含地拒绝所有挂起的请求，从而消除了一些可能导致重复请求不必要的 piece 的竞争条件。此外，如果一个节点收到了一个从未请求的 piece ，那么它必须关闭连接。

Have All/Have None

*Have All*: <len=0x0001> <op=0x0E>
      *Have None*: <len=0x0001><op=0x0F>
      这两种消息都包含一个长度为 1 字节的整数和一个操作码，其中 "Have All" 的操作码是 0x0E，"Have None" 的操作码是 0x0F 。当存在这两个消息时，它们会替换掉 “Have Bitfield” 消息。在握手之后，必须恰好出现一个 “Have All” 、"Have None" 或 "Have Bitfield" 中的一个。

“Have All” 和 “Have None” 是 BitTorrent 协议中的消息类型，表示发送方已经拥有所有或者没有任何 piece 。当存在这两个消息时，它们会替换掉 “Have Bitfield” 消息。在握手之后，必须恰好出现一个 “Have All” 、”Have None” 或 “Have Bitfield” 中的一个。

这些消息的目的是为了节省带宽，并且避免没有 piece 时不发送任何消息的特殊情况。当 Fast Extension 被禁用时，如果某个节点接收到 “Have All” 或 “Have None” 消息，则该节点必须关闭连接。

建议性 Piece

*Suggest Piece*: <len=0x0005><op=0x0D><index>

“Suggest Piece“ 是一个建议性的消息，意味着” 您可能想要下载这个 piece” 。它的预期用途是为了在不降低吞吐量的情况下进行超级共享（super-seeding1），以避免重复下载，并使磁盘 I/O 受限的种子可以上传连续或相同的数据块，以避免过多的磁盘查找。在所有情况下，种子应该操作以在网络中维护大致相等数量的每个块的副本。

对于任何给定时间，节点可以发送多个”Suggest Piece” 消息。如果接收方收到多个”Suggest Piece” 消息，则可能会将其解释为表示所有建议的块都同样适合下载。

当禁用 Fast Extension 时，如果一个节点收到了一个”Suggest Piece” 消息，则该节点必须关闭连接。

Reject Request 拒绝请求

*Reject Request*: <len=0x000D><op=0x10><index><begin><length>
      通过发送这个消息，Peer 可以告诉其他 Peer 自己无法提供所请求的数据块。接收方在收到该消息后，会将相应的请求从队列中删除，并尝试向其他 Peer 请求相同的数据块。

Reject Request 用于通知请求方，它所请求的数据块无法被满足。

如果 Fast Extension 没有启用，且一个节点接收到了 Reject Request 消息，则该节点必须关闭与请求方之间的连接。

启用 Fast Extension 时，节点在处理 Reject Request 消息时的规范行为：

• 如果一个节点接收到一个未曾发送请求的 Reject Request 消息，则它应该关闭与发出该消息的节点之间的连接。

• 当一个节点向另一个节点发送 Choke 消息时，它必须拒绝该节点发出的所有请求，除非这些请求涉及允许的快速集合中的数据块。节点应该先 choke 再拒绝请求，这样收到 Choke 消息的节点不会重新请求那些被 choke 的数据块。

• 如果一个节点收到了来自被 choke 的节点的请求，则它会拒绝该请求，除非所请求的数据块在允许的快速集合中。

• 如果一个节点收到了太多来自被 choke 的节点的请求，则它可以选择关闭连接而不是拒绝这些请求。但是，要考虑到一旦一个节点被 choke，缓冲区可以需要几秒钟才能排空并且消息传播才能完成。因此，需要在决定关闭连接之前仔细考虑这个问题。

Allowed Fast

*Allowed Fast*: <len=0x0005><op=0x11><index>

使用指定的 BitTorrent 协议，新加入的节点由于缺少数据片段，需要等待一段时间才能与其他节点进行有效的文件共享。在这个过程中，节点可能会不断地被 choke（阻止上传），导致共享效率降低。

为了解决这个问题，BitTorrent 协议中引入了 “Allowed Fast” 消息。这个消息告诉其他节点，即使自己处于 choke 状态，也可以向它请求某些数据片段，并保证会立即响应。这样，其他节点就可以更快地获取到需要的数据，而新加入节点也可以更快地开始参与 tit-for-tat 的交换过程，从而提高整个网络的文件共享效率。

在这个协议中，当一个节点拥有某个文件的一部分时，它可以把这些 piece 分享给其他节点。当其他节点需要下载这个文件时，它们可以从那个节点处请求这些 piece，以便更快地完成文件的下载。

而 “Allowed Fast 集合” 则是指每个节点所允许请求的一组 piece 的集合。为了保证所有节点之间的数据请求都是公平的，在协议中使用了一个经过验证的生成算法来生成这个集合。这个算法会为每个接收消息的节点生成唯一的 piece 索引，使得当两个节点都提供了 k 个 piece 时，它们所能够请求的 piece 的数量也是相同的；如果其中一个节点提供了 k+1 个 piece，则请求数量也会相应增加一个。 k 的值应该足够小以避免滥用，但又足够大以实现 “以牙还牙” 的策略。作者目前将 k 的默认值设置为 10，但节点可以自由更改这个数字，以适应不同的负载情况。

发送方可以在 Allowed Fast 消息中列出它还没有实际拥有的 pieces ，接收方不能根据 Allowed Fast 消息认为发送方确实拥有这些 pieces 。这样做的目的是为了允许节点在连接开始时生成和通信允许快速集合。然而，发送方随时都可以发送 Allowed Fast 消息。

一个节点如果有足够的资源，应该向任何一个起始节点发送 Allowed Fast 消息，以提高其他节点下载文件分块的速度。但是，在某些情况下，节点可以拒绝已经发送了 Allowed Fast pieces 的请求，例如本地节点资源不足、请求的 pieces 已经发送给请求的节点、或者请求节点并非一个起始节点。此外，当前实现的规则还规定了一种情况，即当请求节点已经下载了超过 k 个 pieces 时，请求被拒绝。

当 Fast 扩展被禁用时，只要节点收到了 Allowed Fast 消息，它就没有能力处理这种消息，因此必须断开与发送方的连接。这个规则的目的是确保协议的兼容性和正确性，保证所有节点都能够按照相同的规则进行通信，从而实现文件分块的有效下载和传输。

Allowed Fast Set 机制

计算对等节点的快速列表的标准算法中所有的整数都是四个字节（32 位）的网络字节序（大端序）。 [a:b] 表示从 a 到 b 的连续字节序列，不包括 b，即 (a, a+1, a+2,…, b-1) 。 x[a:b] 表示数组 x 中从索引 a 开始到索引 b（但不包括 b）的子序列。

计算网络地址的方法。其中，“ip” 代表 P’*s IPv4 地址。该方法目前不支持 IPv6 地址。如果对等方在 NAT 后面，则 “ip” 应为 NAT 的外部 IP 地址。由于发送 “Allowed Fast” 消息的节点计算集合，因此通常正确的 “ip” 是连接另一端的 “ip” 地址。计算集合的主机可以根据需要使用连接另一端的 “ip” 地址。简而言之，这意味着，在计算集合时，可以选择使用连接另一端的 IP 地址作为计算中的 IP 地址，而不一定是自己的 IP 地址。

用 “sz” 代表种子文件中分片的数量。而 “a” 代表允许快速下载的集合，该集合包含一些不在正常下载顺序中的分片。最后，“k” 代表被允许以快速方式下载的分片数量，即允许快速下载的集合中所包含的分片数目。

x = 0xFFFFFF00 & ip                           (1)
      x.append(infohash)                            (2)
      while |a| < k:
        x = SHA1(x)                                 (3)
        for i in [0:5] and |a| < k:                 (4)
          j = i*4                                   (5)
          y = x[j:j+4]                              (6)
          index = y % sz                            (7)
          if index not in a:                        (8)
            add index to a                          (9)

第一步（1）选择节点 P’*s 的 IP 地址中最重要的八位字节。这样可以防止同一个网络上的用户获得多个 Allowed Fast Set 。使用三个字节是基于经验和历史原因的。

第三步（3）在每个调用上生成一个 20 字节的随机数。通过对前一次迭代的哈希执行 SHA-1 哈希，我们可以生成任意长度的伪随机序列。

步骤（4）到（9）将 20 字节哈希划分为若干片段索引，并将其添加到允许快速集合中。简单来说，该过程将随机数分成了 5 个 4 字节的片段，并将每个片段作为指向表示内容不同部分的索引集合中的一个索引。如果该索引尚未被添加到允许快速集合中，则将其添加到集合中。这确保只有拥有特定索引的一部分节点才能被选入 “允许快速” 节点集合。

Example Implementation 示例实现

以下的 C++ 实现由 CacheLogic 提供

void generate_fast_set(
  uint32 k,     // number of pieces in set
  uint32 sz,    // number of pieces in torrent
  const char infohash[20], // infohash of torrent
  uint32 ip, // in host byte order, ie localhost is 0x7f000001
  std::
vector<uint32> &a) // generated set of piece indices
{
   a.clear();
   std::string x;
   char buf[4];
   *(uint32*)buf = htonl(ip & 0xffffff00);
   x.assign(buf, 4);
   x.append(infohash, 20); // (3)
   while (a.size()<k) {
     x = SHA1(x); // (4)
     for ( int i=0&nbsp;; i<5 && a.size()<k; i++ ) { // (5)
       int j = i*4; // (6)
       uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7)
       uint32 index = y % sz; // (8)
       if (std::find(a.begin(), a.end(), index)==a.end()) { // (9)
         a.push_back(index); // (10)
       }
     }
   }
}

此函数生成的示例结果：

7 piece allowed fast set for torrent with 1313 pieces and hex infohash
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
  1059,431,808,1217,287,376,1188
9 piece allowed fast set for torrent with 1313 pieces and hex infohash
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200:
  1059,431,808,1217,287,376,1188,353,508

总结

BitTorrent 的 Fast Extension（简称 FAST）是一种加速下载的协议扩展，它能够显著提高文件下载速度。 FAST 利用了一些技术手段来优化下载过程，如多线程下载、数据块预取和请求重排等。

具体地说，FAST 通过请求多个数据块，并在这些数据块到达之前对它们进行排序以减少延迟，从而使下载更快。此外，FAST 还利用多线程下载技术，同时从不同的上传者处获取数据块，进一步提高下载速度。

需要注意的是，FAST 只适用于支持该协议扩展的 BitTorrent 客户端之间的通信，因此如果你使用的客户端不支持 FAST，那么即使有其他客户端支持该协议扩展，也无法加速你的下载。

参考链接

• http://www.bittorrent.org/beps/bep_0006.html

• https://blog.imfile.io/zh_cn/2023/06/13/bittorrent-xie-yi-gui-fan/