网络协议 15 - P2P 协议

大家说起种子，应该都知道是用来下载资源的。那么资源下载都有哪些方式？种子下载又有什么优势呢？

下载电影的两种方式

    第一种是通过 http 进行下载。这种方式，有过经历的人应该体会到，当下载文件稍大点，下载速度简直能把人急死。

    第二种方式就是是通过 ftp（文件传输协议）。ftp 采用两个 tcp 连接来传输一个文件。

1. 控制连接。服务器以被动的方式，打开众所周知用于 ftp 的端口 21，客户端则主动发起连接。该连接将命令从客户端传给服务器，并传回服务器的应答。常用的命令有：lsit - 获取文件目录，reter - 取一个文件，store - 存一个文件；
2. 数据连接。每当一个文件在客户端与服务器之间传输时，就创建一个数据连接。

ftp 的工作模式

    在 ftp 的两个 tcp 连接中，每传输一个文件，都要新建立一个数据连接。基于这个数据连接，ftp 又有两种工作模式：主动模式（port）和被动模式（pasv），要注意的是，这里的主动和被动都是站在服务器角度来说的。工作模式过程如下：

主动模式工作流程

1. 客户端随机打开一个大于 1024 的端口 n，向服务器的命令端口 21 发起连接，同时开放 n+1 端口监听，并向服务器发出“port n+1” 命令；
2. 由服务器从自己的数据端口 20，主动连接到客户端指定的数据端口 n+1。

被动模式工作流程

1. 客户端在开启一个 ftp 连接时，打开两个任意的本地端口 n（大于1024）和 n+1。然后用 n 端口连接服务器的 21 端口，提交 pasv 命令；
2. 服务器收到命令，开启一个任意的端口 p（大于 1024），返回“227 entering passive mode”消息，消息里有服务器开放的用来进行数据传输的端口号 p。
3. 客户端收到消息，取得端口号 p，通过 n+1 端口连接服务器的 p 端口，进行数据传输。

    上面说了 http 下载和 ftp 下载，这两种方式都有一个大缺点-难以解决单一服务器的带宽压力。因为它们使用的都是传统 c/s 结构，这种结构会随着客户端的增多，下载速度越来越慢。这在当今互联网世界显然是不合理的，我们期望能实现“下载人数越多，下载速度不变甚至更快”的愿望。

    后来，一种创新的，称为 p2p 的方式实现了我们的愿望。

p2p

    p2p 就是 peer-to-peer。这种方式的特点是，资源一开始并不集中存储在某些设备上，而是分散地存储在多台设备上，这些设备我们称为 peer。

    在下载一个文件时，只要得到那些已经存在了文件的 peer 地址，并和这些 peer 建立点对点的连接，就可以就近下载文件，而不需要到中心服务器上。一旦下载了文件，你的设备也就称为这个网络的一个 peer，你旁边的那些机器也可能会选择从你这里下载文件。

    通过这种方式解决上面 c/s 结构单一服务器带宽压力问题。如果使用过 p2p2 软件，例如 bittorrent，你就会看到自己网络不仅有下载流量，还有上传流量，也就是说你加入了这个 p2p 网络，自己可以从这个网络里下载，同时别人也可以从你这里下载。这样就实现了，下载人数越多，下载速度越快的愿望。

种子文件（.torent）

    上面整个过程是不是很完美？是的，结果很美好，但为了实现这个美好，我们还是有很多准备工作要做的。比如，我们怎么知道哪些 peer 有某个文件呢？

    这就用到我们常说的种子（.torrent）。 .torrent 文件由announce（tracker url）和文件信息两部分组成。

    其中，文件信息里有以下内容：

