【毕业学位论文】（Word原稿）大规模可扩展索引技术的研究和系统实现-计算机网络技术

北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 1 硕士研究生学位论文 题目： 大规模可扩展索引技术的 研究和系统实现 姓 名： 刘源 学 号： 10548185 院 系： 信息科学技术学院 专 业： 计算机系统结构 研究方向： 搜索引擎与 息挖掘 导 师： 李晓明 教授 二八年 五月 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 2 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律 责任。北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 3 摘 要 随着互联网的发展，原始的数据库系统无法满足大数据量相关性检索的需求。从而基于倒排表的索引系统越来越多的应用在各项服务中。但是索引系统和数据库系统一样，有着较为复杂的内部逻辑和外部行为，如何创建我们需要的索引系统，如何优化我们的索引系统，是困扰很多索引系统构建者和使用者的难题。 本文的研究范畴是用于信息检索的索引系统，通过一个真实的索引系统引系统，本文从三个方面进行分析和研究：对索引系统进行功能模块上的分析；对索引系统开发和使用中的性能问题的研究和分析；对一个实际系统 的系统实现的详细。具体为： 1) 索引系统的模块分析 本文详细分析了作为一个复杂系统的索引系统，其创建和使用都受到很多条件的制约。本文分析了索引系统的常见的需求，比如如何对原始的文档集合进行分析，如何设计索引内部文档的表示能力，索引如何创建，如何存储等，划分了一系列基本的功能模块。 2) 索引系统的性能分析 因为索引系统的目的是快速的响应检索需求，所以效率问题一直是索引技术的核心问题。在模块功能分析的基础之上，本文进一步分析了索引创建和检索中常见的性能问题，提出了基本的解决方案。同时，对于如何对索引系统进行整体的和局部 的量化分析，引入了 则，尝试给出一个指导实践的经验公式。 3) 引系统的实现分析 对于问题的分析，需要一个具体的系统进行实践。在深入研究天网搜索引擎已有的索引系统和相关索引系统基础上，同时在大量阅读了相关专业文献之后，我们进行了分析和研究，设计实现了 863课题支持的 文以系统的基本模块和重要接口为核心，分析了系统的基本框架能力以及如何进一步对系统进行扩充。 关键词 ：信息检索，索引系统，索引优化，倒排表北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 4 is in is in of As its in to to it is of is of (1) To on of (2) To in of (3) To of (1) ue to of of it is by of In in as of of to to (2) ue to to is in In to in of of is in Q is to (3) n of is in is to is 大规模可扩展索引技术的研究和系统实现 5 目录 摘 要 . 3 . 4 目录 . 5 第一章 绪 论 . 9 引系统背景 . 9 联网服务系统 . 9 则 . 10 求快速查询的场景 . 10 数据库系统的比较 . 11 据库系 统的能力 . 11 引系统和数据库系统的异同 . 11 引系统的简单用例 . 12 引系统基本模块 . 13 引系统基本流程 . 13 文的主要工作 . 14 文的主要研究点 . 14 文的主要创新点 . 14 文组织结构 . 14 第二章 索引系统分析 . 15 引核心模块分析 . 15 析模块 . 15 档表示模块 . 15 储模块 . 18 引创建 . 18 储镜像的逻辑视图 . 21 引检索 . 22 规模索引专有模块 . 23 缩模块 . 23 存模块 . 29 态索引 . 31 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 6 本控制 . 32 存索引 . 34 布式索引 . 34 用性和可靠性与 则 . 35 引切分和索引冗余 . 37 对可用性和效率的解决方案 . 38 章小结 . 38 第三章 索引优化 . 39 引创建的优化 . 39 建时期内存压缩 . 39 态索引二路归并的块合并时机 . 40 索引多路归并方法 . 41 引检索效率的优化 . 42 索时效率分析 . 42 用块状压缩和 跳查来降低 用 . 42 用缓存机制来降低 . 46 引常数 . 47 机的服务能力上限 . 47 体服务优化 . 48 机索引常数 . 49 章小结 . 49 第 4 章 引系统框架 . 50 统目的 . 50 向搜索引擎服务 . 50 扩展性，可实验性 . 50 本模块详细分析 . 50 析模块 . 51 档表述模块 . 52 储模块 . 53 缩模块 . 54 存模块 . 55 引模块 . 56 引创建流程用例分析 . 59 引提供的检索接口用例分析 . 61 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 7 第五章 总结和展望 . 64 文总结 . 64 一步工作 . 64 参考文献 . 66 致谢 . 69 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 图表 1 互联网服务系统示意图 . 9 图表 2 文档集合和查询集合 . 12 图表 3 简单索引流程 . 13 图表 4 对页面进行分析 . 16 图表 5 文档倒排操作 . 18 图表 6 倒排合并操作 . 19 图表 7 并 . 20 图表 8 并 . 21 图表 9 检索过程 . 22 图表 10 缩 . 26 图表 11 码示例 . 27 图表 12 压缩时间对比 . 28 图表 13 解压时间对比 . 28 图表 14 压缩后长度对比 . 29 图表 15 O 读操作 . 29 图表 16 三级缓存策略 . 30 图表 17 索引创 建和服务分离 . 32 图表 18 版本控制 . 33 图表 19 内存索引 . 34 图表 20 索引数据切分 . 35 图表 21 索引数据冗余 . 36 图表 22 索引数据切分且冗余 . 36 图表 23 二路合并 . 40 图表 24 哨兵位和定长压缩数据 . 44 图表 25 独立跳查结构 . 44 图表 26 使用跳查表进行求交 . 45 图表 27 不适用跳查表进行求交 . 46 图表 28 块状存储 . 46 图表 29 分析模块结构图 . 51 图表 30 存储模块结构图 . 53 图表 31 压缩模块接口示意 . 54 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 9 第一章 绪 论 引系统背景 索引技术现在是一种在网络服务中很常用的技术。在很多的信息检索服务中，都会在数据量相对较大和反应时间要求较短的情况下，考虑使用索引系统。其中现阶段最常见的应用就是搜索引擎系统。 文献 2给出了索引系统的一个综述，全面地描述了索引技术的基本问题和已有的解决方法。 联网服务系统 对于大规模的互联网的服务系统，基本的系统构架都如图所示。 图表 1 互联网服务系统示意图 服务机器会将用户的请求（比如查询请求），按照某种逻辑进行划分，分配到对应的后台机器上去。 后台机器一般来说在数据结构，或者服务能力上是同构的。比如，每台都有同构的数据库表格，存储的是单一一台机器无法成功存储的数据量。 服务机器最终会接受后台机器集群的结果，给以 综合计算，将最终用户需要的信息返回。 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 10 则 当需要对一个互联网服务系统进行分析和评价的时候，我们常常会陷入困境。因为和普通应用程序不同，我们很难对整体系统进行精确的算法分析，以及应用类似复杂度计算的分析手法。 我们面对的可能情况是： 硬件级别上的异构：我们的服务机器和后台机器可能是不同的硬件系统，拥有不同的计算能力 应用上的差异：对于前端服务机器来说，需要处理的问题一般是负载均衡，结果合并和过滤等计算密集型任务；后台的机器则需要完成较多的数据读取这类 为密集的任务。 在这样的情况下，可以使用 则来帮助我们分析系统问题。 则将计算机的所有计算能力（ 率，内存速率， 率，网络速率等）都看作是底层的数据流（ 而我们提供的服务是一个一个的查询操作（ 在这种情况下，每秒钟可以处理查询的条数和每条查询需要处理的数据的乘积就是我们的系统的服务能力。 公式 1 而我们整个系统的数据流提供能力的总和，应该和上面的结果匹配。关于则的具体细节，请 参考文献 33。 求快速查询的场景 对于互联网服务系统来说，其面对的数据量都是巨大的。这样的话，进行快速的查询和海量的数据就构成了矛盾。现在最常见的就是搜索引擎的检索服务，需要在非常短的时间内（ 1 秒左右），在非常大的数据量（亿级别网页， 找到符合某一类要求（比如包含查询字串）的结果。文献 7从信息检索角度对基本的数据结构和算法进行分析。 比如，我们需要查找 北京大学 相关的内容，在互联网上，相关的网页集合可能非常的大。并且用户得到一定的反馈之后，可能继续进行检索行为。因北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 11 此 ，我们应该可以同时满足在海量数据上的查找以及快速的反馈。 数据库系统的比较 数据库系统非常广泛的被应用于互联网服务系统中，比如非常流行的 系统框架。同时，大规模的分布式数据库系统也得到了广泛的应用。索引系统和一般意义上的数据库系统有着什么样的不同呢？我们可以从其能力上进行对比。 据库系统的能力 数据库系统的能力可以被其查询语言 很好的描述，我们可以通过给出一个严谨的 句来达到一个较为特定的目标。 2 6; 从例子我们可以看出，查询者有一个非常明确的目标，从 2 到 16 岁之间的 对于这条语句的执行结果是： 所有的 符合要求的内容都会返回，使得查询者的 需求得到满足。 另外一个较为让人混淆的概念是数据库中的索引，数据库中的索引是一个逻辑意义上的索引结构，用来加快数据库表的检索速度而将一类数据建立了索引项，这些数据一般来说不保证在物理上相邻。从某些方面来说它更像书籍的索引。 引系统和数据库系统的异同 而对于索引系统来说，他提供的检索能力与数据库系统是不同的。是基于相关性计算 得到的结果集合。所谓的 相关性 是说： 查询和结果在某种程度上 相关 ，比如查询中的词在结果中多次出现就是一种相关性。 一种最简单的相关性模型就是向量空间模型（ 他认为查询词和文档都是一些词集合（ 通过计算它们之间的向量夹角 可以得到他们之间的相似度。 对于 型，举例如下。 文档一 ： 北京 大学 南门 文档二 ： 清华 大学 西门 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 12 查 询 ： 大学 南门 整体词的集合： 北京 清华 大学 南门 西门 相似度（文档一，查询） = 向量夹角（ (1, 0, 1, 1, 0), (0, 0, 1, 1, 0)） 相似度（文档二，查询） = 向量夹角（ (0, 1, 1, 0, 1), (0, 0, 1, 1, 0)） 这样的计算结果，我们可以看到文档一和查询的相似度比较大。 所以，对于索引来说，通过计算相关性的值来将索引文档集合进行排序，返回给用户相关性最高的文档。但是对于用户来说，查询词所代表的意义是不明确的和有歧义的。比如 病毒 ， 些歧义查询，以及 北大主页 这种导航性查询， 怎么治疗感冒 这类信息型查询等等。用户只是通过一些模糊的概念来选择查询，根据不同的需求浏览相关文档，进一步修正查询词，得到相关信息。 对应于数据库查询的接口来说，这些 相关性 查询很难转换为规则的 时数据库系统的一般行为是返回所有符合查询逻辑的结果，这对于海量的文档集合来说，也是不合实际的。 引系统的简单用例 为了更加直观的解释索引系统的能力，我们可以构造一个简单的用例来说明。假设我们有以下三篇文档，和两组查询词。我们的 目标是在文档集合中找到查询词出现的文档集。 图表 2 文档集合和查询集合 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 13 整个的过程是将文档集合进行分析（ 建立索引，然后可以提供对索引文件的检索。整个流程可以简单的由下图表示。 图表 3 简单索引流程 引系统基本模块 通过上述的用例，我们可以观察到索引系统可以划分为一些基本的功能模块，比如： 从原始文档到可索引文档的分析模块，将索引进行存储的模块，索引建立的模块以及 索引检索的模快。 引系统基本流程 索引的基本流程可以说有两个大模块，索引的建立和索引的检索。索引的北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 14 建立就是把原始的文档集合经过分析后，创建索引镜像；索引的检索模块是说对于用户的检索请求，在索引镜像中找出相关的原始文档集合。 文的主要工作 本文的主要工作有以下几点： 1. 分析索引系统的功能和框架。 2. 分析索引系统的系统优化。 3. 给出一个索引系统的实现细节。 文的主要研究点 本文的主要研究点是针对大规模索引，如何使其在数据上拥有可扩展能力，以及在代码模块上拥有可扩展可替换能力； 以及如何进行一个实际的索引系统的设计和实现 23, 26。 文的主要创新点 对于大规模索引来说，如何对索引系统的能力进行分析是一个较为困难的任务。本文提出使用 则来对整个索引系统进行框架性的分析，同时对于单个索引机器的分析，尝试性的给出了 索引常数 的概念，即通过一个经验公式，尝试对单个机器的在索引上的运算能力进行建模。 文组织结构 本文的章节按照如下方式安排： 第一章：即本节着重从背景和应用的角度说明了索引系统的基本理论。 第二章：将会按照索引系统的功能划分，详细论述索引系 统在系统级别上每个模块的作用和行为。 第三章：主要描述在实际过程中可能会遇到的性能的问题，以及如何去做优化。 第四章：详细的分析了天网的 统索引模块的内容，每一个模块的关键接口和流程都会进行描述，同时会通过两个用例来展示索引模块的两个主要能力。 第五章：对本文的总结和进一步工作的展望。北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 15 第二章 索引系统分析 索引系统在功能上可以进行划分，得到彼此相关的一些模块，这些模块有些是基本的索引系统必须的，而有些是为了特殊的性能要求才需要的，我们逐一对这些模块进行分析。 引核心模块分析 核心模块的意思是说这些模块在所有的索引应用中都是必须的，主要包括了分析，文档表示，存储，索引，检索几个基本模块。 析模块 索引的分析模块的主要作用是将外部的文档格式转换为一个单元（ 序列。 其中单元（ 需要索引的最小的成分。 般由其字串，在文档中的偏移信息，以及类型信息等组成。在分析的过程中，可以识别出来一些需要的 者进一步转化一些 字串，如采用英文中的词干提取（ 术，以及过滤掉一些常用无意义的词汇（ 对于分析后的信息，可以进一步建立索引的文档表示。 档表示模块 文档表示是索引的最基本的模块，它往往说明了索引的检索粒度和能力。一般的索引系统都将文档表示成为词集合（ 方式，尽管像 26，但是却没有对应的检索模块。原因之一是像 样的标记性语言，它的结构信息很多是用来表示视觉的展示，而不是表达内容的相关性。 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 16 图表 4 对页面进行分析 我们可以看到，在这个网 页上有着通用的页面信息（ 标题： 正文信息： 略 正文第一句： 正文内链接文本信息： 和 链接信息： 左侧的大量文本 从直觉上可以得知，上面的几类文本在这个网页中的重要性是不同的，需要分别标识用来给检索模块提 供信息。对于文本的分类标识，可以从两个方面考虑，域（ 附加信息（ 域可以简单的认为是一种前缀信息，我们将类别和文本组成了二元组 来区别不同类型的文本。那么，上面的标题文本在词集合的行为下就可以表示成为 : 北京大学硕士学位论文 大规模可扩展索引技术的研究和系统实现 17 域信息会有什么样的用处呢？一个最简单的方式是可以在检索阶段赋予标题域一个和正文域不同的权值。通常来说不同