北京大学硕士学位论文

北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 1 绪论 3 1.1 Maze 项目产生的背景.3 1.2 陈霖硕士的相关想法.4 1.3 谢欣硕士做出的新颖设计.4 2 相关工作 5 2.1 节点发现与通讯策略的相关研究.5 2.2 文件传输策略的相关研究.6 3 Maze 的系统结构设计.6 4 节点发现与通讯策略.8 4.1 分布式认证机制.8 4.2 节点登记与节点发现.9 4.3 节点间通讯策略.9 5 节点发现与通讯策略的改进.11 5.1 社会性的 Maze.11 5.2 脱离中心服务器正常运行.12 6 文件共享与传输策略.13 6.1 Maze URL 定义与解析13 6.2 目录浏览与索引.13 6.3 下载队列和排队队列.14 6.4 Maze 积分机制和排队算法.14 6.5 文件传输协议.15 7 文件共享与传输策略的改进.15 7.1 资源的索引与检索.15 7.2 多点同时下载.16 7.3 多点下载的文件分块算法.16 7.4 获得镜像下载地址.17 7.5 Maze 种子机制：动态的镜像下载地址.17 7.6 文件内容摘要的提取.18 7.7 使用社交网络改进文件共享与下载.18 8 系统的可持续发展策略.19 8.1 可扩充的协议.19 8.2 监控与管理非法资源或不健康资源的共享.19 8.3 丰富资源的策略.20 9 Maze 的程序结构与数据结构.21 9.1 各中心服务器及其主要功能.21 9.1.1 用户管理服务器.21 9.1.2 心跳服务器.22 9.1.3 目录收集服务器.22 9.1.4 种子服务器.23 9.1.5 检索服务器.23 9.2 Maze 前台界面程序结构.24 9.2.1 文件下载功能模块.24 9.2.2 节点发现与通讯模块.25 9.2.3 本地管理模块.25 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 2 9.2.4 界面模块.25 9.3 Maze 后台服务程序结构.26 10 Maze 的 XML 格式通讯协议27 10.1 用户管理服务器与 Peer 的通讯协议27 10.1.1 注册新帐户:27 10.1.2 申请信用卡.27 10.1.3 更新积点.28 10.1.4 更改密码.28 10.1.5 更改呢称.29 10.2 心跳服务器与 Peer 的通讯协议29 10.2.1 登录.29 10.2.2 心跳.30 10.2.3 发送消息.30 10.2.4 随机查找.31 10.2.5 Maze 邻居.31 10.2.6 请求资料.32 10.2.7 登记关注名单与定时接收状态.32 10.2.8 惩罚.33 10.2.9 取消惩罚.34 10.3 Peer 之间的 UDP 通讯协议.34 10.3.1 发送消息.34 10.3.2 浏览和下载目录.34 10.3.3 请求详细资料.35 10.3.4 获取外部端口.36 10.3.5 你是谁？.36 10.4 Peer 之间的 TCP 文件传输协议 .37 10.4.1 数据包包头格式.37 10.4.2 请求者发送的命令与格式.37 10.4.3 服务者答复的命令与格式.38 10.4.4 一个正常的文件传输逻辑.39 10.11 种子服务器与 Peer 间的通讯协议39 10.11.1 上传种子39 10.11.2 增加镜像链接40 10.11.3 删除镜像链接40 10.11.4 获得所有在线镜像41 10.12 目录收集服务器与 Peer 的通讯协议41 10.12.1 上传文件目录41 10.12.2 更新目录状态42 10.13 Maze 搜索的 XML 检索协议.42 10.13.1 天网搜索的 CGI 与参数.42 10.13.2 天网搜索的 XML 结果格式.43 10.14 Maze 的配置.44 11 比较和总结 45 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 3 1 绪论绪论 1.1 Maze 项目产生的背景项目产生的背景 根据天网搜索的信息统计， 原来基于 FTP 的网络文件系统已经日益呈现出资源 “相对” 困乏的局面。 FTP 站点的总数量已经开始呈现下降趋势， 并且绝大部分的 FTP 站点已经不 能匿名访问。下图是我们在 2002 年 10 月于天网主页上进行问卷调查的结果统计，可以很 明显地看出“下载难”乃是天网文件搜索引擎急待解决的核心问题。 36.3% 14.8% 14.8% 10.2%9.6% 8.0% 6.5% 0.0% 5.0% 10.0% 15.0% 20.0% 25.0% 30.0% 35.0% 40.0% 下载难 搜索准确 全新共享网 数据量 界面 分类目录 增强功能 图 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 协议 “下载难” 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 4 等问题的方案。我们希望在保持传统 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 年初，网络实验室谢欣硕士在他的公开进展报告中提出 了“天网人”项目。这个项目设计在处理资源不足的方面提出了基于货币交易的共享网络 的思路来鼓励资源的共享。 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 5 天网人项目为了实现三个目标： 一、 增加资源数量 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 网络中的节点发现。对于社交网络软件的 定义有很多，如“个人带着软件成为社会网络的一部分” 或 “是帮助人们建立社会网络 和自动组织群体的软件” 或 “关注软件使用过程中建立的群体联系超过对软件技术的关 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 6 注”等等。社交网络软件按其所体现和促进社会关系网络形成不同形式可以分为显性社交 网络软件和隐性社交网络软件。 显性社交网络软件在功能上是直接促进某种程度人际互联 关系的构建和发展。 而隐性社交网络软件则是在完成软件某种功能的过程中促进了人际关 系的互联和建设。另外社交网络软件按其应用指向性，我们还可以将其分为即时通讯类和 基于某种任务应用的社交网络软件。著名 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 系统至少应该包含以下几个主 要功能： ? 支持即时通讯和 BBS (类似 QQ) ? 支持跨防火墙的文件共享与下载 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 7 ? 支持在线资源搜索和文件目录视图 ? 支持多点下载和断点续传(类似 BitTorrent) ? 基于积点的资源交易体系 ? 采用社交网络的网络链接关系 为了实现上述各个功能，我们设计了如下的体系结构： 图 2 Maze 的系统结构图 在设计的具体操作过程中，我们觉察到纯 P2P 系统在发现局域网内部节点方面，对用 户共享资源的管理方面以及全局搜索方面都有不同程度的缺陷，因此，经过综合的考虑， 我们将 Maze 设计成为一种混合型的 P2P 系统。 在 Maze 系统中的每个 Peer 就相当于一个传统 FTP 服务器和 FTP 客户端的结合体。 整 个系统除了多个 Peer 外，还包括集中式的用户、目录、检索、心跳还有种子服务器。用 户管理服务器实现用户注册与身份认证。 目录收集服务器负责收集每个 peer 的共享的目录 列表到集中的数据库。检索服务器读取目录数据库为所有 Peer 的文件目录建立索引并提 供 XML 接口的检索服务。心跳服务器负责维护在线用户的列表。每个在线的 Peer 每隔几 秒就通知心跳服务器“我还在线” ，这也就是我们将之命名为“心跳”的意义。同时每个 Peer 每隔一段时间就把自己的目录信息在 Maze 的目录收集服务器上更新。检索服务器定 期重新建立索引，并由心跳服务器提供的在线状态只显示在线用户的文件检索结果。种子 服务器是为模仿 BitTorrent 机制建立的 Maze 种子提供保存与更新的服务器。 在检索服务器方面，我们采用天网文件搜索来为 Maze 提供在线文件检索服务。天网 文件搜索引擎是北京大学网络与分布式系统实验室从 1999 年开始的一个大型项目，系统 运行稳定，索引数千万文件，每天都有数十万用户使用，这个系统不仅仅可以检索 ftp 文 件，还有多种接口来检索其他协议的文件列表，例如 http 上的文件、局域网共享的文件等 等，同时它还提供了 XML 的检索接口，以便二次开发使用。Maze 系统采用了天网文件搜 索这样一种成熟的检索技术来提供检索服务， 使得检索效果和天网文件搜索引擎一样既快 又准。 基于这个体系架构，我们设计了一系列的策略来解决上述当前许多文件共享系统存在 的各种各样的问题，主要有如下策略： 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 8 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) 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 9 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:一个 P2P 文件共享系统的设计与实现 10 息包后，直接向这个包里包含的地址发送一个连接包，包含自己的 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 暂时没 有实现，但保留了扩展接口，目前采用心跳服务器转发的机制来实现相关功能。 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 11 这样，网络中的任意两个节点之间都可以实现稳定的比较直接的通讯链路了。 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 的社交网络 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 12 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） ， 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 13 在无中心服务器的情况下，处于不同局域网内的两个节点也是可以建立一条稳定的通路 的。如图 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。 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 14 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) 11 Peer 在积点改动比较大或一定时间后向用户管理服务器更新自己的积点变化（更改时 需要携带自己的信用卡并对更改的数据进行加密） 。在 Peer 每次更新信用卡时从数据库取 出当前积点，计算星级，保存在信用卡中。 当一个 Peer 下载其他 Peer 的文件时，对方将向心跳服务器请求来源节点的信息，其 中包括了来源节点的星级。 我们规定星级较高的用户有一定的排队优先权。 优先算法如下： 当节点进入排队队列时，从原来的队列末尾开始，跳过所有的星级比这个节点低且入队的 时间与当前时间的差少于星级差(单位分钟)的节点，然后再插入队列。因而，如果一个 2 星的用户已经排了 2 分钟队，当一个 5 星的用户来时，5 星用户可以直接插入到这个 2 星 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 15 用户的前面，因为 5-22。 这样，星级较高的用户在下载文件时，排队时间将远远少于 星级较低的用户，要想获得更高的下载权限，就必须共享更多的资源，这样由此促进了更 多的人提供更多的资源共享。 每次 Maze 给心跳服务器发送状态包时，都携带了当前排队队列的长度，因而在检索 的结果信息中就可以反映出来，用户可以从检索结果中挑选排队队列最短的进行下载。 6.5 文件传输协议文件传输协议 进入下载队列的 Peer 可以向提供文件服务的 Peer 建立 TCP 连接。如果自己在局域网 外，对方在局域网内，则需要采用我们前述的反向连接策略。如果双方都在局域网内，则 需要选择中间代理服务器进行连接。 在连接建立之后，请求者向对方提交自己的用户信息，包括 Maze UID 和允许连接的 一个校验码。接收方检查该 UID 是否已经在下载队列中且提交的校验码是否是该 UID 进 入下载队列时分配的校验码。通过身份验证后，请求者发送文件大小请求包，提交要下载 的文件的虚拟路径。接收者根据虚拟路径计算实际的物理路径，判断文件是否存在，如果 不存在，返回错误，否则返回文件大小。 获得文件大小后，请求者可以请求文件的某些块。因为 Maze 支持多点下载，一条链 接可能只是为了下载整个文件中的某一小块。 请求者根据文件大小分配当前此条链接应该 下载的文件块起始位置和文件块数。接收者答复这些文件块的内容。请求者每次只请求很 少的块以便可以在请求端动态调配各个下载链接的任务， 例如可以让下载速度快的链接承 担更多的块下载任务。 当需要传输的所有文件块都传输完毕时，请求者断开 TCP 链接。接收者把请求者的 UID 从下载队列取出放入一个缓存队列，然后取出排队队列头部的排队者进入下载队列。 7 文件共享与传输策略的改进文件共享与传输策略的改进 7.1 资源的索引与检索资源的索引与检索 我们使用了天网文件搜索索引与检索的程序来为 Maze 提供检索服务，有关天网文件 搜索的具体实现技术可以参考我们的相关论文2。 图 8 Maze 与天网文件搜索的集成 天网文件搜索服务器 CGI程序接收 查询请求，返 回 XML 结果 检索服务器 Maze 目录收集服务器 搜集各个 Peer 的目录，建立 倒排索引文件 用户 Maze 心跳服务器 各个 Peer 的在 线状态 北京大学硕士学位论文 Maze:一个 P2P 文件共享系统的设计与实现 16 7.2 多点同时下载多点同时下载 经过统计发现，教育网上各个站点共享的资源有很大的重复度，一般情况下，相同的 资源可能会在很多站点上存在。 针对这个特点我们在 Maze 中采用了多点并行下载的策略， 即用户下载资源时可以从拥有相同资源的多个 Peer 上同时排队下载同一个资源。 具体方法如下：请求方在下载文件之前先把文件分成多块，然后给所有含有该文件的 站点（在检索结果中或后面叙述的 Maze 种子中可以获得这个列表）发出下载请求。由于 可能某些站点的下载队列已经满了，必须排队等待进入下载队列，因而只对排队完成的站 点分配下载文件的任务。每个站点分别提供该文件的某些部分，最后请求方根据服务者返 回的数据把各个块整合成一个整体。当整个文件都下载完毕时，如果还有站点还处于排队 状态中，必须发送退出排队命令，以减轻该站点的负担。这样，请求方可以同时从多个站 点获取数据，并且每个站点也只需传输文件的一部分，达到了加快下载速度和减轻站点负 担的目的。 另外，由于写磁盘和网络传输是下载资源时的两个瓶颈，为了减少代价，我们采用了 网络下载与文件读写并行处理的策略，网络下载采用异步 Socket，文件读写也采用异步文 件操作函数， 请求方向文件中写入第 k 块数据的同时正从网络上下载第 k+1 块数据。 同理， 提供文件下载的站点在读第 k