• info 区：指定该种子包含的文件数量、文件大小及目录结构，包括目录名和文件名；
• name 字段：指定顶层目录名字；
• 每个段的大小：bittorrent（bt）协议把一个文件分成很多个小段，然后分段下载；
• 段哈希值：将整个种子种，每个段的 sha-1 哈希值拼在一起。

    下载时，bt 客户端首先解析 .torrent 文件，得到 tracker 地址，然后连接 tracker 服务器。tracker 服务器回应下载者的请求，将其他下载者（包括发布者）的 ip 提供给下载者。

    下载者再连接其他下载者，根据 .torrent 文件，两者分别对方自己已经有的块，然后交换对方没有的数据。

    可以看到，下载的过程不需要其他服务器参与，并分散了单个线路上的数据流量，减轻了服务器的压力。

    下载者每得到一个块，需要算出下载块的 hash 验证码，并与 .torrent 文件中的进行对比。如果一样，说明块正确，不一样就需要重新下载这个块。这种规定是为了解决下载内容的准确性问题。

    从这个过程也可以看出，这种方式特别依赖 tracker。tracker 需要收集所有 peer 的信息，并将从信息提供给下载者，使下载者相互连接，传输数据。虽然下载的过程是非中心化的，但是加入这个 p2p 网络时，需要借助 tracker 中心服务器，这个服务器用来登记有哪些用户在请求哪些资源。

    所以，这种工作方式有一个弊端，一旦 tracker 服务器出现故障或者线路被屏蔽，bt 工具就无法正常工作了。那能不能彻底去中心化呢？答案是可以的。

去中心化网络（dht）

    dht（distributed hash table），这个网络中，每个加入 dht 网络的人，都要负责存储这个网络里的资源信息和其他成员的联系信息，相当于所有人一起构成了一个庞大的分布式存储数据库。

    而 kedemlia 协议 就是一种著名的 dht 协议。我们来基于这个协议来认识下这个神奇的 dht 网络。

    当一个客户端启动 bittorrent 准备下载资源时，这个客户端就充当了两个角色：

1. peer 角色：监听一个 tcp 端口，用来上传和下载文件。对外表明我这里有某个文件；
2. dht node 角色：监听一个 udp 端口，通过这个角色，表明这个节点加入了一个 dht 网络。

    在 dht 网络里面，每一个 dht node 都有一个 id。这个 id 是一个长字符串。每个 dht node 都有责任掌握一些“知识”，也就是文件索引。也就是说，每个节点要知道哪些文件是保存哪些节点上的。注意，这里它只需要有这些“知识”就可以了，而它本身不一定就是保存这个文件的节点。

    当然，每个 dht node 不会有全局的“知识”，也就是说它不知道所有的文件保存位置，只需要知道一部分。这里的一部分，就是通过哈希算法计算出来的。

node id 和文件哈希值

    每个文件可以计算出一个哈希值，而 dht node 的 id 是和哈希值相同长度的串。

    对于文件下载，dht 算法是这样规定的：

如果一个文件计算出一个哈希值，则和这个哈希值一样的那个 dht node，就有责任知道从哪里下载这个文件，即便它自己没保存这个文件。

    当然不一定总这么巧，都能找到和哈希值一模一样的，有可能文件对应的 dht node 下线了，所以 dht 算法还规定：

