1. 首页
  2. 技术分享

激励措施在BitTorrent中建立稳健性

作者: 原创: 点对点科技 IPFS点滴资讯

搭建全球化分布式存储网络并不是最近几年的新鲜品,其中最有名的三个就是BitTorrent、Kazaa、和Napster,至今这些系统在全世界依旧拥有上亿活跃用户。尤其是BitTorrent客户端,现在BitTorrent网络每天依然有超过1千万节点在上传数据。(不少刚从高校毕业不久的朋友应该还记得在内网IPV6上分享电影和游戏资源)但令人遗憾的是,这些应用最初就是根据特定的需求来设计,在这三者基础上灵活搭建更多的功能显然很难实现。虽然在此之前学术界和工业界做出了一些尝试,但自始至终没有出现一个能实现全球范围内,低延时,并且完全去中心化的通用分布式文件系统。

IPFS主要借鉴了BitTorrent网络的三大特性,首先是消极上传者的惩罚措施;在BitTorrent,客户端上传数据会奖励积分,而长期不上传的消极节点会扣分。如果分数低于一定限度,那么网络会拒绝再为他们提供服务。其次,是文件可用性检查,BitTorrent优先把稀缺的文件分享出去,各个客户端之间相互补充,这样种子不容易失效,传输效率也提高了。

今天我们就将BT协议做一个很好的分析,方便各位IPFS爱好者更好地了解背后的技术背景。

摘要

BitTorrent文件分发系统使用TFT(tit-for- tat)的方式作为寻求帕累托效率的方法。与目前已知的任何协作技术相比,它实现了更高水平的稳健性和资源利用率。 我们解释了BitTorrent的作用,以及如何使用经济方法来实现这一目标。

BitTorrent的功能

当使用HTTP使文件可用时,所有上载成本都在主机上。使用BitTorrent,当多个人同时下载同一个文件时,他们会相互上传文件。这会将上传的成本重新分配给下载者(通常甚至不会计量),从而使一份可能会有无数潜在下载者的文件变得可负担。研究者们试图找到实用的技术来实现这一点。之前没有大规模部署,因为后勤和稳健性问题非常困难。弄清楚哪些节点具有文件的哪些部分并且应该将它们发送到哪里,而不会引起巨大的开销是很难实现的。此外,实际部署的流失率非常高。节点很少连接超过几个小时,而且通常只连接几分钟[4]。最后,存在公平性的普遍问题[1]。根据数学上的需要,所有下载器的总下载速率必须等于总上传速率。分配上传的策略似乎最有可能让节点对其下载率感到满意,使得每个节点的下载速率与其上传速率成正比。在实践中,很难保持节点下载速率,免于偶尔下降到零,更不用说使上传和下载速率相互关联。我们将解释BitTorrent如何很好地解决所有这些问题。

BitTorrent界面

BitTorrent的界面几乎是最简单的。 用户通过单击他们希望下载的文件的超链接来启动它,并给出标准的“另存为”对话框,然后是下载进度对话框,值得注意的是,除了下载速率之外,该对话框还具有上传速率。这种使用的简单性极大地促进了BitTorrent的采用,甚至可能比本文中描述的性能和成本再分配功能更重要。

部署

使用BitTorrent的决定是由文件的发布者做出的。下载者使用BitTorrent,因为它是获取所需文件的唯一方法。通常,一旦下载完成,下载器就停止上传,尽管在下载完成后让客户端上传一段时间被认为是礼貌的。标准实现继续上传,直到窗口关闭,这经常导致上传继续,直到用户返回他们的机器。

在典型的部署中,不完整的下载器的数量(即没有整个文件的下载者)在文件可用后非常快速地增加。它最终达到峰值,然后以大致指数的速度下降。完整下载器的数量缓慢增加,在不完整的下载器数量达到峰值之后的某个时间达到峰值,然后也呈指数下降。不完整的下载器的峰值在下载器完成后过去。不完整下载者的峰值随着下载完成的下载器停止上传而过去。两者的呈指数衰减反映了在初始高峰期结束后新下载器加入的速度。

技术框架

发布内容

为了启动BitTorrent部署,在普通Web服务器上放置一个扩展名为.torrent的静态文件。.torrent包含有关文件,文件长度、名称和哈希信息以及跟踪器的URL的信息。跟踪器负责帮助下载者找到对方。他们约定一个非常简单的协议,分层在HTTP之上,其中下载器发送有关它正在下载的文件,正在侦听的端口以及其他类似的信息,跟踪器响应下载相同文件的节点的联系信息列表。然后,下载器使用此信息相互连接。要使文件可用,必须启动恰好具有完整文件的“下载器”,称为种子节点。跟踪器和Web服务器的带宽要求非常低,而种子节点必须至少发送一份原始文件的完整副本。

节点分布

