没有合适的资源?快使用搜索试试~ 我知道了~
首页一种通用Cache的设计,实现和在天网搜索引擎中的应用
摘 要 2 第一章 背景介绍 3 1.1 万维网和海量信息 3 1.2搜索引擎概述 4 1.3 Cache概述 5 第二章 相关研究 6 2.1 Cache替换算法 6 2.2 Cache在搜索引擎中的应用 8 第三章 一种通用Cache的设计和实现 9 3.1 通用Cache的设计目标 9 3.3.1 通用性目标 9 3.3.2 高效性要求 10 3.3.3 自评测目标 10 3.2 通用Cache的设计 10 3.2.1总控器 11 3.2.2层次控制器 12 3.2.3数据存储器 13 3.2.4分层Cache设计的优点 13 第四章 通用Cache的搜索引擎检索端应用 15 4.1 实验环境 15 4.2 用户查询日志的分析 16 4.2.1查询的总体分布 16 4.2.2查询的时间局部性性质 18 4.3.3用户查询结果翻页的考察 19 4.3 通用Cache应用结构和配置 21 4.3.1总体结构 21 4.3.2缓存配置 23 4.3.3时间分析 25 第五章 总结和进一步工作 28
资源详情
资源评论
资源推荐
目 录
摘 要...............................................................................................................................2
第一章 背景介绍...........................................................................................................3
1.1 万维网和海量信息...........................................................................................3
1.2 搜索引擎概述...................................................................................................4
1.3 Cache 概述........................................................................................................4
第二章 相关研究...........................................................................................................6
2.1 Cache 替换算法................................................................................................6
2.2 Cache 在搜索引擎中的应用............................................................................7
第三章 一种通用 Cache 的设计和实现.......................................................................9
3.1 通用 Cache 的设计目标...................................................................................9
3.3.1 通用性目标.............................................................................................9
3.3.2 高效性要求...........................................................................................10
3.3.3 自评测目标...........................................................................................10
3.2 通用 Cache 的设计.........................................................................................10
3.2.1 总控器...................................................................................................11
3.2.2 层次控制器...........................................................................................12
3.2.3 数据存储器...........................................................................................13
3.2.4 分层 Cache 设计的优点........................................................................13
第四章 通用 Cache 的搜索引擎检索端应用.............................................................15
4.1 实验环境.........................................................................................................15
4.2 用户查询日志的分析.....................................................................................16
4.2.1 查询的总体分布...................................................................................16
4.2.2 查询的时间局部性性质.......................................................................18
4.3.3 用户查询结果翻页的考察...................................................................20
4.3 通用 Cache 应用结构和配置.........................................................................21
4.3.1 总体结构...............................................................................................21
4.3.2 缓存配置...............................................................................................23
4.3.3 时间分析...............................................................................................25
第五章 总结和进一步工作.........................................................................................28
参考文献......................................................................................................................29
致 谢.............................................................................................................................31
- 1 -
摘 要
摘 要
在处理 Web 海量信息的过程中,有两个问题制约着性能的提高。一
方面,由于信息量非常大,只能把所有数据存放在磁盘等相对慢速的设备
上,或者放在多台不同的机器上。对于数据的读取和保存只能从这些慢速
设备或者分布式的机器上获得。另一方面,信息量的庞大也造成了大量的
计算,消耗大量计算时间。在很多应用中,存在着引用的局部性规律,即
大量的操作需要访问少量的数据。本文工作包括:
1) 本文设计了一种通用的缓存 (Cache)结构。其主要特点是通用性,
在各 种应 用中 ,用 户可 以自 由地 对该 Cache 的容 量, 替换 算法 ,数 据项
结构,预取策略,体系结构进行配置。同时提供一个模拟接口,用户可以
通过这个接口执行模拟操作,对算法、容量进行评估。
2) 分析天网用 户查询日志, 发现对于用户 的查询,无论 是否考虑翻
页的情况,都满足类 Zipf 分布,这样的具有比较强的局部性的分布形式,
提示我们如果采用 Cache 结构可以带来很大的好处。
3) 在天网搜索引擎中检索模块中加入这种通用 Cache 模块。通过选
取适 当的 Cache 大 小, 替换 算法 ,预 取策 略和 层次 结构 ,进 一步 提高 搜
索引擎检索端的性能。
关键词:海量信息 缓存技术 分布特征 搜索引擎
- 2 -
第一章 背景介绍
第一章 背景介绍
1.1 万维网和海量信息
万维 网( WWW, 即World Wide Web ) 是因 特网 ( Internet ) 最
成功的应用之一。因特网的前身是美国国防部高级研究计划署的研究试验
性网ARPANET。 1983年TCP/IP 成为ARPANET上事实上的协议。 此后
ARPANET 上 连 接 的 网 络 、 机 器 和 用 户 快 速 增 长 。 1988 年 NSFNET 和
ARPANET 互联,它的规模以指数增长,很多地区网络开始加入,并且开
始与加拿大、欧洲和太平洋地区的网络连接。 从而Internet 逐渐形成和壮
大。
万维 网 起源 于 1989 年 的欧 洲 粒子 物 理研 究 室 ( CERN )。 1989 年 3
月, 由物 理学 家 Tim Berners-Lee 提出 万维网的计划。 1990 年9 月, 第一
个文本原型正式运行。此后,许多的大专院校和业界公司纷纷加入到万维
网的研究中来,开发大量的基于万维网的应用程序。在九十年代这短短几
年时间里,万维网吸引了的大量的用户和开发者,使得它不断地完善和发
展。
万维 网 是一 个 分布 式 的信 息 系 统, 它 由超 文 本 (hypertext) 和 超 媒体
(Hyper- media) 组成。超文本一般由文本信息和链接信息组成,文本信息
是供人 们浏 览阅读 的,链 接信息 又称 为超链 接 (Hyperlink) , 它们 是指向
别的超文本信息的指针,可以指向万维网上一个位置。超媒体是超文本的
扩展,包括在万维网上的各种资源,包括视频,音频,图像等等。
在这样一个系统中,一方面,用户可以通过超链接的指引,非常容易
地获取分布在不同机器上的信息。另一方面,各种不同地 区,职业的人们
可以自由地把本地的信息放到这个系统中去。这样,这个系统就成为一个
全球区 域的 ,包括 大量信 息的系 统。 根据Google 搜 索引擎 的统计 ,截 至
到2002年4月,全球的网页数已经超过20亿[Google]。在中国,万维网也
以惊人的速度发展。万维网于 1994 年正式在中国 建立, 2003 年中国互联
网络信 息资 源数量 调查报 告显 示,截 至2003 年 底, 中国的 网页总 数已 经
超过 3 亿, 总 字节数 超 过了 6T ,总 网 站 数达 到 59.6 万, 网 民 数近 8000 万
[Cnnic]。
这样庞大的一个万维网的规模,包含的信息是海量的。按照万维网的
这种发展速度,海量信息也是爆炸式的增长的。而人工在如此大规模的信
息中寻找有效信息是很困难的,低效的。我们需要采用一种方法,获取这
些海量信息并对它们进行一定程度的加工,从而帮助人们更好地利用这些
信息。其中的一种方法就是信息检索的方法( Information Retrieval ,简
称 IR)。它的过程是这样的:用户给出一个查询的请求(通常是一组关
键字或者一些问题),信息检索系统给出系统中与该查询相关的结果。从
- 3 -
第一章 背景介绍
而用户就可以方便的从获得的结果中提取有用的信息。
1.2 搜索引擎概述
搜索引 擎是信 息检索 在万维网上 一种很 好的应 用。 它的 基本功 能是:
用户给出查询,搜索引擎返回给用户和查询相关的万维网上的信息。由于
在很多情况下,相关信息结果是大量的,因此系统需要对这些结果进行查
询相关性排序,把更加相关更加有用的信息放在前面,便于用户的浏览,
最后返回排序后的结果。用户可以通过搜索引擎,很容易地获取他们所需
要的万维网上的信息,大大提高了利用信息的效率。
最 早 的 万 维 网 的 搜 索 引 擎 叫 做 World Wide Web Worm (WWWW)
[McBryan.,1994] ,它建于1994年,当时它只有收集了110000的网页,每
天对于它 的查 询在 1500个左右 。在以后的 10 年里 ,搜索引擎有 了大规模
的 发 展 , 截 至 2003 年 底 , Google 索 引 的 网 页 数 已 经 超 过 了 40 亿
[Google] 。
天网搜索引擎[天网]是针对中国万维网上丰富的信息资源而开发的具
有中文特色的搜索引擎。本文的工作,就是在天网搜索引擎的基础上完成
的。
搜索引擎的工作流程基本包括三个步骤:
1 、Web 网页的搜 集:它 的基 本原理 是先设 定一 个初始 的 URL 集合
S , 对 于 集 合 中 的 每个 URL , 搜 集 器 下 载对 应 的 网 页 ,从 S 中 删除 这 个
URL ,扫描这个网页,把这个网页向外的链接中没有被下载过的 URL 加
到 S 中,如此的循环操作,直至 S 集合为空。通过这一过程,我们获取了
Web 上从初始集合 S 出发的所有可达网页。
2、对 Web 网页建立索引库:建立索引的目的是加快查询的速度。通
常的是采取倒排表的技术,即对于每一个关键词,建立这个关键词出现的
文档号和位置号的列表。在检索的时候,用户输入的关键词就可以快速对
应到倒排文件的某一个关键词,从而获得结果。
3、检索查询:用户输入一系列关键词,程序在倒排表中找到相应的
项,进行相关的运算,获得结果的集合。然后根据网页的重要程度以及网
页和查询的相关程度进行评测,给出结果的排序,然后根据这个排序返回
给用户结果页面。
1.3 Cache 概述
高速缓 冲存 储器( Cache )在单 机的 物理结 构上, 是处于 CPU 和主
存之间的一种存储器,它的大小一般很小,只有几十到几百 K,存取速度
在主存和 CPU 寄存器之间,考虑到计算机在使用的过程中对数据块的存
取有很强的时间局部性和空间局部性,因此我们采用它来暂存常用的数据
块,以缩短存取的时间。
- 4 -
第一章 背景介绍
我们这 里的 Cache 只是一 种和 物理 Cache 思想 类似的 逻辑结 构, 它
的物理媒介是主存。在很多应用程序中,对数据的使用有很强的局部性的
特征。这里的数据包括:存储在磁盘,磁带等慢速设备上的数据 ;存在分
布式系统上的数据;需要经过复杂操作和运算才能获得的数据。这些数据
的一个共同特点是:获得这些数据都需要花费很长的时间,对于磁盘、磁
带上的数据,需要很长的寻道时间;对于其他机器上的数据,需要较长的
网络传输的时间;对于复杂操作获得数据,需要较长的 CPU 计算时间。
考虑到如果这些应用有一些局部性的规律,那么我们可以把这些数据中可
能会 比较 常用 到的 保存 在 Cache 中 ,在 以后 的使 用中 ,就 可以 避免 上述
的代价较大的三种操作。 Cache 和一般内存的一个区别就是在逻辑上,它
可以有一定的替换策略,决定在一定的时候添加哪些内容,替换出哪些内
容,这些操作使得内存中存储的总是最可能在近期被访问到的。
- 5 -
剩余30页未读,继续阅读
anspider
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0