（计算机应用技术专业论文）bittorrent系统中可扩展性的研究.pdf

b i t t o r r e n t 系统中可扩展性的研究 v 7 0 0 5 5 9 上 摘要 点对点网络( p 2 p ) 指网络用户之间可以直接通信的网络结构。p 2 p 使用户 可以直接连接到其他用户的计算机，而不是像过去那样连接到服务器去浏览与下 载；另外，p 2 p 改变了互联网现在的以大网站为中心的状态、重返“非中心化”， 把权力交还给用户。 可扩展性是p 2 p 系统的一个重要指标。本文首先讨论了p 2 p 文件共享系统的 可扩展性问题，分析了一种结构化p 2 p 网络c h o r d 如何解决在分布式p 2 p 文件 共享系统中查找资源的可扩展性问题。 b i t t o r r e n t 是一种p 2 p 资源发布系统。b i t t o r r e n t 系统具有很强的负载平衡能 力，可以很快将大文件分发给很多用户；而且b i t t o r r e n t 系统中有专门的算法保 证了系统的公平性。不过b i t t o r r e n t 系统依赖于系统中的一个集中式的设备 追踪器，因而b i t t o r r e n t 系统中存在单点失效的问题，而且单一追踪器无法为很 多用户提供服务，b i t t o r r e n t 系统的可扩展性不够好。 针对于b i t t o r r e n t 系统可扩展性不好的问题，本文定义了b i t t o r r e n t 追踪器问 通信协议，提出追踪器网络模型。追踪器之间用追踪器间通信协议通信，就可以 实现追踪器网络，从而提高b i t t o r r e n t 系统的可扩展性。 关键词：点对点b i t t o r r e n t 可扩展性文件共享系统资源发布系统层次结构 b i t t o r r e n t 系统中可扩展性的研究 a b s t r a c t p e e r - t o - p e e r ( p 2 p ) n e t w o r ki san e t w o r ks t r u c t u r ew h e r e u s e r sc a l lc o m m u n i c a t e w i t he a c ho t h e rd i r e c t l y p 2 pe n a b l e sp e o p l et oc o m 3 c c tt oo t h e ru s e r s c o m p u t e r d i r e c t l y , i n s t e a do f o l dm e t h o d sl i k eb r o w s i n go rd o w n l o a d i n gf r o mas e r v e r ；a n dp 2 p c h a n g e s t h ei n t e m e tf r o mc e n t e r e db y l a r g es i t e st o “n o n c e n t e r ，r e t u r n st h ep o w e rt o u s e r s s c a l a b i l i t yi sa ni m p o r t a n ta s p e c to fp 2 ps y s t e m s i nt h i sp a p e rw ef i r s td i s c u s s s c a l a b i l i t yo f p 2 pf i l e s h a r i n gs y s t e m s ，a n da n a l y z eh o w as t r u c t u r e dp 2 pn e t w o r k ， c h o r d ，i m p r o v e st h es c a l a b i l i t yo fs e a r c h i n gi nd i s t r i b u t e dp 2 pf i l es h a r i n gs y s t e m s b i t t o r r e n ti sap 2 pc o n t e n td e f i v e r ys y s t e m ，w i t ha l l e f f i c i e n tl o a db a l a n c i n g m e c h a n i s m ，a n dl a r g ef i l e sc a l lb ed e l i v e r e dq u i c k l yt om a n yu s e r sb yb i t t o r r e n t ； b i t t o r r e n ts y s t e mg u a r a n t e e sf a i r n e s sw i t hab u i l t i na l g o r i t h m h o w e v e r , b i t t o r r e n t s y s t e mr e l i e so nac e n t e rd e v i c e ，i r a c k e r , s os i n g l e - p o i n t - f a i l u r ep r o b l e me x i s t si n b i t t o r r e n t m o r e o v e r , s i n c eo n et r a c k e rc a n n o ts e r v em a n yu s e r s ，b i t t o r r e n ts y s t e m d o e sn o th a v e g o o ds c a l a b i l i t y a i m i n g a ts c a l a b i l i t yp r o b l e mi nb i t t o r r e n ts y s t e m ，w ed e f i n eb i t t o r r e n tt r a c k e r c o m m u n i c a t i o np r o t o c o l ，a n dp r e s e n tt r a c k e rn e t w o r km o d e l b ya p p l y i n gt r a c k e r c o m m u n i c a t i o n p r o t o c o l ，t r a c k e r sa r eo r g a n i z e di n t oan e t w o r k ，a n dt h es c a l a b i l i t yo f b i t t o r r e n ts y s t e mi si m p r o v e d k e yw o r d s ：p e e r _ t o p c e r ( p 2 p ) ，b i t t o r r e n t ，s c a l a b i l i t y , f i l es h a r i n gs y s t e m , c o n t e n t d e l i v e r ys y s t e m ，l a y e r e ds t r u c t u r e - 2 b i t t o r r e n t 系统中町扩展性的研究 第一章绪论 1 1 p 2 p 的概念 点对点网络( p e e rt op e e r ，简称p 2 p ) 指网络用户之间可以直接通信的网络 结构。简单的说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互。p 2 p 使得网络上的沟通变得容易、更直接共享和交互，真正地消除中间环节。p 2 p 使 用户可以直接连接到其他用户的计算机，而不是像过去那样连接到服务器去浏览 与下载。p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状态，重返 “非中心化”，把权力交还给用户。 从互联网的发展历史上看，p 2 p 并不是一个全新的概念。我们知道t c p i p 是现代互联网整体架构的基础，但在t c p i p 中并没有客户端和服务器的概念， 所有的设备都是通信的平等的一端l ”。早在3 0 年前许多公司的计算结构就可以 划分到现在的p 2 p 中，只不过由于带宽及处理能力等的限制，使得我们的沟通 中出现了很多的中间环节，如中间服务器、导航网站、第三方信息( 交易) 平台 等。可是，对于服务器来说，它们之间仍然是对等互联的。例如电子邮件系统， 互联网上并没有一个巨大的、唯一的邮件服务器来处理所有的电子邮件，而是对 等联网的邮件服务器相互协作把电子邮件传送到相应的服务器上去。但是，互联 网在应用层以上层面的发展使得互联网上绝大部分的非服务器节点不能和其它 节点直接地交流，而失去了网络的p 2 p 特点。现在，廉价的计算能力、网络通 信能力、p c 计算机的存储能力强有力的推动了这项技术的迅速发展。 1 2 c s 与p 2 p 客户端，服务器( c l i e n t s e r v e r , 简称c s ) 与点对点网络( p 2 p ) 是因特网中 两种最主要的网络模型【2 j 。 b i t t o r r e n t 系统中口j 扩展性的研究 削1 1 ( a ) c s 结构( b ) p 2 p 结构 他们之间主要的区别在于c s 模型是不对称的，而p 2 p 模型是对称的。在 c s 模型中，一般的通信过程是这样的：客户端与服务器建立连接，客户端发送 请求，服务器应答。与c s 模型不同，在p 2 p 模型中，节点( 使用者，相当于 c s 模型中的客户端) 之间会互相发送服务请求，也会互相提供服务。实际上， 在p 2 p 模型的通信过程中，每次通信过程都是一个微型c s 结构的通信，由某 节点发出请求，另一节点提供服务。所以可以认为p 2 p 模型中任一节点都既是 服务器，也是客户端。 传统的网络应用比如h r r p 、f t p 等都是基于c s 结构的，但是c s 结构在 网络越来越发达的情况下暴露出了一个问题：服务器端的可用性不足。c s 模型 中，对于某一服务器端，当连接的客户端数量逐渐增加时，服务器端的负荷越来 越重。而一旦服务器端失效，所有客户端都无法正常使用网络。这个问题被称为 “单点失效”。人们为了解决这个问题，使用过很多办法，比如使用更高级的硬 件、镜像技术等等。但是当客户端数量更多时。服务器还是无法应付，只能更换 更高级的硬件，使用更多的镜像，陷入一个恶性循环。 p 2 p 模型中不存在单点失效问题。因为不存在一个服务器，而且所有节点的 地位均等，所以，单一节点失效不影响整个网络，其他节点之自j 还可以继续通信。 1 3 p 2 p 网络结构的特点 如上所述，p 2 p 网络中，节点是对称的。除此之外，p 2 p 网络还有以下特点： 1 ) 节点自治性 6 b i t t o r r e n t 系统中可扩腥性的研究 p 2 p 系统中的节点具有很高的自治性，每个节点都希望得到更多的服务。在 p 2 p 系统中，某个节点得到的服务一定是其他节点提供的，然而就某个节点来讲， 它总是希望能得到别的节点提供的服务，而不愿意为其他节点提供服务。为了让 更多的节点提供服务，在很多p 2 p 系统中，有一些激励手段，让提供服务的节 点可以优先享受服务 3 0 1 。 2 ) 充分利用网络资源 c s 结构根本的问题在于资源使用的不合理，服务器端负荷很重，但是客户 端的资源并没有完全发挥作用。p 2 p 结构中客户端的资源得到了充分利用，整个 系统性能提高了很多。客户端( 也就是p 2 p 模型中的节点，p e e r ) 贡献可用资源， 给其他节点提供服务，有效的减轻了服务器端的负荷。 3 ) 高度动态性 p 2 p 网络是高度动态的，节点可以随时加入或离开网络。另外，节点之间的 连接很不稳定，随时都可能断开。p 2 p 系统必须能适应网络结构的变化。 1 4 关于p 2 p 的研究与应用 关于p 2 p 的研究很多，i p t p s ( i n t e m e tw o r k s h o p o np e e r - t o - p e e rs y s t e m s ) 是专 门关于p 2 p 相关技术的学术会议，一些网络方面的国际会议上也会出现p 2 p 方 面的论文。p 2 p 研究的方向包括p 2 p 网络算法，p 2 p 安全性，关于p 2 p 网络的测 试和比较等等。 p 2 p 应用大致分为几种：p 2 p 文件共享，即时通信，p 2 p 流媒体等。下面简 单介绍一下各种p 2 p 应用： 1 ) p 2 p 文件共享 p 2 p 文件共享网络的出现解决了以往c s 结构中单点失效的问题，在p 2 p 文 件共享网络中，用户可以很容易的共享自己的文件，也可以从别的用户直接下载 自己感兴趣的文件。在典型的p 2 p 文件共享网络中，文件被分为小块，当很多 用户同时下载同一文件时，他们之间会互相交换已经下载好的小块，能有效的提 高下载效率。当前已经有很多p 2 p 文件共享协议，在因特网上流行的有f a s t t r a c k ( k a z a a l 3 7 使用的协议) 、e d o n k e y o v e r n e t 3 8 1 、b i t t o r r e n t l 3 9 1 、g n u t e l l a l 4 0 1 等。 p 2 p 文件共享的流量巨大，是p 2 p 网络乃至整个因特网的最主要流量【7 1 ，因 此对于p 2 p 文件共享系统的研究将影响整个因特网的发展。在p 2 p 文件共享系 b i t t o r r e m 系统中可扩展性的研究 统中，如何更高效的搜索，如何使系统可扩展性更好，如何提高系统的安全性、 匿名性，都是值得研究的问题。 2 1 即时通信 即时通信( i n s t a n tm e s s e n g e r ，简称i m ) 软件是广大网络用户最常用的软件 之一，比如q q 、m s n 、i c q 、网易泡泡、雅虎通、s k y p e l 2 3 】等。i m 软件最大的 特点是广泛的交互性。无论是在办公室还是在家，无论近在咫尺或是远隔重洋， 亲朋好友或同事之间都可以通过i m 软件进行文字、语音、视频交流。随着网络 的成熟与发展，即时通信工具的实时交互、资费低廉等优点开始逐渐受到用户的 喜爱，已经成为网络生活中不可或缺的一部分。 3 ) p 2 p 流媒体 p 2 p 技术也可以应用到流媒体，每个流媒体用户也是一个p 2 p 中的一个节点， 在目前的流媒体系统中用户之间是没有任何联系的，但是采用p 2 p 技术后，用 户可以根据他们的网络状态和设备能力与一个或几个用户建立连接来分享数据， 这种连接能减少服务器的负担和提高每个用户的视频质量。p 2 p 技术在流媒体应 用中特别适用于一些热门事件，即使是大量的用户同时访问流媒体服务器，也不 会造成服务器因负载过重而瘫痪。此外，对于多人的多媒体实时通信，p 2 p 技术 也会对网络状况和音视频质量带来很大改进。 香港中文大学的x i n y a nz h a n g 已经开发出一个投入实用的p 2 p 流媒体播放 软件c o o l s t r e a m i n g 引。在2 0 0 4 年6 月欧洲杯期间使用该软件的用户达到4 0 0 0 人， 在最近的2 0 0 5 年春节使用该软件观看春节联欢晚会的用户达到8 0 0 0 人。 1 5 p 2 p 文件共享协议 1 4 - 1 n a p s t e r n a p s t e r 是最早的p 2 p 文件共享协议。n a p s t e r 是一个专门交换m p 3 文件的平 台，用户可以搜索m p 3 文件，然后连接到拥有该m p 3 文件的用户，下载m p 3 。 n a p s t e r 使用了一个中央服务器作为索引服务器，即哪些用户共享了哪些文件， 都在中央服务器上记录，用户在查找m p 3 文件时也先连接到中央服务器提交查 找条件，然后从中央服务器得到拥有该m p 3 文件的用户地址列表，然后才能连 接到该用户。n a p s t e r 虽然采用了p 2 p 方式( 用户之间直接传输m p 3 文件) ，但 b i t t o r r e n t 系统中可扩展性的研究 是整个系统还是依赖于中央服务器，属于单点失效的系统。 图1 2n a p s t e r 1 4 2 g n u t e n a g n u t e l l a 是另一个p 2 p 文件共享协议。g n u t e l l a 与n a p s t e r 完全不同，系统中 没有中央服务器，称为分布式结构。在g n u t e u a 中节点与一些其他的节点连接， 这些节点称为“邻居”，节点之间通过交换邻居列表，来“认识”更多的邻居， 即连接更多的节点。用户要下载某文件，必须在网络上进行搜索。在g n u t e l l a 的 搜索过程中，节点向所有邻居发送搜索请求，每个邻居收到搜索请求后会检查本 机是否有符合条件的文件，另外，也会向自己的邻居发送搜索请求，邻居的邻居 继续向自己的邻居发送搜索请求。这样，一传十，十传百，搜索可以遍历g n u t e l l a 系统中所有节点。 b i t t o r r e n t 系统中可扩展性的研究 图1 3g n u t e l l a 但是g n u t e l l a 系统的最大问题是搜索的不可扩展性，搜索带来的冗余网络流 量太多。g n u t e l l a 系统中，搜索必须遍历每一个节点，再由节点亲自检查本桃是 否有搜索发起者需要的文件。如果能把节点拥有的文件做成索引，统一放在一起， 那么搜索产生的冗余网络流量就可以减少很多，就像n a p s t e r 系统中的中央服务 器。 为了解决非结构化系统中的随机搜索造成的不可扩展性，大量的研究集中在 如何构造一个高度结构化的系统。在这些结构化的系统中，网络结构被严格控制， 文件( 或者文件指针) 存放在确定的位最上。系统提供从文件标识符到存放该文 件的节点标识的映射服务，然后查找请求路由到该节点。通过以上方法系统提供 了一个可扩展的方案实现了文件的“精确匹配”查找。目前人们把研究的重点放 在了如何有效地查找信息上，最新的成果都是基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 的分布式查找和路由算法。第一批d h t 算法出现在2 0 0 1 年，4 个d h t 算法同 时出现，c a n 9 1 、c h o r d l l 0 1 、p a s t r y t q 、t a p e s t r y 1 2 】；后来又不断出现新算法，包 括k a d e m l i a 13 1 、k o o r d e l l 4 1 、v i c e r o y 15 1 、b 锄b o o 【1 6 1 等。有些系统已经投入实用， c h o r d 应用于c f s 研，k a d e m l i a 应用于o v e m e t ，t a p e s t r y 、b a m b o o 应用于 o c e a n s t o r e 1 引，p a s t r y 应用于p a s t 1 川等等。 1 4 3 k a z a a k a z a a 是一个基于f a s t t r a c k 协议的p 2 p 文件共享平台，k a z a a 最主要的特点 是它的分层结构。在k a z a a 中节点分为两种，普通节点和超级节点，普通节点必 b i t t o r r e n t 系统中可扩展性的研究 须通过超级节点连接到k a z a a 网络中，超级节点之间互相直接连接。搜索时，予 节点向超级节点提交搜索请求，超级节点在自己的子节点信息中找，另外也询问 其他超级节点，综合两者，返回一些符合条件的节点地址列表，然后子节点直接 与资源拥有者通信。k a z a a 的分层结构介于n a p s t e r 的集中式结构和g n u t e l l a 的 分散式结构之间，较好的解决了单点失效和可扩展性问题之间的矛盾。 幽1 4f a s t t r a c k ( k a z a 曲 1 4 4 e d o n k e y o v e r n e t e d o n k e y o v e m e t 是另外一种p 2 p 文件共享平台，它分为两种网络结构e d 2 k 和k a d e m l i a 。e d 2 k 是类似于n a p s t e r 的服务器结构，节点必须连接到某个服务器， 服务器管理所有连接到服务器的节点共享文件的信息。k a d e m l i a 是一种基于 d h t 算法的分布式p 2 p 网络，不依赖于服务器。两种网络结构一起构成了 e d o n k e y o v e r n e t 系统，两者之间形成互补。 1 4 5 b i t t o r r e n t 最后要介绍的种p 2 p 文件共享协议就是b i t t o r r e n t ( 简称b t ) 。严格来讲， b i t t o r r e n t 并不是一种p 2 p 文件共享系统，而是一种p 2 p 资源发布系统( c o n t e n t d e l i v e r ys y s t e m ) 。在b i t t o r r e n t 下载系统中，主要解决了负载平衡的问题，而不 是资源的搜索问题，搜索是用户在加入b t 网络之前由自行解决的。b t 系统可 以迅速将资源分发给很多用户，另外在b t 系统中有专门的算法保证了系统的公 平性。据统计f 3 l 】，b t 网络流量已经超过k a z a a 成为消耗网络流量最多的p 2 p 系 统。不过b t 系统依赖于一个集中式的设备，具有单点失效性，而且可扩展性不 b i t t o r r e n t 系统中可扩展性的研究 好。 1 6 本文的结构 第一章介绍p 2 p 网络；第二章研究一种结构化p 2 p 网络c h o r d 是如何解决 p 2 p 文件共享系统中查找的可扩展问题；第三章详细介绍b i t t o r r e n t 系统；第四 章提出追踪器间通信协议，并通过追踪器间通信协议在b i t t o r r e m 系统中建立追 踪器网络，增强了b i t t o r r e n t 系统的可扩展性；第五章对全文做出总结，对将来 的研究工作做了展望。 b i t t o r r e n t 系统中可扩展性的研究 第二章p 2 p 文件共享系统的可扩展性 2 1 g n u t e l l a 2 1 1 g n u t e l l a 简述 g n u t e l l a 是一个典型的分布式p 2 p 文件共享系统。由于g n u t e l l a 是开放所有 源代码，所以g n u t e l l a 很适合研究，学术界已经有很多关于g n u t e l l a 的研究结果。 g n u t e l l a 系统中，没有中央服务器，每个节点与其他一些节点连接，节点之间可 以交换共享文件。 图2 1g n u t e l l a 2 1 2 g n u t e l l a 系统中的查找机制 节点可以在g n u t e l l a 网络中查找感兴趣的内容，找到之后与持有该文件的节 点通信，从对方节点下载文件。g n u t e l l a 系统中的查找是通过广播方式完成的， 主要有以下几种机制”1 ： ( 1 ) 向前广播入消息； g n u t e l l a 协议采用公平简单的方法向周围节点广播消息。g n u t e l l a 网络中 的每个客户端都管理着一系列和其它客户端的连接。对于每个客户端除了知 道本地连接外并不知道网络的拓扑，网络中的每个节点将接收到的消息发送 到除消息的来源节点外的所有与其直接相连的的节点上。 ( 2 ) 丢弃已见过的入消息； b i t t o r r e n t 系统中町扩展性的研究 一个客户端从其它客户端接收到一个请求消息时，它仅仅检查这个消息 是否是先前已经处理过的。如果这个消息是先前己经处理过的，它就丢弃该 消息，不再向前广播：如果这个消息是先前没有处理过的，它就将这个消息广 播到和它相连的所有对等点上。为了确定每个消息是否是先前处理过的，每 个消息都需要有一个唯一的标识号，在每个客户端都需要维护一个近来收到 的消息队列。如果这个新近接收到的消息号在其维护的消息对列中未出现， 就对这个消息进行广播，否则就将其丢弃。 ( 3 ) 丢弃n l = 1 的入消息； 传播的消息每经过一个节点，其消息的t t l 值就减l ，h o p c o u n t s 的值就增 加1 ，当发现该消息的”l 值等于1 时，则停止向前广播该消息。 ( 4 ) 源路返回应答消息： 作为请求的应答消息，根据节点记录的历史信息，其沿源路径返回： o n u t e l a 消息源路返回机制如下：当目标节点, 对r e q u e s t 消息产生b r e s p o n s e 响 应后，它就传递给和它直接相连的节点，产生的r e s p o n s e 消息和请求的r e q u e s t 消息具有一致的消息d 号，接收n r e s p o n s e 消息的节点就将该消息的i d 号和 自己保存的消息列表中的i d 号进行比较并判断该消息的类型，如果该消息的 类型是r e s p o n s e 而且消息列表中又具有该消息i d 号时，爿进行传递；否则丢 弃，直至到达请求的源节点。 ( 5 ) 节点自己产生的消息向所有连接广播； 对于节点自身产生的消息，将在其所有的连接上进行广播。 2 1 3 g n u t e l l a 广播查找方式存在的问题 在这种搜索方式中，会产生很多冗余网络流量。比如在图2 2 所示的结构中， 节点a 为初始节点，a 把搜索请求发给b 、c ，b 又把搜索请求发给c ，c 把搜 索请求发给b ，这样b 和c 各收到一个重复的搜索请求。 b i t t o r r e n t 系统中可扩展性的研究 o n j l u | i o 图2 2g n u t e l l a 搜索造成，余网络流量 当g n u t e l l a 系统规模越来越大，因为搜索产生的冗余网络流量越来越多，网 络中的消息呈指数级数增长，用有限带宽来处理这些无限增长的消息量，过载是 一种必然的结果，从而导致g n u t e l l a 系统无法使用。因此，g n u t e l l a 系统的可扩 展性不好。 2 2 c h o r d g n u t e l l a 之所以可扩展性不好，是因为g n u t e l l a 中的查找功能效率不高，为 此，学者们提出了一些结构化p 2 p 网络结构，在这些网络结构中的核心操作是 有效地对象定位。下面介绍一种典型的结构化p 2 p 网络：c h o r d 。 2 2 1 c h o r d 简述 使用c h o r d 协议非常简单：指定一个对象( o b j e c t ) ，协议就把对象映射到相应 的节点。在基于c h o r d 协议的应用中，节点负责存贮与节点相联系的对象。c h o r d 使用相容哈希函数把对象分配到相应的节点上，每节点分摊差不多相同数量的对 象，同时在节点的加入和离去时仅需要移动很少的对象，使系统达到负载平衡。 以前的相容哈希函数是建立在每个节点知道系统其他节点前提下，所以，该 方法不能扩展到具有众多的节点的系统中。相反地。在c h o r d 系统中，节点并不 需要知道所有的节点，仅需要保存少数几个节点的路由信息，由于路由表是按某 种规律分布的，一个节点可根据其路由表与其它节点通信及进行查找。一个包含 n 个节点的系统在稳定状态下，每个节点保留只需o o o g n ) 节点的相关信息，通 过o ( 1 0 9 n ) 次消息转发就可完成查找请求。另外，系统在节点的加入与离去时保 证路由信息与系统的变化保持同步。 b i t t o r r e n t 系统中可扩展性的研究 c h o r d 节点需要o ( 1 0 9 n ) 个有效节点路由信息，可见，当部分路由信息失效 时，系统的查找效率将适度下降。出于网络中的节点可以随时的加入或离去，维 护路由信息一致性是很困难。在实际应用中，每个节点的必须保持其路由信息正 确性，来保证其查找路由的f 确性，c h o r d 协议为我们提供一个简单的算法来维 持动态信息的一致性。 2 2 2 c h o r d 协议 c h o r d 协议实际上是一个环形的查找服务。c h o r d 环上有m 位空i 、日j ，提供2 “ 个标识符。每个连入c h o r d 系统的节点被分配一个节点编号，比如可以用节点的 i p 地址、端口和程序的进程序号来计算节点编号。c h o r d 环的空间足够大( 也就 是说维数m 足够大) ，保证没有两个节点算出的节点编号相同。c h o r d 协议保证 了给定任意一个标识符，都能找到一个具有等于或大于标识符的最小编号的节点 ( 标识符处在环上，总能找到后继) ，这个节点称为标识符的后继节点( s u c c e s s o r ) ， 另外称每个节点为后继节点的前趋节点( p r e d e c e s s o r ) 。对于每个节点n 来说，该 节点的节点编号都对应个后继节点n ，这个节点n 也称为节点。的后继节点。 c h o r d 环中可以保存一些对象，每个对象也用哈希函数计算出一个标识符，称为 这个对象的编号，对象就保存在它的编号的后继节点中。 图2 3c h o r d 环 如图2 3 所示，c h o r d 环中总节点数n = 1 0 ，标识符空间位数为m = 6 ，对象数 为5 ，其中，对象0 1 0 ( 编号为1 0 的对象) 的对象被存储在其后继节点n 1 4 ( 编 号为1 4 的节点) ，同样，对象0 2 4 保存在节点n 3 2 ，对象0 3 0 也保存在节点n 3 2 ， 对象0 3 8 保存在节点n 3 8 ，对象0 5 4 保存在节点n 5 6 。 b i t t o r r e n t 系统中可扩展性的研究 为了保持一致性，c h o r d 环在有节点加入环或者有节点离丌环时要进行一些 对象的转移。新节点加入c h o r d 环，一些应该储存在该节点的对象还保存在该节 点的后继节点上，应该把这些对象转移到新节点上。而当有节点要离丌c h o r d 环时，所有储存在该节点上的对象都应该转移到该节点的后继节点上去。比如在 图2 3 中，如果节点编号为2 5 的新节点n 2 5 加入c h o r d 环，那么0 2 4 对象就要 转移到n 2 5 上；而如果节点n 3 8 离开c h o r d 环，对象0 3 8 就要转移到n 4 2 上。 2 2 3 一种简单的对象查找算法 那么，如何在c h o r d 环上找到一个已知编号的对象昵? 一个简单但速度慢的 算法是，每个节点都保存后继节点的地址，整个环就可以通过迭代方式遍历，那 么访问任意节点，都可以通过遍历c h o r d 坏找到任意编号的对象。 n 1 ：甓n 愁鎏黧墨篙5 一矿耐圆 n nn j n c c e s s o r d 一 证e n n f 酬) 一 n l ms u c c 衄o i ： “。 d s e 细，耐埔日q u c * y a r o u n d t h e c i r c l e m e l ；t n mn “5 r 毋h d j i r e f d ) ： 图2 4 简单对象查找算法 图2 4 ( a ) 是该算法的伪代码，n f i n ds u c c e s s o r 0 是一个节点n 的r p c 函数 f i n d _ s u c c e s s o r 0 ，用户或其他节点可以调用这个函数，找出指定标识符的后继节 点。图2 4 1 ：b ) 是调用节点n 8 找出对象0 5 4 的过程。在查找过程中，每个n 8 与 n 5 6 之间的节点都被遍历了一遍。这个算法中遍历的节点数为o ( n ) ，n 是c h o r d 环中的节点总数。 2 2 4 可扩展的对象查找算法 为了加快查找速度，减少经历节点数，c h o r d 协议中在每个节点上加入了一 些额外的节点地址信息。不过这些信息的正确性不影响查找结果，因为只要每个 节点能正确的找到自己的后继节点，就能保证结果的正确性。 b i f l o r r e n t 系统中可扩展性的研究 如前所述，m 是c h o r d 环的维数。令每个节点n 维护一张表，其中包括n 1 个 节点的地址，我们称之为路由表。路出表中的第i 项内容为标识符( n + 2 i - i ) 的后 继节点地址，可由下式描述： n f i n g e r i 】_ s h c c c s s o r ( n + 2 “1 ) ，l _ i ；m( 2 1 ) 其中节点的地址包括i p 地址和端口。需要注意的是，节点n 的路出表中第一项 对应的节点就是n 的后继节点。 n 1 图2 5 节点n 8 的路由表 圈 d 暗自。由n t o a ，d j f 船钾矿i d n 最【坩j u c c 埘- 口r f l 由 * ( 耐n ，_ 叫) i 缸f t m t z s 口o r ； b ，# r l f 舯w d m “村c d ) ： h l l t ”j h d j u 舢胛f f d k 暗枷l o e a ! “幽扫舢姆m 胂豳r 咖d t id 0 5 e n p f o c d i h 窿胛d b t d i f 打，嚣m d c , n t , i e 滞船 lc - f ，越j r e t t m f f i 盯l t j ： r t t m n ： 图2 - 6 ( a ) 可扩展节点查找算法 图2 6 ( b ) 可扩展节点壳找算法 图2 5 画出了节点n 8 的路由表。图2 6 ( a ) 的伪代码是新的应用了路由表的对 象查找算法f i n d _ s u c c e s s o r 0 函数，如果对象编号在节点编号与后继节点编号之 间，那么查找完成，返回后继节点：如果对象编号与路由表中某项相同，那么查 找完成，返回路由表中的这一项；否则找到路由表中比对象编号小的节点中编号 最大的一个，调用该节点的f i n d _ s u c c e s s o r o 函数。参考图2 6 ( b ) 中的例子，还是 调用n 8 找出0 5 4 ，n 8 的路由表中没有n 5 4 ，那么比5 4 小的节点中最大的是 b i t t o r r e n t 系统中可扩展性的研究 n 4 2 ，于是n 8 调用n 4 2 的f i n d _ s u c c e s s o r 0 函数继续找，n 4 2 继续调用n 5 1 ，最 终n 5 1 发现5 4 在自己和自己的后继节点n 5 6 之间，于是返回n 5 6 的地址。 这个算法中需要经历的节点数为o ( 1 0 9 n ) ，试验证明平均经历节点数为 1 = ( t o g n ) n 2 3 c h o r d 系统的动态稳定性 在c h o r d 系统中，由于加入了路由表，节点在加入或离开c h o r d 环时，需要 更新前趋节点，后继节点以及路由表。不过最重要的是后继节点的地址，只要每 个节点都能正确的返回后继节点，那么所有的路由表就都可以被修证，c h o r d 环 就可以趋于稳定。以下我们分别讨论节点的加入，节点加入对查找的影响，节点 失效，节点主动离丌c h o r d 。 2 3 1 节点加入与稳定 为了在c h o r d 节点发生变更时，保障查找能够顺利进行，必须每节点的后继 指针保持适时更新，c h o r d 协议通过周期性的后台调用“稳定”( s t a b i l i z e ) 函数， 使路由表和后继与节点的变化保持一致。 a ，删t 口h 卅c 圳廊墒f b 矗_ 自咖f 钿孵f * 由“睇甜： “c f r e 。d a t e ( ) ，。n j l ；“善翟2 i ：2 ，b ，n 。n ，e 扣“。，。1 ；饿m 配i 梆。= n ：p 强函n e 肼= n ； - 红咖目a 咖汀嘶蝴曲曲甚n 曲w 7l 口f p 州，蠢- i 啦咖 噼一_ 霉f t a b l e 砷f 韶 “j o i n ( n t p c z e d * 舒培抽d 旨矿曲- _ 删填，1 9 盯f t 疗t p 西k s w n i l ； 。f i x d l t a m 0 矗k 墨：o r 赢n 7 碰“峨抖f n ) ；n 州篇h 盯# 十，； 祥( n # 蝌m ) 翻函d ，抽d b 取啊嚣h j 拥_ d 附n 盯f 世j ； 爿硝曲d 撑出小f _ 坤“= j 。堋b 们 h 唰h 科 = 一日5 w 粼州n4 堂群。k h 就a m 吐z 0 ；嚣嚣鬟毫嚣y：舞兰= 燃嚣谪椭。f 幽”拯却埘 爿帕船o r 篁：计0 州d 静脯k sb i i d 嗣阵阳r 啪嘎务l r ，：p 硪b 印l 坩r 罱n i l ： 图2 71 7 点加入与稳定的算法 图2 7 y u 出了节点加入和稳定的伪代码，当节点n 开始加入时，它调n j o i n ( n 1 函数( 其中，参数n 是已知c h o r d 环中的节点) ，或者，调用c r c 砒e ( ) 函数产生一个 新i 拘c h o r d 环。在j o i n ( n ) 函数中请求节点n 查找节点n 的直接后继，此函数并不能 使网络中其他节点知道节点n 的加入。 为了使节点获取新加入节点的信息，每个节点周期性的调用s t a b i l i z e 函数。设 b i t t o r r e n t 系统中p j ：l r 展他的研究 节点n 调用s t a b i l i z e 函数，操作过程如下：请求节点n 的后继给出它的前趋( 令p = n s u c c e s s o r - p r e d e c e s s o r ) ，如果p 是新加入c h o r d 环的节点，那么节点n 令p 作为它的 后继；同时s t a b i l i z e ( ) 函数给后继节点n s u c c e s s o r - - 个通知，向n s u c c e s s o r 宣布它 的前趋节点n 的存在，这样就给n s u c c e s s o r - - 个修改前趋的机会。如果n s u c c e s s o r 知道的节点都l k , n 离自己更远，则n 作为n s u c c e s s o r 的前趋节点。 每节点周期性调用f i x 函数，保证它的路由表适时更新；新节点加入fmgers0 c h o r d 环时，初始化其路由表也是通过这个函数：同时c h o r d 坏上的节点在其路由 表并入新加入的节点地址也是通过这个函数。每个节点的周期调用 c h e c kp r e d e c e s s o r ( ) 函数，检查前趋指针是否有效，如已失效，则令其前趋为空， 以便在n o t i 母( ) 通知到来时，重新指定它的前趋。 举一个简单的例子，设节点n 加入系统，它位于p 与s 之间，即p i d n i d s i d 。 在节点n 调用j o i n ( ) 时，获得s 作为后继，同时，s 收到通知后，令节点n 作为其前趋； 当p 调用s t a b i l i z e ( ) i 函数时，请求节点s 给出它的前趋( 现在为n ) ，随后，p 将节点n 作为其后继。最后，p 通知节点n ，使p 为其前趋。到此为止，所有节点的前趋和 后继皆已更新。在上述过程中，p 一直可同后继指针访问节点s ( 或直接或通过节 点n ) ，并发查找不会被中断。图2 8 说明，节点加入过程，n 2 1 、n 2 6 、n 3 2 分别 对应p 、n 、s ；一旦后继指针被更新后，调用f i n d _ s u c c e s s o r o 将能够找到新加入的 节点。由于新加入的节点并没有被并入其他节点的路由表中，可能使 f i n d _ s u c c e s s o r ( ) 开始没有命中，不过在查找算法的循环过程中，一直沿着后继指 针( f m g e r 1 ) ，将可到达所查找的前趋。最后，函数f i x _ f i n g e r s 将调整路由表中的 指针项，结束线性查找。 n 2 ln 2 l 图2 8 新仃点加入c h o r d 环例 一系列的加入操作后，被s t a b i l i z e ( ) 中断，那么，最后的加入操作后某时刻 荡 矗回 篙 矗圆圈 丢回囹 惮 一回回 b i t t o r r e n t 系统中可扩展性的研究 后继指针将形成一个回环( c y c l e ) 。换句话说，某个时间，每个节点可沿后继指 针访问网络中其他节点。稳定机制能在节点加入c h o r d 环时，保证现有c h o r d 环节点是可访问的，即使遇到并发加入或消息丢失或失序的情况，也能保持网络 的连接性。稳定程序本身并不能纠正系统中存在多个不连结的回环或者使c h o r d 环上的部分节点的形成回环的情况，在一般情况下，一系列节点加入是不可能产 生这种病态的结构，即使出现了病态结构，c h o r d 协议也能通过周期性检查把结 构修复。 2 3 2 节点加入对查找的影响 1 ) 考虑对c h o r d 环的正确性的影响 在节点s t a b i l i z e 完成之前，执行查找操作，可能出现三种结果。第一，最常 见的结果，节点的路由表己经更新，查找经历o ( 1 0 9n ) 次转发后得到正确的后继。 第二，后继指针己更新，但路由表更新没有完成，查找的结果是正确的，但是要 经历更多时间的延迟。最后，局部节点( 发生加入) 操作还没有更新后继指针，或