本节书摘来华章计算机《计算机网络：自顶向下方法（原书第6版）》一书中的第2章 ，第2.6节，（美）James F.Kurose Keith W.Ross　著 陈　鸣　译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.6　P2P应用

在目前为止本章中描述的应用（包括Web、电子邮件和DNS）都采用了客户-服务器体系结构，极大地依赖于总是打开的基础设施服务器。2.1.1节讲过，使用P2P体系结构，对总是打开的基础设施服务器有最小的（或者没有）依赖。与之相反，成对间歇连接的主机（称为对等方）彼此直接通信。这些对等方并不为服务提供商所拥有，而是受用户控制的桌面计算机和膝上计算机。
在本节中我们将研究两种不同的特别适合于P2P设计的应用。第一种应用是文件分发，其中应用程序从单个源向大量的对等方分发一个文件。文件分发是开始研究P2P的良好起点，因为它清晰地揭示了P2P体系结构的自扩展性。作为文件分发的一个特定的例子，我们将描述流行的BitTorrent协议。我们将研究的第二种P2P应用是分布在大型对等方社区中的数据库。对于这个应用，我们将探讨分布式散列表（Distributed Hash Table，DHT）的概念。

2.6.1　P2P文件分发

我们通过考虑一个非常自然的应用来开始涉足P2P，这种应用即从单一服务器向大量主机（称为对等方）分发一个大文件。该文件也许是一个新版的Linux操作系统，对于现有操作系统或应用程序的一个软件补丁，一个MP3音乐文件，或一个MPEG视频文件。在客户-服务器文件分发中，该服务器必须向每个对等方发送该文件的一个副本，即服务器承受了极大的负担，并且消耗了大量的服务器带宽。在P2P文件分发中，每个对等方能够重新分发它所有的该文件的任何部分，从而在分发过程中协助该服务器。到2012年止，最为流行的P2P文件共享协议是BitTorrent。该应用程序最初由Bram Cohen所研发，现在有许多不同的独立且符合BitTorrent协议的BitTorrent客户，就像有许多符合HTTP协议的Web浏览器客户一样。在下面的小节中，我们首先研究在文件分发环境中的P2P体系结构的自扩展性。然后我们更为详细地描述BitTorrent，突出它的最为重要的特性和特色。
1. P2P体系结构的扩展性
为了将客户-服务器体系结构与P2P体系结构进行比较，阐述P2P的内在自扩展性，我们现在考虑一个用于两种体系结构类型的简单定量模型，将一个文件分发给一个固定集合。如图2-24所示，服务器和对等方使用接入链路与因特网相连。其中us表示服务器接入链路的上载速率，ui表示第i对等方接入链路的上载速率，di表示了第i对等方接入链路的下载速率。还用F表示被分发的文件长度（以比特计），N表示要获得的该文件副本的对等方的数量。分发时间（distribution time）是所有N个对等方得到该文件的副本所需要的时间。在下面分析分发时间的过程中，我们对客户-服务器和P2P体系结构做了简化（并且一般是准确的［Akella 2003］）的假设，即因特网核心具有足够的带宽，这意味着所有瓶颈都在网络接入链路。我们还假设服务器和客户没有参与任何其他网络应用，因此它们的所有上传和下载访问带宽能被全部用于分发该文件。

我们首先来确定对于客户-服务器体系结构的分发时间，我们将其表示为Dcs。在客户-服务器体系结构中，没有对等方参与来帮助分发文件。我们做下列观察：

• 服务器必须向N个对等方的每个传输该文件的一个副本。因此该服务器必须传输NF比特。因为该服务器的上载速率是us，分发该文件的时间必定是至少为NF/us。
• 令dmin表示具有最小下载速率的对等方的下载速率，即dmin=min{d1,dp,…,dN}。具有最小下载速率的对等方不可能在少于F/dmin秒时间内获得该文件的所有F比特。因此最小分发时间至少为F/dmin。

将这两个观察放在一起，我们得到

该式提供了对于客户-服务器体系结构的最小分发时间的下界。在课后习题中将请你给出服务器能够调度它的传输以便实际取得该下界的方法。因此我们取上面提供的这个下界作为实际发送时间，即