除了一模一样的那个 dht node 应该知道文件的保存位置，id 和这个哈希值非常接近的 n 个 dht node 也应该知道。

    以上图为例。文件 1 通过哈希运算，得到匹配 id 的 dht node 为 node c（当然还会有其他的，为了便于理解，咱们就先关注 node c），所以，node c 就有责任知道文件 1 的存放地址，虽然 node c 本身没有存放文件 1。

    同理，文件 2 通过哈希计算，得到匹配 id 的 dht node 为 node e，但是 node d 和 e 的值很近，所以 node d 也知道。当然，文件 2 本身不一定在 node d 和 e 这里，但是我们假设 e 就有一份。

    接下来，一个新节点 node new 上线了，如果要下载文件 1，它首先要加入 dht 网络。如何加入呢？

    在这种模式下，种子 .torrent 文件里面就不再是 tracker 的地址了，而是一个 list 的 node 地址，所有这些 node 都是已经在 dht 网络里面的。当然，随着时间的推移，很有可能有退出的，有下线的，这里我们假设，不会所有的都联系不上，总有一个能联系上。

    那么，node new 只要在种子里面找到一个 dht node，就加入了网络。

    node new 不知道怎么联系上 node c，因为种子里面的 node 列表里面很可能没有 node c，但是没关系，它可以问。dht 网络特别像一个社交网络，node new 会去它能联系上的 node 问，你们知道 node c 的联系方式吗？

    在 dht 网络中，每个 node 都保存了一定的联系方式，但是肯定没有所有 node 的联系方式。节点之间通过相互通信，会交流联系方式，也会删除联系方式。这和人们的沟通方式一样，你有你的朋友圈，他有他的朋友圈，你们互相加微信，就互相认识了，但是过一段时间不联系，就可能会删除朋友关系一样。

    在社交网络中，还有个著名的六度理论，就是说社交网络中的任何两个人的直接距离不超过六度，也就是即使你想联系比尔盖茨，最多通过六个人就能够联系上。

    所以，node new 想联系 node c，就去万能的朋友圈去问，并且求转发，朋友再问朋友，直到找到 c。如果最后找不到 c，但是能找到离 c 很近的节点，也可以通过 c 的相邻节点下载文件 1。

    在 node c上，告诉 node new，要下载文件 1，可以去 b、d、f，这里我们假设 node new 选择了 node b，那么新节点就和 b 进行 peer 连接，开始下载。它一旦开始下载，自己本地也有文件 1 了，于是，node new 就告诉 c 以及 c 的相邻节点，我也有文件 1 了，可以将我加入文件 1 的拥有者列表了。

    你可能会发现，上面的过程中漏掉了 node new 的文件索引，但是根据哈希算法，一定会有某些文件的哈希值是和 node new 的 id 匹配的。在 dht 网络中，会有节点告诉它，你既然加入了咱们这个网络，也就有责任知道某些文件的下载地址了。

    好了，完成分布式下载了。但是我们上面的过程中遗留了两个细节性的问题。

1）dht node id 以及文件哈希值是什么？
    其实，我们可以将节点 id 理解为一个 160bits（20字节）的字符串，文件的哈希也使用这样的字符串。

2）所谓 id 相似，具体到什么程度算相似？
    这里就要说到两个节点距离的定义和计算了。

    在 kademlia 网络中，两个节点的距离采用的是逻辑上的距离，假设节点 a 和 节点 b 的距离为 d，则：

d = a xor b

    上面说过，每个节点都有一个哈希 id，这个 id 由 20 个字符，160 bits 位组成。这里，我们就用一个 5 bits id 来举例。
    我们假设，节点 a 的 id 是 01010，节点 b 的 id 是 01001，则：

距离 d = a xor b = 01010 xor 00011 = 01001 = 9

    所以，我们说节点 a 和节点 b 的逻辑距离为 9。

    回到我们上面的问题，哈希值接近，可以理解为距离接近，也即，和这个节点距离近的 n 个节点要知道文件的保存位置。

    要注意的是，这个距离不是地理位置，因为在 kademlia 网络中，位置近不算近，id 近才算近。我们可以将这个距离理解为社交距离，也就是在朋友圈中的距离，或者社交网络中的距离。这个和你的空间位置没有多少关系，和人的经历关系比较大。

dht 网络节点关系的维护

    就像人一样，虽然我们常联系的只有少数，但是朋友圈肯定是远近都有。dht 网络的朋友圈也一样，远近都有，并且按距离分层。

    假设某个节点的 id 为 01010，如果一个节点的 id，前面所有位数都与它相同，只有最后 1 位不停，这样的节点只有 1 个，为 01011。与基础节点的异或值为 00001，也就是距离为 1。那么对于 01010 而言，这样的节点归为第一层节点，也就是k-buket 1。

    类似的，如果一个节点的 id，前面所有位数和基础节点都相同，从倒数第 2 位开始不同，这样的节点只有 2 个，即 01000 和 01001，与基础节点的亦或值为 00010 和 00011，也就是距离为 2 和 3。这样的节点归为第二层节点，也就是k-bucket 2。

    所以，我们可以总结出以下规律：

