历史

2001, Bram Cohen, BitTorrent

2003, Red Hat Linux 9 发布，服务器挤爆，3天交换了21150GB的数据
国内，网络蚂蚁、网际快车

BitTorrent由BitTorrent Community Forum进行维护，相关协议称为BEP(BitTorrent Enhancement Proposals)

BitTorrent协议

实体组成

一个静态的 ‘metainfo’ 文件(torrent种子文件)
一个 BitTorrent tracker
一个 ‘原始的’ 下载者
终端用户下载者

bencoding

字符串
十进制的长度前缀 + 冒号 + 字符串本身
例如：4:spam
整数
i + 十进制数字 + e
例如：i3e, i-3e, i0e
列表
l + 元素 + e
例如：l4:spam4:eggsi3ee 代表 [‘spam’, ‘eggs’, 3]
字典
d 后交替地跟着键和它们的对应值，然后是 e 字符表示结束
例如：
d3:cow3:moo4:spam4:eggse 表示 {‘cow’: ‘moo’, ‘spam’: ‘eggs’}
d4:spaml1:a1:bee 表示 {‘spam’: [‘a’, ‘b’]}

torrent文件结构

解析torrent文件的工具

http://torrenteditor.com/
https://github.com/effigies/BitTornado (python3 btshowmetainfo.py)

文件结构

{
    "announce":"Tracker 的 URL",
    "announce-list":[
        ["Tracker 的 URL2"],
        ["Tracker 的 URL3"]
    ]
    "info":{
        "name":"UTF-8 编码的字符串，建议的保存文件（或字典）时所采用的名字",
        "piece length":"文件分割后每个片的字节数，2的幂",
        "pieces":"长度是 20 的整数倍的字符串，每个都是对应 index 处的片的 SHA1 hash 值",
        "length":"文件的大小，以字节为单位（如果是文件列表，下面的files，则不会出现该字段）",
        "files":[
            {
                "length":"单个文件的大小",
                "path":"单个文件名"
            },
            {
                "length":"xxxx",
                "path":"xxxx"
            }
        ]
    }
}

trackers

发起GET请求，请求字段如下

info_hash: torrent文件中info值的SHA1
peer_id: 每个下载client的随机id
ip: peer的ip地址
port: peer监听端口
uploaded: 到目前为止上传的数据量，以十进制 ascii 编码
downloaded: 到目前为止下载的数据量，以十进制 ascii 编码
left: 当前 Peer 仍然需要下载的字节数，以十进制 ascii 编码
event: started，completed，或 stopped

tracker服务器返回的响应也是bencoding的，示例如下：

{
    "failure reason":"xxx"
}

{
    "interval":12345,
    "peers":[
        {
            "peer id":"xxxxxx",
            "ip":"xxxxxx",
            "port":1234
        },
        {
            "peer id":"xxxxxx",
            "ip":"xxxxxx",
            "port":1234
        },
        {
            "peer id":"xxxxxx",
            "ip":"xxxxxx",
            "port":1234
        }
    ]
}

p2p

从Tracker服务器获取到 peers 列表后，会进行请求并维持跟每一个peer的连接状态

连接在任一端包含两个状态位：

阻塞或不阻塞(choke/unchoke)
是否感兴趣(interested/uninterested)

当且仅当一方 unchoke 且另一方 interested 的时候，才会进行数据传输
当 Peer 完成一个片的下载，并检查了哈希值的匹配性，它将向它所有的 Peers 通告它具有该片

p2p消息类型

handshake：连接 peer 间连接建立后发送的第一个消息，主要用于通告 info_hash 与
1
| 19 (1) | "BitTorrent protocol" (19) | reserved_byte (8) | info_hash (20) | peer_id (20) |
keepalive
1
| len (4) |

除基础消息外的其他消息均有固定的格式如下：消息体长度 + 类型 + 负载。

1	\| len (4) \| type (1) \| payload \|

可能的类型值有：

