1.2 常见P2P系统简介

1.2.1 BitTorrent

BitTorrent（简称BT，俗称BT下载）是一种内容分发协议，是2002年由布拉姆·科恩自主开发并发布在CodeCon上的，原始的BitTorrent以Python语言编成，3.2 版以前的源代码基于 MIT 许可证发布；4.x 版与 5.x 版的源代码基于BitTorrent开放源代码许可证（一个Jabber开放源代码许可证的改作版）发布；5.3版被重新以GPL发布；自6.0版起，BitTorrent成为µTorrent的改名版，因此不再开放源代码，并仅支持Windows与Mac OS X 10.5.x版。如今，经过了十几年的发展，BitTorrent成为了互联网领域不可或缺的重要工具，亦成为数百万人日常生活的一部分，它伴随了整整一代人的成长。每天都有大量的数据通过 BitTorrent传输，而且这个数字仍在增加。

BitTorrent采用高效的软件分发系统和点对点技术共享大体积文件（如一部电影或电视节目），并使每个用户像网络重新分配节点那样提供上传服务。一般的下载服务器为每一个发出下载请求的用户提供下载服务，而BitTorrent的工作方式与之不同。分配器或文件的持有者将文件发送给其中一名用户，再由这名用户转发给其他用户，用户之间相互转发自己所拥有的文件部分，直到每个用户的下载都全部完成。这种方法可以使下载服务器同时处理多个大体积文件的下载请求，而无须占用大量带宽。

以下是BitTorrent协议中重要的名词定义和算法介绍。

种子文件（Torrent文件）。BitTorrent是通过一个扩展名为.torrent的种子文件进行下载部署的，它由文件最初发布者创建，发布到互联网上，供感兴趣的用户下载。种子文件记录了负责管理该文件所在分发网络的Tracker服务器的地址、文件名、文件长度以及每个文件分块的SHA-1校验值。

种子节点（Seed节点）。Seed节点是指在一个P2P共享下载网络中，拥有完整文件拷贝的节点。这类节点只提供上传服务，而没有下载请求。

下载节点（Leecher节点）。共享网络中相对于Seed节点的是Leecher节点，它只拥有部分的文件拷贝，在提供这部分拷贝的同时，还会向其他节点请求自己缺少的那部分文件。

跟踪服务器（Tracker服务器）。Tracker是一个中心服务器，负责跟踪系统中所有的参与节点，收集和统计节点状态，帮助参与节点互相发现，维护共享网络中文件的下载。一个Tracker服务器可以同时维护和管理多个文件共享网络。

共享网络（Swarm网络）。一个Swarm共享网络是拥有和传输同一个文件资源的所有节点所构成的一个覆盖网络，包括共享该文件的Seed节点、Leecher节点和Tracker服务器。

分片机制。BitTorrent像其他文件共享软件一样对文件进行了分片（Piece），Piece是最小的文件共享单位，每个Leecher在下载完一个完整的分片后才会进行完整性校验，完整性校验成功后通知其他节点自己拥有这部分数据。为了加快文件传输的并行性，每个分片还会分成更小的分块（Block），Block是最小的文件传输单位，数据请求者每次向数据提供者请求一个Block的数据。

片选择机制。为了保证共享网络的健壮性，延长一个共享网络的生命周期，BitTorrent通过局部最少块优先（Rarest-First）策略在节点间交换数据。下载节点根据自己周围的邻居节点拥有的数据块信息，选择拥有节点最少的分块优先下载，从而维护局部的数据块相对平衡。

节点选择机制。BT系统采用了基于“Tit-for-Tat”的激励机制来抵御“Free-riding”行为，其中Choking/Unchoking算法最为关键。每个BT节点通过Interest/Uninterest消息来维护与多个节点的并发连接，但是只能为少数节点提供上传。服务提供节点在收到上传请求后会通过Choking/Unchoking机制决定是否对文件请求节点提供上传服务，可以拒绝服务（Choking）或者允许服务（Unchoking）。该机制决定了两个相连的节点是否共享彼此的资源。为了防止部分节点只下载不上传的自私行为，Choking/Unchoking算法优先选择曾经为自己提供过上传数据并拥有高下载速率的节点，前者可以鼓励节点上传以获取下载，后者有助于最大化系统资源利用率。此外，Choking/Unchoking算法每隔30 s将不考虑过去的贡献随机选择一个节点进行上传，一方面有利于发现可能存在更高下载速率的节点，另一方面可以避免新节点因从未进行过上传而无法获得有效的下载连接。

