（计算机软件与理论专业论文）中文搜索引擎的设计与实现.pdf

i 摘要 搜索引擎是 web 信息检索的主要工具crawler 是搜索引擎的核心组件用于 搜集 web 页面实现一个可扩展高性能大规模的中文搜索引擎核心是设计一 个可扩展高性能大规模的 crawler 考虑到 web 的容量以及增长速度设计了并行 crawler 系统该系统由多个 crawler 进程组成每个 crawler 进程运行在一台机器上一台机器只运行一个 crawler 进程crawler 进程有自己的本地页面库和本地索引库它下载的页面以及 对页面建立的索引分别保存在本地页面库和本地索引库中 为了在各个 crawler 进程之间进行协调避免并行 crawler 系统下载页面重叠 设计了 url 服务器 它运行在单一机器上 用于在各个 crawler 进程之间分配 url 以及存放 crawler 进程新发现的 url考虑到数据库的负载实现了多数据库并行 存取技术 每个 crawler 进程就是一个小型搜索引擎这些搜索引擎一起组成了一个大规 模搜索引擎为了在多个 crawler 上进行检索设计了检索服务器它将用户的检 索请求提交给各个 crawler由 crawler 查询自己的索引库并将检索结果返回给检 索服务器检索服务器对结果排序输出 为了减少页面集批量更新的巨大开销研究了增量式 crawler它用于对页面集 中某些页面进行更新以便达到刷新整个页面集的目的但是增量式 crawler 需要知 道页面集中哪些页面发生了变化为此使用人工神经网络建立了页面变化模型该 模型可以预测页面下一次变化的时间从而确定对 web 上实际页面进行重访来完成 页面集的刷新任务 关键词搜索引擎神经网络网络爬虫中文分词 ii abstract search engine is a primary tool of information retrieval, and crawler is an essential component of search engine, which is designed to download web pages. to design a extensible, high performance and large scale search engine, the core task is to design a extensible, high performance and large scale crawler. given the size and increasing speed of web, a parallel crawler system is designed. the system is made up of multi-crawler processes. each crawler process runs at a computer, and each computer contains a single crawler process. every crawler process has a local page repository and a local index repository. the web pages downloaded are saved in its local page repository, and the index built is saved in its index repository. in order to coordinate between multi-crawler processes so that overlapping can be avoided, the url server is designed. it runs at a single server, to dispense urls between multi-crawler processes, and save urls that crawlers have found. given the overload of database, parallel access of multi-database is implemented. each crawler process is a small search engine, and all small search engines form a large scale search engine. the retrieval server is designed, which submits users request to all crawler processes, and every crawler retrieves in its local index repository, and then sends its search results to the retrieval server. finally the retrieval server collects all search results, sorts them and outputs. in order to decrease the heavy cost of local repository updating, incremental crawler is studied, which performs updating some old pages to refresh the local repository. a page changing model is built using artificial neural networks. based on this model, the changing time interval of pages can be computed, and crawler can revisit those pages to refresh the local repository. k e y w o r d s search engine, neural networks, crawler, chinese word segmentation 独创性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工 作及取得的研究成果近我所知除文中已标明引用的内容外本论文 不包含任何其他人或集体已经发表或撰写过的研究成果对本文的研究 做出贡献的个人和集体均已在文中以明确方式标明本人完全意识到 本声明的法律结果由本人承担 学位论文作者签名王 军 日期2004 年 11 月 7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版允 许论文被查阅和借阅本人授权华中科技大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索可以采用影印缩印或扫描等复 制手段保存和汇编本学位论文 保密在_年解密后适用本授权数 本论文属于 不保密 请在以上方框内打 学位论文作者签名王军 指导教师签名周英飚 日期2004 年 11 月 7 日 日期2004 年 11 月 7 日 1 1 绪论 1 . 1 课题背景 web 作为信息技术的载体已成为人们重要的工作学习生活娱乐工具web 的发展给人类生活带来了巨大的方便人们可以跨越时间和空间界限来共享大量信 息但是面对 web 上如此丰富的内容人们同时也感到无所适从太多的内容使 得迅速定位真正需要的信息变得更困难跟随一个一个链接uniform resource locatorurl在 web 上漫游则会浪费大量的时间而且很可能徒劳无功人们迫 切需要有效的信息发现工具来为他们在 web 上进行导航 最早出现的工具是目录导航系统 它通过有专业知识的网页编辑人员对 web 网 页进行精选建立一个索引目录来给用户提供服务这种系统的优点是提供的网 页准确率高网页内容质量高但覆盖的范围小而且不容易扩展这种类型的系 统典型代表是 yahoo目前 yahoo 已成为全球最大的门户网站 随后出现了搜索引擎系统搜索引擎是伴随 internet 的发展与信息量的急速增 长而产生发展起来的它们以一定的策略在互联网中搜集发现信息对信息进行 理解提取组织和处理并为用户提供检索服务从而起到信息导航的目的1-6 这类系统的优点是涵盖的网页数量巨大覆盖范围广容易扩展但搜索的准确率 比较低网页内容质量不高需要有较好的排序技术其典型代表是 google 搜索引擎采用全文检索为核心技术由于中文信息的固有特点使得国外许多 完善的搜索引擎使用的全文检索系统不能直接应用于处理汉字信息中文的语言文 化对国外搜索引擎产品是一个天然的屏障以中文全文信息为主的搜索引擎还是国 内自主开发的较多7-10但是如今这个屏障不存在了随着中国市场的开放国外 公司纷纷把目光转向中国在中国设立一个又一个研究院与国内相比他们有更 强的技术实力更大的人力资源优势以及更多的资金投入短短几年时间国外搜 索引擎企业就完成了产品的本土化迅速蚕食国内市场 搜索引擎市场竞争异常激烈一方面是由于它巨大的市场需求另一方面是由 于它潜在的经济效益特别是竞价排名的出现企业可以通过购买关键字来获得较 2 好的检索排名这种类似于拍卖性质的交易给搜索引擎厂商带来了丰厚的利润同 时也能给那些在线购物的用户提供更贴近的检索结果 激烈的竞争有助于搜索引擎技术的发展然而其浓厚的商业性质也必然导致搜 索引擎实现技术的隐蔽性关于搜索引擎实现技术方面的资料很少本文在参照了 几个为数不多的搜索引擎的介绍之后设计并实现了一个大规模中文搜索引擎为 以后进一步研究提供一个实验平台 1 . 2 国内外概况 1 . 2 . 1 国内外发展概况 国外搜索引擎发展较早有著名的 yahooaltavistagoogle 等yahoo是最具 代表性的目录导航式系统它为用户提供分类导航和关键词检索两类查询方式 altavistagoogle 则主要提供网络搜索服务它们依靠机器在 web 上自动搜索页面 并对页面进行索引 用户可以通过关键词查询信息其中 google 是目前使用最广泛 的搜索引擎它支持 35 种语言提供了便捷的网上信息查询方法通过对 43 亿个 网页进行索引 google 可为世界各地的用户提供性能良好的检索服务 现在 google 每天需要提供 2 亿次查询服务 国内搜索引擎随着中文信息处理技术特别是中文分词技术的发展出现了一些 优秀的中文搜索引擎11如百度慧聪百度是国内最大的中文搜索引擎索引页 面达到 1 亿 3 千万以上并且还在以每天几十万个页面的速度增长百度与 google 都采用相同的链接分析排名技术pagerank 12-13 但是 google 的排名技术做得更 好相比之下百度最大的优势就是提供了搜索帮助能根据用户提供的搜索关键词 提出相关搜索进一步协助用户提高查询的准确率 1 . 2 . 2 关键技术 这一部分讲述搜索引擎使用到的关键技术pagerank 技术中文分词技术以及 crawler 技术pagerank 是一种对检索结果进行排序的技术它在一定程度上提高 了检索质量中文分词技术目的在于提高检索的准确性减少无意义的检索结果 网络爬虫crawler是搜索引擎的核心组件用于下载页面进行处理14 3 1pagerank 技术 搜索引擎主要用到信息检索技术信息检索在计算机科学发展中是一个有着悠 久历史的领域20 世纪 70 年代基于图书馆档案馆对检索的需要信息检索开 始进入一个蓬勃发展的时期到 20 世纪 90 年代信息检索的研究已经相对成熟 出现了很多成熟的模型和算法其中向量空间模型和词频/倒排文档频率the term frequency /the inverse document frequencytf/idf算法对搜索引擎的检索技术起 到很大的影响15早期的搜索引擎基本上采用信息检索的相关技术 但是随着 web 的发展和人们对搜索引擎检索质量要求的不断提高原有的仅 仅依赖信息检索技术的搜索引擎检索策略已经不能满足时代的需要其原因在于传 统的信息检索技术有两个重要的内在假设 第一个假设是被索引的信息本身有着很高的质量至少在信息的组织和内容上 有着比较高的质量在 web 出现以前传统的信息检索之所以能够行之有效很大 程度上依赖这一点很多的信息检索产品一般都是针对一个特定的领域如法律信 息医疗信息环保信息等等这样就可以针对这个领域进行算法的优化 第二个假设是检索信息的用户有一定的相关技能和知识也就是说当用户面 对一个很大的信息源时他知道通过什么样的手段去提高检索的查准率但同时又 不降低系统的查全率与此相对应传统的信息检索系统总是提供一套十分完美的 复杂检索语法来满足用户的需要 但不幸的是这些假设在 web 上都已不再成立 第一个原因是 web 上网页的质量参差不齐 大量的网页组织性 结构性比较差 同时web 又是一个无所不包的载体它涉及到政治经济教育文化生活等各 个层面这就使得信息检索中的很多技术都派不上用场另一方面web 上充斥着 很多没有任何意义的网页还存在很多镜像的网页如果不采取相应的技术处理 将会在很大程度上影响检索质量 第二个原因是大部分检索用户是没有任何经验的他们经常只输入一个或者两 个检索词来检索他们需要的网页但会得到大量的返回结果很少的用户尝试使用 逻辑运算来提高检索的质量 基于以上的讨论人们发现原有的信息检索技术已经不再适应 web 的发展 4 必须改进原有的信息检索相关技术研究新的适合 web 技术的算法提高 web 检 索的质量 为了提高检索质量必须对检索结果进行有效的排序早期的搜索引擎单纯依 靠检索词出现的位置或者出现的次数来对检索结果进行排序它们认为检索词在网 页标题中出现或者在网页中出现次数比较多的检索结果应该排在前面显然这种排 序策略对于大量符合条件的欺骗性网页没有丝毫防备 为了解决网页排序问题 google 的创始人 sergey brin 和 larry page 提出了一个 对网页质量进行评估的算法 pagerank也称为网页重要性评估指标通过预先计算 每个页面的 pagerank 值将检索结果按照按照 pagerank 值进行排序 pagerank 来源于链接重要性的思想如果 a 网页有一条链接指向 b 网页那 么这个链接称作 a 的一个出链和 b 的一个入链把 a 叫做 b 的来源网页决定网 页重要性的因素包括入链数量和入链质量如果一个网页拥有很多入链(被很多其他 网页指向)就如同一篇文献被很多其他文献引用那么这个网页通常是具有较高质 量的重要网页此外如果指向一个网页的来源网页中有很多是重要网页那么这 种来自重要网页的链接比来自一般网页的链接显然更能体现被指向网页的价值16 google 在每次下载完页面后离线计算 pagerank 向量向量中的每个值对应 某个网页的 pagerank 值也就是网页的重要性每次用户提交检索请求google 将检索结果按照 pagerank 进行排序输出给用户计算 pagerank 是一个迭代过程 计算开始时每个页面的 pagerank 赋值为 1然后按照公式进行迭代一直到前后 两次计算的 pagerank 之间的平方差小于规定的值迭代结束得到每个页面的 pagerank 值 pagerank 基于 web 的链接结构计算没有考虑网页的实际内容在 google 提 出该算法之后taher h. haveliwala 提出主题敏感topic-sensitive的 pagerank17 主题敏感的 pagerank 的实现原理是预先选择有代表性的主题集合根据链接信 息计算每个页面在各个主题上的 pagerank 值在用户提交检索请求时将检索请 求归类到某一个主题根据该类主题的各个页面的 pagerank 值对检索结果进行排 序输出如果检索请求不能归类到某一个主题那么就直接使用不含任何主题的 pagerank 值 5 可以看到主题敏感的 pagerank 实际上是早期 pagerank 的扩展早期 pagerank 把所有的 web 页面看成一个主题因此只需要计算一次 pagerank而主题敏感的 pagerank 把所有的 web 页面看成很多主题的集合每个页面可以属于多个主题 但是在不同的主题之中同一页面的 pagerank 值不一定相同这种算法不仅考虑 了 web 的链接结构还考虑了页面的内容采用这种算法检索结果的排序效果比 早期 pagerank 算法好得多google 在 2003 年 11 月 16 日正式采用该算法 搜索引擎的好坏很大程度上依赖于检索结果的排序策略18-20google 使用 pagerank 算法获得了巨大的成功使得 google 从诞生到现在 6 年时间里一直深受 用户好评 2中文分词技术 词是最小的能独立活动的有意义的语言成分因此通常的搜索引擎都是 以每一个独立的词为单位建立索引在查询时按照检索词出现的位置和相关信息对 文档进行输出英语文本是小字符集上的已充分分隔开的词串而汉语文本是大字 符集上的连续字串并且在词与词之间并没有明显的分割标记故需要对汉语中的 词加以识别也就是切分词如果不分词按字检索检索的结果与用户的查询要 求就可能大相径庭例如当检索德国货币单位马克时就会把马克思检索 出来而检索华人时会把中华人民共和国检索出来进行分词可以提高 检索的准确率 由于书面汉语是字的序列词与词之间没有间隔标记使得词的界定往往模糊 不清即使这样在过去的时间里人们在汉语的自动分词技术的研究上还是做了 很多工作设计了许多实用高效的算法可以分为两类第一类主要基于词典的 匹配和词的频度统计21这类方法实用具体比较容易实现第二类方法主要基 于句法语法分析并结合语义分析通过对上下文内容所提供信息的分析对词进 行定界22这类方法试图让机器具有人类的理解能力一般不易实现下面对分词 算法进行介绍 1最大正向匹配法 最大正向匹配法的基本思想为设 d 为词典max 表示 d 中的最大词长str 为待切分的字串 每次从 str 中取长度为 max 的子串与 d 中的词进行匹配 若成功 6 则该子串为词指针后移 max 词长后继续匹配否则子串逐次减一进行匹配 2逆向最大匹配法 逆向最大匹配的基本原理与最大正向匹配相同不同的是分词的扫描方向它 是从右至左取子串进行匹配统计结果表明单纯使用正向最大匹配的错误率为 1/169单纯使用逆向最大匹配的错误率为 1/245逆向最大匹配在切分的准确率上 比最大正向匹配有很大提高 这两种分词方法也称串匹配算法 分词的准确性很大程度上依赖于词典的好坏 而且对于新出来的词或词典中没有的词分词效果就不是很理想为此提出基于词 频统计的分词方法 3基于词频统计的分词方法 从形式上看词是稳定的字的组合在上下文中相邻的字同时出现的次数越 多就越有可能构成一个词字与字相邻共现的频率或概率能够较好的反映成词的 可信度可以对语料中相邻共现的各个字的组合的频度进行统计计算它们的互现 信息两个字的互现信息是指两个汉字 xy 相邻共现概率互现信息体现了汉字 之间结合关系的紧密程度当紧密程度高于某一个阈值时便可认为此字组可能构 成了一个词 这种方法只需对语料中的字组频数进行统计不需要切分词典因而又叫做无 词典分词法或统计取词方法但这种方法也有一定的局限性会经常抽出一些共现 频度高但并不是词的常用字组例如这一之一有的我的许多 的等并且对常用词的识别精度差时空开销大 实际应用的词频统计分词系统都要使用一部基本的分词词典常用词词典进 行串匹配分词同时使用统计方法识别一些新的词即将词频统计和串匹配结合起 来既发挥匹配分词切分速度快效率高的特点又利用了无词典分词结合上下文 识别生词自动消除歧义的优点 4基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解达到识别词的效果其基 本思想就是在分词的同时进行句法语义分析利用句法信息和语义信息来处理歧 义现象它通常包括三个部分分词子系统句法语义子系统总控部分在总控 7 部分的协调下分词子系统可以获得有关词句子等的句法和语义信息来对分词歧 义进行判断模拟人对句子的理解过程这种分词方法需要使用大量的语言知识和 信息由于汉语语言知识的笼统性和复杂性难以将各种语言信息组织成机器可直 接读取的形式因此目前基于理解的分词系统还处在试验阶段 从分词的精度来看基于词典的分词算法要优于无词典的分词算法基于词典 的分词算法的分词精度很大程度上依赖于分词词典的好坏无词典的分词算法不需 要利用词库信息它通过对大规模的生语料库进行统计分析自动地发现和学习词 汇 2crawler 技术 crawler 是一个搜索 web 页面的程序常用于搜索引擎它从一个初始链接队 列出发取出一个链接根据该链接下载页面获取页面上的链接并将这些链接 加到链接队列中接着从队列中再次取出链接进行遍历重复这个过程下载的页 面保存在页面集中对页面建立的索引保存在索引库中用户可以通过索引库进行 检索 关于 crawler 的研究当前主要集中在并行 crawler 和增量式 crawler23-25并行 crawler 用于提高下载页面的速度增量式 crawler 可以避免批量更新页面集的巨大 开销这两部分分别在第二章和第四章进行探讨 1 . 2 . 3 主流搜索引擎结构 google 是当今使用最广泛的搜索引擎也是商业化性质最浓的搜索引擎 mercator 是一个实现方案公开的最成功的搜索引擎提供了详细的设计文档 这部分讲述 google 和 mercator 这两个搜索引擎的结构和工作流程目前只能 得到早期的 google 的系统结构关于新版 google 的系统结构没有相关资料进行揭 示 1google 系统结构 图 1.1 显示了早期的 google 的系统结构图16工作流程包括八个步骤 8 图 1.1 google 系统结构图 1url 服务器url server它负责在各个 crawler 之间分配 url 2每个 crawler 下载的页面对应一个 docid这个 docid 分配给该页面所对 应的 url每当从页面上获取一个链接时就分配一个 docid 给它将下载的页面 发送给存储服务器store server由它对页面进行压缩存储在页面库repository 中 3索引器indexer从 repository中获取页面解压页面将页面 html 标记去掉得到文档每个文档被转化为单词出现位置的集合称为 hitshits 记录文 档中的单词 单词出现的位置 字体大小 大小写 由 indexer 将 hits 存储到桶 barrels 中创建一个部分排序的前项索引forward index 4indexer 从页面上获取所有的链接创建 anchor 文件它记录链接的来源 指向以及链接文本信息 5url 解析器url resolver读取 anchor 文件并把相对 url 转化成绝 对 url分配 docid并将链接文本docid 以及链接本身放入前项索引forward index中 6创建链接数据库links database记录 url 的来源和指向用来计算所 有文档的 pagerank 9 7 排序器 sorter 对 barrels 进行处理 将按 docid 排序的 barrels 按照 wordid 进行重新排序以便创建倒排表同时将 wordid 列表和偏移存入倒排表中一个称 为 dumplexicon的程序将 indexer 产生的词表与 wordid联系起来创建一个新的词表 用于搜索 8searcher 运行在 web 服务器上并使用 dumplexicon创建的词典倒排 索引和 pagerank 来接受用户的查询请求并返回查询结果 google 的早期版本使用 c+实现运行于 solaris 和 linux未使用分布式处理 技术这种设计方案在下载 2,400,000 个页面之后性能以及扩展性都不理想 google 在当前的版本中采用了并行 crawler 技术装备 54,000 多台 linux 服务 器组成一个结构单一的超级计算机使得对下载的页面的后续处理速度得到了极 大的提升能满足每天 2 亿次检索的需求 2mercator 系统结构 图 1.2 显示了 mercator 的主要组件下载页面由多个工作线程完成每个工作 线程反复做下载和处理文档的步骤26 图 1.2 mercator 系统结构图 1crawler 是从共享的 url 队列url frontier中获得一个绝对 url 用于 下载绝对 url 以一个模式开始(比如http)它标志了用于下载它的网络协 议 在 mercator 中这些网络协议通过协议模块protocol modules来实现这个 用于 crawler 中的协议模块可以在用户提供的配置文件中指定在 crawler 开始运行 10 的时候动态加载 缺省配置包括图 1.2 中显示的 httpftpgopher 协议模块图 1.2 中协议模 块栈表明每个线程对应一个单独的协议模块实例这就允许每个线程访问局部数据 而不需要同步 2基于 url 的协议工作线程选择适当的协议模块用于下载文档然后调 用协议模块的 fetch 方法这个方法把从 internet 上下载的文档保存到一个回写流 rewindinputstreamris中27ris 的内容可以多次重读 3一旦文档写进了 ris工作线程就调用 content-seen test 判断这个文档是 否已被处理过如果处理过那么该文档就不会被再次处理然后工作线程从 urlfrontier 中取出下一个 url 每个下载的文档有一个与之对应的多功能 internet 邮件扩展类型multipurpose internet mail extensionsmime除了把模式与协议模块联系起来之外mercator 配置文件也把 mime类型与一个或多个处理模块相联系 处理模块用来处理下载文档例如从 html 页面中获取链接计算在 html 页面上发现的标记数或收集关于 gif 图像的统计信息与协议模块相似每个处 理模块对应一个线程 4基于下载文档的 mime 类型工作线程调用与 mime 类型相对应的处理 模块的 process 方法例如图 1.2 中的 link extractor 和 tag counter 模块用于处理 text/html 文档gif stats 模块用于处理 image/gif文档 缺省情况下获取链接的处理模块与 mime类型 text/html 是对应的这个模块 的 process 方法从 html 文档中获取所有链接每个链接被转换成一个绝对 url 并调用由用户定义的 url filter 确定是否要下载该链接如果确定要下载工作线 程就调用 url-seen test 方法这个方法检查该 url 是否处理过如果没有被处理 它就被加到 urlfrontier 中 mercator 使用分布式方法每台机器包含一个功能单元的拷贝url 集合通过 对 url 站点的域名 domain 进行散列分成 n 份一台机器一份并且把这些 url 赋给各台机器hash(domain)%n这样由每台机器全权负责 internet 一个子集 如果 url 指向外面的站点那么该 url 就会转移到相应的机器mercator 的负责 11 人报告说80%的链接是相对的大部分 url 不需要转发28-29 mercator 是介绍资料比较详细的搜索引擎本论文的很多思想都来自于 mercator 1 . 3 课题主要研究工作 本课题在研究搜索引擎各种技术的基础上参考了多个搜索引擎的实现策略 将设计并实现一个中文搜索引擎该搜索引擎将以中文 web 页面为检索目标进行 信息搜集与索引考虑到 web 的巨大容量和增长速度该搜索引擎应能满足大数据 量的要求具备一定的扩展能力和较高的检索性能并期望能够设计出一种灵活的 框架结构以便扩展新的功能整个系统将采用 java 语言实现本课题的研究工作包 括四个方面 1并行 crawler 系统的设计与实现 crawler 下载页面的速度以及扩展能力会影响到搜索引擎的性能和扩展能力 为 此将设计并行 crawler 系统该系统由多个 crawler 进程组成这些 crawler 进程 运行在不同的机器上每个 crawler 设计成一个小型检索系统 2url 服务器的设计与实现 为了防止多个 crawler 下载页面重叠将设计 url 服务器它用于在不同的 crawler 进程之间分配 url以及存储 crawler 在下载页面的过程中发现的 url 并实现多数据库并行存取技术 3检索服务器的设计与实现 每个 crawler 被设计成一个小型检索系统 所有 crawler 一起组成了一个大规模 搜索引擎设计了检索服务器它的主要功能是将用户的请求提交给各个 crawler 进行检索并返回检索结果 4增量式 crawler 的设计 增量式 crawler 是用于对索引进行动态更新的技术它能大幅度减少批量更新 索引带来的开销有利于节省资源和提高性能本文将对增量式 crawler 进行研究 并基于人工神经网络对页面变化情况建模利用模型可以计算页面的下一次变化时 间作为增量式 crawler 重访页面刷新页面集的依据 12 2 系统设计 为了实现可扩展高性能大规模中文搜索引擎本章将研究搜索引擎的设计 方案首先介绍当前 web 的规模以及搜索引擎面临的挑战然后讨论搜索引擎设计 方案的选择与论证接着就系统结构图分析各个组成部分的功能需求以及采用的技 术方案 2 . 1 系统结构 crawler 是搜索引擎的核心组件用于遍历 web 下载页面搜索引擎的性能 规模扩展能力很大程度上依赖于 crawler 的处理能力这一部分将围绕 crawler 需要解决的问题设计搜索引擎的系统结构 1crawler 面临的挑战 当前 google 能索引 43 亿个页面 每个 web 页面的平均大小是 10kb 那么 web 页面的总共大小至少几十 tbweb 的增长速度也很快在过去不到两年的时间里 web 页面的数目翻了一倍除了新创建的页面之外已存在的页面也在不断更新 40%的 web 页面至少每周更新一次考虑到 web 的规模和变化情况crawler 需要 解决四个难题 1crawler 要下载哪些页面在大多数情况下crawler 不能下载 web 上的 所有页面即使当前使用最广泛的搜索引擎也只能索引 web 很小一部分页面基于 这个事实crawler 必须慎重选择访问哪些页面并首先访问重要的页面 这样它访问 的 web 页面才更有意义 文献25研究了怎样遍历 web 以便使它访问的页面对用户 更有价值 2crawler 如何刷新页面一旦 crawler 下载了指定数量的页面它就不得 不对这些页面进行重访以便检测页面的变化并刷新下载的页面集 由于 web 页面变 化速率大不相同因此 crawler 需要确定重访哪些页面以及跳过哪些页面以便获 取较高的页面刷新率30-31例如如果某个页面很少变化那么 crawler 就不会经 常对该页面进行重访而把较多时间留给变化更频繁的页面 13 3 如何使得 crawler对它正在访问的站点造成的负载最小当crawler 从web 上搜集页面的时候它就占用了属于其他组织的资源例如当 crawler 在站点 s 上 下载页面 p 时站点 s 就需要在它的文件系统中检索页面 p这就占用了站点 s 的 cpu 资源站点检索该页面之后需要将该页面通过网络进行传输网络也是另一 个被多个机构共享的资源因此crawler 需要减少它对这些资源造成的负担 4遍历过程如何并行化由于 web 的巨大容量crawler 常常运行在多台机 器上并行下载页面 为了在给定时间内下载大数量级的页面并行化常常是必要的 很明显 这些并行 crawler 之间应该进行协调防止不同的 crawler 访问同一个 web 页面多次但是这种协调会导致大量的通信开销从而限制了 crawler 的并行效 果 本章以及后续几章内容将探讨这些问题这里首先讨论第 4 个问题 2并行 crawler 随着 web 容量的增长单进程在给定时间内几乎不可能遍历整个 web许多搜 索引擎采用多进程并行下载技术 我们称这种 crawler 为并行 crawler 并行 crawler 要解决三个问题 1 重叠 当多进程并行下载页面的时候 不同的进程可能下载同一页面多次 一个进程可能意识不到其他进程已下载了该页面 2质量crawler 首先下载重要的页面但是在并行 crawler 情况下每 个 crawler 进程不一定知道当前所有 crawler 下载的页面集合crawler 进程基于它 自己下载的页面集合对页面的重要性进行评价并按照页面的重要性信息做出遍历 决策由于缺少全局的信息导致遍历决策未必就是最重要的页面最先访问 3通信带宽为了防止下载重叠以及提高下载页面的质量crawler 进程需 要彼此之间周期性进行通信与协调但是通信量会随着 crawler 进程数量的增加而 显著增长 虽然并行 crawler 设计很复杂但是相对于单进程 crawler 来说它们有三个很 显著的优势 第一是扩展性能较好由于 web 的容量巨大在某些情况下 运行并行 crawler 非常必要以便保证下载页面的速度 14 第二可以分散网络负载 并行 crawler 的多个 crawler 进程可能运行在地理上遥 远的地方每个 crawler 下载地理邻近的页面例如在德国的 crawler 进程下载所 有的欧洲的页面而另一个在日本的 crawler 进程则下载所有亚洲的页面通过使 用这种方式就能把网络负载分散到多个地方特别是当网络不能处理来自于大规 模 crawler 的负载时这种分散就显得尤为必要 第三可以减少网络负载除了分散负载之外并行 crawler 实际上减少了网络 负载假定在北美洲的 crawler 接到一个来自欧洲的页面为了下载这个页面这 个页面首先得通过欧洲的网络然后通过欧洲-美洲之间的网络最后通过北美洲的 网络相反如果欧洲的 crawler 进程只下载欧洲的页面北美洲的 crawler 进程只 下载北美洲的页面那么整个网络负载将会减少 注意到这些下载的页面以后需要传输到一个中央位置以便创建一个集中索 引在这种情况下可以采用三种措施降低传输开销减少网络负载 1压缩传输一旦页面搜集并存储就很容易在传输到集中位置之前进行压 缩 2增量传输而不是传输所有下载的页面可以首先考虑当前页面集与前一 次传输的页面集之间多出的部分并且传输这个多出的部分由于很多页面都是静 态的变化并不频繁这种措施能大幅度减少网络通信量 3汇总在某些情况下可能需要一个唯一的集中索引而不是原始页面 那么就只需要获取对于索引创建必须的信息进行传输 3系统结构 基于上述讨论设计了如图 2.1 所示的系统结构 整个结构由三部分组成url 服务器url server并行 crawler 系统以及检索服务器retrieval server 由于单台机器不可能存储所有的 url为了提高扩展性能以及存取性能设计 了 url 服务器它按照一定的划分算法把 crawler 发现的 url 存入位于不同机器 上的数据库中同时也负责从数据库中取出尚未处理的 url 分配给各个 crawler 进 程 为了在短时间内下载更多的页面设计了并行 crawler 系统并行 crawler 系统 由多个 crawler 进程组成这些 crawler 进程并行下载页面 有利于提高页面下载速 15 度和页面处理速度 为了提高检索性能 设计了检索服务器 它将检索请求发送给各个 crawler 进程 由各个 crawler 在自己的索引库中进行检索并把结果提交给检索服务器最终由 检索服务器对结果进行排序输出 图 2.1 系统结构图 16 2 . 2 并行crawler系统 页面的平均大小为 10kb 那么 10 亿个页面就需要 10,000gb 的存储空间虽然 页面可以被压缩并去掉 html 标记即使可以压缩到十分之一仍然需要 1,000gb 的存储空间另一方面如果每个 crawler 进程以每秒 30 个页面的速度下载那么 一年也只能下载 10 亿个页面在这期间会有大量的页面发生变化导致这 10 亿 个页面中只有一小部分可用为了分散存储提高性能采用并行 crawler 技术 图 2.2 并行 crawler 的系统结构图 图 2.2 是一个并行 crawler 的系统结构图并行 crawler 由多个 crawler 进程组 成 每个 crawler 进程运行在单一机器上 所有 crawler 可以并行工作 这些 crawler 进程之间根据连接方式可以采取两种并行策略32 1站内并行 crawler所有的 crawler 进程都运行在同一个局域网中并使用高 速网络进行通信 这种方案相当于所有的 crawler 进程都运行在图 2.2 左边的局域网 中crawler 在从 web 网站上下载页面的时候使用同样的局域网这样系统产生 的网络负载就集中在单一位置 2 分布式 crawler crawler 进程分布在不同的地理位置并通过广域网进行连接 17 例如一个 crawler 进程运行在美国下载所有美洲的 web 页面另一个 crawler 进程运行在法国下载所有欧洲的页面分布式 crawler 能分散并减少整个网络的 负载当 crawler 运行在不同的地理位置并使用 internet 进行通信时crawler 之间 通信的频率和方式就显得尤为重要 由于条件的限制我们采用站内并行 crawler 策略系统结构如图 2.1所有的 crawler 进程运行在同一局域网中每个 crawler 进程对应一台机器这些 crawler 并行工作但是当多个 crawler 进程并行下载页面的时候不同的 crawler 可能下 载相同的页面为了避免重叠 crawler 彼此之间需要进行协调确定各自下载哪些页 面这种协调可采取两种方式进行 第一种方式比较极端crawler 进程之间完全独立下载页面而不进行任何协调 也就是说每个 crawler 进程从它自己的 url 队列出发而不与其他 crawler 进程进 行协调在这种情况下即使所有的 crawler 进程从完全不同的 url 队列开始遍历 web也会有很大程度的重叠虽然这种方式节省了 crawler 进程之间的通信开销 而且扩展性也较好但是页面重叠问题相当严重 第二种方式称之为动态分配由一个 url 服务器逻辑地把整个 web 按照某个 划分算法划分成很多小的划分块并动态地把每个划分块分配给各个 crawler 进程 去下载例如url 服务器按照 url 所在的站点域名划分 web这样同一个站 点的页面属于同一个划分块 不同站点的页面属于不同的划分块crawler 进程按照 分配的划分块下载页面获取链接当获取的链接指向同一个划分块的页面时 crawler 进程就遍历该链接如果获取的链接指向另外一个划分块那么 crawler 进 程就将该链接报告给 url 服务器url 服务器收集这些链接再次划分发送给 对应的 crawler 进程去下载这种方案有利于防止重叠 注意到采用动态分配方案不能在 url 服务器中保留所有发现的 url不利于 pagerank 的计算为此必须对动态分配方案进行改进改进方案为crawler 进程 将发现的链接都发送给 url 服务器处理而不遍历这些 urlurl 服务器首先查 看这些 url 在数据库中是否存在 如果不存在就存入数据库中 否则不做任何处理 当 crawler 的本地 url 队列为空时就向 url 服务器申请一定数量的 url 这样就在 url 服务器上保存了所有发现的 url虽然这会加重 url 服务器的 18 负担也会影响扩展性能但是有利于 pagerank 计算的准确性在前面已提到 crawler 不能下载 web 上的所有页面crawler 必须慎重选择访问哪些页面并首先访 问重要的页面为了解决这个问题每次 crawler 申请 url 时url 服务器就从数 据库中选出还未处理的 pagerank 值最大的 5000 个 url 发送给它 这样 crawler 就 能首先访问 pagerank 值较高的页面从而提高下载页面的质量 每个 crawler 进程有自己的页面库和索引库crawler 下载的页面保存在自己的 页面库中对页面建立的索引保存在索引库中这样就将数据在各个 crawler 运行 的机器上分散存储有利于系统的扩展而且多个 crawler 进程并行工作有利于提 高系统的性能 图 2.3 crawler 的结构图 图 2.3 为单个 crawler 的结构图其中下载线程池是用于从 web 上下载页面的 组件当 url 队列为空时就向 urlserver 申请 url 每个下载线程的处理过程如下从队列中获得一个 url下载页面并将下载 的页面交由页面解析器处理页面解析器去掉页面上的 html 标记得到页面内容 并将新发现的 url 发送给 urlserver 存储页面解析器使用 md5 算法对页面的内 19 容建立摘要并判断该摘要在数据库中是否存在如果存在表示该页面已被处理 放弃该页面重新获取 url 下载否则表示该页面以前没有被处理过将摘要保存 在数据库中页面内容交由索引器建立索引后保存在索引库中页面内容本身保存 在页面库中这些工作完成之后重新获取 url 下载 当下载页面结束后下载线程池会自动销毁并建立一个工作线程池它负责 接受检索服务器的检索请求在索引库中查找并返回检索结果同时从页面库中获 取含有检索文字的一段摘要返回给检索服务器 crawler 的结构中没有专门设计域名解析器而采用 java 提供的自动域名解析 功能因此省掉了这个组件 单个 crawler 处理内容比较复杂涉及到的问题比较多将在本章及第三章中 依次介绍 2 . 3 url服务器 遍历 web 需要管理大量的 url每个 url