如果一个节点的 id，前面所有位数相同，从倒数第 i 位开始不同，这样的节点只有 2^(i-1) 个，与基础节点的距离范围为 [2^(i-1), 2^i]，对于原始节点而言，这样的节点归为k-bucket i。

    你会发现，差距越大，陌生人就越多。但是朋友圈不能把所有的都放下，所以每一层都只放 k 个，这个 k 是可以通过参数配置的。

dht 网络中查找好友

    假设，node a 的 id 为 00110，要找 b（10000），异或距离为 10110，距离范围在 [2^4, 2^5)，这就说明 b 的 id 和 a 的从第 5 位开始不同，所以 b 可能在 k-bucket 5 中。

    然后，a 看看自己的 k-bucket 5 有没有 b，如果有，结束查找。如果没有，就在 k-bucket 5 里随便找一个 c。因为是二进制，c、b 都和 a 的第 5 位不停，那么 c 的 id 第5 位肯定与 b 相同，即它与 b 的距离小于 2^4，相当于 a、b 之间的距离缩短了一半以上。

    接着，再请求 c，在 c 的通讯里里，按同样的查找方式找 b，如果 c 找到了 b，就告诉 a。如果 c 也没有找到 b，就按同样的搜索方法，在自己的通讯里里找到一个离 b 更近一步的 d（d、b 之间距离小于 2^3），把 d 推荐给 a，a 请求 d 进行下一步查找。

    你可能已经发现了，kademlia 这种查询机制，是通过折半查找的方式来收缩范围，对于总的节点数目为 n 的网络，最多只需要 log2(n) 次查询，就能够找到目标。

    如下图，a 节点找 b 节点，最坏查找情况：

    图中过程如下：

1. a 和 b 的每一位都不一样，所以相差 31，a 找到的朋友 c，不巧正好在中间，和 a 的距离是 16，和 b 的距离是 15；
2. c 去自己朋友圈找，碰巧找到了 d，距离 c 为 8，距离 b 为 7；
3. d 去自己朋友圈找，碰巧找到了 e，距离 d 为 4，距离 b 为 3；
4. e 在自己朋友圈找，找到了 f，距离 e 为 2，距离 b 为 1；
5. f 在距离为 1 的地方找到了 b。

节点的沟通

    在 kademlia 算法中，每个节点下面 4 个指令：

• ping：测试一个节点是否在线。相当于打个电话，看还能打通不；
• store：要钱一个节点存储一份数据；
• find_node：根据节点 id 查找一个节点；
• find_value：根据 key 查找一个数据，实则上和 find_node 非常类似。key 就是文件对应的哈希值，找到保存文件的节点。

节点的更新

    整个 dht 网络，会通过相互通信，维护自己朋友圈好友的状态。

• 每个 bucket 里的节点，都按最后一次接触时间倒序排列。相当于，朋友圈里最近联系的人往往是最熟的；
• 每次执行四个指令中的任意一个都会触发更新；
• 当一个节点与自己接触时，检查它是否已经在 k-bucket 中。就是说是否已经在朋友圈。如果在，那么就将它移到 k-bucket 列表的最底，也就是最新的位置（刚联系过，就置顶下，方便以后多联系）。如果不在，就要考虑新的联系人要不要加到通讯录里面。假设通讯录已满，就 ping 一下列表最上面的节点（最旧的），如果 ping 通了，将旧节点移动到列表最底，并丢弃新节点（老朋友还是要留点情面的）。如 ping 不同，就删除旧节点，并将新节点加入列表（联系不上的老朋友还是删掉吧）。

    通过上面这个机制，保证了任意节点的加入和离开都不影响整体网络。

小结

• 下载一个文件可以通过 http 或 ftp。这两种都是集中下载的方式，而 p2p 则换了一种思路，采用非中心化下载的方式；
• p2p 有两种。一种是依赖于 tracker 的，也就是元数据集中，文件数据分散。另一种是基于分布式的哈希算法，元数据和文件数据全部分散。

 

欢迎添加个人微信号：like若所思。

欢迎关注我的公众号，不仅为你推荐最新的博文，还有更多惊喜和资源在等着你!一起学习共同进步！