图1-6给出了BT系统下一个节点的生命周期。首先，一个新节点通过论坛或网站获得Torrent文件。随后该节点通过Torrent中的URL链接与对应的Tracker服务器通信，获得由Tracker提供的一个包含30~80个节点的随机邻居列表。成功加入Swarm网后，该节点成为一个新的Leecher节点，并与其邻居节点建立TCP连接，请求数据分片。当拥有了有效数据分片后，该 Leecher 节点会通过Choking/Unchoking机制同其他节点交易数据。当拥有了所有数据分片后，Leecher节点成为Seed节点，为其他节点提供数据。在整个生命周期过程中节点会定期与Tracker服务器通信获得活跃的邻居节点，并更新自身的下载状态。

随着BT的发展，相继产生了基于结构化P2P的Mainline DHT协议，以及基于节点间邻居节点交换的PEX协议。Mainline DHT为BT共享网络提供了结构化拓扑，是减轻Tracker负担的一种扩展协议，其协议大致基于Kademlia协议开发。Peer Exchange（PEX）也是一种被广泛应用于BT系统，用来减轻Tracker服务器压力的扩展协议。目前，多数BT客户端和95%以上的节点均支持PEX扩展协议，当前的PEX主要有3种典型的实现：AZ PEX、UT PEX和BC PEX。在所有的PEX协议中，节点周期性地向其他节点发送PEX消息，这些消息中包含一组新连接的节点和一组新断开的节点。目前，主流的客户端如Vuze和_Torrent均支持这3种PEX协议，并与其他客户端兼容。PEX极大地提高了系统资效率，增强了系统健壮性。

1.2.2 eMule

eMule是一款开源免费的P2P文件共享软件，基于eDonkey2000的eDonkey网络，并遵循GNU通用公共许可证协议。最早的eMule版本只运行在Windows系统下，是2002年5月13日由本名为Hendrik Breitkreuz的Merkur开发的。最初，Merkur由于不满意当时的eDonkey2000客户端，并且相信自己能做出更出色的P2P软件，于是便着手开发了一款新的P2P共享软件。他凝聚了一批原本在其他领域有出色发挥的程序员在他的周围，eMule 工程就此诞生。他们的目标是将eDonkey的优点保留下来，加入新的功能，并使图形界面变得更好。eMule软件源码最初于2002年7月6日发布在Source Forge网站上。eMule软件最初于2002年8月4日发布，初始版本号为0.05a。

eMule用Microsoft Visual C++编译，使用了MFC。由于eMule开放源代码，其代码基础也被Linux平台下的客户端x Mule和跨平台客户端a Mule、JMule所使用。同时，eMule也派生出了很多修改版，即eMule Mod（s）。很长时间以来，eMule都是Source Forge网站上下载量最多的软件。截至2009年9月，官方eMule在Source Forge上的下载点击数已超过5亿。

由于eMule保留了最初的eDonkey2000客户端的一些功能，构成了一个覆盖网络，一般称作eD2k网络。eD2k网络由服务器和客户端组成，但这个服务器和客户端与传统的C/S结构并不相同，eD2k网络中的服务器并不提供文件内容的下载，服务器只保存共享文件的索引信息和客户端信息，同时该结构与 Napster的中心服务器结构也有所区别，网络中存在着大量的eD2k服务器，任何人都可以构建自己的eD2k服务器，服务器之间通过 eDonkey2000协议进行通信，构成eD2k服务器的一个通信网络。

每个eMule客户端都预先设置好了一个服务器列表和一个本地共享文件列表。客户端通过一个单一的TCP连接到eD2k服务器进行网络登录，得到想要的文件信息和可用客户端信息。eMule客户端用几百个TCP连接与其他客户端进行文件的上传和下载。每个eMule客户端为它的共享文件维护一个上传队列。正在下载的客户端加入这个队列的底部，然后逐渐地前进，直到它们达到队列的顶端开始下载文件。一个客户端可能从多个其他eMule客户端下载同一个文件，从不同的客户端取得不同的部分。客户端也可以上传一个没有完全下载文件部分数据。

eD2k服务器使用一个内部数据库来保存客户端和文件的信息。eD2k服务器不保存任何文件，它是文件位置信息的中心索引。服务器的另一个功能，正在受到质疑，它将作为通过防火墙连接的客户端之间的桥梁，这样的客户端不能接受引入的连接。桥接功能让服务器承担了过分的负担，大大降低了服务器的能力，目前，应用中大部分的服务器已经关闭了这个功能，也就是说，两个Low ID的客户端是不能传输数据的。电骡使用UDP增强客户端与服务器和其他客户端的通信能力，但是客户端收发UDP信息的能力不是客户端日常操作强制要求的，即使防火墙阻止客户端收发UDP信息，客户端仍能完美地工作。