我们从式（2-1）看到，对足够大的N，客户-服务器分发时间由NF/us确定。所以，该分发时间随着对等方N的数量线性地增加。因此举例来说，如果从某星期到下星期对等方的数量从1000增加了1000倍，到了100万，将该文件分发到所有对等方所需要的时间就要增加1000倍。
我们现在来对P2P体系结构进行简单的分析，其中每个对等方能够帮助服务器分发该文件。特别是，当一个对等方接收到某些文件数据，它能够使用自己的上载能力重新将数据分发给其他对等方。计算P2P体系结构的分发时间在某种程度上比计算客户-服务器体系结构的更为复杂，因为分发时间取决于每个对等方如何向其他对等方分发该文件的各个部分。无论如何，能够得到对该最小分发时间的一个简单表示式［Kumar 2006］。至此，我们先做下列观察：

• 在分发的开始，只有服务器具有文件。为了使社区的这些对等方得到该文件，该服务器必须经其接入链路至少发送该文件的每个比特一次。因此，最小分发时间至少是F/us。（与客户-服务器方案不同，由服务器发送过一次的比特可能不必由该服务器再次发送，因为对等方在它们之间可以重新分发这些比特。）
• 与客户-服务器体系结构相同，具有最低下载速率的对等方不能够以小于F/dmin秒的分发时间获得所有F比特。因此最小分发时间至少为F/dmin。
• 最后，观察到系统整体的总上载能力等于服务器的上载速率加上每个单独的对等方的上载速率，即utotal=us+u1+…+uN。系统必须向这N个对等方的每个交付（上载）F比特，因此总共交付NF比特。这不能以快于utotal的速率完成。因此，最小的分发时间也至少是NF/(us+u1+…+uN)。

将这三个观察放在一起，我们获得了对P2P的最小分发时间，表示为DP2P。

提供了对于P2P体系结构的最小分发时间的下界。这说明，如果我们认为一旦每个对等方接收到一个比特就能够重分发一个比特的话，则存在一个重新分发方案能实际取得这种下界［Kumar 2006］。（我们将在课后习题中证明该结果的一种特情形。）实际上，被分发的是文件块而不是一个个比特。式（2-2）能够作为实际最小分发时间的很好近似。因此，我们取由式（2-2）提供的下界作为实际的最小分发时间，即

图2-25比较了客户-服务器和P2P体系结构的最小分发时间，其中假定所有的对等方具有相同的上载速率u。在图2-25中，我们已经设置了F/u=1小时，us=10u，dmin≥us。因此，在一个小时中一个对等方能够传输整个文件，该服务器的传输速率是对等方上载速率的10倍，并且（为了简化起见）对等方的下载速率被设置得足够大，使之不会产生影响。我们从图2-25中看到，对于客户-服务器体系结构，随着对等方数量的增加，分发时间呈线性增长并且没有界。然而，对于P2P体系结构，最小分发时间不仅总是小于客户-服务器体系结构的分发时间，并且对于任意的对等方数量N，总是小于1小时。因此，具有P2P体系结构的应用程序能够是自扩展的。这种扩展性的直接成因是：对等方除了是比特的消费者外还是它们的重新分发者。

2. BitTorrent
BitTorrent是一种用于文件分发的流行P2P协议［Chao 2011］。用BitTorrent的术语来讲，参与一个特定文件分发的所有对等方的集合被称为一个洪流（torrent）。在一个洪流中的对等方彼此下载等长度的文件块（chunk），典型的块长度为256KB。当一个对等方首次加入一个洪流时，它没有块。随着时间的流逝，它累积了越来越多的块。当它下载块时，也为其他对等方上载了多个块。一旦某对等方获得了整个文件，它也许（自私地）离开洪流，或（大公无私地）留在该洪流中并继续向其他对等方上载块。同时，任何对等方可能在任何时候仅具有块的子集就离开该洪流，并在以后重新加入该洪流中。
我们现在更为仔细地观察BitTorrent运行的过程。因为BitTorrent是一个相当复杂的协议，所以我们将仅描述它最重要的机制，浏览某些内部的细节；这将使得我们能够通过树木看森林。每个洪流具有一个基础设施结点，称为追踪器（tracker）。当一个对等方加入某洪流时，它向追踪器注册自己，并周期性地通知追踪器它仍在该洪流中。以这种方式，追踪器跟踪正参与在洪流中的对等方。一个给定的洪流可能在任何时刻具有数以百计或数以千计的对等方。
如图2-26所示，当一个新的对等方Alice加入该洪流时，追踪器随机地从参与对等方的集合中选择对等方的一个子集（为了具体起见，设有50个对等方），并将这50个对等方的IP地址发送给Alice。Alice持有对等方的这张列表，试图与该列表上的所有对等方创建并行的TCP连接。我们称所有这样与Alice成功地创建一个TCP连接的对等方为“邻近对等方”（在图2-26中，Alice显示了仅有三个邻近对等方。通常，她应当有更多的对等方）。随着时间的流逝，这些对等方中的某些可能离开，其他对等方（最初50个以外的）可能试图与Alice创建TCP连接。因此一个对等方的邻近对等方将随时间而波动。

