可扩展Web信息搜集系统的 设计、实现与应用初探

Presentation on theme: "可扩展Web信息搜集系统的 设计、实现与应用初探"— Presentation transcript:

1 可扩展Web信息搜集系统的 设计、实现与应用初探
闫宏飞 北京大学网络与分布式实验室 2002年6月14日

2 提纲 问题提出 可扩展网页搜集系统 网页搜集系统的动态配置 海量网页应用研究初步 工作总结 2

3 工作的背景和意义 Web发展 中国的Web 发展
1989年提出->1993Mosaic->1997年底(3亿2000万） ->2000年1月(超过10亿) -> 2002年5月(超过20亿) ，… 中国的Web 发展 1995年底(10万到100万之间) 每年以指数形式增长 2002年1月(超过5000万)，... 单机能力，“天网”故事，引出必要性 3

4 搜索引擎工作流程 起源于传统的信息全文检索理论 包括如下3个工作过程 www 搜集Web信息 建立索引库 检索查询 用户
1.搜集Web信息：发现、搜集Web上的网页信息。需要有高性能的搜集器自动的在Web中搜索信息。Web信息搜集器是下载Web上网页的程序。它顺着网页之间的链接移动，自动地下载所经过的网页。给定起始URL集合S，Web搜集器不停的从S中移除URL，下载相应的网页，解析出网页中的超链接URL，将未访问过的URL加入集合S。Web搜集器也称作Web机器人或Web蜘蛛。搜集器把所获得的信息保存下来以备建立索引库和用户检索。 2.索引库的建立：对搜集到的Web信息提取和组织，建立索引库。这关系到用户能否迅速地找到准确、广泛的信息。对搜集器抓来的网页信息快速地建立索引，通常采用倒排表技术。如果在建立索引库的过程中对用户在检索端搜索的查询串进行跟踪，并对查询频率高的查询串建立Cache，可以在检索端请求时，加快索引库的响应速度。 3.检索端的查询：根据用户输入的查询字串，在索引库中快速检索出文档。采用基于网页内容分析和基于超链分析相结合的方法进行相关度评价，客观地对检索出的网页进行排序，从而尽量保证搜索出的结果与用户的查询串相一致。然后将输出的结果返回给用户。为了加快检索端的响应速度，可以根据最近用户查询信息建立检索端Cache。 搜集Web信息 建立索引库 检索查询 用户 4

5 搜集Web信息 应用到下列方面： 搜集方式 目标 搜索引擎 网页存档 其它方面
尽快高效地获取网页 可扩展Web信息搜集系统 为处理海量数据而设计 主题Web信息搜集系统 为发现专业信息而设计 依据不同的应用需要，Web信息搜集可以采用不同的策略和方法。大到为处理海量数据而设计的具有可扩展性的Web信息搜集系统，小到为发现专业信息而设计的主题Web信息搜集系统。除了上述的先搜集网页再统一建索引提供服务外，近几年还涌现出了通过基于Web代理的在线信息搜集方法[MB98] [Men99]。Web代理概念的流行并不是因为它的成功——目前还没有成功的Web代理搜索引擎，而是因为它是一个很有吸引力的想法——你想做什么，告诉它，它会自动的帮你完成。Web代理的问题在于不能象搜索引擎提供实时的信息反馈。此外，代理的最大问题是让人去做机器擅长的工作（等待），而机器做人擅长的工作（思考）[Shi99]。这种颠倒角色的方式看起来完全可以击败创造计算机的目的。尽管Web搜集代理面向整个Web搜集确实不成功，但是采用Web代理应用于事先定制好的站点来处理用户的请求（比如旅行预定）还是可行的。 因为主题Web信息搜集系统是可扩展Web信息搜集系统的子集，只要对可扩展Web信息搜集系统增加限制条件就可以获得。Web代理不适合搜集面向整个Web的应用。所以本文着重探讨为处理海量数据而设计的可扩展性Web信息搜集系统。 5

6 提纲 问题提出 可扩展网页搜集系统 网页搜集系统的动态配置 海量网页应用研究初步 工作总结 分布式系统 搜集策略 增量式搜集
需要解决的基本问题： 1)规模：volume:web site, coverage,信息类型 2)性能：real-time: 一定时间内fetch, 服务时要求相应时间<1s 3)质量：消重、排序 6

