BitTorrent协议

注：本笔记是根据https://www.bilibili.com/video/av57748098视频整理而来。

早期文件的传播方式：

一对一文件传播
缺点：下载的人越多，分享到的带宽越小，下载速度越慢，另外是否能下载也高度依赖资源提供者。

BitTorrent协议：

美国工程师 Bram Cohen 于2001发布BitTorrent协议。
资源不再由一个人或一个中心服务器提供，而是所有人提供给所有人，下载的人越多，速度越快——Peer to peer模式（P2P下载）
核心思想：
把文件分成很多小块，让下载者互相连接，每个下载者维护这个文件的某个小块，交换彼此下载好的部分，参与的人越多，互相交换的就越密集，下载速度越快。
如何做到？
BitTorrent协议需要资源共享者生成一个包含下载信息的种子文件，后缀是.torrent，种子文件里面是个json，包含文件名字(name)，大小(lengh)，分块后每块文件的大小(piece length)，哈希值(pieces)，和Tracker服务器的地址(announce，announce-list)，Tracker很重要，通过Tracker才能找到其他下载者的联系方式。
当用下载软件打开种子，就会开始联动种子文件里内置的Tracker服务器，服务器会记录下你的IP，并把其他正在下载或下载完成的人的IP返回给你，这样你们就可以组队下载了。如果没有找到正在下载的人，资源发布者也不在线，就只能以0kb/s的速度等着了。
Tracker服务器是P2P网络的弱点，如果Tracker被关闭或封禁，那就无法找到同伴，也就难以完成下载。
摆脱对Tracker服务器的依赖：

磁力链接（Magnet URI scheme）下载方式：

magnet:?xt=urn:btih:25AR0360C94182EB90BCB5691B5F2FB2450F7690
magnet：磁力链接
xt：exact topic
urn：uniform resourc name
btih：BitTorrent Info Hash
40位16进制字符

任何文件丢进哈希算法都能得到一串40位16进制字符，40位的16进制只属于这个文件，可当作一个文件ID，它能帮我们找到我们要下载的东西。
磁力链接的本质是将所有人变成一个小型Tracker，每个人都拿着一份动态更新的地址和文件信息，这样一传十，十传百，形成一个网络，每个人就可以通过这个网络找到每个人了。

两个人如何在这张网络中以最短的逻辑距离相互连接？

DHT网络的构建过程
每个磁力链接会有一个唯一的文件ID，可产生2的160次方种组合，等于160个2进制字符，而每个节点（文件节点和资源提供者的路径节点）也有一串160位的二进制字符作为节点ID。
根据这160位数，就可计算出节点和节点，节点和文件之间的距离。
举例：
A发布者发布了一个文件，就能计算他所知道的节点ID(？)，与这个文件ID的距离，让算出来距离最短的节点，再计算它知道的节点和文件ID的距离，重复这个过程就能找到与文件ID距离最短的一批节点ID，把A提供的下载信息存在这里，这样下载者也只需要找到和文件ID距离最近的节点ID，就能建立连接，开始下载。

这个距离如何算出来？

用异或算法计算节点之间的逻辑距离。
用4位来举例，假如你的节点ID是0100，目标节点ID是1111，那你们之间的二进制距离通过异或算出来就是1011=十进制11，有了距离，我们就可以在一个二叉树（所有可能的节点ID组成的二叉树）里快速查找目标了，四位数需要分叉4次， 生成2的4次方即16条路径，每条路径的终点就是一个节点ID，这时，你作为0100就可以拆分这棵二叉树了，从第一次分叉开始，把不包含你的那棵子树拆分，然后在剩下的子树的第二次分叉处再次拆分，直到剩下你自己，这样就拆分除了4棵子树。
我们在每个子树里选两个点，就得到了4个K-bucket，仔细想想就会发现，用异或算法计算层级最深的K-bucket和你的距离最近（0100异或0101=1），倒数第二深的子树K-bucket是2-3，以此类推，倒数第三深子树的K-bucket是4-7，然后是8-15，刚刚算过，你的节点0100到目标节点1111的 距离是11，接下来我们就可以联系这两个节点（8-15区间子树的2个节点）帮我们找1111，以1110为例，1110也可以拆分出4个子树，得到4个K-bucket，计算1110和1111之间的距离是1，那么1111就在1110旁边。
这种网络结构被称为DHT（Distributed Hash Table）分布式哈希表，一个高宽容度去中心化网络，只需要一串文件ID和存储在本地的K-bucket数据就可以高效找到要下载的文件，而资源的发布和传播者也只需要分享40个数字就好，够方便简单和隐私。
在真实的DHT网络，每个K-bucket至少记录了8个节点，任何一个节点下线都不会影响整个网络的运行。