【毕业学位论文】（Word原稿）Maze检索系统性能优化和资源评价-计算机系统结构网络与分布式系统

硕士研究生学位论文 题目： 索系统性能优化和资源评价 姓 名：王正克 学 号： 10308160 院 系：信息科学技术学院 专 业：计算机系统结构 研究方向：计算机网络与分布式系统 导 师：李晓明教授 ， 雷凯 讲师 二六 年 五 月 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。北京大学硕士学位论文 - I - 摘 要 统是 基于 内容 交换系统 ，采用集中式架构管理用户和资源。本文的研究范围为 索系统以及 统中资源的性质。 第一部分 详细介绍了 索系统的设计和实现，并针对 索系统的性能问题进行了研究，讨论检索效率的影响 因素，并提出一些改进方法和途径。这些方法包括改进整数压缩编码、基于 多级 缓冲技术 等方法。最后对 提出改进方案。 第二部分 研究 统中资源的性质。首先提出了根据文件指纹的搜索方式，利用文件指纹聚合镜像文件，向用户提供所需文件 的所有可下载源。然后提出 禁用 指纹库 和 禁用词表 结合的 禁用 文件识别方法，控制 络中的 禁用 文件的传播。最后，本文提出 法，利用下载关系构造一个投票模型，评估资源的价值。 法对资源进行全局评价，有助于选择性索引文件资源和合理排序返回结果。 关键词： 索系统，倒排文件，缓冲机制， s i, is a 2P, it In we of In we we do on of of on we to In we of We on is to be to s we a of an to At an is We to a to to in be to to be to - 目 录 摘 要 . I . 一章 绪论 . 1 究工作的背景和意义 . 1 文研究工作的内容 . 3 文的组织 . 4 第二章 索系统基本技术 . 5 言 . 5 统设计与结构 . 6 录服务模块 . 7 引创建模块 . 7 索服务模块 . 8 章小结 . 8 第三章 倒排文件技术和缓冲技术 . 10 言 . 10 排文件结构 . 11 数压缩编码技术 . 12 冲技术及评估 . 14 排表缓冲 . 14 间对象缓冲 . 15 询结果缓冲 . 17 章小结 . 18 第四章 检索效率的综合测评 . 19 言 . 19 真实验设计 . 19 真实验结果 . 20 进前后的性能对比 . 21 北京大学硕士学位论文 - 章小结 . 22 第五章 基于文件指纹的搜索和禁用文件控制 . 23 言 . 23 件指纹搜索方式 . 23 用文件识别技术 . 25 统的禁用文件控制机制 . 27 章小结 . 28 第六章 法 . 29 言 . 29 于下载行为的投票模型 . 30 票模型解释 . 31 票模型的数学表示 . 32 票模型中的特殊 构和改进 . 32 上传 . 32 下载 . 33 票闭环群 . 34 立 . 35 型的改进 . 36 法 . 37 敛性 . 37 源评价的应用 . 38 询结果排序 . 39 章小结 . 41 第七章 总结与未来展望 . 42 结 . 42 足与展望 . 43 参考文献 . 44 致 谢 . 46 北京大学硕士学位论文 - 1 - 第一章 绪论 究工作的背景和意义 近年来， 术的 蓬勃发展 ，改变了人们使用网络的方式。 人们不再只是浏览者，而是参与者，平等的交流认为最有价值的资源。 如今，在文件交换方面的应用， 术正是炙手可热。 自从 1999 年 生，它的用户量迅速增长，在短时间内激增到数千万人。 2000 年 五大唱片商的对簿公堂，更使 术成为人们的焦点。而原告之一 司与 成和解 协议，更证明了数字方式发布音乐是不可阻挡的潮流，与其妄图阻止类似 享软件的不断出现，不如将其变成合法的在线音乐销售渠道。 在 后，基于 术的内容共享软件层出不穷，如 等。值得一提的是， 2003 发布，就是因为有 种 技术，才让 热于尝新的 用户 们 第一时间 获 得这样 庞大的拷贝。如此快捷、自发而又有序的数据传播方式，在 术的兴起 之 前，可是不可思议的事。至 此， 基于 内容共享，因其自由、平等 及 高效等特性，成为人们不可缺少的 数据传播方式。 基于 内容共享系统， 架构可分三种：集中式、混合式和纯分布式。 因其网络组织方式不同，其资源的定位算法也截然不同 et 2003。取集中式的架构，中央服务器拥有所有 享资源信息 ； 由中央服务器负责定位资源，回应 交 寻找资源 的查询。 混合式架构的 统采取不同的策略，如 用部分性能较好的 当超级节点，由它们索引相近的 叶节点 所共享的 资源；由超级节点合作定位资源，回应 交的寻找资源的查询。而完全分布式 架构 的 享系统 有两种：一是完全无结构的 ， 资源定位 算法有 泛洪查找、宽度优先、和 随机漫步 等算法； 若 在每个节点保存一些关于 其他节点 资源信息， 则可 采取以上算法的 一些 变种。二是结构化的纯分布式 系北京大学硕士学位论文 - 2 - 统采取 法建立，所有的操作都基于 ， 由它来处理资源分布 和定位 。 本文的研究对象 统采取集中式架构，有一系列的中央服务器负责用户管理 和资源管理。由用户服务器负责 册、登陆管理；由心跳服务器负责用户状态管理；由中央目录 服务器 接收 传的 享 内容信息，以建立全局的倒排索引；并有中央检索服务器接收和 处理 资源定位请求 ， 并 做 禁用资源控制和 禁用 用户管理 。 集中式架构的 统具有检索高效、推荐最优和系统可控的优点。 基于 内容共享系统的检索系统 建立于信息检索技术之上 。信息检索技术的研究，主要在于 分析信息的结构和组织，研究其存放和检索，利用各种技术，以 有效 提高其检索效率和效果。 非 结构化的文本一直是信息检索的研究重点，近年来，大规模搜索引擎因其应用广泛、数据规模大、查询请求多且实时性要求高，成为了 信息检索技术研究的焦点。 对搜索引擎的研究， 在 各个方面都获得了累累硕果 ，从网页抓取、 网页净化 、镜像识别到检索效率和检索效果，都取得了极大进展。其对 统的检索系统研究有着极大的借鉴意义。 混合式和纯分布式的 统的搜索方式是 式 的，它们的研究热点集中在网络结构组织、资源存储、资源发现和查询请求转发等方面，与搜索引擎有着极大的不同。 本文研究兴趣不在于此，故不作深入阐述。 集中式架构的 统 ，其检索系统有着和搜索引擎许多相似的研究 点 。 它们都需要收集分布在 互联 网 的 各个地方的资源信息，都需要对所收集资源进行预处理，识别 禁用 资源和镜像资源，还 需要对资源进行评价，以求返回给用户最贴近用户需求的资源。 它们也存在很多的不同点。首先研究对象不同，搜索引擎 的研究对象 是网页 ，网页是半结构化文本，主要需要语言处理技术；而 统的研究对象是各式各样的文件，有文本、多媒体文件和各种软件等等， 可利用信息主要是文件名信息，若需更多的信息则得抓取额外描述信息，或采取多媒体处理技术 。再者 资源所在站点 性质不同， 搜索引擎的资源所在网站是不知中央服务器存在和只能被动提交资源信息； 统的组成 可知 中央服务器 存在 ，且具有计算能力， 可自行处理部分数据。 综上所述， 集 中式 统的 所需 检索技术 可 参考搜索引擎的检索技术 ，同时 要针对自身特性研究新的检索技术。 北京大学硕士学位论文 - 3 - 本文主要分析 统 的检索技术。 统 是一种 基于 、集中式的内容共享 系统 ，可从 解 其 基本概况 。 它 的检索系统 的 设计实现参考学习了天网搜索的检索技术， 考虑 文件资源和网页资源的差异， 并充分 利用 计算能力，采用 针对 性 的技术 ，以打造高效的、可控的 统。 文研究工作的内容 本文的研究工作集中在 统的 检索系统性能的优化 和资源评价 ，主要在数据 组织 、检索效率、检索效果 等方 面进行研究 。 本文从用户行为、资源分布特性等 方面出发，研究 统特性，提出以下技术 ： 基于 多级 缓冲技术 。 统是由自主行为的 成 ； 而 在线与否决定了该 源的可用性。 本文 设计 基于 多级 缓冲技术，充分利用 在线属性，提高缓冲效率。 文件指纹 搜索技术 。 统中有众多镜像文件，它们分布于不同的各镜像 命名 差异较大 。本文提出提取文件指纹，将分布于不同 同命名的镜像文件聚合在一块，提供根据文件指纹的搜索方式 ， 查 找用户 所 需 文件 的所有 可下 载源 。 禁用 文件控制技术 。 统具有众多 禁用 文件存在，识别它们并控制它们的传播是 统一项重要任务。本文提出通过人工提取 禁用词 ，查找含 禁用词 的文件，对这些文件进行人工查看 和机器审查 ，进而提取确认为 禁用 文件的指纹，组成 禁用 指纹库 。 统利用禁用 指纹库 和禁用词表，合作 进行 对 禁用 文件的控制。 法 。 法利用下载行为评估资源价值。它通过挖掘 下载日志，利用 资源互相 互动关系，建立投票 模型，刻画资源的热门度。利用资源 评价，参与对返回结果排序 。 北京大学硕士学位论文 - 4 - 文的组织 本文第二章 先 围绕检索效率和检索效果，介绍 索系统的结构设计，再介绍 索系统的组成 模块 和实现模块 所需的基本技术。 第三章先介绍 统的倒排索引文件结构设计，再介绍采用的索引压缩编码，并对该编码方式进行效果实验；然后介绍 统采用的对不同缓冲对象各自采用的缓冲机制，并对缓冲的命中率进行分析。 第四章对 统的检索效率 进行 综合 测评 。 先对 考察检索系统在不同负载状况下的各个性能参数，对影响检索系统性能的主要因素进行分析。 然后对运用上述技术改进前 后的性能进行对比。 第五 章首先提出文件指纹搜索方式，阐述文件指纹搜索方式对于文件名搜索方式的补充作用 ，以及其对深入搜索的意义 。然后提出一种识别 禁用 文件方法，就是结合 禁用 指纹库 和 禁用词 表来发现禁用文件 ，并且叙述 统中的 禁用文件控制机制 。 第六 章先提出 基于下载行为的投票 模型， 从数学、算法和应用的方面对投票模型进行详细解析。 然后 介绍结果排序所涉及的因素，并 提出 结果排序算法。 第七 章 先总结 索系统中的技术和 区中资源性质的研究，然后阐述现有检索系统不足和未来可发展的一些方向。 北京大学硕士学位论文 - 5 - 第二章 索系统基本技术 言 如前所述， 统有三种架构：集中式 、混合性、完全分布式。对于资源搜索来说，这三种架构各有利弊。 集中式架构的 统，具有中央索引服务 ，可快速定位任意资源，具有查询响应时间短的优点，而且可控性较好。 但它需要所有用户向中央服务器提交资源共享信息，并且中央服务器索引重建需要一定周期，因此它有不能即时的体现 统内共享信息的变化；另外 集中式架构的 对 较差 ，整个系统的瓶颈在于中央服务器的性能 。 混合式和完全分布式的 统，或采用 超级节点的 分层结构，或采 用法定位资源，具有可扩展性好 的优点。但它的资源定位能力较差；虽热门文件定位迅速，但一般性文件定位至少需要 n） 的时间 代价。此外，它对 资源的控制较差，对 禁用 文件和违规 能及时进行处理。 综合考虑上述优劣， 统采用集中式架构 。 统在中央服务器上接收用户共享内容列表，索引所有共享内容，并对 禁用 文件进行集中控制。 在系统设计时， 统充分考虑集中式架构的优点，追求尽可能快的给用户返回最好的资源信息，并且控制 禁用 文件的传播，打 造高效的，健康 的网上社区。另外，考虑到集中 式架构的缺点，设计时尽量 缩短索引重建周期，尽可能快的体现社区中资源的变化；并且尽可能的增强系统的可扩展性。 统现有 注册用户达 400 多万，索引约 1 亿个文件资源。每天活动用户达 10 万余人，下载次数达 110 多万，每日查询次数达 17 万。 本章以 统为基础，分析检索系统的基本技术和 统的特有技术。 北京大学硕士学位论文 - 6 - 统设计与结构 索系统的设计考虑三个因素 ：检索效率，检索效果和系统可扩展性。检索效率是用户可直接体验的因 素，一般来说，对查询请求响应时间 要求 在秒级 ，用户 才没有等待的感觉。检索效果是另一 个用户 可直接体验的因 素， 主要表现在返回结果列表中排列在前的结果与查询词 是否 相关度 高， 并且 易于下载。检索效率和检索效果是评价检索系统的成功与否的两个主要因素，它们存在竞争，为获得较好的检索效果，需要在服务器做更多的计算，势必影响到检索效率。系统可扩展性是指系统适应变化能力， 是否能 满足用户 数量 增长、文件资源 增多 后的查询请求 ；这是集中式架构的较弱的环节，设计时要着重考虑 。 这三个要素对 块的设计都起了重大影响。 统的设计目标是，将查询请求相应时间控制在秒级前提下，尽可能的提高返回结果的相 关度，并且保证系统 具有一定的 可扩展性。 根据功能 将 索系统分成三 个模块：文件列表收集模块，索引建立模块，检索服务模块；系统结构图如下所示。 图 2统架构图 目录服务模块负责接收 时上传的共享资源列表，写入文件。索引建立模块定时读取共享资源列表，建立倒排索引文件和相关文件。检索服务模块读取北京大学硕士学位论文 - 7 - 倒排索引文件和相关文件， 定时从状态服务器接收 用户在线状态 列表 ，同时接收和处理 交的用户查询请求。下面详细描述各个模块功能，以及各个模块为提高性能所采取的技术。 录服务 模块 目录服务模块负 责接收 时上传的资源 列表。 各个 隔设定时间检查自身共享内容，若未曾有过变化，向目录服务器提交时间更新消息，确认资源的有效性；若自身共享内容发生变化，则发送新的资源列表。目录服务模块 根据收到的消息类型，或 将接收到的资源列表写入文件，等待索引创建模块使用 ，或更新该 源列表的有效时间 。 我们在 设计 资源信息结构时，充分利用了 计算能力，将能在 立计算的所需资源属性都下放到 计算，以减轻中央服务器的负载。比如文件资源的指纹计算和 禁用资源 的 部分过滤工作 ，都放在 处 理 。 引创建 模块 索引创建模块负责资源的倒排索引的创建。对 传的原始资源列表建立倒排文件和其他资源相关文件 ，以供检索服务模块的使用 。 倒排 索引 的 设计， 是检索服务的基础， 对检索系统性能有着巨大影响。为提高检索系统性能，本文关注以下内容 ： 索引 结构设计 。 良好的索引结构设计可以提高解析效率和方便相关性评价。在所有 的与 索引 相关的 结构 体 中，都考虑 d 属性，充分利用 索引压缩技术。 索引压缩的目的是以 算时间换取空间，最终节约磁盘访问时间，提高检索效率 。这是大规模、多用户的检索系统提高性能的重要手段。 禁用 文件控制技术。利用 禁用 指纹库 和禁用词表合作 识别 禁用 文件，阻止禁用 文件的传播。另外根据用户共享的 禁用 文件情况， 对用户进行审查，记录 违规 用户的 便 对违规 用户进行惩罚 ，最终净化 区 。 北京大学硕士学位论文 - 8 - 索 服务 模块 检索 服务 是用户直接参与的过程，也是用户体验最明显的过程。检索过程分为以下几个步骤： 解析用户提交的查询请求； 查找 与查询关键词相关的资源记录，考虑 线属性，对非在线站点资源进行过滤； 根据查询请求属性和 资源属性过滤 资源 记录 ； 根据相关度和站点 及文件评价对相关文件列表进行排序 ； 返回相关文件的描述信息 在检索过程中，影响效率的最大因素通常是对磁盘的访问；而影响效果的最大因素是返回结果的相关性评价 和 结果所在 可下载性评价。在 为提高查询处理效率和检索效果 ，最终给用户良好的体验，我们采用了以下技术： 缓冲技术。利用数据访问的局部性， 在内存保存使用可能性更高的数据，以 减少对磁盘的访问 。使用缓冲技术，可以加快查询处理速度，减少用户的等待时间 ，也有利于系统的可扩展性 。 术。利用 区中的 载行为日志， 建立基于下 载行为的投票模型 ， 评价 资源和 利用这些评价值对返回结果进行 重要 性评价。 相关度的综合评价 技术 。 综合查询词、资源评价和 价等因素，计算文件的相关度。根据相关度对返回 资源进行排序，将相关度最高的一些资源返回给用户。如此，可以减少无 用的记录返回比例，提升用户的使用感受。 章小结 本章 从 索系统的设计和实现出发，探讨检索技术。首先介绍 索系统的设计目标， 索系统的设计是围绕效率、效果和可扩展性展开的。接着介绍了 索系统 的架构， 索 系统 从功能 可 划分为 三个模块： 目北京大学硕士学位论文 - 9 - 录服务、索引创建、检索服务。 最后 对 索系统中 各模块的功能 进行描述，并对 其中 采用 的各种 检索 技术做了粗略介绍。 这些技术包括索引压缩技术、缓冲技术和相关度评价技术， 它们 是 实现 高效检索系统的保证。 北京大学硕士学位论文 - 10 - 第三章 倒排 文件 技术 和缓冲技术 言 倒排文件技术是一种检索系统常用的数据组织技术 。它 结构简单， 检索效率高， 能迅速的定位所需资源的位置 ，是大规模、高效率的检索系统的基础 。 随着网络的发展，网络应用的检索系统索引的数据量不断增大，对查询响应的实时性要求也逐渐提高。如何有效的组织倒排 文件 、优化检索算法 ，一直是研究的热点 。近年来 ， 频率和内容容量大规模增长，而磁盘读写效率却相对增长较慢，因此 对 磁盘 上倒排表数据的 访问常成为 检索系统效率的瓶颈。于是有大量的研究投入到 对倒排表的压缩上 et 2002，试图减少对空间的需求，充分的利用 计算能力，进而提高检索的整体效率。另外 1996提出在压缩的倒排表中插入同步点，使得可以跳过某些数据块，直接读取与用户查询最相关的数据块 ，减少读盘和解压缩开销 。 et 1999对海量数据管理方法进 行讨论，全面的 叙述了各种 压缩技术和索引技术。 本章对 倒排文件的设计需考虑下列因素 无二义性。只有一种明确的 解析 方式，这是倒排文件可正确使用的前提条件 。 倒排文件规模小。通过压缩倒排表， 以增加 算 换取 减少文件占用空间， 于是 减少 了 磁盘访问开销，提高整体检索效率。 结构简单。简单的结构有助于快速的定位到最终相关资源的描述信息， 减少索引服务解析时间 ，提高检索效率。 综合上述思想， 本章 提出用 码方式压缩倒排表，减少磁盘访问开销；并且按 基本单位组织倒排表，利用 在线属性，只读取 可用的倒排表项。 另一方面，缓冲技术也是检索系统必不可少的技术。 随着检索系统索引数据量和访问量的增大，提高系统性能和 扩展性至关重要 。缓冲技术就是提高系统性北京大学硕士学位论文 - 11 - 能和扩展性的重要手段，它在计算机的各个领域得到广泛应用。 缓冲技术的有效性建立于被缓冲对象的访问的局部性特征之上。 在 索引擎方面的缓冲技术 已有很多的 研究 ，如 et 2002, et 2005等 ，而 统中的缓冲技术研究相对较少。虽然他们一是研究网页，二是研究文件，但他们存在共性，因为使用者较多关心的 都是热门资源。 本文借鉴搜索引擎中对缓冲技术的研究，考察 统中各种数据使用，提出适用于 统的缓冲技术。 缓冲对象可分为三级：查询结果、中间对象、倒排表。 本文根据 统运行产生的实际数据，对各种缓冲对象的局部性特征进行研究，实现对查询结果和倒排表的缓冲机制，并设计基于 中间对象缓冲方法。 本章第 2、 3 节对倒排文件结构设计和压缩算法的应用进行阐述。第 4 节对各种缓冲对象的局部性特征进行研究，第 5 节着重阐述基于 中间对象缓冲方法，顺带介绍对查询结果和倒排表的缓冲方法。 排文件结构 在线属性是 索系统的一个至关重要的属性，它贯穿整个检索系统的设计。 不同于 索系统， 中央服务器不能实时的了解网站的服务状态；而 统 有一个中央状态服务器，可以实时的了解 在线 信息，确定 于一个 文件共享系统， 资源所在 在线是该资源可用的前提 。资源 所在 处于离 线 状态，那么这个 资源 就无法 被其他 载 ，也就毫无使用价值 。将无法下载 的资源 返回 给用户， 浪费了检索过程中的 内存资源 ，更 影响用户对 检索 结果的评价 。 因此，对返回的用户查询结果 ， 必须 利用线信息 进行 过滤。 在 检索服务 设计 时，要尽可能早 的 考虑 在线属性 的过滤 。 在检索早期进行 根据 在线属性的过滤，能大量减少中间数据量和运算量 ，提高检索效率 。 因此 根据在线属性进行 过滤 ，对离线站点资源不予以解压缩 。 倒排文件分成两个部分 ，下面详细讲解各个部分的构成，及其作用 ： 北京大学硕士学位论文 - 12 - 倒排文件头： 倒排文件头记录所有索引词对应的倒排表在倒排文件的起始偏移信息。 索引词序列号。 索系 统不作切词，直接采用双字节作为索引词，或为汉字，或为字母和数字组合 。后一项属性是指该索引词对应的倒排表在倒排文件的起始偏移。倒排文件 头 是对倒排文件访问的入口。 倒排文件主体 ： 倒排文件主体记录索引词对应的倒排表信息 。倒排文件主体按关键词顺序排列其对应的倒排表 ； 在各 关键词对应的 倒排表内部，按站点顺序排列各站点相关文件信息 。对于每个资源，在倒排文件中 可提取出 三个属性：站 点序列号、站内文件序列号、索引词在资源名中的偏移量。 站点序列号信息，标识后续资源 项的站点属性，方便考察该资源的在线属性。 站点占位长度标识该站点的资源在该索引词的倒排表占据的长度，据此属性 可略过对离线站点资源的解压缩。站内文件序列号和站点序列号一起表示 一个文件。最后一项属性是该索引词在文件名中的偏移，据此属性分析文件和查询短语的相关度。 检索时，通过检索文件头定位所需索引词的 对应 倒排表在倒排文件的位置，再读取所需 倒排表，利用资源的站点序列号进行在线属性过滤 ，得到 与 查询相关的文件列表 。 数压缩编码技术 我们 采用 整数压缩编码技术 压缩