0 - choke
1 - unchoke
2 - interested
3 - not interested
4 - have
告诉对方某个piece已经成功下载并且通过hash校验
5 - bitfield
告诉对方我已经有的piece
6 - request：请求某个块(block)
- index: 整数，指定从零开始的piece索引
- begin: 整数，指定piece中从零开始的字节偏移
- length: 整数，指定请求的长度
7 - piece：返回请求的块(block)的数据，是真正的资源信息
- index: 整数，指定从零开始的piece索引
- begin: 整数，指定piece中从零开始的字节偏移
- block: 数据块
8 - cancel
消息除了类型和 request 消息不同外，其他均与 request 一致，用于向 peer 取消之前发出的 request 请求。这是由于为了加快最后若干分片的下载速度，客户端会启用 Endgame 模式，这个模式下，peer 会向所有的 peer 请求相同的分片片段，当 peer 从某个 peer 获得所需的分片片段后，需要向剩余的 peer 发送 cancel 消息以减少不必要的传输

其中 choke，unchoke，interested，和 not interested 没有载荷。

peer的来源

Magnet：磁力连接中有 x.pe 参数可以预设一些 Peer；
Tracker：Tracker 服务器的作用就是提供 Peer；
Local Service Discovery（BEP14）:通过对本地组播地址 239.192.152.143:6771 和 [ff15::efc0:988f]:6771 发出 info_hash 宣告来尝试获得响应，如果有响应，则添加为 Peer；
Peer Exchange：通过 Peer 间的 Peer Exchange 扩展消息来与其他 Peer 交换 Peer，后面会详细提到；
DHT：通过 DHT 网络获取；

BT中涉及到的策略

分片选择策略

Random First Piece（随机首分片）

当下载开始时， peer 没有分片可以用于上传，所以最重要的是尽快得到一个完整的分片。稀有的分片往往只被某一个 peer 拥有，从这个 peer 处下载这个分片（分成多个子片段）将会慢于从多个 peer 处下载相同分片的不同子片段。出于这个原因，刚开始下载时，会随机选择一个分片进行下载，随后策略转为稀有优先。

Rarest First（稀有优先）

在选择接下来下载哪个分片时，peer 会选择最稀有的分片（自己没有这个分片，同时其他 peer 有，但是有这个分片的 peer 数量相对其他分片最少）进行下载。这个算法保证了不稀有的分片在之后仍然能被下载到，同时稀有的分片在逐渐变多。通过尽快复制最稀有的分片，减小了稀有分片在当前连接的 peer 中完全消失的可能性。

Strict Priority（严格模式）

一旦请求了某个分片的子片段，那么就会在请求其他子片段之前请求该特定分片的剩余子片段，以尽量优先获得这个完整的分片。

Endgame Mode

有时从一个 peer 请求某个分片会很慢，这在下载整个资源你的中途不会是一个问题（因为中途同时发生不少请求），但是这种情况可能会影响最终的即将下载完成阶段。当所有剩余的子片段都已经在向其他 peer 请求时，它会同时向所有的 peer 请求这些子片段。当某一个 peer 返回了一个子片段，就向剩余的 peer 发送 cancel 消息以节约带宽。在实践过程中，Endgame 模式持续时间非常短，所以浪费的带宽不多，而且使得资源的最后一部分下载非常快。

choking算法

BT 没有中心化的资源分配，每个 peer 都想最大化自己的下载速率，又希望更少的上传。

这是一个囚徒困境，曾经有人为此举办过两次比赛，看谁的策略最好，最终胜出的是一个叫做“争锋相对”的算法(tit-for-tat)，这个算法策略很简单，一开始采用合作，假如对方上一轮合作，则本轮合作；如果对方上一轮对抗，则本轮对抗。

为了解决tit-for-tat潜在的问题，BT做了相应的优化，以一定的概率去执行以牙还牙，但是也允许以一定的概率不管上次选什么，这次和对手选择合作。

大致算法描述如下：

Choking Algorithm：每 T 时间选择合适的 k 个 peer 进行 unchoke，选择的标准为过去 S 时间 peer 的下载速率；
Optimistic Unchoking：每 nT 时间，随机选择一个 peer 进行 unchoke，以尝试发现更优质的 peer；
Anti-snubbing：如果 mT 时间内没有从某个 peer 处获取到一个分片，则认为被 snubbed 了，对其进行 choke；
Upload Only：当一个 peer 下载完成了，即成为了一个 seed，则只进行上传，不再下载。peer 会选择那些该 peer 对其有较高上传速率的 peer 进行上传。