文件下载的所有后勤问题都在节点之间的交互中处理。一些关于上传和下载速率的信息被发送到跟踪器,但是这只是为了收集统计数据。跟踪器的职责严格限制为帮助节点找到彼此。

虽然跟踪器是节点找到彼此的唯一途径,并且是唯一的协调点,标准跟踪器算法是返回一个随机的节点列表。随机图具有非常好的稳健性[2]。许多节点选择算法产生幂律图,只需少量流变就可以对其进行分割。请注意,节点之间的所有连接都可以双向传输。

为了跟踪哪些节点具有什么,BitTorrent将文件切割成固定大小的片段,通常为四分之一兆字节。每个下载程序向其所有节点报告它具有哪些部分。为了验证数据的完整性,所有部分的SHA1哈希值都包含在.torrent文件中,并且节点在检查哈希值之前不会报告它们有一块。纠删码被建议作为可能有助于文件分发的技术[3]使用,但是这种更简单的方法已被证明是可行的。

节点不断地下载来自所有节点的片段。当然,它们不能从它们没有连接的节点下载,有时节点没有任何它们想要的或当前不允许它们下载的片段。稍后将讨论对等点不允许下载的策略,称为阻塞。其他建议的文件分发方法通常涉及树结构。简单地让节点宣布它们所具有的结果导致不到百分之十的带宽开销,并且可靠地利用所有可用的上传容量。

流水线

在通过TCP传输数据时,如同BitTorrent一样,始终有几个待处理请求非常重要,以避免发送的数据之间出现延迟,这对传输速率来说是灾难性的。BitTorrent通过在线上将片段进一步分成子片段(通常为16千字节大小)来促进这一点,并且始终保持一定数量,通常是5个,的请求。 每次子片段到达时,都会发送一个新请求。已选择流水线数据量作为可以可靠地使大多数连接饱和的值。

片段选择

选择好的下载顺序的对于良好的性能非常重要。 一个糟糕的片段选择算法可以导致拥有当前所提供的所有片段,或者另一方面,没有任何作品可以上传到你想到的节点。

严格优先

BitTorrent的第一个片段选择政策是,一旦请求了一个片段,就会在从任何其他片段中请求子片段之前,请求该特定片段的剩余子片段。 这样做可以尽快获得完整的片段。

最少片段优先

在选择接下来要开始下载的片断时,节点通常先下载它们自己节点中数量最少的片断,这种技术我们称之为“最稀有优先”。这种技术可以很好地确保节点拥有所有节点都想要的部分,因此可以在需要时进行上传。它还确保更常见的部分留待以后使用,因此当前提供上载的节点稍后不会有任何感兴趣的可能性会降低。

信息理论规定,在文件的每个部分都被种子节点上载之前,任何下载器都不能完成。对于具有单个种子节点的部署,其上载容量远远低于许多下载器,如果不同的下载器从种子节点中获取不同的部分,性能会好得多,因为冗余下载会浪费种子节点获取更多信息的机会。“最稀有优先”只从种子节点下载新片段,因为下载者将能够看到他们的其他节点已有种子节点已经上传的作品。

对于某些部署,原始种子节点最终会因成本原因而被删除,只留当前的下载器进行上传。这导致某个特定片段不能够从当前下载器那里获得。“最稀有优先”也很好地处理这个问题,尽可能快地复制最稀有的部分,从而降低当前节点停止上传时他们完全丢失的风险。

随机首片段

最稀有优先的例外发生在下载开始时。此时,节点没有上传的内容,因此尽快获得完整的片段非常重要。稀有片段通常只存在于一个节点上,因此它们比存在于多个节点上的片段下载的速度要慢,对于多个节点,可以从不同位置下载子片段。由于这个原因,要下载的片段是随机选择的,直到第一个完整的片段被组装,然后策略首先改变为最稀有优先。

终结模式

有时,从一个传输速率非常慢的节点请求一个片段。在下载过程中这不是问题,但是可能会延迟下载的完成。为了防止这种情况发生,一旦一个节点没有的所有子块都被主动请求,它就向所有节点发送所有子块的请求。到达片段的发送取消是为了防止过多的带宽被浪费在冗余发送上。在实践中,这种方式不会浪费太多的带宽,因为终结时间非常短,并且文件的末尾总是快速下载。

阻塞算法

BitTorrent没有中央资源分配。每个节点负责尝试最大化自己的下载速率。节点通过从任何人那里下载,并通过TFT机制的变体决定上传到哪个节点来实现这一点。为了合作,节点上传;不合作,他们“阻塞”节点。阻塞是暂时拒绝上传;它停止上传,但下载仍然可能发生,当阻塞停止时,连接不需要重新协商。

阻塞算法在技术上不是BitTorrent有线协议的一部分,但是对于良好的性能是必需的。一个好的阻塞算法应该利用所有可用的资源,为每个人提供合理的一致的下载速率,并且对于只下载而不上传的节点有一定的抵抗力。