在任何给定的时间，每个对等方将具有来自该文件的块子集，并且不同的对等方具有不同的子集。Alice周期性地（经TCP连接）询问每个邻近对等方它们所具有的块列表。如果Alice具有L个不同的邻居，她将获得L个块列表。有了这个信息，Alice将对她当前还没有的块发出请求（仍通过TCP连接）。
因此在任何给定的时刻，Alice将具有块的子集并知道它的邻居具有哪些块。利用这些信息，Alice将作出两个重要决定。第一，她应当从她的邻居请求哪些块呢？第二，她应当向哪些向她请求块的邻居发送？在决定请求哪些块的过程中，Alice使用一种称为最稀缺优先（rarest first）的技术。这种技术的思路是，针对她没有的块在她的邻居中决定最稀缺的块（最稀缺的块就是那些在她的邻居中副本数量最少的块），并首先请求那些最稀缺的块。这样，最稀缺块得到更为迅速的重新分发，其目标是（大致地）均衡每个块在洪流中的副本数量。
为了决定她响应哪个请求，BitTorrent使用了一种机灵的对换算法。其基本想法是，Alice根据当前能够以最高速率向她提供数据的邻居，给出其优先权。特别是，Alice对于她的每个邻居都持续地测量接收到比特的速率，并确定以最高速率流入的4个邻居。每过10秒，她重新计算该速率并可能修改这4个对等方的集合。用BitTorrent术语来说，这4个对等方被称为疏通（unchoked）。重要的是，每过30秒，她也要随机地选择另外一个邻居并向其发送块。我们将这个被随机选择的对等方称为Bob。因为Alice正在向Bob发送数据，她可能成为Bob前4位上载者之一，这样的话Bob将开始向Alice发送数据。如果Bob向Alice发送数据的速率足够高，Bob接下来也能成为Alice的前4位上载者。换言之，每过30秒Alice将随机地选择一名新的对换伴侣并开始与那位伴侣进行对换。如果这两名对等方都满足此对换，它们将对方放入其前4位列表中并继续与对方进行对换，直到该对等方之一发现了一个更好的伴侣为止。这种效果是对等方能够以趋向于找到彼此的协调的速率上载。随机选择邻居也允许新的对等方得到块，因此它们能够具有对换的东西。除了这5个对等方（“前”4个对等方和一个试探的对等方）的所有其他相邻对等方均被“阻塞”，即它们不能从Alice接收到任何块。BitTorrent有一些有趣的机制没有在这里讨论，包括片（小块）、流水线、随机优先选择、残局模型和反怠慢［Cohen 2003］。
刚刚描述的关于交换的激励机制经常被称为“一报还一报”(tit-for-tat)［Cohen 2003］。已证实这种激励方案能被回避［Liogkas 2006;Locher 2006;Piatek 2007］。无论如何，BitTorrent“生态系统”取得了广泛成功，数以百万计的并发对等方在数十万条洪流中积极地共享文件。如果BitTorrent被设计为不采用一报还一报（或一种变种），然而在别的方面却完全相同的协议，BitTorrent现在将很可能不复存在了，因为大多数用户将成为搭便车者了［Sarouiu 2002］。
［Guo 2005;Piatek 2007］提出了BitTorrent协议的有趣变种。此外，许多P2P直播流式应用如PPLive和PPstream从BitTorrent中获得了灵感［Hei 2007］。

