Maze 一个P2P文件共享系统的设计与实现.doc

北京大学硕士学位论文Maze:一个P2P文件共享系统的设计与实现1绪论31.1Maze项目产生的背景31.2陈霖硕士的相关想法41.3谢欣硕士做出的新颖设计42相关工作52.1节点发现与通讯策略的相关研究52.2文件传输策略的相关研究63Maze的系统结构设计64节点发现与通讯策略84.1分布式认证机制84.2节点登记与节点发现94.3节点间通讯策略95节点发现与通讯策略的改进115.1 社会性的Maze115.2脱离中心服务器正常运行126文件共享与传输策略136.1Maze URL定义与解析136.2目录浏览与索引136.3下载队列和排队队列146.4Maze积分机制和排队算法146.5文件传输协议157文件共享与传输策略的改进157.1资源的索引与检索157.2多点同时下载167.3多点下载的文件分块算法167.4获得镜像下载地址177.5Maze种子机制：动态的镜像下载地址177.6文件内容摘要的提取187.7使用社交网络改进文件共享与下载188系统的可持续发展策略198.1可扩充的协议198.2监控与管理非法资源或不健康资源的共享198.3丰富资源的策略209Maze的程序结构与数据结构219.1各中心服务器及其主要功能219.1.1用户管理服务器219.1.2心跳服务器229.1.3目录收集服务器229.1.4种子服务器239.1.5检索服务器239.2Maze前台界面程序结构249.2.1文件下载功能模块249.2.2节点发现与通讯模块259.2.3本地管理模块259.2.4界面模块259.3Maze后台服务程序结构2610Maze的XML格式通讯协议2710.1用户管理服务器与Peer的通讯协议2710.1.1注册新帐户:2710.1.2申请信用卡2710.1.3更新积点2810.1.4更改密码2810.1.5更改呢称2910.2心跳服务器与Peer的通讯协议2910.2.1登录2910.2.2心跳3010.2.3发送消息3010.2.4随机查找3110.2.5Maze邻居3110.2.6请求资料3210.2.7登记关注名单与定时接收状态3210.2.8惩罚3310.2.9取消惩罚3410.3Peer之间的UDP通讯协议3410.3.1发送消息3410.3.2浏览和下载目录3410.3.3请求详细资料3510.3.4获取外部端口3610.3.5你是谁？3610.4Peer之间的TCP文件传输协议3710.4.1数据包包头格式3710.4.2请求者发送的命令与格式3710.4.3服务者答复的命令与格式3810.4.4一个正常的文件传输逻辑3910.11种子服务器与Peer间的通讯协议3910.11.1上传种子3910.11.2增加镜像链接4010.11.3删除镜像链接4010.11.4获得所有在线镜像4110.12目录收集服务器与Peer的通讯协议4110.12.1上传文件目录4110.12.2更新目录状态4210.13Maze搜索的XML 检索协议4210.13.1天网搜索的CGI与参数4210.13.2天网搜索的XML结果格式4310.14Maze的配置4411比较和总结451 绪论1.1 Maze项目产生的背景根据天网搜索的信息统计，原来基于FTP的网络文件系统已经日益呈现出资源“相对”困乏的局面。FTP站点的总数量已经开始呈现下降趋势，并且绝大部分的FTP站点已经不能匿名访问。下图是我们在2002年10月于天网主页上进行问卷调查的结果统计，可以很明显地看出“下载难”乃是天网文件搜索引擎急待解决的核心问题。图 1 天网文件搜索最迫切需要解决的问题面临如此困境，理所当然，我们应当先分析一下传统FTP服务究竟存在哪些弊端，在当今这个日新月异的信息时代，随着宽带网的普及，上网用户想从网络上获得的不仅是文字、图片、软件等信息，更希望通过各个FTP站点共享和下载更多的用于娱乐和工作学习的多媒体文件，例如DVD视频和mp3音乐。然而多媒体文件相对其他文件来说一般很大，一个普通的DVD文件就要600多M，这必然导致网络流量的大幅度上升，越来越多的上网用户往往在相同的时间段集中访问某些著名的FTP站点，这样传统的FTP协议在处理多用户同时下载大文件的时候就不可避免的表现出了某些弊端。首先，FTP服务器不能承受大量用户同时连接和下载，当超过最大连接数时便会自动拒绝所有超额连接，而传统FTP协议中浏览目录使用的也是这种稳定的TCP连接，因此在服务器超负荷时用户甚至不能浏览目录，这种并非因为错误而产生的拒绝服务导致人们在使用FTP时非常不方便，往往需要人工的多次尝试连接以等待FTP服务器有空闲的连接资源，“登录难”、“下载难”的问题油然而生。其次，由于传统FTP协议并没有定义一个节点发现协议，只有依靠FTP搜索引擎等附加工具来发现已存的FTP站点，这样那些著名的FTP站点由于太多用户访问而经常处于超负荷的状态，而那些虽然含有相同资源的但并不出名的FTP站点却没有承担起分担负载的任务，更没有充分发挥作为一个FTP站点提供资源的作用。在仔细研究了传统FTP协议的这些不足之处以后，我们试图设计出一个更友好的协议，以保证只要网络资源存在就一定能够有效的发现资源，而只要能够看到的资源就一定可以成功下载。经过深刻的研究，我们决定将当前热门的“P2P”技术以及“社交网络”技术相结合以作为节点发现策略，而使用类似BitTorrent的“多点下载”作为文件传输技术的核心，并且通过天网文件搜索引擎提供检索服务，从而给出一个解决上述传统FTP协议“下载难”等问题的方案。我们希望在保持传统FTP风格的文件共享环境和天网搜索环境的前提下，能够系统有效的解决上述问题，并且进一步促进网络资源的丰富。在2002年10月的问卷调查之后，北京大学网络与分布式系统实验室针对天网文件搜索引擎中出现的“下载难”问题展开了广泛的讨论，大家集思广益，产生了数种试图解决该问题的方案，下面将列举其中几个对后来Maze的实现有着深刻影响的方案，这些想法作为Maze的前期讨论与研究，对Maze的最终的功能与算法起着不可忽视的作用。1.2 陈霖硕士的相关想法2002年底，网络实验室的陈霖硕士撰写了一篇“关于天网FTP搜索的思考”的论文，这篇文章对增强文件下载的自动性和可靠性提出了一些很好的想法。他发现在天网搜索中经常出现下面两种情况：a、 某个文件当时不在任何的FTP上，过一段时间可能会出现某一两个FTP上，这种情况用户需要隔几天查询一下，相当不方便，用户希望天网搜索能帮助自动继续查询。b、 FTP服务器拒绝访问、或者由于用户数太多了无法登录。这种情况用户需要反复试好几个并不一定是有效的FTP站点，希望天网文件搜索能够协助找到可以匿名（或者提供密码的）登录的有效FTP站点。而同时，陈霖硕士对检索资料与版权方面有如下考虑：a、 在文件的识别上，或者说在该文件的表述上，我们希望不仅仅得到文件的语法上的表述，更希望得到语义上的表述（用以确定用户需要的确实是这个文件。我们希望得到一种类似于加密系统中文件摘要的东西）。总之，我们需要能有一种方法准确的知道用户想要什么。可是目前觉得似乎没有什么合适的解决之道，我们尽量取与文件最相关的1到3个备份。b、 对于版权的考虑。天网本身不提供文件存放的任何空间，存放空间可以由例如燕星等文件存储系统提供。不过，这样引起的效率的问题需要考虑我们可以有Cache吗？作为补偿，我们生成一些用户，然后让这些用户重复以前用户的比较频繁的请求（用LRU算法或者其他），然后把这些请求所获得的结果放在这些用户的FTP空间。这些新生成的用户的空间与我们的系统之间有充裕的带宽相连，并且这些用户空间将被系统优先考虑。c、 引申2）中的方法，把整个网络看成以大系统，我们将要有FTP系统的稳定性和速度的记录，以取得最好的效率（或者说服务质量）综上所述，陈霖硕士认为网格技术可能是解决问题的比较好的方案，因为文件共享存在高性能计算的需求和无缝服务的需求，而我们要做的事情与信息网格颇为相似，也与宣称一体化服务、一站式服务的服务网格有同样的思路。他希望北大天网能够成为一个网格门户。1.3 谢欣硕士做出的新颖设计基于前面的讨论和设想，2003年初，网络实验室谢欣硕士在他的公开进展报告中提出了“天网人”项目。这个项目设计在处理资源不足的方面提出了基于货币交易的共享网络的思路来鼓励资源的共享。天网人项目为了实现三个目标：一、 增加资源数量a、 强制命令每个用户安装一个FTP服务器b、 构建基于交易的共享网络，采用自由定价，自由贸易的市场经济原则二、 提高服务质量a、 自动提前文件摘要，识别相同文件b、 提高服务的可靠性，保证宕机时的交易正常进行。c、 加强用户参与，降低用户加入门槛三、 最终目标：实现基于货币交易、强调用户参与的文件共享网络（不仅仅是搜索引擎）2 相关工作目前实现文件共享的系统相当多，主要有以传统C/S结构为基础的共享系统，如FTP、星空UFTP等等，以及以P2P结构为基础的共享系统，如Napster，Gnutella, Kaza, BitTorrent, PP点点通，百宝箱等等。不同类型文件共享系统的主要技术区别在于它们的节点发现与通信策略和它们的文件共享与传输策略。2.1 节点发现与通讯策略的相关研究传统FTP协议中并没有提供节点发现的算法，一般只是采用口头宣传或者网页链接的方式发布FTP站点。对于FTP服务器是否在线只有FTP搜索引擎可能会进行检测，如天网FTP搜索引擎就对其搜集范围内的FTP站点是否在线、是否可以匿名下载进行检测。但是这些外部的检测不能过于频繁的进行，否则便会影响FTP服务器的正常运行，所以这种检测结果往往并不精准。P2P系统是当前非常受欢迎的网络系统1。根据拓扑结构P2P系统主要有两种。一种是混合型P2P系统，比如P2P的鼻祖Napster，之所以说它是混合型是因为它还存在集中式的服务器用于发现peer。还有一种就是纯P2P的系统，典型有Gnutella系统，它没有服务器，节点的发现只是依靠Peer间消息的广播。总之，各种P2P系统解决的方案各不相同，有的采用中心服务器的方式，有的采用某种复杂路由的方式。在上个世纪60年代，美国一位著名社会心理学家米尔格伦(Stanley Milgram)提出了“六度分隔”(Six Degrees of Separation)的理论，并设计了一个连锁信的实验来验证这个假设。这个理论认为，任何两个陌生人都可以通过“朋友的朋友”建立联系，并且他们之间所间隔的人不会超过六个。也就是说，最多通过六个人你就能够认识任何一个陌生人。这也就是著名的“小世界假设”。从2001年秋天开始，美国哥伦比亚大学的社会学教授瓦特斯(Duncan Watts)组建了一个研究小组，根据米尔格伦的假设，利用Email这一现代通信工具，开始进行“小世界假设”的实验20。在1年多时间里，总共有166个国家和地区的6万多名志愿者参与实验，实验结果证明，一封邮件平均被转发6次，即可回到接收者那里。基于六度分隔理论设计的实现了连接“朋友的朋友”的软件被称为社交网络软件（Social network Software）。社交网络模型可以协助P2P网络中的节点发现。对于社交网络软件的定义有很多，如“个人带着软件成为社会网络的一部分” 或 “是帮助人们建立社会网络和自动组织群体的软件” 或 “关注软件使用过程中建立的群体联系超过对软件技术的关注”等等。社交网络软件按其所体现和促进社会关系网络形成不同形式可以分为显性社交网络软件和隐性社交网络软件。显性社交网络软件在功能上是直接促进某种程度人际互联关系的构建和发展。而隐性社交网络软件则是在完成软件某种功能的过程中促进了人际关系的互联和建设。另外社交网络软件按其应用指向性，我们还可以将其分为即时通讯类和基于某种任务应用的社交网络软件。著名SS理论家毛向辉先生将社交网络软件的功能分为核心四层7，就是Identity（身份）、Portfolio（档案）、Communication（交流）、Social Network（应用社会关系）。在不同的社交网络软件中，这四者的体现和侧重的程度不一样。Identity是个人的身份标识，这很容易理解，就是要有个人的账号；而Portfolio则是电子档案的意思，是对个人体身份可信度的记录或描述。从某种意义说Identity是网络上数字符号的个体代表，而Portfolio则是实际存在的个体见证，像BLOG具有类似Portfolio的功能。Communication标识和实现了在社交网络软件中人际之间可能有的互动形式和通道，Social network则是从总体上展现了以个体为出发点、以应用为体现、所形成的社会网络应用结构。2.2 文件传输策略的相关研究1971年，第一个FTP（File Transfer Protocol）的RFC(RFC 114)由A.K. Bhushan在1971年提出，同时由MIT与Harvard实验实现。1985年，一个作用持续至今的官方文档RFC 959(STD 9)出台。FTP协议乃是Internet文件传送的基础。通过该协议，用户可以从一个Internet主机向另一个Internet主机拷贝文件，实现了因特网上文件的共享。与大多数Internet服务一样，FTP也是一个客户机/服务器系统。用户通过一个支持FTP协议的客户机程序，连接到在远程主机上的FTP服务器程序，通过客户机程序向服务器程序发出命令，服务器程序执行用户所发出的命令，并将执行的结果返回到客户机。比如说，用户发出一条命令，要求服务器向用户传送某一个文件的一份拷贝，服务器会响应这条命令，将指定文件送至用户的机器上。客户机程序代表用户接收到这个文件，将其存放在用户目录中。在FTP的使用当中，用户经常遇到两个概念：“下载”（Download）和“上载”（Upload）。“下载”文件就是从远程主机拷贝文件至自己的计算机上；“上载”文件就是将文件从自己的计算机中拷贝至远程主机上。用Internet语言来说，用户可通过客户机程序向（从）远程主机上载（下载）文件。BitTorrent下载(俗称BT下载) 是目前比较流行的peer-to-peer下载软件。BT的原理是BT首先在上传者端把一个文件分成了Z个部分，甲在服务器随机下载了第N各部分，乙在服务器随机下载了第M个部分，这样甲的BT就会根据情况到乙的电脑上去拿乙已经下载好的M部分，乙的BT就会根据情况去到甲的电脑上去拿甲已经下载好的N部分，这样就不但减轻了服务器端得负荷，也加快了用户方(甲乙)的下载速度，效率也提高了，而且，在你下载的同时，你也在上传(别人从你的电脑上拿那个文件的某个部分)，所以说在享受别人提供的下载的同时，你也在贡献。3 Maze的系统结构设计经过长期的研究，综合多个讨论与建议，我们认为Maze系统至少应该包含以下几个主要功能：l 支持即时通讯和BBS (类似QQ)l 支持跨防火墙的文件共享与下载l 支持在线资源搜索和文件目录视图l 支持多点下载和断点续传(类似BitTorrent)l 基于积点的资源交易体系l 采用社交网络的网络链接关系为了实现上述各个功能，我们设计了如下的体系结构：图2 Maze的系统结构图在设计的具体操作过程中，我们觉察到纯P2P系统在发现局域网内部节点方面，对用户共享资源的管理方面以及全局搜索方面都有不同程度的缺陷，因此，经过综合的考虑，我们将Maze设计成为一种混合型的P2P系统。在Maze系统中的每个Peer就相当于一个传统FTP服务器和FTP客户端的结合体。整个系统除了多个Peer外，还包括集中式的用户、目录、检索、心跳还有种子服务器。用户管理服务器实现用户注册与身份认证。目录收集服务器负责收集每个peer的共享的目录列表到集中的数据库。检索服务器读取目录数据库为所有Peer的文件目录建立索引并提供XML接口的检索服务。心跳服务器负责维护在线用户的列表。每个在线的Peer每隔几秒就通知心跳服务器“我还在线”，这也就是我们将之命名为“心跳”的意义。同时每个Peer每隔一段时间就把自己的目录信息在Maze的目录收集服务器上更新。检索服务器定期重新建立索引，并由心跳服务器提供的在线状态只显示在线用户的文件检索结果。种子服务器是为模仿BitTorrent机制建立的Maze种子提供保存与更新的服务器。在检索服务器方面，我们采用天网文件搜索来为Maze提供在线文件检索服务。天网文件搜索引擎是北京大学网络与分布式系统实验室从1999年开始的一个大型项目，系统运行稳定，索引数千万文件，每天都有数十万用户使用，这个系统不仅仅可以检索ftp文件，还有多种接口来检索其他协议的文件列表，例如http上的文件、局域网共享的文件等等，同时它还提供了XML的检索接口，以便二次开发使用。Maze系统采用了天网文件搜索这样一种成熟的检索技术来提供检索服务，使得检索效果和天网文件搜索引擎一样既快又准。基于这个体系架构，我们设计了一系列的策略来解决上述当前许多文件共享系统存在的各种各样的问题，主要有如下策略：a、 Peer节点的发现与通讯策略：包括节点的身份认证和任意两个节点间的通讯策略。b、 文件共享与传输策略：包括资源目录的浏览和确保资源可下载的策略。c、 系统可持续发展的策略：包含非法资源的管理与促进资源丰富的策略。4 节点发现与通讯策略4.1 分布式认证机制由于每个Peer都要同时与多个服务器通讯，我们采用了一种类似信用卡机制的分布式认证算法，来确保用户身份认证的安全性和有效性。参考Kerberos机制，我们有信用卡发放机构(TGS: Ticket Grant Server)，称之为用户管理服务器，由它进行用户注册和发放信用卡。用户持有效的信用卡访问其他的服务器，其他的服务器检查信用卡上的数字签名来验证身份，判断是否允许进行某项操作。一个正常的从注册到登录的流程如下：图3 分布式认证机制1. Peer首先登录到用户管理服务器，申请一个Maze UID账号，申请时把登录密码保存在用户管理服务器上。2. 账户申请完毕之后，Peer向用户管理服务器请求这个Maze账户的身份认证数据包，同时提交自己的Maze服务端口、自己看到的本地IP地址。3. 用户管理服务器在身份认证数据包中记录Peer的Maze UID、从用户管理服务器看到的外部IP、Maze服务端口、是否在局域网内（根据Peer提交的自己看到本地IP和心跳服务器看到Peer的外部IP是否一致判断）、用户级别、信用卡失效时间等信息，用系统签名私钥密码对数据包进行数字签名，把整个数据包和其数字签名（我们把它称之为信用卡）用Peer的登录密码进行加密，把加密后的证书返回给Peer。整个算法可以用下列公式表示：Certificate = Maze ID + IPoutside + Portservice + InGatewayOrNo + Level + ExpireTime Ticket = Certificate + Sign system-private-key (Certificate)EncryptedTicket = Ecrypt peer-password (Ticket)4. 如果用户在Peer端有正确的登录密码，就可以把加密的数据包解密，从而获得有数字签名的信用卡。Ticket = Decrypt peer-password (EncryptedTicket)5. 当Peer需要访问其他的服务器（如心跳服务器等）时，出示这个信用卡，服务器用系统签名公钥密码检查数字签名是否正确，以及是否已经过期，如果检查失败，要求Peer重新申请新的信用卡，否则允许下一步操作，也就是登录成功。这种基于信用卡机制的分布式身份认证算法，可以保证用户密码只在注册初期出现，此后并不在网上明文传送；系统签名密码则只在用户管理服务器上出现，因而从客户端很难破解，这些方法都保证了用户身份认证的安全性。4.2 节点登记与节点发现Peer持有效的信用卡，在心跳服务器上登记。Peer与心跳服务器的通讯采用UDP协议。只有当心跳服务器要求Peer提交信用卡时才需要提交信用卡，心跳服务器收到有效的信用卡后记录这个客户的来源IP地址，以后来自相同IP的相同Maze账户的用户请求都当作是合法的。Peer定期向心跳服务器登记在线状态（发送心跳包），包括该Peer上正在排队的人数等信息。心跳服务器把所有用户的在线状态定期发送到检索服务器，检索服务器由此过滤掉离线用户的检索结果，使得所有的检索结果都是在线的。为了获得好友的在线状态，Peer可以向心跳服务器登记一批关注用户名单，心跳服务器定期把这批用户的在线状态发给Peer。心跳服务器还提供在线用户的检索功能，可以随机给出一批在线用户列表或者给出与请求Peer邻近的Peer列表（也就是Maze上非常受欢迎的“Maze邻居”功能）。4.3 节点间通讯策略为了使任意两个Peer之间都可以通讯，心跳服务器实现了通用的消息转发机制。它为每个在线Peer维护一个消息队列。有任何消息发到心跳服务器后，心跳服务器就给该消息一个序号，并将其放到接收者的消息队列，然后向接收者发送出去。接收者在收到该消息之后，反馈收到的序号，心跳服务器就把这条消息从接受者的消息队列中删除，否则心跳服务器将每次在接收者的心跳包到达时都把消息队列中的消息发送给接收者，直到接收者下线为止。而当接收者下线时，检查其消息队列，如果还有消息没有发送出去而且该消息的类型值得保留，则自动使用数据库把这些消息保存下来，在接收者下次上线的时候，重新取出这些消息放到其消息队列中，由此实现离线消息的支持。虽然，通过心跳服务器可以完成所有的节点间通讯，但是为了减轻心跳服务器的负担，我们用了多种策略来实现Peer to Peer之间的直接通讯。Peer可以向心跳服务器请求其他节点的地址信息，包括外部IP地址、Maze服务端口、是否在局域网内等。考虑多种不同类型的网络情况，Maze设计了不同的策略来实现Peer to Peer的通讯：第一种情况：当对方节点不在局域网内，则Peer可以由对方的IP地址和Maze服务端口，无论用户本身是否在局域网内都可以与之直接通讯。但是如果对方节点在局域网内时，我们就需要一些特殊的技术来实现点对点的直接通讯。第二种情况：当对方节点的外部IP与自己的外部IP相同时，也就是说两个Peer处于同一局域网内或同一台计算机上时，可以利用对方的内部地址与之直接通讯。我们采用心跳服务器现有的通讯机制向对方节点发送一个反向连接请求包“passive connect”，里面包含自己的内部IP地址和端口以及一个反向连接序列号。对方节点从心跳服务器取得这个消息包后，直接向这个包里包含的地址发送一个连接包，包含自己的Maze 账户和连接序列号。根据连接序列号我们可以获得一个合法的对方节点的内部IP和内部端口地址。由于双方都在同一局域网或同一台计算机内，因而后续的通讯都可以直接进行了。图4 节点间通讯策略第三种情况，当对方节点的外部IP与自己节点的外部IP不同时，如果自己节点的外部IP地址与自己本机的IP地址相同，说明自己处于局域网外。为了从局域网外与局域网内的建立直接的连接，需要令局域网内节点主动发起一个向外的连接。我们采用类似第二种情况的办法，通过心跳服务器发送一个反向连接请求包“passive connect”，里面包含自己的IP地址和端口以及一个反向连接序列号。对方节点从心跳服务器取得这个消息包后，直接向这个包里包含的地址发送一个反向连接包，包含自己的Maze 账户和反向连接序列号。根据反向连接序列号我们可以获得一个合法的对方节点的外部IP和外部地址。对于UDP通讯，取得局域网内节点的外部IP与外部端口之后，就可以采用定时消息的模式保持一条虚拟的UDP通路。传送文件时，我们可能需要稳定的TCP/IP链路，也用相同的办法令局域网内部节点向外部发起一个TCP连接，在连接建立之后就可以进行文件传输了，这类似于FTP协议的Passive模式。第四种情况，当对方节点和自己节点都处于局域网内又不是在同一个局域网内时，唯一的通讯策略是通过一个中间代理服务器转发。对于普通的消息通讯，可以直接利用心跳服务器线程的通讯机制实现，对于文件传输，必须依赖在局域网外的某个节点中作为中间代理服务器。心跳服务器挑选一个临近请求者的有独立IP地址的用户作为中间代理服务器，请求者向中间代理服务器建立TCP连接并获得一个隧道号，请求者通过心跳服务器转发消息把隧道号告诉接收者，接收者也向中间代理服务器建立TCP连接并提交隧道号。两个局域网内的节点通过上述方式与中间代理服务器建立一条稳定的TCP连接，中间代理服务器作为一个代理，把数据包来回转发。由于中间代理模式比较复杂，Maze暂时没有实现，但保留了扩展接口，目前采用心跳服务器转发的机制来实现相关功能。这样，网络中的任意两个节点之间都可以实现稳定的比较直接的通讯链路了。5 节点发现与通讯策略的改进5.1 社会性的Maze 从社交网络软件的定义来看，文件共享者之间的关系类似于社交网络，具有社交网络的一些共性。比如文件收藏者A由于其个人的兴趣爱好，他经常访问的站点（假设为B,C,D等）将是一个有限的范围，如果由A到他经常访问的站点B,C,D建立一条链接，则其他用户在A处可以看到的文件以及它们的同类文件，应该也就可以在B,C,D中找到。Diego Doval从图论的角度证明了社交网络是可以自动聚集的8。根据这个假设，我们可以在两个方面改进文件共享的技术：I. 一个软件可以从更多的点上同时下载，从而提高下载的速度。由于A的软件很大可能性在B,C,D上存在备份，因而向A发起的下载请求可以分发到B,C,D中，从而找到更多的镜像下载地址。II. 可以找到更多同类软件。由于A经常访问B,C,D，因而B,C,D中应该包含了A收藏的某类软件的大部分乃至更多。这样访问A的用户可以也去看看B,C,D以便发现更多和A收藏的软件类似的软件。由此，我们改进了Maze的节点发现策略，以实现上述两项功能。从前文可以看到，Maze已经实现了有保障的节点间通讯策略，因而，只需要在这个通讯链路上增加新的协议即可。我们在原有通讯协议上增加了请求好友列表和答复好友列表的协议。答复好友列表的消息中，包含了自己所有的好友以及这些好友的资料信息以及上次好友在线时的IP地址和端口。这样，在请求端就可以以树状形成一个好友网络视图，如图5所示。同时，请求端可以把这些“朋友的朋友”当作是自己的朋友，向系统请求这些朋友的资料，进行聊天、浏览目录、下载文件等等。也可以继续展开，获得“朋友的朋友的朋友”，展开的层数在Maze中没有限制。图5 Maze的社交网络5.2 脱离中心服务器正常运行和所有的混和型P2P一样，原先的Maze体系结构存在一个重大的缺陷，就是有中心服务器这一概念，存在单一服务器瓶颈。尤其是心跳服务器，当心跳服务器崩溃或者网络中断时，所有的Peer都将无法正常使用。但是，在Maze增加社交网络软件的特性之后，我们发现了一种可以实现Maze永远可用的模式。在设计中，我们除了实现依赖中心服务器的节点间通讯外，还实现了直接的点对点通讯协议，因为Maze已经在某个时刻获得了好友的IP地址（也就是在中心服务器存活的阶段获得的），所以即使中心服务器不能提供服务，Peer主动连接对方也是可行的。也就是说，Maze依靠缓存的某个节点的IP地址，连接到这个节点，获得这个节点的好友列表，从而得到更多节点的IP地址，从而可以连接到更多节点，实现了脱离中心服务器运行。图 6. 社会性P2P中的节点发现策略在实现上，为了保证所连接的IP地址的节点就是我们本来已知的节点（因为如果对方采用动态IP地址，有可能两个节点对换了IP），我们采用“你是谁”的发现机制，给对应IP地址发送“你是谁”的包，由对方反馈“我是谁”。如果收到一个“我是谁”的包，根据来源UID是否是自己的好友，如果是就把这个好友的状态标志为在线。反过来，当一个节点收到“你是谁”的包时，也可以判断来源UID是否是自己的好友来判断好友在线。这样就可以获得当前已知节点中谁在线谁离线了。既然可以点对点获得对方的状态，当然点对点的通讯也就可以建立起来了。当Maze的社交网络展开时，由于可以由点对点通讯取到好友的好友的地址列表，按照上述办法就可以与好友的好友建立直接联系。但是，这种脱离中心服务器判断好友在线的办法有一个缺陷，就是当双方处于不同的局域网内的时候，双方都没有办法向对方主动建立连接，这样也就无从知道对方是否在线，更不用说点对点通讯了。但这是有解决办法的，只要双方有一个共同的好友，并且这个好友有独立IP地址而且在线，则双方都可以到这个独立IP的好友处登记状态，也可以从这个独立IP好友里面获得对方的在线状态。这样，这个独立IP的好友承担起了这两个在不同局域网的节点的通讯转接责任。而根据前述的不同局域网节点建立连接的策略（4.3），在无中心服务器的情况下，处于不同局域网内的两个节点也是可以建立一条稳定的通路的。如图6所示。Maze脱离中心服务器运行的前提是中心服务器曾经正常工作过，否则最初的节点发现就难于实现。这样，即使中心服务器的崩溃或者网络中断，在一个连通网络内的节点间仍然可以正常通讯，正常的共享文件，不再受到局限。6 文件共享与传输策略6.1 Maze URL定义与解析为了方便用户访问Maze系统所共享的文件，我们采用了类似标准URL风格的Maze URL。Maze URL以maze:/开头，以Maze UID作为主机名，之后为虚拟路径。例如：maze:/000022/电影/无间道A.rm在有了Maze URL的定义后，天网文件搜索引擎为Maze提供的检索功能就可以如同以往的FTP一样，在网页上提供显式的下载链接。而且Maze在Windows注册表中注册了Maze协议，只要用户点击网页链接或者在IE地址栏输入Maze URL地址就可以直接驱动Maze客户端进行文件下载或目录浏览。同时，为了支持脱离中心服务器运行Maze，并方便用户直接访问熟悉的Maze服务器，Maze URL定义了maze:/IP地址/虚拟路径 的传统风格的URL(如maze:/4/)，对这样的URL，Maze首先向该IP地址发送”你是谁”数据包，根据对方回答的”我是谁”数据包来获得对方的Maze UID，然后把URL转化成标准的Maze URL，即maze:/UID/路径 的风格。在用户访问这种URL的时候，由于此UID对应的IP地址是已知的，后续的访问就与正常访问一样。6.2 目录浏览与索引我们采用上述的节点间通讯策略来实现UDP包的传送，并使用超时重发的机制来处理UDP包丢失的问题。节点的目录浏览其实就是一种特殊的消息包。请求者发送要浏览的Maze URL，接收者把对应目录下的文件列表信息进行打包。每个文件的信息包括用户ID、文件名、文件路径、文件类型、文件大小、文件上次修改时间、MD5码和一些附加信息等。所有文件的文件信息组装成多个XML包，但是每个包的大小不可以超过6K，因为可以穿越网关的UDP数据包不能太大。请求者把收到的文件列表信息在界面上用列表视图显示出来，并采用Windows系统的图标和类型说明标志它，使得远程的Maze文件如同本机文件一样，让用户用起来更为习惯方便。每个Peer有一个后台线程定时上传本机共享的文件目录到目录收集服务器。上传的数据包结构与目录浏览看到的数据包结构完全一样，只是递归包含了所有共享的文件和目录。目录服务收到上传的XML信息后进行解析，并加入到数据库中。在上传过程中，Peer计算每个目录的总大小及其MD5值并缓存到硬盘上，这样当其他Peer浏览目录时，子目录的大小和MD5就不需要即时计算，而是可以即刻得到。目录收集服务器定时调用天网文件搜索的索引程序为所有收集到的目录信息建立倒排索引3。6.3 下载队列和排队队列用户可以设置Maze文件服务可同时接受下载的最大连接数目。当其他节点希望下载这个节点的文件时，首先必须采用前面所叙述的节点间通讯策略向对方请求一个排队位置，服务端的Peer检查当前正在下载的连接数是否超过最大连接数目，如果没有，则返回排队号0，并把请求Peer的Maze UID放入下载队列中；如果超过，则将这个Maze UID放入排队队列，返回排队位置和整个队列的长度。服务端的Peer定期更新排队队列，通知所有正在排队的用户他当前所在排队队列的位置以及整个队列的长度。当Peer排队位置变为0 时，说明可以下载，此时即可以建立稳定的TCP连接，进行文件传输。图7 排队下载6.4 Maze积分机制和排队算法在Maze系统中，为了促进更多的人共享更多的资源，我们希望给贡献大量资源的人更高的下载权限，因而我们引入了Maze积点和Maze星级的概念，并采用了优先级队列的方式组织排队队列。每个Peer的Maze积点以其被下载的总大小减去这个Peer下载的总大小计算，以兆为单位，每兆算作一个Maze元。Maze的星级则是按Maze积点计算，由Maze积点是2的多少次方减去11作为星级，例如2048元以下为0级，4096元以下为1级，8192元以下为2级，依次类推，一直到1048576元为9级，相当于这个Peer被其他Peer下载了1T的文件。如下公式：Account(x) = Account(x) - Download(x) + Upload(x)Level(x) = Account(x) 11Peer在积点改动比较大或一定时间后向用户管理服务器更新自己的积点变化（更改时需要携带自己的信用卡并对更改的数据进行加密）。在Peer每次更新信用卡时从数据库取出当前积点，计算星级，保存在信用卡中。当一个Peer下载其他Peer的文件时，对方将向心跳服务器请求来源节点的信息，其中包括了来源节点的星级。我们规定星级较高的用户有一定的排队优先权。优先算法如下：当节点进入排队队列时，从原来的队列末尾开始，跳过所有的星级比这个节点低且入队的时间与当前时间的差少于星级差(单位分钟)的节点，然后再插入队列。因而，如果一个2星的用户已经排了2分钟队，当一个5星的用户来时，5星用户可以直接插入到这个2星用户的前面，因为 5-22。 这样，星级较高的用户在下载文件时，排队时间将远远少于星级较低的用户，要想获得更高的下载权限，就必须共享更多的资源，这样由此促进了更多的人提供更多的资源共享。每次Maze给心跳服务器发送状态包时，都携带了当前排队队列的长度，因而在检索的结果信息中就可以反映出来，用户可以从检索结果中挑选排队队列最短的进行下载。6.5 文件传输协议进入下载队列的Peer可以向提供文件服务的Peer建立TCP连接。如果自己在局域网外，对方在局域网内，则需要采用我们前述的反向连接策略。如果双方都在局域网内，则需要选择中间代理服务器进行连接。在连接建立之后，请求者向对方提交自己的用户信息，包括Maze UID和允许连接的一个校验码。接收方检查该UID是否已经在下载队列中且提交的校验码是否是该UID进入下载队列时分配的校验码。通过身份验证后，请求者发送文件大小请求包，提交要下载的文件的虚拟路径。接收者根据虚拟路径计算实际的物理路径，判断文件是否存在，如果不存在，返回错误，否则返回文件大小。获得文件大小后，请求者可以请求文件的某些块。因为Maze支持多点下载，一条链接可能只是为了下载整个文件中的某一小块。请求者根据文件大小分配当前此条链接应该下载的文件块起始位置和文件块数。接收者答复这些文件块的内容。请求者每次只请求很少的块以便可以在请求端动态调配各个下载链接的任务，例如可以让下载速度快的链接承担更多的块下载任务。当需要传输的所有文件块都传输完毕时，请求者断开TCP链接。接收者把请求者的UID从下载队列取出放入一个缓存队列，然后取出排队队列头部的排队者进入下载队列。7 文件共享与传输策略的改进7.1 资源的索引与检索我们使用了天网文件搜索索引与检索的程序来为Maze提供检索服务，有关天网文件搜索的具体实现技术可以参考我们的相关论文2。Maze目录收集服务器搜集各个Peer的目录，建立倒排索引文件 天网文件搜索服务器CGI程序接收查询请求，返回XML结果用户检索服务器Maze心跳服务器各个Peer的在线状态图8 Maze与天网文件搜索的集成7.2 多点同时下载经过统计发现，教育网上各个站点共享的资源有很大的重复度，一般情况下，相同的资源可能会在很多站点上存在。针对这个特点我们在Maze中采用了多点并行下载的策略，即用户下载资源时可以从拥有相同资源的多个Peer上同时排队下载同一个资源。具体方法如下：请求方在下载文件之前先把文件分成多块，然后给所有含有该文件的站点（在检索结果中或后面叙述的Maze种子中可以获得这个列表）发出下载请求。由于可能某些站点的下载队列已经满了，必须排队等待进入下载队列，因而只对排队完成的站点分配下载文件的任务。每个站点分别提供该文件的某些部分，最后请求方根据服务者返回的数据把各个块整合成一个整体。当整个文件都下载完毕时，如果还有站点还处于排队状态中，必须发送退出排队命令，以减轻该站点的负担。这样，请求方可以同时从多个站点获取数据，并且每个站点也只需传输文件的一部分，达到了加快下载速度和减轻站点负担的目的。另外，由于写磁盘和网络传输是下载资源时的两个瓶颈，为了减少代价，我们采用了网络下载与文件读写并行处理的策略，网络下载采用异步Socket，文件读写也采用异步文件操作函数，请求方向文件中写入第k块数据的同时正从网络上下载第k+1块数据。同理，提供文件下载的站点在读第k+1块数据的同时也正在传输地k块数据。如图9所示，电影“指环王”同时从六个镜像站点下载，其中三个已经排队完毕，正在传输文件块，同时还有3个站点处于排队状态中。图9 多点下载示意图7.3 多点下载的文件分块算法从多个Peer同时下载一个文件，其中非常关键就是文件分块算法。把一个文件分成多个块，并按照某种算法使得某些块由某些Peer提供，并且要求速度越快的节点提供的块越多。我们把块大小固定，顺序十块十块地发送下载请求，当不足十块时取剩下的块数。当全部块的下载请求都发送完毕后，再顺序检查所有的块，看看有没有某些块的数据并没有收到（可能网络错误或者校验错误导致块丢失，或者某个服务者中途离线导致向这个服务者发送的所有请求全部丢失），对这些零星的块单独请求。直到所有的块数据都取得后，才算文件下载完毕。当某个已经建立好的TCP链接发送队列空闲时，由回调Socket主动调用块分配算法，因而发送速度块的链接在整个传输过程中就可以承担更多的下载任务，从而保证整体的传输速度和连接利用率。7.4 获得镜像下载地址要实现多点下载，就必须获得一个文件的多个镜像下载地址。在Maze的检索结果中，究竟哪些地址对应同一文件，需要一个判断文件完全相同的算法。仅仅从文件名和文件的大小作判断是不够的，因为重名而且文件大小相同对于小文件来说是很平常的事，比如Setup.ini文件大小相同的概论很高。Maze系统采用的方法是MD5加大小，而没有使用文件名。MD5是非常好的对文件内容的一种“压缩”方法。如果大小和MD5都相同我们认为两个文件是相同的。没有采用文件名的原因是有些情况下文件名不同有可能是相同的文件，比如“英雄1.rm”和“英雄a.rm”尽管名字不同但是内容可能是相同的。当然大小和MD5都相同但是不是同一个文件的情况是有可能发生的，但是这种情况的概率非常得小。我们采用天网文件搜索引擎来发现相同的资源镜像地址列表，把检索结果集中文件大小相同且MD5也相同的记录当作是同一文件的不同镜像下载地址。在下载时，为了防止某些用户在系统记录MD5后又修改了文件，需要文件服务端在答复下载请求时，返回文件的大小，请求端根据文件大小再判断一次是否是同一文件。如图10所示，六个文件名不尽相同的URL地址在Maze中当作是同一文件“指环王3”的多个镜像地址。图10 文件名不同的地址作为同一文件的多个镜像文件的MD5码的计算是这样的。对于小于4M的文件我们计算全部文件内容的MD5，如果文件的大小大于4M我们从文件的头、尾和中间内容各取1M用于MD5码的计算。我们这样做的目的是为了减少大文件的MD5计算的时间。对于目录的MD5，我们采用的方法是计算该目录下所有文件的MD5值全部异或再加上该目录下的文件个数。我们计算目录的MD5是在目录结构上传到目录收集服务器的时候进行的，这样可以降低浏览目录时实时计算目录MD5带来的开销。由于目录MD5的存在，我们可以判断两个目录是否是相同的，因而也就可以同时从两个以上的站点同时下载一个目录，以便加快目录下载的速度。7.5 Maze种子机制：动态的镜像下载地址BitTorrent是当前比较流行的下载软件，它的思想简单说来就是记录一个文件块可能的所有镜像下载地址，当下载者请求这个文件块时，下载者可以从镜像地址中挑选下载，同时，下载者已下载的文件块也可以作为镜像为其他用户提供服务。Maze采用这种思想设计了Maze种子机制。与BitTorrent不同的时，Maze种子以文件作为单位，而不是以文件块作为单位。Maze用户可以创建Maze种子，种子是一个XML格式的文件，里面包含了种子的名称、大小、创建者、描述。种子被登记到Maze种子服务器中，Maze种子服务器为每一个种子维护一个镜像下载地址表。新创建的种子创建时至少包含一个有效下载地址。当用户双击打开一个种子时，Maze客户端请求Maze种子服务器以获得这个种子的多个有效下载地址列