【毕业学位论文】（Word原稿）一种通用Cache的设计，实现和在天网搜索引擎中的应用-计算机网络技术

目 录 - 1 - 摘 要 . 2 第一章 背景介绍 . 3 维网和海量信息 . 3 索引擎概述 . 4 述 . 5 第二章 相关研究 . 6 换算法 . 6 搜索引擎中的应 用 . 8 第三章 一种 通用 设计和实现 . 9 用 设计目标 . 9 用性目标 . 9 效性要求 . 10 评测目标 . 10 用 设计 . 10 控器 . 11 次控制器 . 12 据存储器 . 13 层 计的优点 . 13 第四章 通用 搜索引擎检索端应用 . 15 验环境 . 15 户查询日志的分析 . 16 询的总体分布 . 16 询的时间局部性性质 . 18 户查询结果翻页的考察 . 19 用 用结构和配置 . 21 体结构 . 21 存配置 . 23 间分析 . 25 第五章 总结和进一步工作 . 28 参考文献 . 29 致 谢 . 31 摘 要 - 2 - 摘 要 在处理 量信息的过程中，有两个问题制约着性能的提高。一方面，由于信息量非常大，只能把所有数据存放在磁盘等相对慢速的设备上， 或者放在多台不同的机器上 。 对于数据的读取和保存只能从这些 慢速 设备或者 分布式的 机器上 获得。另一方面，信息量的庞大也造成了 大量的计算，消耗大量计算时间 。 在很多 应用中，存在着 引用 的局部性规律 ，即大量的操作需要访问少量的数据。 本文工作包括： 1) 本文设计了一种通用的 缓存 (构 。 其 主要 特点是通用性 ， 在各种应用中 ，用户可以自由地对该 容量，替换算法，数据项结构，预取策略，体系结构进行配置 。 同时 提供一个 模拟接口，用户可以通过这个接口执行模拟操作 ，对算法、容量进行评估 。 2) 分析 天网 用户 查询日志，发现 对于 用户的查询 ，无论是否考虑翻页的情况，都 满足类 布 ，这样的具有比较强的局部性的分布形式 ， 提示我们如果采用 构 可以带来很大的好处 。 3) 在 天网 搜索引擎中检索模块中加入这 种通用 块 。 通过 选取适当的 小，替换算法，预取策略和层次结构， 进一步提高搜 索引擎检索端的性能 。 关键词 ： 海量信息 缓存 技术 分布特征 搜索引擎 第一章 背景介绍 - 3 - 第一章 背景介绍 维网 和海量信息 万维网（ 因特网（ 成功的应用之一。 因特网 的前身是美国国防部高级研究计划署的研究试验性网 1983年 P 成为 议。 此后， 器和用户快速增长。 1988年 的规模以指数增长，很多地区网络开始加入，并且开始与加拿大、欧洲和太 平洋地区的网络连接。 从而 万维网起源于 1989年的欧洲粒子物理研究室（ 1989年 3月，由物理学家 1990年 9月，第一个文本原型正式运行。此后，许多的大专院校和业界公司纷纷加入到万维网的研究中来，开发大量的基于万维网的应用程序。 在九十年代这短短几年 时间 里，万维网吸引了的大量的用户和开发者，使得它不断地完善和发展。 万维网是一个分布式的信息系统，它由超文本 (超媒体 (成。 超文本一般由 文本信息和链接信息 组成 ，文本信息是供人们浏览阅读的，链接信息 又称为超链接 (它们 是指向别的超文本信息的指针 ，可以指向万维网上一个位置 。超媒体是超文本的扩展，包括在万维网上的各种资源，包括视频，音频，图像 等等。 在这样一个系统中， 一方面， 用户可以通过超链接的指引，非常容易地获取分布在不同机器上的信息。 另一方面，各种不同地区，职业 的人们可以自由地把本地的信息放到这个系统中去。这样，这个系统就成为一个全球区域的，包括大量信息的系统。根据 至到 2002年 4月，全球的网页数已经超过 20亿 在中国，万维网也以惊人的速度发展。万维网于 1994年正式在中国建立， 2003年中国互联网络信息资源数量调查报告 显示 ，截至 2003年底，中国的网页总数已经超过 3亿，总字节数超过了 6T，总网站数达到 背景介绍 - 4 - 万，网民数近 8000万 这样庞大的一个万维网的规模，包含的信息是海量的。按照万维网的这种发展速度，海量信息也是爆炸式的 增长的。 而 人工在如此大规模的信息中寻找有效信息是很困难的，低效 的。 我们需要采用一种方法 ，获取这些海量信息并对它们进行一定程度的加工 ， 从而帮助人们 更 好 地 利 用 这 些 信 息 。 其 中 的 一 种 方 法 就 是 信 息 检 索 的 方 法（ 称 它的过程是这样的：用户给出一个查询的请求（通常是 一组 关键字 或者一些问题 ），信息检索系统给出系统中与该 查询相关的结果。从而用户就可以方便的从获得的结果中提取有用的 信息。 索引擎概述 搜索引擎是信息检索在万维网上一种很好的应用 。它的基本功能是：用户给出查询，搜索引擎返回给用户和查询相关的万维网上的信息。由于在很多情况下，相关信息结果是大量的，因此系统需要对这些结果进行查询相关性排序， 把更加相关更加有用的信息放在前面，便于用户的浏览，最后返回 排序后的结果 。用户可以通过搜索引擎，很容易地获取他们所需要的万维网上的信息，大大提高了利用信息的效率。 最早的万维网的搜索引擎叫做 1994， 它建于 1994年， 当时它只有 收集了 110000的网页，每天对于它的查询在 1500个左右。在以后的 10年里，搜索引擎有了大规模的发展， 截至 2003年底， 的网页数已经超 过了 40亿 天 网 搜 索引 擎 天网 是 针对 中国 万 维 网 上 丰 富 的信 息 资 源 而 开发的具有中文特色的搜索引 擎。本文的工作，就是在天网搜索引擎的基础上完成 的。 搜索引擎的工作流程基本包括三个步骤： 1、 页 的搜集：它的基本原理是先设定一个初始的 合 S，对于集合中的 每个 集器下载对应的网页，从 S 中删除这个 描这个网页，把这个网页 向外 的链接中没有被下载过的第一章 背景介绍 - 5 - 到 S 中，如此的循环操作，直至 S 集合为空。通过这一过程，我们获取了 从初始 集合 S 出发的所有可达网页。 2、 对 页建立索引库： 建立索引的目的是加快查询的 速度。通常的是采取倒排表的技术，即对于每一个关键词，建立这个关键词出现的文档号和位置号的列表。在检索的时候，用户输入的关键词就可以快速对应到倒排文件的某一个关键词 ，从而获得结果 。 3、 检索查询：用户输入一系列关键词，程序在倒排表中找到相应的项，进行相关的运算 ，获得结果的集合。然后根据网页的重要程度以及网页和查询的相关程度 进行评测，给出结果的排序，然后根据这个排序返回给用户结果页面。 述 高速缓冲存储器（ 在单机的物理结构上，是处于 主存之间 的一种 存储器，它的大小一般很小， 只有几十到几百 K， 存取速度在主存和 存器之间， 考虑到计算机在使用的过程中对数据块的存取有很强的时间局部性和空间局部性，因此我们采用它来暂存常用的数据块，以缩短存取的时间。 我们这里的 是一种和物理 想类似 的逻辑结构，它的物理媒介是主存。在很多应用程序中，对数据的使用有很强的局部性的特征。这里的数据包括：存储在磁盘，磁带等慢速设备上的数据；存在分布式系统 上的数据；需要经过复杂操作和运算才能获得的数据。 这些数据的一个共同特点是： 获得这些数据都需要花费很长的时间，对于磁盘、磁带上的数据， 需要很长的寻道时间 ； 对于其他机器上的数据，需要较长的网络传输的时间 ；对于复杂操作获得数据，需要较长的 算时间。考虑到如果这些应用有一些局部性的规律，那么我们可以把 这些数据中可能 会比较常用 到 的保存在 以后的使用中，就可以避免上述的代价较大的三种操作。 可以有一定的替换策略，决定在一定的时候添加哪些内容，替换出哪些内容，这些操作使得内存中存储的总是最可能在近期被访问到的。 第二章 相关研究 - 6 - 第二章 相关研究 换算法 为动态和静态两 种：静态的 指在应用程序真正使用数据之前，把一些数据填充到 ，当真正需要使用 这些数据 的时候，就从 获得，这些事先填充到 的数据是被预测会在以后的阶段中 会 被频繁使用的 。 动态的 指 ，在真正使用数据之前， 以是空的或者是满的，但是在使用的过程中，当某个数据被访问，而它又满足一定条件的时候，这个数据可以被加到 来。这里会产生的一个问题就是，当 经满了，但是又需要有新的数据添加到 来的时候，我们需要替换掉一个或者一些 旧的数据（考虑数据不定长的情况），这时候我们丢弃哪些数据才是最合适的？ 在 想提出的几十年来，提出了大量不同的替换算法，我们就描述一下这些替换算法。 者 称为 0静态的 是在开始 时填充 真正使用的时候，所有的未命中的数据都不允许加入就是没有数据项被替换。 老的先进先出算法。当某数据在 不存在，就采用其他方式（读取或者计算）获得该数据，然后把该数据加入到 需要替换的时候，先进入的数据先被丢弃 ，而不用考 虑数据的被使用的情况 。 算法选择 最长时间没 有被引用的数据丢弃。它主要考虑了数据访问的时间局部性。它的主要思想是： 在近期被访问的 数据更容易在不久的将来被访问。这种算法是操作系统中 内存和磁盘 间最 常用替换算法。 机算法。该算法不考虑数据的引用时间和引用频率，而是随机的选取一个块丢弃 ，主要应用于局部性并不明显而 量又相对较大的场合 。 算法总是丢弃 最大的数据项。这种算法的思想第二章 相关研究 - 7 - 是让 存储 的数据项都是 比较小的，因此容量固定的 能 够 存 储 比 较 多 的 数 据 项 ， 从 而 提 高 数 据 项 的 命 中 率 996。 该算法采用访问次数作为丢弃的主要依据。主要思想是：越多被访问的数据就越容易在以后被再次访问。方法 就是记录每个数据项的访问次数，在需要丢弃的时候丢弃访问次数最少的数据项。 是 一个变种， 在考虑数据的访问次数的同时，也考虑了时间局部性的影响 。 方法是 随着时间的推移，以前访问过的数据块，乘上一个小于 1 参数 ， 从而 不同时刻的访问对数据项的权值 的贡献 是不同的，越新近被访问的， 对权值的贡献就越大 ，越早被 访问的，对数据项权值的贡献就越小。 是 一个变种 ，它的记录了该数据块的最近 果只有访问了 m 次 （ 查询），查询频度越大，则两次相邻查询之间的间隔越小，对数值之间呈比较好的线性关系。对于访问频度比较高的查询，他们 的时间局部性比较好。 户查询结果翻页 的考察 我们考察用户更倾向 于查看返回结果的哪些页面，以及考虑用户第 四 章 通用 搜索引擎检索端应用 - 20 - 点翻页的趋势 。在搜索引擎中，我们很 难预测用户可能的后续查询，在 999中作者讨论了 单个用户查询的一些模式，但这种模式的划分只是涉及到用户查询的主题级的 信息，而不能够比较确切的获得用户的 更进一步 意图。但是， 比较明确的一点是， 当 用户输入一组关键词获得结果以后，是很容易翻页的 。 图 5 给出了查询的翻页情况， 其中横坐标代表用户翻的页号，纵坐标代表用户所有查询中，该页号的查询占总查询的比例。 发现一半以上的查询都是集中于第一个页面的， 随着页面的推后，这种查询的比例依次递减 。 到第 10 页以后，看得人就非常少了。 5 7 9 11 13 15 17 19 21 23 25 27 29页号所占查询比例图 5 查询的翻页分布 图 6 给出了翻下页的可能情况。 横坐标代表页号，纵坐标代表翻下页的可能性，其中的某一点 (x,y)就是表示对于某一组关键词，如果翻了第 x 个页面，那么 在一定的时间间隔内（这里我们间隔设置为1000 个查询）， 会翻第 (x+1)个页面的可能性。 从图中可以看出，当x=1 的时候，这种可能性比较小（大约 20%），当 X 2 的时候，这种可能性就比较大了，即当用户翻到第 i（ 以后，继续翻下一页的可能性比较大。 第 四 章 通用 搜索引擎检索端应用 - 21 - 3 4 5 6 7 8 9图 6 往后翻页的可能性分布 这样，我们就一定程度上预测了用户翻页的行为。我们可以采 取一定的预取策略，即在用户翻第 i 个页面（ i=2）的时候，我们可以先把第 i+1 个页面取过来。 用 用 结构和配置 体结构 在原来的天网系统中，已经采用了 技术 ， 具体 方法是这样的：当用户提交由一组关键词组成的查询的时候，系统就 判断这个查询对应的记录是否在 存在，如果不存在，则按照 讲的方法把查询递交给服务结点，把服务结点返回结果的综合的文档号序列存到一个文件中，在 保存所存储的序列在文件中的偏移值。如果已经存在，就从 获得这个存储记录 的偏移。然后，先从文档号记录文件中读取文档号，再根据文档号在网页数据库中获得网页的信息，组织成页面返回给用户 单松巍 ,2000，如图 示 。这样的结构对 容量要求比较小， 一个标志的长度是一组查询词的最大长度，一个数据项的长度是一个指针的长度。 在 001中，是根据 用户的查询（包括了考虑用户翻页的输入），产生结果页面，然后直接把结果页面缓存到 去，这样的结构会 有比较大的容量要求，一个标志是一组查询词的最大长第 四 章 通用 搜索引擎检索端应用 - 22 - 度加上一个整型长度（存取页号），一个数据项的长度是一个结果页面的大小。 有的 用的体系结构 新设计的 用的体系结构 图 7 两种 构的比较 用户 递交查询 返回结果网页 是否在 否 是 分布服务结点查询 文件读取文档号序列 文档号结果组合排序 读取文档信息 组织显示页面 用 户 递交查询 返回结果 查询 是否在 否 是 文件读取文档号序列 文档号结果组合排序 组织显示页面 查询 是否在 否 是 文档数据库读取信息 分布服务结点查询 第 四 章 通用 搜索引擎检索端应用 - 23 - 我们设计的结构 ， 是上述两种方法的一个综合。 改进后的情况如图 示。 可以看到，在我们现在的结构中，一共有两 次 使用。 其中 储的是包含翻页号的查询的结果网页 ，在本系统里，单个结果页面显示结果数量是 10，所以这里就需要存储 10 个相关网页的信息 。 储一个查询对应的结果文档号序列在文件中存储的偏移量，这就不考虑翻页号，在 只储存一个偏移，而在文件中存储了所有 结果组成 的序列。 引入是为了 缩减读取文档号以及根据文档号从文 档 数据库中获得文档信息 所带来的时间消耗。 引入是为了缩减分布式的查询和运算带来的时间消耗。 另外，根据前面的分析，我们考虑预取策略是，当一个查询查询翻到第 i 个 (i 2)页面的时候，我们就模拟产生一个相同关键词的第i+1 个页面的查询。很显然，这个模拟查询不需要经过图 全过程，只需要在 模拟就可以了，因为 储的是一个查询的所有文档号信息 ， 不同的翻页，对于它不产生影响 。 存配置 下面我们具体考虑两个 该选择的容量，替换 算法和预取策略。 通过通用 测试模块日志的模拟，我们得到了一些数据结果。 在 使用 ，各个算法和容量大小 与命中率的关系 比较如图 8 所示 。其中 a 是总体的情况，数据项的个数范围是 0,32000， 据项的范围是 0,2000。可以看到，当数据项 比较少 的时候 效果比较好，而数据项比较大的时候 较好。因此， 比较好的一个替换算法，当存取 2000 个查询结果的时候，可以到达 20%的命中率。 存取 15000 个查 询结果的时候，可以达到 30%的命中率。 在使用 ，各个算法和容量大小与命中率的关系比较如图 9 所示。横坐标代表有多少数据项，纵坐标代表命中率。这里由于每一个数据项所占的容量比较小，所以我们可以存储比较多的数据项。可以看到，在存储数据量比较大的时候，各种算法的效率相差并不大，综合分析存取排序的代价， 以获得比较好的结果。 第 四 章 通用 搜索引擎检索端应用 - 24 - 0000 20000 30000 体情况 00 1000 1500 2000 容量情况 图 8 页面内容 命中率和容量关系 000 10000 15000 20000数据项数命中率 查询文档号命中结果和容量的关系 第 四 章 通用 搜索引擎检索端应用 - 25 - 下面我们考虑加入预取策略带来的影响。我们的预取策略就是当查询一组关键词，当用户翻第 i（ i 2）页的时候，我们获得第 i+1个页面放入 据前面的分析，页面结果 取 效果比较好，下面我们就用 法 比较是否采取预取策略带来的影响。效果如图 10 所示。我们发现，当采取预取策略以后，命中率会有大幅度的提高，但是通过和图 9 的比较发现和文档号存储 以 旧需要保留。 当然，引入预取策略必然会降低系统总的吞吐率，但是搜索引擎检索端所应该主要考虑的应该是响应时间，即对用户的返回结果的 快慢程度 ，命中率的提高，会减少系统的响应时间 。 000 4000 6000 8000 10000数据项项数命中率没有预取有预取图 10 采用预取策略的效果 间分析 我 们下面分析使用 效率的影响。 当不使用 时候，每一个查询所耗费的时间是 ： t t t t1 读 取 摘 要 组 织 页 面查询排序 (2) 这里，查询排序 时间 就是通过对分布的子节点的查询，获得文档结果集合，并根据相关度进行排序 所花费的总时间 。读取摘要就是根据文档结果号，从文档数据库中读取相应的摘要内容 所花费的时间 ，这里也只有考虑一个页面所能显示个数的文档摘要的读取 。 组织页面就是把相应的内容放入显示页面模板中去 所 花费的时间 ，所占用的时第 四 章 通用 搜索引擎检索端应用 - 26 - 间和前两项相比比较少，所以忽略不计 。 001采用的方法缩减了查询排序和读取摘要两方面的开销，即变为： C a c h e 1t t t t )*t C a c h e2 插入读取摘要查询排序获取1 ( 1 - 命 中 率 1 ） * ( 命中率1(3) 其中命中率 1 就是考虑了缓存结果页面的命中率，t 获取，读取和插入 需要的时间。 单松巍 ,2000采用的方法，缩减的是 查询排序 的开销，它获得的结果是： C a c h e 2t t t* t tC a c h 入查询排序获 取 2 读 取 摘 要 ( 1 - 命 中 率 2 ） * （ ） 命 中 率 2 (4) 其中命中率 2 是缓存结果文档号 命中率。 本方法采用了两层 结构，同时缩减了查询排序和摘要读取的时间，耗费的时间是： 41C a c h e 21( 1 t + * tC a c h eC a c h 插 入 C a c h e 2查询排序插入获 取 读 取 摘 要获取命 中 率 1 ) * ( ( 1 - 命 中 率 2 ) * ( ）+ 命 中 率 2 *+ 命中率(5) 各个变量的含义和 (1)(2)(3)中的含义是一样的。 下面给出 通过统计 获得的 各个部分的耗时 。其中， 插入时间和 获得内容的时间分别是以 以页面存储 命中率为 20%，文档号 命中率为 60%作为示例。可以得到 表 2 的分析结果。由于页面存取 命中率比较低，所以只是采用页面存储 时间消耗会比较大，因为根据设定， 80%的查询还需要通过原来的方式查询各个索引节点的倒排文件。只存取文档号的 需要访问存放文档号的文件，以及访 问文档数据库获得文档的部分信息，即会经过两次 作，那么这里面消耗的时间也比较多。当采用两级 情况下，就会有比较少的时间代价，显然它比只用以上的任何一种都好。 最后我们考虑一下使用预取策略以后的时间代价。从响应时间第 四 章 通用 搜索引擎检索端应用 - 27 - 来看，由于页面存取 命中率的大大提高，仍把数据代入 (5)， 变量 数值 (秒 ) 说明 询 排 序 总 时 间 定 得 摘 要 时 间 10%) 入 页 面 e 时 间 代 价 10%) 取 页 面 信 息 时 间 代 价 60%) 入 文 档 号 间 代 价 t 获取(60%) 取 文 档 号 的 时 间 代 价 用 均 用 时 001的 查 询 平 均用时 单松巍 ,2000查 询 的 平 均用时 文 查 询 平 均 用 时 表 2 不同层次结构 时间影响 获得的时间性能会优表 2 中 命中率为 40为例，可以得到 t= 此对于某一个用户来说，返回结果的速度一般会变快。但是，由于对于将近 50%的第 2 页及其以后的翻页，我们都需要预取下一页的结果 。 从吞吐率上考虑 ，对 100 万个查询，不采取预取总耗时是 00000=740000 秒 ， 而 采 取 预 取 策 略 总 耗 时 000000*(1+832000 秒。吞吐率反而降低了， 因此如果我们系统的负载比较大，即查询 密度很高 的话，我们 采用预取策略 并不好。 第五章 总结和进一步工作 - 28 - 第五章 总结和进一步工作 本文的主要工作是设计了一个通用 模块， 此模块具有通用，高效和具有 自测试能力。它 在容量，替换算法，层次结构，预取策略等方面，都可以由用户 通过对配置文件的配置进行调节 ，因此可以应用于不同的场合。它采取了多层次的体系结构，对用户屏蔽了存储的细节，也提高了并发度。 在分析了天网日志以后，证实了对于搜索引擎的查询具有很强的局部性规律 ，另外获得的一个启发是当用户点击某一个序号大于 1的结果页面以后，就会很可能点击它的后续页面，因此我们决定了一个预取策略。 在应用中，采取了两层的 构，分别存储结果页面和结果文档号，尽量的减少存取和计算的开销 。对于两层 构，发现 页面结果 用 替换算法结果比较好，而文档号 采用 能获得比较好的结果。 下一步工作可以是把通用 通用性进一步提高，满足分布式系统的要求，对于一个应用的需求， 把结果缓存到不同的主机上。另外 ， 也可以把通用 块 应用于更多的方面 。 参 考 文 献 - 29 - 参考文献 . 003 M. N. J. L. W. . RL of 2003.