面向网络爬虫的海量URL数据管理技术研究

论文摘要

海量URL的管理一直是提高网络爬虫性能的一个瓶颈。现在,网络规模越来越大,更新速度也变得越来越快,这些都促使网络爬虫系统来提高其性能。所以如何高效地管理网络爬虫的海量URL,使之能够满足网络爬虫高性能的要求,也就显得越来越重要了。为了能够解决网络爬虫海量URL的高效管理问题,本文从工程的角度,提出这样一个解决方案。它包括一个基于NC-Trie的索引结构、一个面向NC-Trie的缓存机制和一个基于计算机指令流水思想的任务处理体系结构。首先,根据网络爬虫所要管理的URL都是字符串这一特点,本文选取计算机界公认的处理字符串信息最为高效的结构——Tire结构,来作为网络爬虫海量URL管理的索引结构。但是,Trie结构在高效处理字符串的同时,也存在很多缺点。对存储空间的浪费就是Tire结构的最大缺点。因此针对网络爬虫系统海量URL管理的特点,在原有的Trie结构压缩方法的基础上,本文提出一个改进的Trie压缩结构——NC-Trie。NC-Trie比原有的C-Trie具有更高的压缩率,同时也保持了Trie结构高速访问的优点。其次,由于网络爬虫要管理的URL数量巨大,必须借助外存才能更好地实现高效管理。因此,必须对索引结构进行必要的缓存。针对爬虫系统对URL管理的特点,对于海量URL的索引的缓存,本文将采用最近最少用的替换策略,并采用一个转换后的实现算法,来实施缓存的更新。再者,根据网络爬虫对URL访问的特点,本文使用计算机指令流水的基本思想,对网络爬虫对URL的各种操作进行细分,然后重新进行统筹组合,使之具有更高的并发度,以满足现代计算机的检索计算要求。最后,本文将设计和实现一个面向网络爬虫的URL管理系统。这个系统将包含如下模块:预处理模块、NC-Trie缓存管理模块、记录结构解析模块和硬盘缓存访问管理模块等。该系统的实现,为将来相关算法和实验的研究提供了一个基础平台。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究背景和意义
• 1.1.1 研究背景
• 1.1.2 研究意义
• 1.2 课题研究现状
• 1.2.1 基于计算机内存的URL 管理方式
• 1.2.2 基于已有的数据库系统
• 1.2.3 基于文件系统
• 1.3 课题研究内容
• 1.3.1 快速索引技术
• 1.3.2 海量URL 管理的缓存策略
• 1.3.3 海量URL 管理任务流水模型
• 1.4 本文的结构安排
• 第2章 基于NC-Trie 的海量URL 索引技术
• 2.1 常用的索引技术介绍及分析
• 2.1.1 HASH 索引技术
• 2.1.2 树结构索引技术
• 2.1.3 Hybrid-TH 索引技术
• 2.2 Trie 索引技术
• 2.2.1 Trie 概述
• 2.2.2 Trie 结点的表示
• 2.2.3 Trie 压缩技术
• 2.3 海量URL 管理的索引技术－NC-Trie
• 2.3.1 NC-Trie 的定义
• 2.3.2 NC-Trie 的结点结构
• 2.3.3 NC-Trie 的操作算法
• 2.3.4 NC-Trie 的效率分析
• 2.3.5 NC-Trie 的并发控制
• 2.4 NC-Trie 的辅助压缩
• 2.4.1 压缩属性值域的元素个数
• 2.4.2 压缩属性序列的长度
• 2.4.3 MD5 预处理
• 2.5 NC-Trie 中N 的确定
• 2.5.1 NC-Trie 外存结点的表示
• 2.5.2 确定NC-Trie 中N 的实验
• 2.5.3 实验结果及其分析
• 第3章 海量URL 管理的缓存技术
• 3.1 NC-Trie 索引的缓存技术
• 3.1.1 NC-Trie 索引的缓存组织结构
• 3.1.2 NC-Tire 索引的缓存替换策略
• 3.1.3 NC-Tire 索引的缓存替换算法
• 3.1.4 NC-Trie 缓存的访问控制
• 3.2 NC-Trie 结点更新缓存
• 3.2.1 NC-Trie 更新结点的缓存组织
• 3.2.2 NC-Trie 更新结点的数据一致性
• 3.2.3 缓存内容更新优化
• 3.3 记录的缓存技术
• 3.3.1 记录的结构
• 3.3.2 记录的缓冲器设计
• 3.3.3 记录的缓存更新优化
• 3.4 记录缓存优化和NC-Trie 结点缓存优化试
• 3.4.1 实验描述
• 3.4.2 实验结果和分析
• 3.5 NC-Trie 索引缓存试验
• 3.5.1 实验描述
• 3.5.2 实验结果及分析
• 第4章 基于指令流水思想的海量URL 管理优化
• 4.1 引入指令流水模型原因
• 4.1.1 提高程序的并发度
• 4.1.2 提高计算机处理器执行指令效率
• 4.2 海量URL 的指令管理
• 4.3 海量URL 的查询指令流水模型
• 4.3.1 查询操作执行过程
• 4.3.2 查询任务的分割
• 4.3.3 查询任务处理器设计
• 4.4 海量URL 的更新指令流水模型
• 4.4.1 更新操作执行过程
• 4.4.2 更新任务分割
• 4.4.3 更新任务处理器的设计
• 4.5 优化后的效果及其分析
• 第5章 基于硬盘NC-Trie 索引的海量URL 管理系统
• 5.1 系统设计与实现
• 5.1.1 开发平台及工具
• 5.1.2 实现意义及目标
• 5.1.3 系统总体设计
• 5.2 系统详细设计
• 5.3 系统的模块设计
• 5.3.1 任务预处理器
• 5.3.2 NC-Trie 索引管理模块
• 5.3.3 记录管理模块
• 5.3.4 任务流水线
• 5.3.5 外存优化访问管理器
• 5.3.6 流水线管理器
• 5.4 本章小结
• 结论
• 参考文献
• 致谢