【毕业学位论文】（Word原稿）Maze一个P2P文件共享系统的设计与实现

北京大学硕士学位论文 个 件共享系统的设计与实现 1 绪论 . 3 目产生的背景 . 3 霖硕士的相关想法 . 4 欣硕士做出的新颖设计 . 4 2 相关工作 . 5 点发现与通讯策略的相关研究 . 5 件传输策略的相关研究 . 6 3 系统结构设计 . 6 4 节点发现与通讯策略 . 8 布式认证机制 . 8 点登记与节点发现 . 9 点间通讯策略 . 9 5 节点发现与通讯策略的改进 . 11 社会性的 . 11 离中心服务器正常运行 . 12 6 文件共享与传输策略 . 13 义与解析 . 13 录浏览与索引 . 13 载队列和排队队列 . 14 分机制和排队算法 . 14 件传输协议 . 15 7 文件共享与传输策略的改进 . 15 源的索引与检索 . 15 点同时下载 . 16 点下载的文件分块算法 . 16 得镜像下载地址 . 17 子机制：动态的镜像下载地址 . 17 件内容摘要的提取 . 18 用社交网络改进文件共享与下载 . 18 8 系统的可持续发展策略 . 19 扩充的协议 . 19 控与管理非法资源或不健康资源的共享 . 19 富资源的策略 . 20 9 程序结构与数据结构 . 21 中心服务器及其主要功能 . 21 户管理服务器 . 21 跳服务器 . 22 录收集服务器 . 22 子服务器 . 23 索服务器 . 23 台界面程序结构 . 24 件下载功能模块 . 24 点发现与通讯模块 . 25 地管理模块 . 25 北京大学硕士学位论文 个 件共享系统的设计与实现 2 面模块 . 25 台服务程序结构 . 26 10 式通讯协议 . 27 户管理服务器与 通讯协议 . 27 册新帐户 : . 27 请信用卡 . 27 新积点 . 28 改密码 . 28 改呢称 . 29 跳服务器与 通讯协议 . 29 录 . 29 跳 . 30 送消息 . 30 机查找 . 31 居 . 31 求资料 . 32 记关注名单与定时接收状态 . 32 罚 . 33 消惩罚 . 34 间的 讯协议 . 34 送消息 . 34 览和下载目录 . 34 求详细资料 . 35 取外部端口 . 36 是谁？ . 36 间的 件传输协议 . 37 据包包头格式 . 37 求者发送的命令与格式 . 37 务者答复的命令与格式 . 38 个正常的文件传输逻辑 . 39 子服务器与 的通讯协议 . 39 传种子 . 39 加镜像链接 . 40 除镜像链接 . 40 得所有在线镜像 . 41 录收集服务器与 通讯协议 . 41 传文件目录 . 41 新目录状态 . 42 索的 索协议 . 42 网搜索的 参数 . 42 网搜索的 果格式 . 43 配置 . 44 11 比较和总结 . 45 北京大学硕士学位论文 个 件共享系统的设计与实现 3 1 绪论 根据 天网 搜索 的信息统计，原来 基于 网络文件系统已经日益呈现出资源 “相对”困乏 的局面 。 点的总数量已经开始呈现下降趋势，并且绝 大部分的 点已经不能匿名访问。下图是我们在 2002 年 10 月于 天网 主页上进行 问卷调查 的结果统计， 可以 很明显地 看出 “ 下载难 ”乃是天网文件搜索引擎急待 解决的核心问题。 载难搜索准确全新共享网数据量界面分类目录 增强功能图 1 天网文件搜索最迫切需要解决的问题 面临如此困 境，理所当然，我们应当先分析一下 传统 务 究竟存在哪些弊端， 在当今这个日新月异的信息时代，随着宽带网的普及，上网用户想从网络上获得的不仅是文字、图片、软件等信息，更希望通过各个 点共享和下载更多的用于娱乐和工作学习的 多媒体文件， 例如 频和 乐。 然而多媒体文件 相对其他文件来说一般很大，一个普通的 件就要 600 多 M，这必然导致 网络流量 的 大幅度上升 ，越来越多的上网用户往往在相同的时间段集中访问某些著名的 点，这样传统的 议在处理多用户同时下载大文件的时候就不可避免的表现出了 某些弊端 。首先 ， 务器不能承受大量用户同时连接和下载， 当 超过最大连接数时 便 会 自动 拒绝所有 超额 连接， 而传统议中浏览目录使用的也是 这种稳定的 接，因此在服务器超 负荷 时用户甚至不能浏览目录， 这种并非因为错误而产生的拒绝服务导致人们在使用 非常不方便，往往需要人工的多次尝试连接以等待 务器有空闲的连接资源 ，“登录难”、“下载难”的问题油然而生 。 其次 ， 由于 传统 议 并没有定义一个节点发现协议，只有依靠 加工具来发现已存 的 点 ， 这样那些 著名的 点由于太多用 户访问而经常处于超负荷的状态，而那些虽然 含有相同资源的 但并 不出名 的 点 却 没有承担起分担负载的任务 ，更没有充分发挥作为一个 点提供资源的作用 。 在仔细研究了传统 议的这些不足之处以后，我们试图 设计 出 一个更友好的协议，以保证 只要网络资源存在就一定能够 有效 的发现资源，而只要能够 看到的资源 就 一定可以 成功 下载。 经过深刻的研究，我们决定将 当前 热门 的 “ 技术以及 “ 社交网络 ” 技术 相结合以 作为节点发现策略， 而 使用类似 “ 多点下载 ” 作为文件传输技术 的核心，并且通过 天网文件搜索引擎提供 检索服务 ， 从而 给出一个解决 上述传统 议“下载难”北京大学硕士学位论文 个 件共享系统的设计与实现 4 等问题的方案。我们希望在 保持传统 格的文件共享环境和天网搜索环境的前提下，能够系统有效的解决上述问题 ， 并且进一步 促进网络资源的丰富。 在 2002 年 10 月的问卷调查之后，北京大学网络与分布式系统实验室 针对天网文件搜索引擎中出现的“下载难”问题 展开了广泛的讨论， 大家集思广益， 产生了数种 试图解决该问题的方案，下面将 列举 其中 几个 对后来 实现 有 着深刻影响的方案， 这些想法作为 前期讨论与研究，对 最终的功能与算 法起着不可忽视 的作用。 霖硕士的相关想法 2002 年底，网络实验室的陈霖硕士撰写了一篇“关于天网 索的思考” 的论文 ，这篇文章对增强文件下载的自动性和可靠性提出了一些很好的想法。 他发现在天网搜索中经常出现下面两种情况： a、 某个文件当时 不在任何的 ，过一段时间可能会出现某一两个 ，这种情况用户需要隔几天查询一下， 相当不方便，用户希望天网搜索能帮助自动 继续查询。 b、 务器拒绝访问、或者由于用户数太多了无法登录。这种情况用户需要 反复 试好几个 并不一定是有效的 点 ，希望天网 文件搜索能够协助 找 到 可以匿名（或者提供 密码的）登录的 有效 点 。 而 同时，陈霖 硕士对检索资料与版权方面有如下 考虑： a、 在文件的识别上，或者说在该文件的表述上，我们希望不仅仅得到文件的语法上的表述，更希望得到 语义上的表述（用以确定用户需要的确实是这个文件。我们希望得到一种类似于加密系统中文件摘要的东西）。总之，我们需要能有一种方法准确的知道用户想要什么。可是目前觉得似乎没有什么合适的解决之道，我们尽量取与文件最相关的 1 到 3 个备份。 b、 对于版权的考虑。天网本身不提供文件存放的任何空间，存放空间可以由例如燕星等文件存储系统提供。不过，这样引起的效率的 问题需要考虑 我们可以有 ？作为补偿，我们生成一些用户，然后让这些用户重复以前用户的比较频繁的请求（用 法或者其他），然后把这些请求所获得的结果放在这些用户的 间。这些新生成的用户的空间与我们的系统之间有充裕的带宽相连，并且这些用户空间将被系统优先考虑。 c、 引申 2）中的方法，把整个网络看成以大系统，我们将要有 统的稳定性和速度的记录，以取得最好的效率（或者说服务质量） 综上所述， 陈霖 硕士 认为网格技术可能是解决问题的比较好的方案，因为文件共享存在高性能计算的需求和无缝服务的需求， 而我们要做的事情与信息网格颇为相似，也与宣称一体化服务、一站式服务的服务网格有同样的思路。他希望北大天网能够成为一个网格门户。 欣硕士做出的新颖设计 基于前面的讨论 和设想 ， 2003 年初，网络实验室谢欣硕士在他的公开进展报告中提出了“天网人”项目。这个项目设计在处理资源不足的方面提出了基于货币交易的共享网络的思路 来鼓励资源的共享 。 北京大学硕士学位论文 个 件共享系统的设计与实现 5 天网人项目为了实现三个目标： 一、 增加资源数量 a、 强制命令 每个用户安装一个 务器 b、 构建基于交易的共享网络， 采用自由定价，自由贸易的市场经济原则 二、 提高服务质量 a、 自动提前文件摘要， 识别相同文件 b、 提高服务的可靠性 ， 保证宕机时的交易正常进行。 c、 加强用户参与，降低用户加入门槛 三、 最终目标：实现基于货币交易、强调用户参与的文件共享网络（不仅仅是搜索引擎） 2 相关工作 目前实现文件共享的系统相当 多，主要有 以 传统 C/S 结构为基础的 共享系统，如 空 等 ，以及以 构为基础的共享系统，如 点通，百宝箱等等。 不同类型文件共享系统的主要技术区别 在于它们的节点发现与通信策略和它们的文件共享与传输策略。 节点发现 与通讯策略的相关研究 传统 议 中并 没有提供节点发现的算法，一般 只是 采用口头宣传或者网页链接的方式发布 点。对于 务器是否在线只有 索引擎可能会进行检测，如天网 索引擎就对其搜集范围内的 点是否在线、是否可以匿名下载进行检测。但是这些外部的检测不能 过于频繁 的进行，否则便会 影响 务器的正常运行 ，所以这种检测结果往往并不精准 。 统是当前非常受欢迎的网络系统 1。根据拓扑结构 统主要有两种。一种是混合型 统，比如 鼻祖 之所以 说它是 混合型是因为它还存在集中式的服务器用于发现 有一种就是纯 系统，典型有 统，它没有服务器，节点的发现 只是 依靠 消息的广播。总之， 各种 统解决的方案各不相同，有的采用中心服务器的方式，有的 采用某种复杂路由的方式。 在上个世纪 60 年代，美国一位著名社会心理学家米尔格伦 (出了“六度分隔” (理论，并设计了一个连锁信的实验来验证这个假设。这个理论认为，任何两个陌生人都可以通过“朋友的朋 友”建立联系，并且他们之间所间隔的人不会超过六个。也就是说，最多通过六个人你就能够认识任何一个陌生人。这也就是著名的“小世界假设”。从 2001 年秋天开始，美国哥伦比亚大学的社会学教授瓦特斯(建了一个研究小组，根据米尔格伦的假设，利用 一现代通信工具，开始进行“小世界假设”的实验 20。在 1 年多时间里，总共有 166 个国家和地区的 6 万多名志愿者参与实验，实验结果证明，一封邮件平均被转发 6 次，即可回到接收者那里。 基于六度分隔理论设计的 实现了连接“朋友的朋友”的 软件 被 称为社 交网络软件（ 社交网络模型可 以协助 络中的节点发现。 对于 社交网络软件的定义有很多，如“个人带着软件成为社会网络的一部分” 或 “是帮助人们建立社会网络和自动组织群体的软件” 或 “关注软件使用过程中建立的群体联系超过对软件技术的关北京大学硕士学位论文 个 件共享系统的设计与实现 6 注”等等。 社交网络软件按其所体现和促进社会关系网络形成不同形式可以分为显性社交网络软件和隐性社交网络软件。显性社交网络软件在功能上是直接促进某种程度人际互联关系的构建和发展。而隐性社交网络软件则是在完成软件某种功能的过程中促进了 人际关系的互联和建设。另外社交网络软件按其应用指向性，我们还可以将其分为即时通讯类和基于某种任务应用的社交网络软件。 著名 论家 毛向辉先生将社交网络软件的功能分为核心四层 7，就是 份） 、 案） 、 流） 、 用社会关系）。在不同的社交网络软件中，这四者的体现和侧重的程度不一样。 很容易理解，就是要有个人的账号；而 是电子档案的意思，是对个人体身份可信度的记录或 描述。从某种意义说 网络上数字符号的个体代表，而 是实际存在的个体见证，像 有类似 功能。识和实现了在社交网络软件中人际之间可能有的互动形式和通道， 是从总体上展现了以个体为出发点、以应用为体现、所形成的社会网络应用结构。 文件传输策略的相关研究 1971 年，第一个 的 14)由 1971年提出，同时 由 1985年，一个作用持续至今的官方文档 59()出台。 议乃 是 件传送的基础。通过该协议，用户可以从一个 机向另一个 机拷贝文件 ，实现了因特网上文件的共享 。与大多数 务一样， 是一个客户机 /服务器系统。用户通过一个支持 议的客户机程序，连接到在远程主机上的 务器程序 ， 通过客户机程序向服务器程序发出命令，服务器程序执行用户所发出的命令，并将执行的结果返回到客户机。比如说， 用户发出一条命令，要求服务器向用户传送某一个文件的一份拷贝，服务器会响应这条命令，将指定文件送至用户的机器上。客户机程序代表用户接收到这个文件，将其存放在用户目录中。在 使用当中，用户经常遇到两个概念： “下载 ”（ “上载 ”（ “下载 ”文件就是从远程主机拷贝文件至自己的计算机上； “上载 ”文件就是将文件从自己的计算机中拷贝至远程主机上。用 言来说，用户可通过客户机程序向（从）远程主机上载（下载）文件。 载 (俗称 载 ) 是目前比较流行 的 载软件。 原理是先在上传者端把一个文件分成了 Z 个部分，甲在服务器随机下载了第 N 各部分，乙在服务器随机下载了第 M 个部分，这样甲的 会根据情况到乙的电脑上去拿乙已经下载好的 M 部分，乙的 会根据情况去到甲的电脑上去拿甲已经下载好的 N 部分，这样就不但减轻了服务器端得负荷，也加快了用户方 (甲乙 )的下载速度，效率也提高了，而且，在你下载的同时，你也在上传 (别人从你的电脑上拿那个文件的某个部分 )，所以说在享受别人提供的下载的同时，你也在贡献。 3 系统结构设计 经过长 期的研究， 综合多个讨论与建议，我们认为 统至少 应该包含以下几个主要功能： 支持即时通讯和 类似 支持跨防火墙的文件共享与下载 北京大学硕士学位论文 个 件共享系统的设计与实现 7 支持在线资源搜索和文件目录视图 支持多点下载和断点续传 (类似 基于积点的资源交易体系 采用社交网络的网络链接关系 为了实现上述各个功能，我们设计了如下的体系结构： 心 跳 服 务 器文 件 目 录 服 务 器索 引 和 检 索 服 务 器P e e r 1上 传 共 享 文 件 目 录检 索P e e r 2上 传 共 享 文 件 目 录检 索建 立 索 引建 立 链 路用 户 管 理 服 务 器图 2 系统结构图 在设计的具体操作过程中，我们觉察到 纯 统在发现局域网内部节点方面，对用户共享资 源的管理方面以及全局搜索方面都有不同程度的缺陷，因此，经过综合的考虑，我们将 计成为一种混合型的 统 。 在 统中的每个 相当于一个传统 务器和 户端的结合体。整个系统除了多个 ，还包括集中式的用户、目录、检索、心跳还有种子服务器。用户管理服务器实现用户注册与身份认证。目录收集服务器负责收集每个 共享的目录列表到集中的数据库。检索服务器读取目录数据库为所有 文件目录建立索引并提供 口的检索服务。 心跳服务器负责维护在线用户的列表。每个在线的 隔几秒就通知心跳服务器“我还在线”，这也就是 我们将之命名为“ 心跳 ” 的意义。同时每个隔一段时间就把自己的目录信息在 目录收集服务器上更新。检索服务器定期重新建立索引，并由心跳服务器提供的在线状态只显示在线用户的文件检索结果。种子服务器是为模仿 制建立的 子提供保存与更新的服务器。 在检索服务器方面， 我们采用天网文件搜索来为 供在线文件检索服务。天网文件搜索引擎是北京大学网络与分布式系统实验室从 1999 年开始的 一个大型项目，系统运行 稳定 ，索引数千万 文件，每天 都 有数十万用户使用，这个系统不仅仅可以检索 件，还有多种接口来检索其他协议的文件列表，例如 的文件、局域网共享的文件等等，同时它还提供了 检索接口，以便二次开发使用。 统采用了天网文件搜索这样一种成熟的检索技术来提供检索服务，使得检索效果和天网文件搜索引擎一样既 快又准。 基于这个体系架构 ，我们设计 了一系列的策略来解决上述 当前 许多文件共享系统存在的 各种各样的问题，主要有如下策略： 北京大学硕士学位论文 个 件共享系统的设计与实现 8 a、 点的发现与通讯策略： 包括节点的身份认证和任意两个节点间的通讯策略。 b、 文件共享与传输 策略：包括资源目录的浏览和确保资源可下载的策略。 c、 系统可持续发展的策略：包含非法资源的管理与促进资源丰富的策略。 4 节点发现与通讯策略 布式认证机制 由于每个 要同时与多个服务器通讯，我们采用了一种类似 信用卡 机制的分布式认证算法，来确保 用户 身份 认证的安全性和有效性。参考 制，我们有信用卡发放机构 (称之为用户管理服务器，由它进行用户注册和发放信用卡。用户持有效的信用卡访问其他的服务器，其他的服务器检查信用卡上的数字签名来验证身份， 判断是否允许进行某项操作。一个正常的从注册到登录的流程如下： 证 书提 交 密 码 申 请 账 号加 密 的 证 书服 务 器 证 书 解 密P e e 管 理服 务 器图 3 分布式认证机制 1. 先登录到用户管理服务器，申请一个 号，申请时把登录密码保存在用户管理服务器上。 2. 账户申请完毕之后， 用户管理服务器请求这个 户的身份认证数据包，同时提交自己的 务端口、自己看到的本地 址。 3. 用户管理服务器在身份认证数据包中记录 用户管理服务器看到的外部 务端口、是否在局 域网内（根据 交的自己看到本地 心跳服务器看到 外部 否一致判断）、用户级别、信用卡失效时间等信息，用系统签名私钥密码对数据包进行数字签名，把整个数据包和其数字签名（我们把它称之为信用卡）用 登录密码进行加密，把加密后的证书返回给 个算法可以用下列公式表示： D + 4. 如果用户在 有正确的登录密码，就可以把加密的数据包解密，从而获得有数字签名的信用卡。 北京大学硕士学位论文 个 件共享系统的设计与实现 9 5. 当 要访问其他的服务器（如心跳服务器等）时，出示这个信用卡，服务器用系统签名公钥密码检查数字签名是否正确，以及是否已经过期， 如果检查失败，要求新申请新的信用卡，否则允许下一步操作，也就是登录成功。 这种 基于信用卡机制的分布式 身份 认证算法，可以保证 用户 密码只在注册初期出现，此后 并不在网上明文传送；系统签名 密码 则只在用户管理服务器上出现，因而从客户端很难破解，这些方法都 保证 了 用户身份认证的安全性。 点登记与节点发现 有效的信用卡，在心跳服务器上登记。 心跳服务器的通讯采用 议 。 只有当心跳服务器要求 交信用卡时才需要提交信用卡，心跳服务器收到有效的信用卡后记录这个客户的来源 址，以后 来自相同 相同 户的用户请求都当作是合法的。 期向心跳服务器登记在线状态（发送心跳包），包括该 正在排队的人数等信息。心跳服务器把所有用户的在线状态定期发送到检索服务器，检索服务器由此 过滤掉离线用户的检索结果，使得所有的检索结果都是在线的 。 为了获得好友的在线状态， 以向心跳服务器登记一批关注用户名单，心跳服务器定期把这批用户的在线状态发给 跳服务器还提供在线用户的检索功能，可以随机给出一批在线用户列表或者给出与请求 近的 表（也就是 非常受欢迎的“ 居”功能）。 点间通讯策略 为了使