【毕业学位论文】（Word原稿）可扩展Web信息搜集系统的设计、实现与应用初探-计算机系统结构网络与分布式系统

i 可扩展 现与应用初探 摘 要 本文研究工作是国家重点基础研究发展规划项目“网络环境下海量信息组织与处理的理论与方法研究”的一部分；研究对象是 样的动态海量信息载体；研究的主要目标是要得到一种高性能、高可靠，支持海量网页信息搜集、分析与处理的系统结构。主要贡献包括以下几个方面： 1) 基于对网页性质及其分布的认识，设计和实现了一种可扩展海量 息搜集系统体系结构。结合 息搜集的基本要求和基于 群的并行分布处理技术，该系统结构力图在搜集策略、可扩展性、减少通信、负载 平衡、任务调度、并行粒度控制等方面得到一个很好的折衷。在仔细的理论分析和大量模拟实验的基础上，目前这种体系结构已经成功地实现并投入运行，在系统规模从 1 到 18 台机器变化的范围表现出很好的可扩展性，达到了 15 天搜集 5700 万网页的性能指标。 2) 针对并行网页搜集系统的节点可能出现临时故障的问题，提出了一种系统动态可配置方案。该方案的基础是一种从网页 搜集节点的两阶段映射关系，它保证了当配置（节点数）变化时系统能经过一个短暂、安全的过渡过程达到一个新的稳态，从而保证了系统的动态可配置性。目前这种方案已经实 现，并成功应用于“天网”搜索引擎和“燕穹” 息博物馆的存储系统中。 3) 基于“燕穹” 息博物馆中的网页信息，探讨了海量 过分析几千万网页的链接结构，给出了对2002 年初中国 大小、形状和结构的一种定量认识，同时说明了如何从海量网页信息中高效地识别网络社区的一种方法。 关键词 ：万维网，搜索引擎，可扩展 息搜集， 息博物馆，动态可配置性，负载平衡， 掘 e eb as a In we in a of 1) on an of a is a of is of a in a of a is in in 8 7 5 2) at in a is is on a a of of a a As of of in in 3) of an is to be to of In we of a is eb as of 002. In an is of eb v 致谢 首先要向我的导师 李晓明 教授表示衷心的感谢，感谢他在我三年的博士生阶段和本论文的完成工作中对我的精心指导和谆谆教诲，他踏实的治学态度和严谨的工作作风使我受益匪浅，他渊博的知识和对事业无止境的追求使我感受至深，他对我的严格要求将对我以后的工作学习产生巨大的影响，使我终生受益，我以作为他的学生而自豪。 同时，感谢王建勇老师，在选题、调研和系统的设计与实现的过程中，以他丰富的经验提出了许多宝贵的意见，在可扩展 息搜集系统结构设 计和动态可配置模型建立方面给了我许多无私的帮助。 感谢我的妻子陈翀，给予我的爱和支持。在我三年的学习中，她对家庭无私奉献，从无怨言；同时还是我的良师益友，在我面对问题、挫折的时候，给我很多启迪。在我论文写作期间，多次帮我校对修正。 特别感谢北大网络实验室天网组谢正茂，赵江华和单松巍同学的帮助。从我刚接触课题到现在两年多的工作学习中，我们是相处时间最多的，共同探讨问题，克服困难，完成任务。尤其是谢正茂同学，许多好的想法和实践经验是我工作按期完成的保障。孙磊同学，近半年刚加入天网组，但是在“燕穹” 息博物 馆的建设中给了我很大帮助。还有同组的郭琳、陈华、龚笔宏、罗昶、孟涛、彭波同学和陈劲松老师，在交流中使我获得新的思路和方法。 感谢北大网络实验室其他老师和同学们的热情帮助和支持。 感 谢 国 家 973 项 目 （ 国 家 重 点 基 础 研 究 发 展 规 划 项 目金资助，北大 985 项目基金资助。 最后感谢我的父母多年来一直对我的关心、爱护。这种关心、爱护，即使在我长大成人，成家之后，都没有一点减少。我希望我的工作、学习成绩能够带给他们一丝安慰。 目录 摘 要 . i . 谢 . v 目录 . 示 . 格 . x 第 1 章 引言 . 1 究工作的背景和意义 . 1 文研究工作的内容、目标与方法 . 2 文的主要贡献 . 6 扩展 息搜集系统体 系结构 . 6 集系统的动态可配置性 . 6 构信息挖掘 . 7 息博物馆的建设 . 7 量式 息搜集的方法 . 8 文组织 . 8 第 2 章 搜索引擎工作原理与基本问题 . 10 言 . 10 索引擎工作流程 . 10 索引擎基本问题 . 11 集 息 . 12 集策略 . 14 除镜像网页 . 16 量式搜集 . 17 章小结 . 23 第 3 章 网页搜集系统的可扩展性研究、设计与实现 . 25 言 . 25 语介绍 . 25 网搜索引擎系统结构 . 26 中式搜集系统 . 28 统设计目标 . 28 统结构和主要设计思想 . 29 扩展搜集系统的设计 . 35 统设计目标 . 35 统结构和主要设计思想 . 36 扩展搜集系统的模拟与实现 . 39 控之间通信量分析 . 39 拟系统运行结果分析 . 40 际系统运行结果分析 . 45 关研究 . 47 索引擎 . 48 索引擎 . 50 . 51 索引擎 . 51 章小结 . 51 第 4 章 网页搜集系统的动态可配置性的研究与实现 . 53 言 . 53 现动态可配置性的三种方法 . 53 阶段映射法 . 56 一步分析和实现两阶段映射模型 . 58 关研究 . 61 章小结 . 61 第 5 章 海 量网页信息的应用研究初步 . 62 言 . 62 穹 息博物馆 . 62 页存储系统 . 62 页回放系统 . 69 关研究 . 77 于中国 大小、形状与结构 . 77 过对搜集过程的分析了解中国 规模 . 78 002 年 初 中国 形状和结构 . 81 关研究 . 93 章小结 . 100 第 6 章 总结和未来工作展望 . 102 参考文献 . 106 附录 A 天网搜索引擎 . 113 行环境 . 113 用方法 . 113 附录 B 燕穹 息博物馆 . 116 行环境 . 116 用方法 . 116 图示 图 3网系统概貌 . 26 图 3网系统结构 . 27 图 3网的主控系统结构 . 29 图 3扩展 集系统结构 . 38 图 3扩展搜集系统负载方差 . 42 图 3拟 N 个主控分布式系统及集中式系统随时间的变化 . 44 图 3拟分布式系统效率 . 44 图 3际 N 个主控分布式系统及集中式系统随时间的变化 . 46 图 3际 分布式系统效率 . 47 图 3统结构 . 49 图 4阶段映射 . 55 图 5节点网页存储系统结构 . 65 图 5体网页存储系统结构 . 66 图 5穹 息博物馆系统结构 . 70 图 5页传输过程 . 76 图 5国各省市网站分布 . 83 图 5页结构 . 86 图 5A)网页有效入度分布， (B)网页出度分布 . 87 图 5页入度分布 . 87 图 5心社区与 系 . 92 图 5统 R 的用户群差别 . 97 图 5种搜索引擎技术比较 . 98 图 网搜索引擎主页 . 114 图 网搜索引擎查询结果 . 114 图 穹 息博物馆 . 117 图 穹 息博物馆查询结果 . 117 x 表格 表 3据描述 . 30 表 3体语法 . 32 表 3扩展搜集系统负载平衡参照序列 . 41 表 3整化可扩展搜集系统负载平衡参照序列 . 41 表 3拟系统四组实验数据方差 . 42 表 3拟系统四组实验结果数据 . 43 表 3际系统四组实验数据方差 . 45 表 3际系统四组实验结果数据 . 46 表 5 C 语言接口 . 64 表 5网搜集记录 . 80 表 5国 点地域分布 . 82 表 5页链接结构 . 84 表 5门站点分类 . 88 表 5链接中至少包含六个不同域名的网页链接结构 . 90 表 5航功能的网页链接结构 . 90 表 5心社区的数目 . 91 表 5心社区例一 . 93 表 5心社区例二 . 93 第 1 章 引言 1 第 1章 引言 究工作的背景和意义 万维网（ 记为 因特网上最成功的应用，起源于 1989 年欧洲粒子物理研究室 最初计划是由物理学家 1989 年 3 月提出的，第一个基于文本原型于 18 个月后运行。 1991 年 12 月在德克萨斯州的 1 超文本会议上进行了一次演示，次年继续发展，并于 1993年 2 月，随着第一个图形界面 发布而达到了其发 展的高峰 核心技术是超文本和超媒体。通过将文本、图形、图像、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。由于其界面友好、易学易用、内容丰富，很快便被政府机关、科研机构、商业企业和个人所接受，成为人们日常信息交流的一个简单易用的工具。在 1993 年下半年， 不到三个月的时间里翻了一翻。在1995 年 4 月， 网上的流量超过了 其它服务的流量，成为 的第一大应用服务。到 1997 年 12 月，网上大约有 3亿 2000 万网页 在最 近几年里， 得到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据 索引擎在 2000年的数据库数据表明，网页数目已经超过了 10 亿，共有 点 4,951,247根据 索引擎在 2002 年 4 月索引网页表明，网页数已经超过 20 亿 1994 年登陆中国，到现在仅 8 年的时间里发展速度惊人。根据文献 结合“天网”搜索引擎（简记为 “天网”搜索引擎的英文名称） 0， 一两年来在网页收集工作中的感受，尤其是我们最近 2002 年 4 月初又完成了一次相当彻底的收集，中国最大的商业搜索引擎服务商百度第 1 章 引言 2 报告 2002 年 3 月中国拥有的网页数已经超过 5000 万。 正如书刊这种信息载体所经历的发展、变迁与应用一样，近年来兴起的新的信息媒介 页也在社会生活中扮演着越来越重要的角色，它以其传播迅速、更新快捷、访问方便等优点成为继纸质书刊之后最大的信息承载体。 当文字成书后，人类的历史 、文化发展、风俗民情、科学进步等就不再是随时间流逝而一去不复返了 它们能够被记录下来，供后人研究借鉴和应用，这样才有了文明史。同样， 息也在重演着纸质信息的变化，只是速度要快得多，所以人类对 息的研究从它在计算机上诞生的那天起到现在，一刻也没有停止过，可以说 息将要对未来的人类文明史做出巨大贡献。 有了这种比较， 息的组织与处理工作就很容易理解了。就像在现之前的图书馆一样，工作人员需要先将来自各地的报纸、刊物、书籍文献收集起来；按照不同的分类规则进行科学分类；建立图书索引；对学习者、研究者等不同领域、不同身份的人提供查询或借阅，帮助他们达到各自的目的。 息处理也包括信息的收集、整理、索引、提供查阅、提供研究、提供个性化服务等等。在这项庞大而复杂的工作中，对息的搜集是一切活动的基础。图书馆的信息搜集是靠手工完成的，而 息搜集必须要靠安全、稳定的搜集架构、高效的计算方法自动完成，只有这样，才能够适应 息海量的累积与递增。 其中“ 息持续指定搜集”工作相当于为了对不同领域的专门研究提供馆藏，图书馆需要将所有特定专题的资料都收集下来；“ 息定期全 面搜集”工作相当于图书馆每隔一段时间（发刊周期）就会收到新的一期报纸或杂志，作一次内容重新收录；所以我们说，进行搜集工作的最终目的是为了建成“燕穹” 息博物馆（简记为 “燕穹” 息博物馆的英文名称） 文研究工作的内容、目标与方法 本文研究工作主要围绕如何更快更全地搜集信息，如何高效处理，第 1 章 引言 3 如何多快好省地建设 提供有应用价值的服务等几个方面。具体体现在研究海量 息的高性能搜集和存贮技术，构信息挖掘理论与实现方法。内容如下： 1. 系统架构设计：分布式多任务搜集系统结构。 2. 系统可扩展性：设计具有可扩展性的搜集系统，达到当任务扩大N 倍，系统处理和存储能力也扩大 N 倍时，系统性能波动较小。当任务不变而系统处理能力和存储能力扩大 N 倍时，系统性能也基本提高 N 倍。 3. 动态可配置性：由于搜集系统面对的是海量信息，通常会长期连续运转。为了保证工作期间，无论是硬件故障还是人为干预造成的系统结构变化（即节点数目的增减）都不影响系统的性能，就要求分布式系统具有动态可配置的特性。 4. 搜集策略制定：因为 页每年是以指 数形式增长，所以搜集系统应该尽量优先搜集重要的网页。搜集策略指如何公正和客观的确定网页的“重要性”。 5. 网页存储格式：确保后续工作，包括为搜索引擎建立索引提供服务、网页历史回放的使用简便；便于复制、备份；存储格式应一目了然，便于交换和供给其他研究机构使用；容错性能强，即使部分数据损害也不影响其他部分；存储操作简单，不会占用系统过多的资源。考虑到后续的二次加工和增值处理的需要，需要提供简单快捷的数据访问接口。 6. 考察搜集过程中生成的副产品：包括网页的链接结构，中国 P 地址，域名与 对应关系。 7. 产生 搜集全集后，初步研究 息在时空意义上发生、存在、变化，以及相互关系的规律。这些规律通常应该具有宏观、统计的意义，它们的例子可能包括简单的“网页的生命周期”和“网页的大小”；稍微复杂一些的“网站的网页数”和“中国网页的拓扑结构及其随时间的演进”；更复杂一些的可能有“国家政策第 1 章 引言 4 的力度和网上信息强度之间的关系”，等等。 8. 建设 为网上信息博物馆，为各方面有需求的人和团体提供研究数据源。 研究目标： 1. 分布式并行搜集系统：保证大规模的信息处理范围， 让系统能力和中国网页规模增长的速度同步 ； 实现在不超过一个月内遍历搜集全国静态网页（不包括通过提交查询词动态生成的网页）。目前这一目标已经达到，采用 内核的 周之内搜集中国所有 息。搜集信息量达到 5000 多万网页。目前搜集系统设备为 18 台 ，线路速度100 2. 可扩展性：实现线性加速比，随着中国网页数的增加，搜集系统增加节点后，基本不影响每个节点的搜集性能。当中国网页数不变，增加节点后，搜集系统性能应该相应提高，表现在搜集周期缩短。 3. 动态可配置性：系统增加节点后，要保持系 统的负载平衡；在人为可控情况下减少节点，其他节点不应该再重复减少节点已经完成的工作。动态协调过程中各节点通信量要尽可能的小，使系统能够快速的从动态可配置状态进入平稳状态。 4. 优先搜集策略：根据 目录深度和链接关系，设定权值，实现类似于宽度优先搜索的启发式搜集策略。 5. 存储格式优化：为简化复杂函数，便于文件在不同的平台间移植比较。索引文件和数据文件以 尾的字符串形式存储 它们不能包含任意的二进制数据。同时提供 C 语言数据访问接口。采用硬盘存储加磁带备份的冗余策略，既能满足灾难恢复要求，又能作为数据源 提供给合作单位，满足多学科交叉研究的灵活性。最近一次搜集中，网页的纯文本信息达到 两盘容量分第 1 章 引言 5 别为 100磁带可以压缩备份下。 6. 搜集过程中生成的副产品，包括：网页的链接结构，中国 点的 址，域名与 对应关系。通过 掘，分析 时通过分析网页的链接关系来排序检索结果和改进搜集策略。 7. 扩展 息的研究至时间和空间两个方面，得到关于中国网上信息（公开网页信息）总体情况的若干基本认识。例如 中国网站的平均网页数约为 500”的认识，和“ 230 左右”的结论 差甚远；还得到过，“搜索引擎的用户查询内容序列（放在时间轴上考虑）具有局部性、稳定性和自相似性” 1的结论。当然，这些算是比较浅层一些的东西；基于 们希望发掘出一些更深层次的结论或规律。 8. 建成 规模和效率方面分别达到高指标，即在规模方面，从 2001 年 6 月起，到 2004 年底，让系统的能力和中国网页规模增长的速度同步（这将直接反映出系统的可扩展性设计）；在效率方面，要做到至少每个月能够将全国 的网页处理一遍。 研究方法： 1. 搜集系统的研究方法：建立系统结构模型，建立实验系统，分析实验过程和实验结果，同时根据所得结果优化实现系统结构模型，保证系统具有负载平衡，可扩展性好的要求。 2. 基于 供的海量 息，利用数学、统计、随机过程分析等手段，结合信息分类、数据挖掘、计算语言学的有关技术，对上千万量级的信息从不同层次进行开采和提炼，并将得 到 的 结 果 在 后 续 信 息 集 合 中 进 行 验 证 和 完 善 （ 注 意 提供不同时间的信息）。 第 1 章 引言 6 文的主要贡献 扩展 息搜集系统体系结 构 提出可扩展 息搜集系统结构，使之达到能够搜集数量不断增长的网页的要求。 0采用集中式搜集网页的处理方式（一个主控控制多个搜集程序并行工作），索引网页达到 100 万量级。全部网页更新周期为 10 天，即每天大约要搜集 10 万网页，达到 100 万量级。目前全世界网页超过 40 亿，如果以 统的速度，要达到 1000 万量级就需要 100 天， 100 天中由于网页的更新，将使搜集到的部分网页失去意义。因此，需要采用并行分布式技术在尽可能短的时间内搜集尽可能多的网页 。 我们设计并实现了可扩展 息搜集系统结构，并把它应用于索引擎系统中。达到了设计目标。这种可扩展 息搜集系统目前出于 国际网