eD2k的网络拓扑如图1-7所示。

eMule作为eDonkey的继承者，对eDonkey进行了大量的改进。而其中最大的改进就是增加了DHT网络的支持，即加入了对Kad网络的支持，这是一个基于Kademlia协议全新的DHT网络。由于DHT网络是将所有的节点连接在一起的，所以这使eMule系统能够获取的资源数目大大增加，同时也增强了eMule系统的稳定性，因为即使没有eD2k服务器，eMule系统也能够正常运行。所以，通常现在的eMule客户端加入了两个覆盖网络，即eD2k覆盖网络和Kad覆盖网络。此外，eMule并不是将两个覆盖网络隔离开来，而是通过客户端软件将它们联系起来，如当eMule客户端要登录Kad网络时，它需要获取几个初始邻居，这时它就可以通过eD2k网络来获取其他邻居的信息，从而发现这些初始邻居，eMule 客户端在客户端边缘将这两个网络连接起来，如图1-8所示。

目前，eMule是世界上最大、最可靠的点对点文件共享客户端之一。由于它奉行开发源代码的政策，众多的开发者得以对eMule工程有所贡献。随着每一个版本的发布，eMule的开发者网络都变得更有效率。eMule v0.40就已经加入了对Kad网络的支持，另外，搜索也更改为以unicode搜索，这使用户可以搜索非拉丁字符，同时，也可以搜索到eDonkey网络上未完成文件的来源。此版还加入了一个损坏来源列表，能够自动向列表中加入连接失败的IP地址，在一段时间内将不再向此地址进行连接。eMule 0.46b加入了“eMule收藏集”功能，可以将许多eD2k链接发布为一个收藏集来下载。2007年开始，一些ISP对一些P2P端口使用了带宽限制。于是eMule 0.47b相应地加入了模糊协议，它能够在eMule第一次运行时自动地随机选择两个端口。2010年以后的eMule较为稳定，不再像以前那样频繁更新，更新间隔为6个月以上。

1.2.3 Kademlia

Kademlia简称Kad，是一种结构化P2P网络拓扑，基于DHT技术。最早由美国纽约大学的Petar Maymounkov和David Mazieres在2002年发布[7]。

简单地说，Kad 是一种分布式散列表（DHT）技术，不过和其他DHT 实现技术比较，如Chord、CAN、Pastry 等，Kad以异或算法（XOR）为距离度量基础，建立了一种全新的DHT拓扑结构，相比于其他算法，大大提高了路由查询速度。

2005年5月，著名的BitTorrent 在4.1.0 版实现基于Kademlia 协议的DHT 技术后，BitComet和BitSpirit很快也实现了和BitTorrent兼容的DHT 技术，实现Trackerless下载方式。另外，eMule中也很早就实现了基于Kademlia类似的技术，称为Kad网络，BT软件使用的Kad 技术的区别在于key、value 和node ID的计算方法不同。

由于eMule对Kademlia的实现更为完整，本节以eMule中的Kad网络为例，介绍Kademlia协议。

1.Kad网络中的定义

（1）节点ID。每一个Kad网络下的节点，都有一个唯一的节点标识（以下简称为ID），一般为128 bit空间的数字，也就是每个ID占16 byte。

（2）路由表。由于Kad网络的每一个节点都是自己维护一个小的路由表，路由表中的每一条由一组<key，value>对组成，其中，key就是包含索引信息的值，value就是拥有对应文件的用户，这里将保存用户的<IP，port>对。当需要做查询操作时，当前被查询的节点就会从其路由表中查找起始节点，当不断向外部查找时，不仅能够获得需要的信息，同时也能填满路由表。路由表覆盖了整个128 bit的ID空间。

（3）节点间距离。用来比较两个节点的距离，或者节点和索引内容的接近程度。节点间距离使用按位异或的结果作为距离，其定义为距离（A，B）=|A 按位异或B|，并且结果为无符号型整数，结果越小，表示二者距离越近，反之，越远。

（4）K桶。路由表被划分为一个一个的桶，每个桶包含一部分节点空间，每一个桶最多能够保存K个节点信息。每个节点的路由表都是一棵二叉树，叶子节点为桶，每个桶保存的是具有相同前缀的节点信息，同时这个前缀也表明了该桶在二叉树中的位置。假设本地节点的ID为1101，新加入节点的ID为1010，那么它们之间的距离为（1101⊕1010=0111），新加入的节点就存储在S点的位置如图1-9所示。

对0≤i <160，每个节点保存离自己距离为<2i，2i+1>（不包括2i+1）的其他节点的列表，每个列表最多有K项，列表中每一项是这样的格式：<IP地址，UDP端口号，NODE_ID>。

