《主控网状通信策略在web搜集系统中的应用及模拟分析 》由会员分享,可在线阅读,更多相关《主控网状通信策略在web搜集系统中的应用及模拟分析 (3页珍藏版)》请在金锄头文库上搜索。
1、1主控网状通信策略在 web 搜集系统中的 应用及模拟分析 摘要:搜索引擎所处理的对象是 Web 上成千上万的 Web 服务器通过网页之间的链接构成的海量信息,各个主机之间的联系或多或少,但都可以说是相对独立的本文研究了网状主控通信策略在 web 搜集系统中的应用情况。 关键词:主控网状通信策略 web 搜集系统中模拟 0 引言 搜索引擎已经成为快速、准确地在纷繁的信息网中定位自己所需东西的重要手段。然而要在搜索引擎中尽可能地找到用户所需信息,就要求搜索引擎索引尽可能多的网页。因此索引网页数量是评价一个搜索引擎好坏的关键因素之一。要索引更多的网页就要获取更多的网页,因此高效地获取网页是一个好搜
2、索引擎的基础。然而,单机系统受限于 CPU 的处理能力、磁盘存储的容量,而最致命的是系统可扩展性低,扩大规模的唯一方法是换成处理能力更强的系统,巨大的成本是难以令人接受的。采用可扩展并行分布式计算机系统结构处理 Web 上的海量信息,成为很自然和诱人的方案,扩大分布式系统处理能力只需要增加机器即可。并行分布技术的可实现性来自计算机网络速度的不断提高,交换技术保证各节点的通信可以相互独立,而不是像共享式技术一样所有节点共享全部带宽。在 10M 以太网的环境下,文件传输的速度可以达到 1MB/s;在 100M 以太网的环境下,文件传输的速度可以达到 10MB/s。一个以太网帧的最大长度是 1518
3、 个字节,在 10M 以太网的环境下传输时间是 1.2 毫秒;如果在千兆网环境下传输时间则是 12 微秒,这个时间延迟对于大多数应用都是可以忽略的。本文研究了网状主控通信策略在web 搜集系统中的应用情况。 21web 搜集系统概述 一个完整的 web 搜集系统主要包括搜集系统、索引系统、检索系统等不同组成部分,其中 Web 信息搜集系统是核心部件。系统分布的核心是数据的分布。对搜集部分而言,实际是将 URL 分布在执行搜集任务的机器之间,保证它们搜集的URL 不会重复。对查询部分,则是将索引数据分布在执行检索任务的机器之间。搜集节点之间相互协调,分配 URL,保证每个 Web 主机的全部网页
4、只能存在于一个搜集节点上。每个索引节点对应搜集节点搜集的网页,查询代理节点通过多播向所有索引节点发送查询命令,等待搜集到全部索引节点返回的检索结果后,对所有结果依据相关度排序,并缓存一定数量的结果,最后向用户返回结果的首页。用户的后续查询(翻页),将会在缓存命中,不必再次启动后面的网络查询,这将大大减少查询的响应时间,降低后面查询系统的负载,从而提高查询系统的性能。 2web 搜集系统的主控通信策略 2.1 主控通信策略的类型整个 Web 可以看作是一张有向图 G=(V,E)组成,V 表示网页的 URL,E 表示两个网页之间存在的超链接 URL,即一个网页中有另一个网页的 URL。对于图中任意
5、两个顶点 Vi,VjV,如果 Vi 到 Vj 有路径,则称 Vi 与Vj 是连通的。假设存在集合 Vs,其中初始仅起始 URL,随着对 G 的遍历,不断的扩充 Vs,对于 G 中任意一个 ViV,存在 VsiVs,从 Vsi 到 Vi 有路径,则认为 G是连通的。所以 Web 的搜集过程可以看作是从集合 Vs 出发,发现有向图 G 中所有 V 的过程。为了尽快的发现有向图 G 中所有的 V,应该采用多个搜集分系统从多个起始 URL 开始。考虑到网络速度限制和集中式系统中单台机器性能的限制,应该采用分布式并行工作。因此就存在一个主控通信的问题,一般主控通信策略主要包括以下两种:主控环形通信策略,
6、邻近的主控之间建立连接,形成环状3图。外发 URL 的传送可以选定顺时针或逆时针方向。主控网状通信策略,各主控制之间两两建立连接,形成一个外发网状图。外发 URL 的传送可以直接传递。 主控环形通信策略的系统运行初始化简单,但是因为有多次传送外发 URL 可能,存在通信量大的缺点。而采用主控网状通信策略则有明显优势,速度快,而且由于每两台主控之间都有连接,当有一台主控当机的情况下或增加新主控时,能够迅速的调整 URL 的分配。2.2 主控网状通信策略的应用 web 搜集系统使用主控环形通信策略的结构如图1 所示。在图 1 中,调度模块(WebGather Server Registry,简记为
7、 WSR),存储分布式系统内所有登记主控的信息,包括各登记主控的 IP 和端口号。当任一个主控的信息有所改变时,WSR 负责发送新的主控信息给其他主控,便于建立连接和变更连接。每个主控模块主控 1,主控 2,主控 N 负责搜集存储属于自己范围内的网页。每一个搜集模块搜集器 1,搜集器 2,搜集器 N 附属于相应的主控模块,负责接收所属主控发送的 URL,抓取该 URL 指向的网页并传送回所属主控。各主控模块之间都建立有双向连接,可以全双工的工作。当任一主控发现自己的搜集模块发回的网页中包含不属于自己的 URL 时,将此 URL 传送给它应属的主控去处理。为减少通信量,各主控之间只传送 URL。
8、3 模拟分析3.1 模拟环境 WebGather 自 1997 年 10 月正式提供查询服务以来,得到了广大用户的好评。本文以 WebGathe 作为模拟环境,在 WebGather 正常运行过程中,利用附加程序,产生分布式算法需要使用的模拟数据,对于每个网页保存了 URL 及其所包含的 URL 信息,大小为 507MB。通过运行程序,产生一有 761,129 个网页的模拟 Web 数据。以此作为我们的实验对象。程序运行的机器是一台 PC 机,配有4双 Intel550CPU,内存为 512MB,硬盘 36GB,运行的操作系统为 Solaris8.0。基于上述实验环境,我们分别模拟实验了主控数
9、 n 为 2,4,8,16 时四种情况。四组模拟实验分四次完成,每次运行 n 个主控时,同时运行一个集中式主控。每组运行时间至少为三天,获得了大量模拟实验数据。由于实验环境需要具有一致性,我们采用了集中解析域名方式,因此各个主控之间只有外发 URL 的通信量。各主控之间传递的只是 URL,根据经验值取定每个 URL 长度最大为 128 字节。这样的设定值既能满足绝大部分 URL 的长度规则,又能够有效控制通信量。考虑在上述后两种情况下的主控通信中,一个副本要传送给多个主控,在实际系统的运行中可以采用多播(multicast)技术。3.2 运行结果分析 为使系统负载平衡,采用 Hash 函数动态
10、分配 URL 给每个主控进行搜集,负载平衡的效果可以通过分析每个主控每小时搜集网页数获得,在运行环境相同的条件下,如果每个主控在相同的时间间隔内搜到的网页数大致相等,则证明系统是负载平衡的。可以看出,在主控数分别为 2,4,8,16 情况下,方差值均小于参照方差值,从图中可以看出任何一组实验数据的方差都小于参考方差。在图 2 中三角形线表示参考数据方差,方形线表示主控数为 2 时的方差,钻石形线表示主控数为 4 时的方差,加号形线表示主控数为 8 时的方差,星号形线表示主控数为 16 时的方差。这说明在各组实验条件下,分布式系统的每个主控程序承担的工作量基本相等(体现为搜集的网页数基本相等),因此搜索引擎分布式系统负载平衡达到预期目标。参考文献: 1孟涛,闫宏飞,王继民.一个增量搜集中国 Web 的系统模型及其实现J.清华大学学报(自然科学版),2005,(S1). 2刘玉莲,周春楠,张强.网页搜集系统的动态可配置性的研究与实现J.信息技5术,2004,(7). 3胡修林,杨刚,张蕴玉.嵌入式多任务操作系统中的任务间通信策略J.微型电脑应用,2007,(8).