帕累托效率

众所周知的经济理论表明,具有帕累托有效性的系统,意味着没有两个交易对手可以进行交换,同时两者都更为幸福,且往往具有上述所有特性。在计算机科学术语中,寻求帕累托效率是一种局部优化算法,在该算法中,成对的参与者查看他们是否能够一起提升,并且这种算法趋向于导致全局最优。具体来说,如果两个节点从他们提供的某些上传得到的往复都很差,他们通常可以开始相互上传,并且两者都获得比以前更好的下载速率。

BitTorrent的窒息算法尝试使用更加充实的针锋相对的版本来实现帕累托效率,而不是用于扮演囚徒困境。节点向上传到它们的节点进行往复上传,其目标是随时具有多个连接,可以在两个方向上主动传输。未使用的连接也被上传到一个试验基础上,看看是否可以使用它们找到更好的传输速率。

BitTorrent的阻塞算法

在技术层面上,每个BitTorrent节点总是取消固定数量的其他节点(默认为4)的阻塞,因此问题变成了哪些节点取消阻塞。这种方法允许TCP的内置拥塞控制可靠地使上载容量饱和。

关于哪些节点取消选择的决定严格基于当前下载速率。有意义地计算当前下载速率是一个令人惊讶的难题;当前实现基本上使用滚动20秒的平均值。以前的窒息算法使用了有关长期净传输量的信息,但是表现很差,因为随着资源消失并变得可用,带宽值随着时间的推移而迅速变化。

为了避免由于快速阻塞和不阻塞节点而浪费资源,BitTorrent重新计算一次他们想要阻塞的对象,然后将情况保持原样,直到下一个十秒为止。足够长的时间让TCP将新的传输速度提升到最大容量。

乐观疏通

简单地上传到提供最佳下载速率的节点将无法发现当前未使用的连接是否比正在使用的连接更好。 为了解决这个问题,BitTorrent节点在任何时候都有一个“乐观疏通”,无论当前的下载速率如何,它都不被阻塞。“乐观疏通”的节点每三个阻塞计算周期重新启动一次(30秒)。30秒是上传达到满载、往复下载和下载达到满载的足够时间。这里针锋相对的类比是很显著的;乐观疏通是在囚徒困境中的第一步中选择合作的响应十分强烈。

防止怠慢

有时,BitTorrent节点会被以前从其下载的所有节点阻塞。在这种情况下,它通常会继续得到低下载率,直到乐观疏通算法找到更好的节点。为了缓解这个问题,当超过一分钟没有得到特定节点的单个片段时,BitTorrent认为它被该节点“怠慢”并且不会上传到它,除非作为一个“乐观疏通”。这经常导致多个并发的乐观疏通(正是上面提到的一个乐观疏通规则的例外),这导致下载速率在它们摇摆时更快地恢复。

仅上传

一旦节点完成了下载,它就不再具有有用的下载速率来决定上载到哪个节点。然后,当前的实现切换到具有更好上载速率的节点,这可以很好地利用所有可用的上载容量并且优先选择当前没有其他任何人正在上传的节点。

激励措施在BitTorrent中建立稳健性

图1:随着时间的推移,超过400兆字节文件的大型部署的种子节点(’seeders’)和下载节点(’leechers’)的数量。 必须至少有1000次成功下载,因为曾经有很多完整的下载器。在此期间完成的实际下载数量可能是数倍。

现实世界的经验

BitTorrent不仅已经实现,而且已经广泛部署。 它通常为数百个并发下载器提供数百兆字节的文件。已知最大的部署已经有超过一千个同步下载程序。 当前的缩放瓶颈(实际上尚未达到)似乎是跟踪器的带宽开销。目前,这大约是所使用带宽总量的千分之一,而一些小的协议扩展可能会降低到万分之一。

Bram Cohen

bram@bitconjurer.org

May 22, 2003

参考文献

[1] E. Adar and B. A. Huberman. Free riding on gnutella. First Monday, 5(10), 2000.

[2] A.-L. Barab ́asi. Linked: The New Science of Net- works. Perseus Publishing, 2002.

[3]  M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. Split- stream: High-bandwidth content distribution in cooperative environments. In Proceedings of IPTPS03, Berkeley, USA, Feb. 2003.

[4]  P. Maymounkov and D. Mazieres. Kademlia: A peer-to-peer information system based on the xor metric. In Proceedings of IPTPS02, Cambridge, USA, Mar. 2002.

激励措施在BitTorrent中建立稳健性

原创文章,作者:点对点资讯,如若转载,请注明出处:https://ipfsdrop.com/tech/jilicuoshizaibittorrentzhongjianliwenjianxing/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

联系我们

(+86)18301922335

在线咨询:点击这里给我发消息

邮件:haskell@freechains.cn

工作时间:7×24小时

QR code