注意，这里距离的计算方法是上面说明的异或计算，这样的列表称为K桶。每一个K桶以这样的方式排序：最近看到的项放在尾部，最晚看到的项放在头部。可以注意到，i越小，K桶可能会很空；当i越大，它的K桶的项数将呈指数增长，因此，Kademlia协议这样设计K桶可以保证离自己较近距离的节点会存储的比例比较多，而离自己比较远的节点相对存储的比例较少，这样就可以保证路由查询是收敛的。对于规模为N的Kad网络，查询目标的步数一般是lg N。

2.Kad网络消息格式

Kademlia协议中实现了4种操作的报文，分别为PING、STORE、FIND_NODE、FIND_VALUE。

（1）PING消息主要用于检测一个节点是否在线，当检测的节点以PONG消息回复PING消息时，则证明该节点在线，反之，不在线。

（2）STORE消息主要通知节点需要存储的资料信息，一般为<key，value>对。

（3）FIND_NODE消息是主要实现查询操作的报文，当一个节点需要请求一个目标ID（target_id）时，它会向请求的节点发送包含target_id的FIND_NODE报文，而接收节点会检查自己的K桶，如果存在target_id的<key，value>对，则直接回复，反之，则回复离target_id最近的m个节点的信息，然后由节点再递归请求，直到请求结束。

（4）FIND_VALUE消息只回复一个节点的信息，与FIND_NODE消息相类似。

3.Kad网络的实现

（1）K桶更新

当Kad节点从其他节点处接收到消息，它将会更新发送节点所在桶的信息。

① 如果发送节点已经在接收者的K桶中存在，那么接收者将发送者的ID移到桶的尾部；

② 如果发送节点不在接收者的K桶中，且接收者的K桶数目小于K，则直接将节点插入桶的尾部；

③ 如果发送节点不在接收者的K桶中，且接收者的K桶数目大于K，那么就PING桶中头部最晚看到的节点。如果最晚看到的节点有回应，则将它放到尾部，且丢弃发送节点，否则，将最晚看到的节点丢弃，然后将发送节点插入尾部。

这样的方式，可以防止Do S攻击，因为只有当老节点失效后，Kad才会更新K桶的信息，这就避免了通过新节点的加入来泛洪路由信息。

（2）Kademlia路由查询机制

Kad技术的最大特点之一就是能够提供快速的节点查找机制，并且还可以通过参数进行查找速度的调节。

假如节点X要查找ID值为t的节点，Kad按照如下递归操作步骤进行路由查找。

① 计算到t的距离，假设为d（使用上述异或距离）；

② 从X的第[lgd]个K桶中取出8个节点的信息，同时进行FIND_NODE操作。如果这个K桶中的信息少于8个，则从附近的多个桶中选择距离最接近d的共8个节点；

③ 对接收到查询操作的每个节点，如果发现自己就是t，则回答自己是最接近t的；否则，测量自己和t的距离，并从自己对应的K桶中选择8个节点的信息回复给X；

④ X对新接收到的每个节点都再次执行FIND_NODE操作，此过程不断重复执行，直到每一个分支都有节点响应自己是最接近t的；没有迅速响应的节点将被迅速排除出候选列表，直到其响应；

⑤ 通过上述查找操作，X得到了k个最接近t的节点信息，当X不能获得新的更接近t的节点信息时，查找结束，注意，很有可能查找不到节点t，也许t并不在当前网络中。

（3）节点加入和离开

如果节点y要加入Kad网络，它至少要知道一个Kad网络中在线节点，比如z。

y 首先把 z 插入自己适当的 K 桶中，然后对自己的节点 ID 执行一次FIND_NODE操作，然后根据接收到的信息更新自己的K桶内容。通过对自己临近节点由近及远的逐步查询，y也完成了对空的K桶信息的构建，同时也把自己的信息发布到其他节点的K桶中。

在Kad网络中，每个节点的路由表都表示为一棵二叉树，以节点y为例，其路由表的生成过程如下。

最初，u的路由表为一个单个的K桶，覆盖了整个160 bit ID空间，如图1-10所示最上面的路由表，当学习到新的节点信息后，则u会尝试把新节点的信息，根据其前缀插入到对应的K桶中，如果该K桶没有满，则新节点直接插入到这个K桶中；如果该K桶已经满了，分为2种情况：

①如果该K桶覆盖范围包括节点u的ID，则把该K桶分裂为两个大小相同的新K桶，并对原K桶内的节点信息按照新的K桶前缀值进行重新分配；

② 如果该K桶覆盖范围不包含节点u的ID，则直接丢弃该新节点信息。

上述过程不断重复，最终形成一个完整的路由表。