7 天网系统体系结构 WWW 控制器 搜集器 原始数据库 索引器 索引数据库 检索器 用户 用户接口 制定搜集策略 过滤IP地址
执行Robot协议 存储所抓取得网页 索引器 索引数据库 先介绍“天网”是什么？ 检索器 用户 用户接口 7

8 集中式搜集系统 1.主进程负责产生其他五个进程，接受存取分析进程的连接，与存取分析进程交互。
2.结果插入进程通过PIPE接收主进程得到的访问结果，通过各种检查后存入数据库已访问网页列表。其中新的URL放入NewUrlCache或者新的未处理URL列表（当NewUrlCache满时）中，等待新URL处理进程进行处理。 3.robots存取分析进程得到URL选取进程发出的SIGUSR1信号后，检查主机表中需要处理的表项进行存取分析。 4.URL过期检查进程定期检查数据库中已经访问的网页，如过时，则将该主页的URL放入未访问URL列表中。 5.未访问URL选取进程从未访问表URL列表中选取合格的未访问的URL放入Cache中。 6.新URL处理进程从NewUrlCache或新的未处理URL列表中，取出新URL进行处理。 8

9 分布式搜集系统 高效搜集尽可能多的网页 系统具有如下特点 尽可能减少主控之间网络通信量 各节点负载均衡 具有可扩展性 系统可以动态变化
目标 搜集器 主控2 主控1 主控3 调度 主控N 系统具有如下特点 分布式并行 分布式策略 物理上分散 IP分段 主控通信策略 环形通信 网状通信 尽可能减少主控之间网络通信量 各节点负载均衡 具有可扩展性 系统可以动态变化 其中主控通信量可以通过分析找到优化的方法，负载平衡和可扩展性通过模拟实验和实际环境实验来验证，动态可配置性涉及问题较多，用第4章单独介绍。本节只讨论前三个关键问题。 为什么采用并行分布式就好，说明4个原则。 9

10 模拟系统实验 模拟数据：大小为507MB->761,129个网页的模拟Web数据
模拟实验机器配置：一台PC机，配有双Intel550 CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris 8.0 基于上述实验环境，分别模拟实验了主控数n为2，4，8，16时四种情况 在2000年6月，我们在WebGather正常运行过程中，利用附加程序，产生分布式算法需要使用的模拟数据，对于每个网页保存了URL及其所包含的URL信息，大小为507MB。通过运行程序，产生一有761,129个网页的模拟Web数据。以此作为我们的实验对象。程序运行的机器是一台PC机，配有双Intel550 CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris 8.0。 基于上述实验环境，我们分别模拟实验了主控数n为2，4，8，16时四种情况。四组模拟实验分四次完成，每次运行n个主控时，同时运行一个集中式主控。每组运行时间至少为三天，获得了大量模拟实验数据。 10

11 负载平衡参照序列 11

12 模拟系统负载平衡 Hash函数：H ( URL ) = ( DNS ( URL中主机部分 ) ) MOD n 参考序列
因为方差可以反映数据分散程度，方差越小说明工作负载越平均；如果四组实验数据的方差都小于上表参照序列值求得的方差，认为系统负载平衡性达到要求， 12 可扩展搜集系统负载方差

13 模拟系统可扩展性 13

14 实际系统实验 机器配置：四台PC机，配有双Intel550 CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris 8.0
14