2.6.2　分布式散列表

在本节中，我们将考虑在P2P网络中怎样实现一个简单的数据库。我们先从描述这种简单数据库的集中式版本开始，该数据库只包含(键，值)对。例如：键可以是社会保险号，值可以是相应的人名；在这种情况下，键-值对的例子如(156-45-7081，Johnny Wu)。或者键可以是目录名（例如，电影、唱片和软件的名字），值可以是存储内容的IP地址；在这种情况下，键-值对的例子如(Led Zppelin IV，128.187.123.38)。我们用键来查询数据库。如果在该数据库中有一个或多个键-值对匹配该查询键，该数据库就返回相应的值。例如，如果该数据库存储了社会保险号和它们对应的人名，我们能够用特定的社会保险号查询，该数据库就返回具有那个社会保险号的人的名字。或者，如果数据库存储了目录名及其相应的IP地址，我们能够用特定的目录名查询，该数据库返回存储该特定内容的IP地址。
构建这样一个数据库直接采用客户-服务器体系结构，以在一个中心服务器中存储所有（键，值）对。因此在本节中，我们将考虑构建这种数据库的一个分布式、P2P的版本，在数以百万计的对等方上存储（键，值）对。在该P2P系统中，每个对等方将保持（键，值）对仅占总体的一个小子集。我们将允许任何对等方用一个特别的键来查询该分布式数据库。分布式数据库则将定位拥有该相应（键，值）对的对等方，然后向查询的对等方返回该（键，值）对。任何对等方也将允许在数据库中插入新键-值对。这样一种分布式数据库被称为分布式散列表（Distributed Hash Table，DHT）。
在描述如何创建一个DHT的方法之前，我们首先描述在P2P文件共享环境中DHT服务的一个特定例子。在这种情况下，键是一个目录名，而值是具有该目录副本的对等方IP地址。因此，如果Bob和Charlie都具有一个最新Linux分发副本的话，则DHT数据库将包括下列两个键-值对：（Linux,IPBob）和（Linux,IPCharlie）。更为具体地说，因为DHT数据库分布在一些对等方上，所以某些对等方如Dave将对键“Linux”负责，并且将具有相应的键-值对。现在假设Alice要获得Linux的一个副本。显然，她在能够开始下载之前，先需要知道哪个对等方拥有Linux的副本。为此，她用“Linux”作为键来查询DHT。该DHT则确定对等方Dave负责键“Linux”。DHT则联系对等方Dave，从Dave处获得键-值对（Linux,IPBob）和（Linux,IPCharlie），并将它们传送给Alice。Alice则能从IPBob或IPCharlie处下载最新Linux分发。
现在我们返回到为通用键-值对设计一个DHT这个一般性的问题上。构建DHT的一种幼稚的方法是跨越所有对等方随机地散布（键，值）对，让每个对等方维护一个所有参与对等方的列表。在该设计中，查询的对等方向所有其他对等方发送它的查询，并且包含与键匹配的（键，值）对的对等方能够用它们匹配的对进行响应。当然，这样的方法完全无扩展性，因为它将要求每个对等方不仅知道所有其他对等方（这样的对等方可能数以百万计!），而且更糟的是，要向所有对等方发送一个查询。
我们现在描述设计DHT的一种精确有效的方法。为此，我们现为每个对等方分配一个标识符，其中每个标识符是一个［0，2n-1］范围内的整数，n取某些固定的值。值得注意的是这样的标识符能够由一个n比特表示法来表示。我们也要求每个键是同一范围内的一个整数。敏锐的读者也许已经观察到刚才描述的键的例子（社会保险号和目录名）并非是整数。为在这些键范围外生成整数，我们将使用散列函数把每个键（如社会保险号）映射为［0，2n-1］范围内的一个整数。散列函数是一种多对一的函数，使两个不同的输入能够具有相同的输出（相同的整数），但是具有相同输出的似然性极低。（不熟悉散列函数的读者可以看一下第7章，其中更为细致地讨论了散列函数。）假定系统中的所有对等方可以使用散列函数。因此，当我们提及“键”，指的是初始键的散列值。因此，假如初始键是“Led Zppelin IV”，在DHT中使用的键将是等于“Led Zppelin IV”散列值的整数。如你猜测的那样，这就是“散列”被用于术语“分布式散列表”中的理由。
现在我们来考虑在DHT中存储（键，值）对的问题。此时的中心问题是定义为对等方分配键的规则。给定每个对等方具有一个整数标识符，每个键也是一个位于相同范围的整数，一种当然的方法是为其标识符最邻近该键的对等方分配一个（键，值）对。为实现这样的方案，我们将需要定义“最邻近”的含义。为了方便起见，我们将最邻近对等方定义为键的最邻近后继。为了加深理解，我们来看一个特定的例子。假设n=4，使所有对等方和键标识符都位于［0，15］范围内。进一步假定在该系统中有8个对等方，它们的标识符分别为1、3、4、5、8、10、12和15。假定要在这8个对等方之一上存储（键，值）对（11，Johnny Wu）。但是放在哪个对等方上呢？使用我们定义的最邻近规则，因为对等方12是键11最邻近的后继，因此我们将（11，Johnny Wu）存储在对等方12上。［为了完成我们的“最邻近”定义，说明如下：如果该键恰好等于这些对等方标识符之一，我们在匹配的对等方中存储（键，值）对；并且如果该键大于所有对等方标识符，我们使用模2n规则，在具有最小标识符的对等方中存储（键，值）对。］
此时假定某对等方Alice要将一个（键，值）对插入DHT。从概念上讲，这是直接的：她首先确定标识符最邻近该键的对等方；然后她向那个对等方发送一个报文，指示它存储该（键，值）对。但是Alice怎样确定最邻近该键的对等方呢？如果Alice要联系系统中所有对等方（对等方ID和相应的IP地址），她能够在本地确定最邻近对等方。但是这样的方法要求每个对等方联系在该DHT中的所有其他对等方，而这对于具有数以百万计对等方的大规模系统而言，是完全不现实的。
1.环形DHT
为了处理规模的问题，我们现在考虑将对等方组织为一个环。在这种环形设置中，每个对等方仅与它的直接后继和直接前任联系（模2n）。在图2-27a中显示了这种环的一个例子。在该例中，n仍取为4，有与前例同样的8个对等方。每个对等方仅知道它的直接后继和直接前任，例如，对等方5知道对等方8和4的IP地址和标识符，但不必知道在该DHT中任何其他对等方的情况。对等方的这种环形设置是覆盖网络的一个特殊情况。在一个覆盖网络中，对等方形成了一个抽象的逻辑网，该网存在于由物理链路、路由器和主机组成的“底层”计算机网络之上。在覆盖网络中的链路不是物理链路，而仅是对等方对之间的虚拟联络。在图2-27a所示的覆盖网络中，有8个对等方和8条覆盖链路；在图2-27b所示的覆盖网络中，有8个对等方和16条覆盖链路。一条单一的覆盖链路通常使用了底层网络中的许多条物理链路和物理路由器。

