【毕业学位论文】（Word原稿）“天网”高性能分布式检索系统的设计与实现-计算机系统结构网络与分布式系统

北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 1 1 序言 信息检索 (计算机科学与工程领域长久以来被广泛研究的技术，有很多专门讨论它的期刊和学术会议，例如美国国家标准局 (文本信息检索会议 (1美国计算机协会 (有自己的会议 究信息检索。同时信息检索还和数据管理技术 (比如数据库 )的研究交叉在一起，可以说，自从人类使用计算机管理数据等信息，就产生了信息检索的需求。计算机 在人类社会的广泛应用，促使我们进入了所谓的“信息化时代”，以计算机作为强有力的工具人类才有能力处理、存储大量电子化的信息，信息规模与日俱增，也使人类面临“信息爆炸”的威胁。如果不能有效的使用这些信息，我们就会被淹没在信息的海洋里，造成“信息过剩”和“信息垃圾”。信息检索的目的就是帮助用户找到自己感兴趣的信息，过程可以简单描述为：用户提交查询请求 (通常是关键字 )，系统返回与用户查询相关的信息。信息检索要解决的问题不是一成不变，它必须跟上人类信息爆炸式增长的现实。 九十年代以来，获得了飞速发展，彻底的 改变着人类的工作和生活。据计算机世界网 ()报道，美国网址专家凯利研究后指出：“ 自网景公司于 1995 年申请上市以来的 2000 天中，人类居然创写了 30 亿网页，建立了 2000 万个网址，而传送的电 子 邮 件 就达 3 兆 5 亿则之多 。 网址还将继续扩张多元发展，但只有少部分是为了营利赚钱，而其他部分则是启发自热情、热心及公共责任，亦即是一种对未来也许可用于经济用途的信心。在这 30 亿网页中，事实上只有 30%是由公司企业所创写，其他 70%都是由非营利机构与一般民众所创作，显现网址人所要的是相 互分享。 ”总之，互联网 (渐成为了信息时代人类发布、交流和共享信息的载体，极大地促进了人类知识的增长和传播。 中国也获得惊人的发展。根据 国互联网络信息中心 )在 2002 年1 月的统计信息表明 1，我国上网计算机数约 1254 万台，其中专线上网计算机数为 234万台，拨号上网计算机数为 1020 万台；我国上网用户人数约 3370 万人，其中专线上网的用户人数为 672 万，拨号上网的用户人数为 2133 万，同时使用专线与拨号的用户人数为 565 万。除计算机外同时使用其它设备（移动 终端、信息家电）上网的用户人数为 118万。我们北京大学计算机系网络与分布式系统实验室开发的“天网”系统在对中国国内互联网的一次搜集结果显示 2，共收集到网页 47,707,998 个，涉及到 46,669 个 中不重复的网页为 22,382,623 个，平均每个站点有 不重复的网页。 不断增长形成了人类历史上最大规模的分布式海量信息系统，如何帮助人们有效的利用这些信息就成为当务之急，而首要的任务便是发现信息 人们迫切需要有效的 航工具，协助用户找到所需的信息。信息检索和 术二者结合，就催生了 的搜索引擎 (它代替原始的人工目录系统，成为人们在互北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 2 联网上查找信息的有效工具，被认为是在 除电子邮件、浏览器之外使用最多的服务。 提供良好的搜索引擎服务，是各类大型门户网站的一个基本配置，而且对任何一个网站，提供对站内网页信息的搜索服务也是方便访问者必不可少的部分。 许多商业化搜索引擎伴随着 潮被开发出来，代表性的是 。 在提供对 30 亿文档 (其中包括 2,073,418,204 张网页 )的访问，利用高效的算法和庞大的机器资源，可以帮助用户准确地找到所需信息。 2001年调查报告显示， 借纯粹的搜索服务，在全球互联网络市场中取得 市场份额，名列第二，排名在雅虎之后，成为最成功的互联网络公司之一。与此同时，搜索引擎也成为各科研机构和大学学术研究的热点，每年的 术会议上和搜索引擎有关的研究题目都占很大比例， 是 学研究成果的商业化。如何有效的获取互联网上的信息，其重要性不言而喻。北京大学计算机系网络与分布式系统实验室研究开发的“天网 ” (索引擎自 1997 年 10 月正式在 提供查询服务以来，受到学术界和用户的广泛好评。我们一直致力于研制更高性能的搜索引擎，有效地开发利用 息资源。 在当今的信息社会，往往信息不是不足，而是太多，从大量无关、冗余和纷乱的信息海洋中方便快捷地找到对用户有价值的信息，就是信息检索 (解决的问题。不仅仅是 息资源，信息化的发展使得社会中的每个组织都有大量公开和非公开的信息资源，它们是社会组织自身拥有的宝贵财富，如何有效利用这些财富就是必须面临的问题。办公自动化系统 (文档数据库 (以及数字图书馆 (数字化资源的建立和使用，都需要一个高效的信息检索系统。信息检索被认为是解决信息过剩 (有效途径，可以说是信息社会的一项核心技术。 人类的数字化信息不仅有文本 (还包括图形、图像、电影和音乐等多媒体信息，但是文字信息是最基本和最重要的形式，也比较容易被检索和识别，相对其他多媒体信息有比较成熟的技术。本文 研究的对象限制在对文本数据库的检索，对于非纯文本文档通常要转换成文本信息，这并不降低我们所研究问题的重要意义。以“天网”搜索引擎为背景，通过对信息检索相关问题的研究、分析和实验，我们给出如何建立一个大规模文档数据库 (达到 )的信息检索系统，它首先是分布式（ 和具备很高的可扩展性（ 而且在并发查询负载下满足一定的性能要求 响应时间 (系统吞吐量 (以及由于系统硬件所产生的种种限制。最后，我们试图 分析在运行“天网”这类大规模系统中具体遇到的管理难题，结合学术界和工业界在系统管理研究领域的最新成果和方向，讨论了解决这个问题诱人的技术前景，并且对“天网”系统管理提出了自己试探性的研究建议。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 3 2 基本问题 信息检索的目的是从大量的信息资源库中找出用户所需要的信息，所以它涉及两个基本的方面。首先是如何表示、存储和组织所拥有的海量信息资源，使它可以被迅速访问；其次，我们如何表征用户的信息需求，如何确定哪些信息是用户所需要。前者是从计算机系统的角度看问题，后者是从人 用户的角度看问题，二者决定了信息检索的复杂性和研究的困难。广泛使用数据库 (术处理结构化信息，操作的数据对象是固定的，用户的每个操作执行的结果是确定的；信息检索处理的对象包罗万象，可以是半结构化、非结构化的信息，这决定了它们的本质区别。由于要处理任何可能的文档，高质量的信息检索系统需要拥有对自然语言内涵的理解能力，即获取信息 (不只是数据 (自然语言往往是模糊的和有隐含意义的，因此信息检索对用户查询生成的结果是非精确的，往往也无法精确化。 因此，衡量一个 统，必须从两个方面考虑：效率 (和效果(“效率”几乎存在于所有计算机领域，任何算法都需要从时间和空间上考虑取舍，比如响应时间、内存和磁盘空间需求。对于联机运行的信息检索系统，最重要的效率指标就是系统的查询响应时间和系统的查询吞吐量，没有它，系统就不可能被用户使用。“效果”指检索返回结果集的准确性，通常有两个指标：查准率 (查全率 (查准率定义为检索结果集中与用户查询相关的文档所占的百分比，查全率则是检索结果集中的相关文档占整个文档集合中的相关文档的百分比。由 于一个文档是否和用户查询相关很难精确判定，实际运行的系统并不大可能用这两个指标准确评价，但是它对研究仍然有很大参考价值。这两个指标可以被形式定义如下：假设整个文档集合是 D， D 的文档数是 N=|D|，用户查询是 Q， Q 的返回文档集合是 S(Q)，用函数 R(x , y)表示文档集合 x 中与查询 y 相关的部分。则查询 Q 的查准率是 |R(S(Q),Q)|/|S(Q)|,查全率是 |R(S(Q),Q)|/|R(D,Q)|。 信息检索的基础是数据管理和自然语言处理 (接限制着信息检索的方式和效果。用户需求可以用自然语言表达出来，但是计算机系统还无法准确的理解其内涵。因此，用户的意图必须首先被翻译成 统可以处理的形式。通常用户查询被表示成一系列关键字 (系统依据给出的关键字判定文档是否和查询相关。为了使得信息检索有较好的效果， 统必须利用 技术，从语义上理解信息资源，评价它和用户查询的相关度 (并依据相关度的排序后将结果返回给用户。 排文件 通过将用户查询和文档资源分解成独立的信息单元 (关键字 )，信息检索的问题 被简化 以关键字为信息单位检索。在数据的组织与管理上，对文档按照分解后的关键字建立索引，可以加快查询访问的速度。信息检索中建索引的技术有三种：倒排文件(下标数组 (签名文件 ( 4比较后得出结论：北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 4 无论从时间和空间上，倒排文件都明显优于签名文件。下标数组空间需求太大，可是说是倒排文件的一种扩充形式。倒排文件则灵活而高效，可以根据需要做不同的变通，成为最广泛使用的索引方法。 倒排文件分两部分：第一部分是由词汇组成的索引 (第二部分是记录对应的每个词的所有出现的文档集合，称为记录文件 (每个词的对应部分称为引文件的每个数据项是由词（关键字）和指向记录文件的指针组成。记录文件的每个数据项记录和一个词对应出现文档的列表。设 示第 j 个单词（关键字），示第 i 个文档， 第 l 次出现表示为 ( 示此次出现的属性 ,它除了包含出现的位置 l,在非纯文本中还可以有其它被赋予的属性，比如此次 可 以根据单词出现处字体的大小计算。一个文档按照单词切分后，相同的单词出现合并在一起，形成 ( , 表示 所有文档的 ( )按照前面所述两级结构组织成根据单词的索引后，倒排文件就建立起来了，如图 示，单词 应的 ( a*)+( di+k , fi+k, a*)+ ， 示 出现次数，也是后面 a 的数量。这是倒排文件的全文本索引 (式 ,它记录了每次出现的位置等信息，要占用较多的存储空间。简化的形式是 ( 可以设定的权值函数 f( , 更简单的方法是 于 现的频率 n。 图 2 . 1 倒排文件 长记录 短记录 索引文件 记录文件 索引文件项格式： w o r d + p o i n t e r ( 指向记录文件 ) 记录文件项格式： ( ) + ( k, )+ 记录项内部按文档号成增序排列 利用倒排文件，系统可以根据用户提交查询中的关键词快速找到相关文档。当对大量文档索引时，会出现一些关键字对应的记录项很大，严重 影响检索的性能，后面我们会详细讨论。信息检索中用户的查询有两种基本的形式： I. 布尔 (询，用逻辑操作 (接关键字。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 5 位置邻近查询 (要求关键字在相邻的范围内。这对查询词组(重要，可以提高检索的准确度，但是要求必须在索引中保留关键字的位置信息，增大了对磁盘空间的需求和查询时的 I/O 操作。 倒排文件可以有效的支持这两种查询操作，由于每个关键词的记录项内按文档升序排列，只要顺序扫描数据就能过滤不相关文档，在内存中的运算很快。 为优化查询速度，可以不支持“或”，使每次操作的结果集始终不断缩小。操作应该从对应文档集合最少的关键词开始，能降低算法复杂度。假设关键词 应的文档记录集合为 P(则两个关键词 作的复杂度是 P(, |P()。每次操作的结果会成为下次操作的输入，影响后面操作的复杂度。在内存允许下，使多个关键词一次同时参与运算，会大大提高执行速度。 关度评价 信息检索的一个核心算法是如何在用户查询 (文档 (间做相关度评价 (这直接关系到查询“效果”。最基本的评价方法是利用向量空间模型 (概念 ,查询和文档都被认为是由所有关键词组成的 关度可以根据它们的向量计算出来。这种方法重要的改进是注意到每个单词在向量中应该被赋予不同的权重参与计算相关度。自然语言中信息单位出现的频度是不一样的，甚至相差很大。信息论原理告诉我们：事物出现频率越大，携带的信息量越小。 s 0表示为： (2这意味着语言的信息项 出现的频率和它的权值成反比，出现频率很高的单词携带的意义非常少，比如英语中的“ ,汉语中的“的”，这些高频词在信息检索中可能需要特殊处理。著名的 此得出，它可以被表示成： d lo g（ 2 N 是所有文档的总数， 示单词 t 的文档频率 (由于 单词在语言中的统计特性，新文档的加入对它影响很小，可以在一次计算出后作为单词的属性使用。单词 文档 的出现频率表示为 ，那么它的复合权值是： = * (25提出了一个经验公式，用文档的长度修正复合权值，消除因文档大小不同带来的误差。文档向量 d 和查询向量 q 的相关度比较通过两个向量的夹角计算： c o s (2n 是向量的维数， 向量 q 和 d 的分量。结果越大，两者的相关度就越高。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 6 我们考虑另一个语言统计特性 语言信息单位的 TF( 单词在语言中出现的概率。设文档 分后的单词数是 DL(它可以作为文档的长度。所有文档切分后的单词总数 ： )( (2那么，单词 TF(： 1) di t j,()( (2语言中单 词的 TF(信息检索的效率 (效果 (个方面都有很大影响。一种语言的词汇可以分为两部分 基本词汇和专业词汇，它们表现出不同的 TF(专业词汇具有高的 较低 TF(可以区分不同领域的文档，在信息检索中更具意义。然而，语言中单个的“词”的含义往往没有足够的含义，要用多个单词组合成的词组 (示更确切的意思 6。比如英语中的“ 属于计算机中的专业词汇， 切分以后的任何单字都不能表示这种含义。所以，词组的 TF(能由它的各组成部分计算出来（例如相加得出）。如果对词组索引匹配，检索的准确度将大大提高。 这种情况对汉语尤为重要。汉语的造词功能很强，通过字的组合创造概念，英语更多的是造单词。比如汉语中“激光”用“激”和“光”组合，在英语中则创造新词“ 汉语中用词组表达确切的含义，在单独一个“字”的意义很弱。汉语文档的索引可以是基于“字”或者基于“词组”，基于“字”的索引会造成词组的整体语义的丢失，比如查询“华人”会检索出“中华人民 共和国”。根据单个的字统计规律得出的 汉语中的有效性也大大降低。在英语检索中，通常将高频的“ a, 单词视为“ 忽略词），不会对检索的效果有太大影响。汉语中，高频词（比如“的，中，在，大，有”等）可能参与组成词组，如果这些字被忽略会严重影响某些查询，例如“美的”（作为商品的商标）和“王大中”（人名），“的”“大”“中”字是不能被忽略的。总之，由于汉语和英语的差别，汉语倾向于使用基于词组的索引，后面我们将详细讨论这对检索效率的影响。 统运行模型 一个完整 的现代信息检索系统不仅要对用户提供检索 (能，还要同时支持浏览 (档 7，如图 示，这两个功能现在都可以通过 术实现统一的用户接口。检索系统可以由用户和文档数据库分成两部分，和用户交互的部分视为系统前端，数据库相关部分视为系统后台，它们通过中间的检索和浏览两大功能子系统连接起来。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 7 图 2 . 2 用户和检索系统的交互（取自 7 ） R e t r i e v a l B r o w s i n g 数据库 ( D a t a b a s e ) 后台部分完成系统中文档资源的维护功能，可以设想它是整个系统的起点，原始的文档信息由此才能进入系统内部。在后台操作员 的控制下，数据库的文档可能不断变化，如文档增加和删除。根据具体的应用不同，这种变化会定期或不定期导致检索和浏览两个子系统数据的更新，虽然大部分信息检索系统并不需要这种变化被实时处理。检索子系统中索引必须重建，根据需要可以采取不同的策略（动态的、增量的、实时的、批量的），由于重建索引的代价巨大，必须尽可能减少它发生的频度。 前端负责和用户接口，它不仅向用户提供信息（返回查询结果，让用户浏览文档），还可以通过和用户交互获得有用的信息 8。系统应该可以全程跟踪用户使用系统的行为，比如在某段时间内查询的内容（用户 感兴趣的主题和事物），浏览的文档。这种信息包括用户的个体行为和用户的整体行为（统计结果），它可反馈回系统，改进系统的检索质量，比如根据用户的查询词学习新词，对用户经常查询的关键字做缓存，甚至可以根据用户浏览文档的行为改变文档的重要性，以此影响查询结果的排序。我们对信息检索系统中用户的行为模型做出如下推断： 1) 信息检索系统中的个体活动模型。每个用户的活动是带有目的性的 查找某一方面的信息，检索和浏览两种行为交替进行，相邻的查询相关度很大，后面的查询可能是前面查询的优化（ 即： 查询 浏览 优化的查询 。这里的浏览包括用户阅读查询结果集合和阅读文档，它可能是一个很长的时间间隔，甚至用户可能终止进一步查询，称它为思考时间（ 2) 信息检索系统中的用户统计模型。单个用户和系统的长时间交互中，检索内容呈现出个人的偏好，这与他的本身的工作、学习和兴趣有关。大量用户在某段时间的检索内容表现出相关性，同一主题被许多人感兴趣，这就是所谓的“热门检索词”。 由此可见，检索系统和数据库系统的用户活动的巨大差别，认识到这一点很重要。根据这两个推断，我们可以采取一系列措施优化检索系统 的性能和质量，分析系统真实的工作负载和用户查询的并发度。 检索和浏览子系统对前端服务接口可以被抽象成如下的基本命令： 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 8 I. 查询命令（ 输入参数为用户的查询字符串和其它信息字段，返回查询结果集合。 读取文档命令（ 输入参数为文档标识，返回该文档的内容本身供用户阅读。 读取摘要命令（ 输入参数为文档标识，返回该文档的摘要信息。 提供读取文档摘要命令，使用户可以快速了解文档的内容。用户在浏览查询结果时，系统显示文档的摘要部分， 这是信息检索系统必要的功能。 图 2 . 3 信息检索系统运行模型 前端交互系统 文档浏览系统 查询处理 文档数据库 索引数据库 数据管理系统 索引系统 查找 相关度评定 索引重建系统 后台维护系统 用 户 反 馈用户反馈 检索和浏览子系统对后台的维护服务接口很简单，输入参数是要被删除的文档和增加的文档，它由后台维护系统选择时机调用。实现这部分功能的困难在于，如何降低索引重建的代价（对大规模数据重建索引需要执行几个小时）和在系统提供正常检索服务的情况下执行重建，同时要保持系统中索引、文档和摘要三部分的一致性和进行失败恢复。如果将此功能当作“事务”执行，应该归为“长事务”（ 9，不能用传统的事务很好描 述。 11描述在一定资源限制下大规模文本的索引创建问题， 1213北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 9 讨论动态和增量方式更新索引中的不同方法和会遇到的各种问题，虽然具体实现和底层的数据管理系统有很大关系，前面所指出的困难却是普遍的，必须根据不同方面的要求做出一定取舍。 根据以上对各系统部分的分析，我们得出如图 系统工作模型。数据管理系统在底层提供文档及索引的存储管理功能，前端交互系统和后台维护系统是系统和外界交互的窗口，检索、文档浏览和索引重建是系统运行的核心（关于索引重建的详细流程并没有在模型图中表示出来）。这个系统模型，作为 一个通用框架，有助于我们在具体应用中对问题的分析、理解和设计。 用案例 现代信息检索最重要同时也是使用最广泛的应用毫无疑问当属 的信息检索服务（ 搜索引擎，如前所述，这是和互联网一起飞速发展的技术。搜索引擎的特殊性表现在： 要索引海量数据。平均每个网页的大小是 10K 字节， 20 亿网页就是 20T 字节的数据，并且网页的数量每天都在增加。 信息通过搜集系统从互联网上获取，由于网页处于不断更新状态，如何建立高效的搜集器和动态更新索引，就非常关键。 信息的 异构性很强，没有任何前提限定，有多种语言存在。 信息存在形式主要是 内部包含丰富的格式信息，以超级链接相互引用，这决定了它有独特的相关度评价（ 术。 图 14给出的一个搜索引擎通用结构，相对一般的信息检索系统增加了从 搜集网页的功能，更大的差别在于系统内部对网页的分析技术，它对提高搜索引擎质量至关重要。 的网页通常比较短小，缺乏足够的自我描述信息，而它们之间的相互链接正好在全局对网页作了补充说明。超链分析（ 以挖 掘 的隐含信息，改进查询的准确度，比较典型的技术是 14有较为详尽的描述。 具体的索引数据结构和系统实现，可参阅 15，它是 一个原型系统。搜索引擎在扩大数据规模的同时，必须满足互联网上大量用户查询产生的系统负载，所以“效率”也是商业搜索引擎系统成败的关键。 信息检索另一个重要的应用是“数字图书馆”（ 它利用数字化技术扩充和增强传统的图书馆业务。所以，数字图书馆不单是一个信息访问的工具，而是要支持各种数字图书业务的 环境。和 息搜索不同，图书馆的信息是要经过“整理”后的，比如目录分类。 16提出一个被广泛接受的数字图书馆构架，它包括用户界面（ 文档库（ , 句柄系统（ 查找系统（ ,如图 示。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 10 图 2 . 4 搜索引擎的通用结构（摘自 1 4 ） 图 2 . 5 数字图书馆的主要构成（摘自 1 6 ） 用户界面包括两个部分，一个是对图书馆的用户，一个是对图书管理员和管理信息资源 (系统管理员。每个界面都是由两部分组成 标准的浏览器（ 京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 11 和客户端服务系统（ 后者是前者与系统交互的中介。文档库管理和存储数字化对象， 议（ 是它的统一访问接口。 来识别各种资源的全局标识符，可以很长时间存在，是资源的元数据（ 查找系统发现文档库中的信息，属于很典型的信息检索。从计算机系统看，这个结构和前面的信息检索模型本质相同，现实中，数字图书馆还 涉及到法律的问题。 以上我们较为详细介绍了信息检索系统的原理和应用实例，显示出它的具体应用实际上是由多个部分相互协作组成的有机整体，复杂的结构和运行环境决定整个系统必须以分布式实现，搜索引擎和数字图书馆都证明了这一点。系统数据规模的不断扩大，使得“效率”始终是必须考虑的问题。我们开发的新一代“天网”搜索引擎，要求规模从原来的索引几百万网页扩大到可以支持上亿篇网页，同时必须保证良好的性能，为此，搜集系统和检索系统都分别被分布式化。下面根据我们在“天网”系统开发中的实践，讨论实现分布式检索系统中如何解决规模和 效率这两个问题，其方法对于任何信息检索应用都有普遍意义。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 12 3 单机系统的检索性能分析 单机系统的检索性能是分布式系统的基础，为了预测在分布式环境下的系统整体性能，必须确定单机系统中数据规模和性能的相互关系。我们的问题是利用当前水平计算能力的商用机器（ ，工作站），在一定性能（ 求下，可能支持的数据规模（ 并且讨论系统的瓶颈和提高系统性能的各种方法。 用计算机性能分析 由于集成电路和计算机体系结构等方面的发展，计算机的性能获 得长足的进步。但是，计算机系统不同组成部分之间的增长是不均衡的，使得系统在实际应用中性能下降。在过去二十年中， 性能几乎增长了 10， 000 倍；单机系统的内存容量也从少于 1B 的量级 ,大约增长了 1， 000 倍，存取时间达到 ；磁盘容量也从几百 加到现在的 30是， I/O 的访问速度却仅提高了不到一百倍（从 00在应用领域，大量信息处理的快速增长和多媒体信息普遍应用，增加了对数据存取的需求，使 I/O 系统和外部存储设备访问愈发成为计算 机系统的瓶颈。信息检索作为一个数据密集应用（ I/O 乃是系统性能的关键，在 三个因素中，我们重点讨论磁盘 I/O 对系统产生的限制。 表 族树 us us 5 MB/s 0 10 MB/s 0 6 20 MB/s 0 20 MB/s 0 6 40 MB/s 0 6 80 MB/s 0 6 160 MB/s ， 相对于 面用的 线 ( 较高的速度，可以接多个设备，在 I/O 高负载下消耗 间少（ 耗 间 5%,0。其各种标准的性能如表 示，从最初的 5MB/s）到即将出现的 320MB/s） ,性能提升很快。实际可用的带宽要小于标准值，比如现在用的 际带宽是 150MB/s。 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 13 磁盘容量的虽然不断扩大，访问速度却改进很少，这由磁盘本身的特性决定（包含机械部分）。磁盘包含度多个盘片（ 1盘片表面分成多个磁道（ 所有盘面在同一垂直位置的磁道组成柱面（ 每个磁道被分成固定大小的扇区（ ,它是磁盘最小的寻址单位，又称作块（ 磁盘访问（读、写）某个块，必须首先将磁头转到所在磁道（寻道时间， 然后等待所在扇区到磁头下面（旋转延迟，最后是读取扇区上的数据块（传输时间， ,总的磁盘访问时间还要加上磁盘控制器执行 I/O 的代价，称为控制器时间（ 寻道时间取决于当前磁头位置和目的磁道的距离，通常取平均值表示性能，现在高性能磁盘的平均寻道时间大约在 10下，是 I/O 访问延迟的主要部分。旋转延迟取决于磁盘转速，10000磁盘平均旋转延迟（转半圈）是 3据的传输时间是数据大小除以内部传输速率，较高性能磁盘的内部传输速率可以达到 20s。表 一些磁盘的性能数据， 表示磁盘每秒钟可以执行的随机 I/O 操作，它可以根据平均访问时间计算得到。总的来说，磁盘的响应时间在毫秒级以上（平均 10每秒钟可 以完成的I/O 操作也很有限（ 均是 100，即达到平均每秒种 100 次 I/O 访问）。而且，具体的性能受数据存储的位置和应用访问的模式影响，不良的数据存储管理将使性能严重下降。 表 一些磁盘的性能数据 MB/s) 6 36 0,000 119 15 0,000 715 5,000 83 0,000 116 2655 ,200 9前单个磁盘的平均数据传输速率 仅 25MB/s，不能完全利用 线的全部带宽，进一步提高性能的方法之一是采用并行磁盘技术 N 个磁盘组成的阵列可以使数据传输速率获得接近 N 倍的提升，并且可以提高 I/O 请求的响应时间（同时也增加了 这是以增加系统硬件成本为代价的。为解决 I/O 产生的瓶颈，工业界开发出了更加先进的外部存储技术，如光纤通道（ 存储区域网络（ （的 15 就是一种 光纤通道，其性能指标要高出普通硬盘很多）。可以认为，随着磁盘的平均数 据传输速率从 10MB/s 到 100MB/s 甚至更高的提升，成本北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 14 也会随之上升。应用中要根据实际需求，在成本和性能之间做出选择。 引数据管理 存储设备性能可否充分利用，还要受操作系统、应用程序（存储管理、缓存管理）的影响。 应用程序要调用操作系统提供的 I/O 服务功能 ,它有几种不同的方式，如图 文件系统的调用接口或 I/O 库函数，优点是可以利用文件系统的缓存和预读机制，缺点是数据要经过多次拷贝。原始 I/O 不通过文件系统，直接读写磁盘。一些操作系统提供直接 I/O（ ），它在文件系统支持 下实现和原始 I/O 类似的功能，没有系统缓存、多次拷贝等开销。另一种减少 I/O 开销的方法是用文件映射（ 统调用），将数据映射到内存空间，直接读写内存，不存在多次拷贝的问题。文件映射的缺点是失去了 I/O 操作的原子性语义，在并发读写中要实现互斥操作。 图 3 . 1 L I N U X 操作系统的 I / O I / O 类型： 原始（ R a w ） I / O ，在数据库中使用。 其它是通过内存映像访问数据。 U s e r U s e r b u f f e r S y s t e m c a c h e M e m o r y m a p p e d D e v i c e 1 2 3 4 5 1 不通过文件系统的原始 I/O 。 2 用 r e a d / w r i t e 系统调用的 I/O 。 3 用 f r e a d / f w r i t e 标准库函数调用的 I/O 。 4 文件系统的元数据。 5 文件系统元数据更 新。 使用文件系统的另一个缺点是文件系统的数据组织往往不能提供应用程序最好的性能。 文件空间分配是直接索引、一级索引、二级索引和三级索引的组合，最坏情况下访问数据要读四次块（大文件）。文件系统一 般的预读策略是提前读，数据块缓存用 法，这些都是对应用程序透明的，不能做到应用级优化（ 数据库一般绕过文件系统，使用自己的存储管理和缓存，优化应用的性能。 倒排文件本质上是关键字到它对应项的索引，一般地，关键字通过字典（ 找，转换成整数作为关键字的标识（ ,索引管理实现从 对应项的访北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 15 问。在“天网”中，用两级文件模拟这种结构，如图 示的，第一级文件中每个结构项是 ( 向二级文件的指针（ 应项的开始） , 应项大小。每次建索引，关键字的 是重新生成，是连续的整数，数量大约 200 万个。由于一级文件并不大（可以读入内存），每次只读取几个字节，其代价可以不考虑。二级文件中，一些关键词的对应项很大，才是影响倒排表查询性能的关键。用文件实现的缺点如前所述，好处是简单易于实现。 如果系统维护统一的字典，关键字和标识（ 映射不变，每次创建倒排文件产生的 不是连续的，二级索引将不再适合，更一般的方法是用 B+树 组织倒排文件。 17讨论在关系数据库之上实现倒排文件，利用成熟产品提供的高性能数据管理，缺点是增加了不必要的开销，比如 询接口。面向对象的概念更能简洁地描述倒排文件的结构，采用面向对象数据库系统（ 更好的选择。 1819用持久对象存储（ 理倒排文件， 但提供基于对象的数据缓存和良好的磁盘空间分配策略，还可以用它高度的可扩展性，根据数据的特性定制存储。 021是商业上最成功的面向对象数据 库 系统（ 之一，它用内存映射技术实现 持久对象存储，和程序语言（ C,C+,全集成，既有程序设计语言的灵活，又可以高效的存储数据，是另一个很好的索引管理工具。 嵌入式数据库系统 B） 22,是一个开放源代码产品，它提供简单高效的功能（三种访问方法 B+，实现 存取，这已完全能满足索引管理的需求。 B 以库的形式存在，在多种程序设计语言（ C, C+, 中支持显式的数据库访问编程接口。 23讨论了在 目中用B 管理倒排文件的具体实现细节，由于它的开放源码特点，也是一个不错的选择。 由于前面所述的磁盘结构特点，提高访问效率的存储分配策略可归结为：将同时访问的数据块分配在磁盘相邻的扇区，称“簇集”（ 如果系统存在多个磁盘（ ,可以将同时访问的数据块分配在不同的物理磁盘上，称“解簇” （ 在查询处理时，倒排文件中 应的 被顺序扫描（ ,过滤后得到满足条件的文档集合，这种顺序访问模式要求每个 好存放在连续的扇区， 面向对象数据库 系统通常可以提供此种能力（比如 用户可以定制对象的存储分配管理 ）。 倒排文件中 度差别很大，为提高效率可以区别对待。高频词（ 度通常 1上（随着文档数据库规模增大，它会快速增长），称作“ 如果对它作顺序访问，从磁盘读入内存会耗费很长时间，同时占用系统大量的 I/O 带宽，从而降低整个系统的吞吐量。解决的方法是将对 顺序访问变成随机访问（ 24， 25, 按照“文档号”分割成长度较小的数据块，在“ “ 作时可以有选择地访问部分数据，不可能相关的文档所在数据块被“跳过”（ 它增加了按照“文档号”索引数据，以空间换取时 间。假设关键词 应的 ( |P(表示 P(文档的数量，两个词 “ “ 北京大学硕士学位论文 “天网”高性能分布式检索系统的设计与实现 16 |P( 远远小于 |P( ，读 P(内存中，程序只需根据 P(文档号，读取 P(包含该文档的数据块。算法的效率提高取决于 |P( 要远远小于 |P(，即至少有一个运算项的 高（关键词只在以一小部分文档中出现），这对多个运算项的同时操作一样适用。 自索引倒排文件（ 24表明， 以大幅度降低查询所用时间。然而，此算法要求 以被定制存储和组织，必须使用 面向对象数据库 系统管理倒排文件，或者从头开发全新的索引管理系统。 另一个改善性能的技术是缓冲区管理，利用文件系统的缓存往往不能得到最佳的性能。前面得出的个体用户行为模型表明，在一段时间内相同的关键词可能被同一个用户反复查询。根据 顺序访问模式，可以采用基于对象 的缓存，对象持久存储中的双向缓冲区 27将对象和分页缓存结合起来，是一种更佳的策略。在信息检索中，低频词的 度小于一页，被检索的频度也很低（很少在短时间被不同的用户查询），应该将多个小对象合并缓存在同一页中。对很高频的单词，由于它对查询准确度的提高很有限（有些系统将它们作为 略，不建索引），缓存整个它的 占用大量内存，少量的高频词就可以耗尽所有的内存 ，所以缓存高频词的 得