15 实际系统负载平衡 模拟实验方差 实际实验方差
模拟实验方差 实际实验方差 因为方差可以反映数据分散程度，方差越小说明工作负载越平均；如果四组实验数据的方差都小于上表参照序列值求得的方差，认为系统负载平衡性达到要求， 15

16 实际系统可扩展性 因为方差可以反映数据分散程度，方差越小说明工作负载越平均；如果四组实验数据的方差都小于上表参照序列值求得的方差，认为系统负载平衡性达到要求， 16

17 搜集策略 表面 深层 17

18 增量式搜集 为什么要增量式搜集 设计目标 消除已经搜集到的网页中已经失效的网页 重新搜集更新过的网页 搜集没有访问过的网页 1.为什么要？
2.设计目标 消除已经搜集到的网页中已经失效的网页。随着时间的流逝，某些已经搜集回来的网页可能已经不存在了，需要消除。 重新搜集更新过的网页。随着时间的流逝，某些已经搜集回来的网页URL虽然没有改变，但是网页内容更新过了，需要重新搜集。 搜集没有访问过的网页。 以多快好省的方式完成增量搜集过程。在尽量短的时间内更快更好的完成上述3个设计目标。 18

19 实现增量式搜集的两种策略 检查全部网页 有选择性的检查网页 重新访问的网页数量不大 检查中与服务器建立连接
网页平均生命周期1.43年，同一时间存在的网页总体的半衰期大约0.99年 有选择性的检查网页 检查全部网页，判断其中失效部分和改变部分 二次连接 重新访问的网页数量不大 检查中与服务器建立连接 网页平均生命周期1.43年，同一时间存在的网页总体的半衰期大约0.99年 有选择性的检查网页，尤其是检查失效和改变几率大的网页（如果可以获得的话）判断其中失效部分和改变部分。 19

20 搜集部分相关研究 Harvest搜索引擎 Google搜索引擎 Internet Archive Inktomi搜索引擎 20

21 提纲 问题提出 可扩展网页搜集系统 网页搜集系统的动态配置 海量网页应用研究初步 工作总结 21

22 实现动态可配置的三种方法 采用全局Hash函数在所有运行节点间动态分配未访问URL。
基于第一种方法，同时每个主控记录着一张Web主机表，这张表在各个主控中是相同的，其中每一条记录包含一个Web主机及其所对应主控信息。 采用两阶段映射的方法 采用全局Hash函数在所有运行节点间动态分配未访问URL。 基于第一种方法，同时每个主控记录着一张Web主机表，这张表在各个主控中是相同的，其中每一条记录包含一个Web主机及其所对应主控信息。 采用两阶段映射的方法。首先用Hash函数映射未访问URL到一张虚拟节点表上，然后将虚拟节点映射到不同的主控（实际节点）。虚拟表项通常远大于实际运行节点个数。 22

23 两阶段映射模型 已知：H : hosts on the web ; N : main-controllers; M : elements in the Array A. 则有：{ (h , n) | m =f1(h), n=f2(m), h∈H, m∈M, n∈N } 要求：(Ui ∩ Uj) = Ø ；(Hi ∩ Hj) = Ø ；(Ni ∩ Nj) = Ø 负载平衡 通信量低 各主控之间不重复工作 有利于后续工作 23

24 两阶段映射举例 设 N = 10 and M = 50000 a) 稳定状态 b)增加节点 c) 减少节点 1 … 2 9 11 10
N2 shift ( ) N10 shift ( ) N1 shift ( ) N1 ( ) Array A URLs N2 ( ) N9 ( ) N1( ) N10( ) N1( ) N2( ) N10( ) N9( ) a) 稳定状态 b)增加节点 c) 减少节点 24

25 提纲 问题提出 可扩展网页搜集系统 网页搜集系统的动态配置 海量网页应用研究初步 中国Web大小、形状和结构 工作总结 25