使用图2-27a中的环形覆盖网络，现在假定对等方3要确定DHT中的哪个对等方负责键11。使用该环形覆盖网络，初始对等方（对等方3）生成一个报文，问“谁负责键11？”并绕环顺时针发送该报文。无论何时某对等方接收到该报文，因为它知道其后继和前任的标识符，它能够确定是否由它负责（即最邻近）查询中的键。如果某对等方不负责该键，它只需将该报文发送给它的后继。因此，例如当对等方4接收到询问键11的报文，它确定自己不负责该键（因为其后继更邻近该键），故它只需将该报文传递给对等方5。这个过程直到该报文到达对等方12才终止，对等方12确定自己是最邻近键11的对等方。此时，对等方12能够向查询的对等方即对等方3回送一个报文，指出自己负责键11。
为减少每个对等方必须管理的覆盖信息的数量，环形DHT提供了一种非常精确有效的解决方案。特别是，每个对等方只需要知道两个对等方，即它的直接后继和直接前任。但该解决方案也引入了一个新问题。尽管每个对等方仅知道两个邻居对等方，但为了找到负责的键（在最差的情况下），DHT中的所有N个结点将必须绕环转发该报文；平均发送N/2条报文。
所以，在设计DHT时，在每个对等方必须跟踪的邻居数量与DHT为解析一个查询而需要发送的报文数量之间存在着折中。一方面，如果每个对等方联系所有其他对等方（网状覆盖网络），则每个查询仅发送一个报文，但每个对等方必须关联N个对等方。在另一方面，使用环形DHT，每个对等方仅知道两个对等方，但对每个查询平均要发送N/2条报文。幸运的是，我们能够完善DHT设计，使每个对等方的邻居数量和每次查询的报文数量都保持在可接受的范围内。细化的方案之一是以该环形覆盖网络为基础，但增加“捷径”，使每个对等方不仅联系它的直接后继和直接前任，而且联系分布在环上的数量相对少的捷径对等方。这种具有某些捷径的环形DHT的例子显示在图2-27b中。使用捷径来加速查询报文的路由选择。具体来说，当某对等方接收到一条查询一个键的报文时，它向最接近该键的邻居（后继邻居或捷径邻居之一）转发该报文。所以，在图2-27b中，当对等方4接收到请求键11的报文，它确定（在它的邻居中）对该键最邻近的对等方是它的捷径邻居10,并且直接向对等方10转发该报文。显然，捷径能够大大减少用于处理查询的报文数量。
下一个自然的问题是：“一个对等方应当有多少条捷径，哪些对等方应当成为这些捷径邻居？”该问题已经受到研究界的高度重视［Balakrishnan 2003;Androutsellis-Theotokis 2004］。重要的是，研究表明DHT能被设计成每个对等方的邻居数量以及每个请求的报文数量均为O(log N)，其中N是对等方的数量。这种设计给出了使用网状和环形覆盖网络拓扑的两种极端解决方案之间的一种满意折中方案。
2.对等方扰动
在P2P系统中，对等方能够不加警示地到来和离去。因此，当设计一个DHT时，我们也必须关注存在这种对等方扰动时维护DHT的情况。为了更好地理解处理这个问题所使用的方法，我们再次考虑图2-27a中的环形DHT。为处理对等方扰动，我们此时将要求每个对等方联系其第一个和第二个后继（即知道它们的IP地址）；例如，对等方4此时联系对等方5和对等方8。我们也要求每个对等方周期性地证实它的两个后继是存活的（例如，通过周期性地向它们发送ping报文并寻求响应）。现在我们考虑当某对等方突然离开时DHT如何维护DHT。例如，假定图2-27a中的对等方5突然离开。在此情况下，因为对等方5不再响应ping报文，在离开的对等方之前的两个对等方（4和3）得知5已经离开。对等方4和3因此需要更新它们后继的状态信息。我们考虑对等方4更新其状态的方法：