实际实现中 T = 10s, k = 7, S = 20s, n = 3, m = 6。

BT扩展

磁力链接

源起

提到 Magnet（磁力链接）大家都会想到 BT，但是磁力链接不是因为 BT 而诞生的，也不止用于 BT，事实上磁力链接的来自 MAGNET-URI Project 这个项目：

MAGNET is a work-in-progress URI specification, and collection of standard practices/implementing code to allow a website to seamlessly integrate with features made available by local utility programs. In one way, it could be thought of as a vendor- and project-neutral generalization of the “freenet:” and “ed2k:” URI-schemes used by the Freenet and EDonkey2000 peer-to-peer networks, respectively.

Gordon Mohr magnet-uri.sourceforge.net/magnet-draft-overview.txt

磁力链接是一个统一的规范，它希望这种 p2p 的链接都可以以按照这个规范展示，这样的话当用户在网页上点击磁力链接的时候，就可以磁力链接的参数（xt，下文会提及）“召唤”合适的客户端。它先被 eDonkey（电驴）推动，电驴链接理论上可以被转换成磁力链接。转换过程大致如下：

1 2	ed2k://\|file\|<name>\|<file-size>\|<ed2k-hash>\|/ magnet:?xt=urn:ed2k:<ed2k-hash>&xl=<file-size>&dn=<name>

然而，这个 MAGNET-URI Project 后来应该没有被推动下去，导致甚至连电驴自己的客户端都没有支持 ed2k 的 magnet 格式。直到后来在 BT 中大放异彩，导致现在狭义上的磁力链接就是指 BT 中使用的磁力链接。

BT 中的磁力链接

BT 中的磁力链接大概有这两种格式：

1 2	v1: magnet:?xt=urn:btih:<info-hash>&dn=<name>&tr=<tracker-url>&x.pe=<peer-address> v2: magnet:?xt=urn:btmh:<tagged-info-hash>&dn=<name>&tr=<tracker-url>&x.pe=<peer-address>

根据 URL 的定义，magnet 前缀表示这个链接是磁力链接，？ 后表示为 GET 模式查询参数列表，参数使用 & 符号隔开。BT 磁力链接的参数如下:

xt

：表示包含文件散列函数值的 URN，这是唯一一个必选参数，可能的 URN 类型有：
- btih：表示 Torrent 文件 info 部分的 SHA1 值，可以是 Hex 编码或者 Base32 编码形式。
- btmh：表示 Torrent 文件 info 部分的 HEX 编码 multihash 值，multihash 是由创造 IPFS 的 Protocal Lab 的项目，用于编码多种 hash 函数的 hash 结果。btmh 可以和 btih 同时存在，这个应该和 SHA1 被破解相关——有 btmh 中使用其他 hash 函数得到的 hash 值加上原来的 SHA1 值就可以做到兼容，同时检测碰撞。
dn：表示建议显示的文件名。
tr：表示 Tracker的 URL，如果有多个 Tracker,则会有多个 tr 参数。
x.pe：表示 Peer 的，格式为 hostname:port，ipv4-literal:port 或者 [ipv6-literal]:port，这些 peer 可以被添加到 peer 列表中用于获取元数据以及后续的文件片段获取。实际上 Magnet 链接中定义了一个通用的参数 xt 用于指定类似 x.pe 所表示的 p2p 连接，但是由于没有合适的 URI 标识符分配给 BT（比如电驴有 ed2k），所以 BT 使用了这个参数，而不是 xt。
so：定义在 BEP53 - Magnet URI extension - Select specific file indices for download 中，用于指定下载特定文件，比如 so=0,2,4,6-8 表示下载 files 列表中索引为 0,2,4,6,7,8 的这六个文件。

有了磁力链接，客户端就可以向 peer 请求 Torrent 文件的 info 部分了，获取完成后就相当于拥有了 Torrent 文件，也就是有了完整的元数据，继而可以下载资源。

DHT

附录

torrent编辑
http://torrenteditor.com/
https://github.com/gerryferdinandus/bittorrent-tracker-editor

BitTorrent简介

历史