26 术语介绍 Web直径 网页出度，网页入度 存在于导航功能中的称为导航影响入度 存在于认可功能中的称为认可影响入度 有效入度
权威型网页，目录型网页 Web直径：P代表所有有序对(u,v)的集合，(u,v)表示存在一条从u到v的路径。所有最短路径的平均长度就是Web直径。 网站：在Web上具有独立的IP，当接收到HTTP请求时，返回响应码200和HTTP应答的网页。站点就是由驻留在该网站IP地址上的链接着的网页构成。对于不同IP，内容一样的网站，认为是不同的网站。 网页出度：在一个网页中发现的所有超链接数。 网页入度：其他网页指向同一个网页的链接数。入度主要有两种功能：导航功能（即网站的设计者自己在相关网页中安排的链接）和认可功能（一个网页对于另一网页的认可链接，两个网页的URL中域名不相同）。 值得注意的是在网页的入度中存在影响分析网页结构的链接。 存在于导航功能中的称为导航影响入度：一种情况是具有相同域名的两个网页之间的链接；一种情况是具有链接关系的两个网页的域名后面大部分相同（如sms.sina.com.cn 指向cul.sina.com.cn，news.sina.com.cn 指向photo.sina.com.cn）。 存在于认可功能中的称为认可影响入度：一个网站中可能有过多网页对于另一个网站中的一个网页认可。一种情况是两个网页的域名解析后的IP是相同的（如 指向 指向 由此引出有效入度的概念。 有效入度：其他网页指向同一个网页的链接数，包括的认可影响入度以10为上限，不包括导航影响入度。 26

27 天网搜集记录 第三次搜集数据具有代表性 覆盖了中国89.6%的网站，45.2%的网页。 类似于宽度优先搜索的策略
第三次搜集覆盖了中国89.6%的网站，45.2%的网页。 WebGather采用一种类似于宽度优先搜索的策略进行搜集，可以保证先搜集的网页更重要 WebGather系统在2002年1月覆盖了93.2%有影响力的网站 第三次搜集数据具有代表性 覆盖了中国89.6%的网站，45.2%的网页。 类似于宽度优先搜索的策略 覆盖了93.2%有影响力的网站 27

28 基本统计数据 平均每个网站有网页548.72个。 网页文字平均为12.92 KB，网站在各省之间的分布方差为24.18。
其中教育网有8144个网站，网站分布方差为16.14； 科技网有732个网站，网站分布方差为27.68。 28

29 中国Web的形状 29

30 Web页面链接 实验数据是2,278,524 网页，58,625,283 个链接 网页的平均出度为25.7。
在58,625,283 个链接中指向国外的链接数只有1%。 30

31 网页有效入度/出度分布 网页的度的分布（尤其是有效入度/入度分布）符合幂级数定律：拥有度为i的网页数与1/ix成正比，其中x>1
31

32 网页入度分布 网页的度的分布（尤其是有效入度/入度分布）符合幂级数定律：拥有度为i的网页数与1/ix成正比，其中x>1 x=1.86
32

