文档介绍：国内图书分类号: 学校代码:10213
国际图书分类号: 密级:公开
工学硕士学位论文
面向广域网的分布式搜索引擎中
任务调度技术的研究
硕士研究生:刘爽
导师:李东教授
申请学位:工学硕士
学科:计算机科学与技术
所在单位:计算机科学与技术学院
答辩日期:2009 年 6 月
授予学位单位:哈尔滨工业大学
1
Classified Index:
:
Thesis for the Master Degree in Engineering
RESEARCH ON WAN-BASED TASK SCHEDULING
IN DISTRIBUTED SEARCH ENGINES
Candidate: Liu Shuang
Supervisor: Prof. Li Dong
Academic Degree Applied for: Master of Engineering
Speciality: Computer Science and Technology
Affiliation: School puter Science and
Technology
Date of Defence: June, 2009
Degree-Conferring-Institution: Harbin Institute of Technology
2
哈尔滨工业大学工学硕士学位论文
摘要
由于 Web 的地域分布式特性以及网络基础条件等方面的限制,随着 Web 的迅
速膨胀,目前的搜索引擎由于其集中式的结构遇到覆盖率和更新率方面的瓶颈。
使用广域网下的分布式搜索引擎,可以很好的适应 Web 信息管理的需求,获得比
传统搜索引擎更高的效率。分布式搜索引擎设计中最重要的部分之一是调度系
统,它将特定 Web 页面的抓取任务调度至广域网上效率较优的爬虫,以提高整个
搜索引擎的抓取效率。准确并且迅速的调度策略是分布式调度系统研究的关键问
题。
本文针对分布式搜索引擎的特点,综合考虑分布式结构中调度系统的需求,
研究分布式调度中关键技术并设计实现广域网上的分布式搜索引擎调度系统。本
文分析了基于随机哈希、基于网站域名后缀及文件类型、基于地理位置、基于 IP
注册信息等传统 Web 划分策略的弊端,首次将网络距离预测应用在 Web 爬虫调度
研究中。
为了更准确地预测爬虫下载网页的速率,本文提出使用应用层上网络距离测
量代替传统的网络层距离测量。之后,根据分布式搜索引擎爬虫加入退出的随机
性和不确定性,选用不依赖于固定测量点的距离预测算法计算 Web 节点网络坐
标。接着,在网络时延空间的基础上,研究和设计了划分准确性较高的基于迭代
自组织的高质量 Web 划分算法。针对 Web 划分结果,研究了一种对广域网上的分
布式搜索引擎按划分集合进行调度的算法,兼顾初始任务分配和动态调度时的负
载均衡性。最后,将坐标建立、Web 划分、调度三部分功能组合起来,设计了一
种可靠性高,支持节点动态组织,易于扩展的分布式调度系统体系结构。
本文针对应用层网络距离预测、Web 划分和负载均衡算法均进行了实验分
析。实验说明本文提出的广域网分布式调度系统的 Web 划分和负载均衡性能都比
较理想。
关键词:分布式搜索引擎;网络距离预测;Web 划分;广域网任务调度;负载均
衡
I
3
哈尔滨工业大学工学硕士学位论文
Abstract
As a result of distributed geographical characteristics of the Web work
infrastructure limitations and other conditions, with the Web's rapid expansion, current
search engines will suffer bottlenecks of coverage and update rates due to their
centralized structures. The use of distributed search engines working on WAN could
highly adapt to the needs