• 对等方4用它的第二个后继（对等方8）来代替它的第一个后继（对等方5）。
• 然后对等方4向新的第一个后继询问它的直接后继（对等方10）的标识符和IP地址。然后对等方4将对等方10标记为它的第二个后继。

在课后习题中，请你确定对等方3是如何更新它的覆盖路由选择信息的。
在简要地讨论了一个对等方离开时必须要做的事后，我们现在考虑当一个对等方要加入DHT时发生的事情。假如一个标识符为13的对等方要加入该DHT，在加入时，它仅知道对等方1存在于该DHT之中。对等方13将先要向对等方1发送一条报文，说“13的前任和后继是什么？”该报文将通过DHT到达对等方12，而它认识到自己将是13的前任，并且它的当前后继即对等方15将成为13的后继。接下来，对等方12向对等方13发送它的前任和后继信息。对等方13此时能够加入DHT，标识它的后继为对等方15，并通知对等方12它应当将其直接后继改为13。
DHT已经在实践中得到了广泛使用。例如，BitTorrent使用Kademlia DHT来产生一个分布式跟踪器。在BitTorrent中，其键是洪流标识符而其值是当前参与洪流的所有对等方的IP地址［Falkner 2007，Neglia 2007］。以这种方式，通过用某洪流标识符来查询DHT，一个新到达的BitTorrent对等方能够确定负责该标识符（即在洪流中跟踪对等方）的对等方。在找到该对等方后，到达的对等方能够向它查询在洪流中的其他对等方列表。