33 Web结构 中国Web直径=17 Researchers Map the Web - Press Release
ALTAVISTA, COMPAQ AND IBM RESEARCHERS CREATE WORLD LARGEST, MOST ACCURATE PICTURE OF THE WEB "Bow Tie" Theory Shows the Web is Not as Connected as Previously Thought SAN JOSE, PALO ALTO & SAN MATEO, Calif. -- May 11, Scientists from IBM Research, Compaq Corporate Research Laboratories and AltaVista Company have completed the first comprehensive "map" of the World Wide Web, and uncovered divisive boundaries between regions of the Internet that can make navigation difficult or, in some cases, impossible. Previous studies, based on small samplings of the Web, suggested that there was a high degree of connectivity between sites as evidenced by recent reports on the "small world Web" and 19 degrees of separation. Contrary to those preliminary findings, the new study -- based on analysis of more than 500 million pages -- found that the World Wide Web is fundamentally divided into four large regions, each containing approximately the same number of pages. The findings further indicate that there are massive constellations of Web sites that are inaccessible by links, the most common route of travel between sites for Web surfers. Developing the "Bow Tie" Theory explained the dynamic behavior of the Web, and yielded insights into the complex organization of the Web. These discoveries will help computer scientists better understand the structure of the Internet, and lead to new technologies and design advances that will speed and simplify e-business. "Bow Tie" Theory Explains the Four Regions of the Web The image of the Web that emerged through the research was that of a bow tie. Four distinct regions make up approximately 90% of the Web (the bow tie), with approximately 10% of the Web completely disconnected from the entire bow tie. The "strongly-connected core" (the knot of the bow tie) contains about one-third of all Web sites. Web surfers can easily travel between these sites via hyperlinks, this large "connected core" is at the heart of the Web. One side of the bow contains "origination" pages, constituting almost one-quarter of the Web. "Origination" pages are pages that allow users to eventually reach the connected core, but cannot be reached from it. The other side of the bow contains "termination" page, constituting approximately almost one-quarter of the Web. "Termination" pages can be accessed from connected core, but do not link back to it. The fourth and final region contains "disconnected" pages, constituting approximately one fifth of the Web. Disconnected pages can be connected to origination and/or termination pages but are not accessible to or from the connected core. Impact of the Study With the Bow Tie Theory, and its new explanation of the structure of Internet, the scientific and business communities will now be able to: Design more effective Web crawling strategies. Crawling then indexing is the fundamental method employed by search engines to organize the Internet. To achieve more complete coverage, AltaVista and other search engines will be able to develop more advanced crawl strategies to capture more of the Web. Increase the effectiveness of e-commerce. Through the design of more effective browsing, advertising, measuring and modeling, E-commerce sites may decide to use different strategies for attracting surfers from various regions. For example, an "origination site" will have to increase its efforts to be easily found by Web crawlers. Once the site is linked to the connected core, its strategy may then shift to other traffic-generating measures. Analyze the behavior of Web algorithms that make use of link information. Because many search engines use link information in ranking algorithms, they become targets for link "spamming" intended to create an artificial increase in a site's linkage. Predict and capitalize upon the continued evolution of the Web. The researchers believe that the Bow Tie structure will be maintained as the Web grows. While some pages may evolve into the connected core, new pages will continue to be created in all three other regions. Create mathematical models for the Web. With these findings, researchers can now develop new models to study the growth of the Web and possibly predict the emergence of new, yet unexplored phenomena on the Web. This study - the largest ever to be conducted on the topography of the Web - is part of an ongoing, collaborative project by AltaVista, Compaq and IBM. The researchers expect to update the study on a regular basis from collected data using AltaVista search engine and advanced connectivity server software with Compaq AlphaServer system containing 16 gigabytes of RAM, enough to hold the entire Web map in memory. IBM Research analyzed the data and contributed to the development of the "Bow Tie" Theory. 33

34 Web社区 网络社区 C= P∪I 二分图定义 完全二分图 网络核心社区对应于完全二分图 Ccore=Pcore∪Icore
由于共同利益或兴趣而自发联系起来的网页。形式化表示为C= P∪I，其中C表示网络社区， P表示彼此之间互相关联或者都对I感兴趣的网页集合，I表示类型相同的网页集合。 二分图定义 若把一个图上的各节点分别编配成红色或蓝色，如果没有任何一条边连接两个相同颜色的节点，这种图称为二分图 完全二分图 若任一个红色结点都与所有的蓝色节点相邻 网络核心社区对应于完全二分图 Ccore=Pcore∪Icore。 提出了一种分析海量数据的方法 34

35 找出Web核心社区的方法 实验数据是2,278,524 网页，58,625,283 个链接，2.5GB。即Ppotential分布于2,278,524 网页根URL中， Ipotential分布于58,625,283个URL中 一个Ppotential相当于一个好的目录型网页（Hub）， 至少包含6个不同域名的超链接 剩下1/8左右的网页（数据文件的大小减少到313MB） 过滤掉后，得到118MB的链接文件 35

36 找出Web核心社区的方法(续1) 得到71MB的链接文件数据 数据文件变成14.5MB大小 去掉网页中有效入度大于9的链接
去掉链接中重复的部分 数据文件变成14.5MB大小 将链接数据中的根URL和超链接URL编码成整数 生成Ipotential列表和Ppotential列表以及URL和整数的对应关系表。得到Ppotential集合包含20,160个URL， Ipotential集合包含201,603个URL，Ppotential与Ipotential的元素个数比是1：10 用i表示Web核心社区中Pcore的元素数，用j表示Icore的元素数。在Web核心社区参数i>=3,j=3和i>=3,j=4的情况下，从Ipotential集合中分别随机抽取100个，200个，…，1000，结合全部的Ppotential，利用倒排表方法找出Web核心社区 36

37 找出Web核心社区的方法(续2) 从图5-10中可以看出随着Ipotential元素数的增加，Web核心社区数增长迅速，与人的直觉是一致的。其中Ipotential元素数在100到200，500到600之间时，核心数增长迅速，然后又过渡到相对平稳增长的状态。说明存在比较大的Web核心社区，当作为较小Web核心社区考虑时，派生出了很多有相交的核心社区。当核心参数增大时，较小的相交的核心社区可以合并 37

38 相关研究 基于Web的链接结构 PageRank HITS(Hyperlink-Induced Topic Search ) ……
权威型网页：对于一个特定的检索，该网页提供最好的相关信息； 目录型网页：该网页提供很多指向其它高质量权威型网页的超链。 38

39 回顾 1. 设计和实现了一种可扩展海量Web信息搜集系统体系结构 已发表 2. 设计实现了动态可配置方案 3.增量式搜集策略和网页搜集策略
Hongfei YAN, Jianyong WANG, Xiaoming LI, and Lin GUO, “Architectural Design and Evaluation of an Efficient Web-crawling System, ” Journal of System and Software, Vol. 60 No. 3, March pp YAN Hongfei, WANG Jianyong, LI Xiaoming, “A Dynamic Reconfiguration Model for a Distributed Web Crawling System”, Proceedings of ICCNMC’01, Beijing, Oct.16-19，2001, pp 待刊 闫宏飞, 李晓明. 中国Web大小、形状和结构.“计算机研究与发展”. No. 6, 2002年6月. 1. 设计和实现了一种可扩展海量Web信息搜集系统体系结构 2. 设计实现了动态可配置方案 3.增量式搜集策略和网页搜集策略 4. 提出了一种分析海量数据的方法，并由此得到了2002年初中国Web的大小、形状和结构，尤其设计了一种获得网络社区的方法。 1.基于对网页性质及其分布的认识，设计和实现了一种可扩展海量Web信息搜集系统体系结构。 2.针对并行网页搜集系统的节点可能出现临时故障的问题，提出了一种系统动态可配置方案。 3.基于Web InfoMall中的网页信息，探讨了海量Web信息应用的内容和方法。通过分析几千万网页的链接结构，给出了对2002年初中国Web的大小、形状和结构的一种定量认识，同时说明了如何从海量网页信息中高效地识别Web社区的一种方法。 4.本文设计和实现了建设Web信息博物馆中涉及到的存储和回放系统体系结构。 5.为了进一步缩短搜集网页的周期，或者搜集更多的网页，本文提出了应用于网页搜集系统的两种增量式搜集策略，一种是针对搜集的网页数目有限的情况，一种是针对海量的网页数目。 39

40 谢 谢！ 11.随着Web的迅猛发展，可以考虑物理上分布多个可扩展Web搜集系统，在更广泛意义下进行并行分布式的工作 40