《网页的收集(预备知识)-CNDS.ppt》由会员分享，可在线阅读，更多相关《网页的收集(预备知识)-CNDS.ppt（39页珍藏版）》请在三一办公上搜索。
1、1,网页的收集（2）,李晓明，2003年10月参考Mining the Web,2,Global Picture,收集（爬取，crawling）批量（batch）还是增量（incremental）？整理净化（purification），打分，切词服务倒排索引（inverted index，含位置信息与否）字面匹配，概念匹配静态摘要还是动态摘要？排序,3,大规模爬取器的一种结构图,4,大规模爬取器：性能和可靠性问题,同时并发抓取多个网页（例如一台机器200个并发）这是充分利用网络带宽的基础避免让DNS查询成为瓶颈利用异步sockets（Soumen的观点）用一个数据结构，显式将一个抓取过程的状态
2、表达出来检查结束标志多进程、多线程：漂亮但不实用URL提取中的问题消除重复，减少冗余的抓取（不那么容易，同义URL问题）避免“spider traps”，陷入少量网站中,5,DNS缓存，预取和解析,如果不采取措施，DNS地址解析会成为一个重要的瓶颈局域网中，DNS服务器通常较小，对付几百个工作站的常规操作没问题，但一个crawler产生的压力大很多避免同时从一个服务器抓许多网页也使DNS的cache能力发挥不出来（破坏了locality）搜索引擎中可以设计一个专用的DNS模块，含有用于地址解析的DNS client（和本模块的DNS缓存服务器打交道）缓存server预取client,6,用于高
3、效地址解析的定制client,一般系统（例如UNIX）提供的DNS client没有考虑cralwer的需求，带来两个问题：以gethostbyname()为基础，它不能并发；不会考虑在多个DNS server之间分配负载。因此一个custom client很必要。专门对付多个请求的并发处理容许一次发出多个解析请求通过polling来看请求的完成情况协助在多个DNS server之间做负载分配（例如根据掌握的URL进行适当调度）,7,缓存服务器（DNS Caching Server）,大缓存容量，跨DNS系统的刷新保持内容Internet的DNS系统会定期刷新，交换更新的域名和IP的信息。普通
4、的DNS cache一般应该尊重上级DNS服务器带来的域名“过期”的信息，但用于爬取网页的DNS cache不一定如此，以减小开销（让缓存中有些过期的无所谓，但也要注意安排适时刷新）映射尽量放在内存，可以考虑用一台专门的PC,8,预取client,为了减少等待查找涉及新主机的地址的时间：尽早将主机名投给DNS系统步骤分析刚得到的网页从HREF属性中提取主机名（不是完整的URL）向缓存服务器提交DNS解析请求结果放到DNS cache中（后面可能有用，也可能用不上）通常用UDP实现非连接，基于包的通信协议，不保证包的投递用不着等待解析的完成,9,10,多个并发的抓取,管理多个并发的连接单个下载可
5、能需要几秒钟同时对不同的HTTP服务器建立许多socket 连接过多的硬件并行好处不大爬取的性能瓶颈主要在网络和硬盘两种基本方法用多线程用带事件处理的非阻塞sockets,11,多线程方法,逻辑线程（进程）操作系统控制的线程（例如pthread），或并发进程（地址空间分离，好处是相互干扰不大）通常根据经验采用一个预先确定的线程数量程序设计创建一个client socket将该socket连接到服务器的HTTP服务上发送HTTP请求读socket(recv)直到没有更多的东西可读 还可以是通过时间判断中止关闭socket通常用阻塞的系统调用（简单；等待和计算的重叠靠并发多线程“随机”实现）,12
6、,多线程：问题,性能代价（performance penalty）互斥（共享的工作数据区数据结构的并发访问）磁盘访问代价并发线程在完成抓取后，进行文档存储时会形成大量交叉的，随机磁盘I/O，外部表现就是磁盘不断的寻道，很慢。用程序的方式协调这种访问的开销可能会更大（线程互斥，或者进程通信，都很复杂）,13,非阻塞socket和事件处理：就是一个进程,非阻塞socketsconnect,send或recv调用立刻返回，不需要等网络操作的完成（因此可以连续给出多个）随后可以通过polling来检查完成的状态“select”系统调用：专门针对非阻塞socket让调用者挂起，直到数据可以通过socke
7、t读/写，或者期限超时可以同时监管多个sockets的状态，一个可用就返回select体现了更高效的存储管理：一次select返回一个socket标识网页抓取的完成不相互影响（自然地序列化了！）于是在共享的任务池上也不需要加锁或者信号灯！,14,“燕捷”就是用这种non blocking socket实现了文件跨多个ftp服务器传送的流水线！,15,链接提取和规格化,目标：得到网页中所含URL的标准型URL的处理和过滤避免多次抓取被不同url指向的相同网页IP地址和域名之间的多对多关系（见以前的讨论）大规模网站用于负载平衡的技术：内容镜像“virtual hosting”和“Proxy pas
8、s”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持）相对URL需要补齐基础URL,16,对URL进行规格化,用一个标准的字符串表示协议利用canonical主机名字查DNS会返回IP和一个canonical名字显式加上一个端口号（80也加上）规格化并清理好文档路径例如将/books/./papers/sigmod1999.ps写成/papers/sigmod1999.ps,17,节省资源：避免“同义”地址,前面总结过各种情况，对于CPAL=1001,1110两种情况我们有可能避免重复抓取1001:新浪，搜狐，,18,礼貌工作：不给网站造成明显负载,随着人们自我保护
9、的意识越来越强，这问题越来越重要“香港天网”从一开始就被抱怨天网最近也受到抱怨不希望搜索引擎上“黑名单”,19,Robot exclusion,检查 在服务器文档根目录中的文件，robots.txt包含一个路径前缀表，crawlers不应该跟进去抓文档，例如#AltaVista SearchUser-agent:AltaVista Intranet V2.0 W3C WebreqDisallow:/Out-Of-Date#exclude some access-controlled areasUser-agent:*Disallow:/TeamDisallow:/ProjectDisallow
10、:/Systems限制只是对crawlers，一般浏览无妨“君子协定”（你的crawler可以不遵守）,20,消除已经访问过的URL,检查某个URL是否已经被抓过了 在将一个新的URL放到工作池之前要很快，不要在这里形成性能瓶颈（检查将要访问磁盘）可以通过计算并对比（规格化后的）URL的MD5来实现利用访问的时空局部性两级hash函数（改善对空间局部性的利用）主机名+端口号，散列到高位（例如高24位）路径散列到低位（例如后面的40位）用B-树管理符合条件（即未被访问过）的URLs放到crawler的任务中.,21,B-tree,一种平衡搜索树，特别适合磁盘操作每个节点和磁盘的block一样大由
11、系统实现的Allocate-Node（）来保证于是每个节点可以容纳很多key每个节点可以有很多子节点，例如1000树通常很“矮”于是搜索涉及的节点个数不多任何时候只有有限的几个节点在内存思考：写出此时在两级hash安排下的搜索算法，并说明它是如何开发了局部性。,22,爬取器的陷阱,防止系统异常病态HTML文件例如，有的网页含有68 kB null字符误导爬取器的网站用CGI程序产生无限个网页用软目录创建的很深的路径HTTP服务器中的路径重映射特征,23,24,爬取器的陷阱：解决方案,不存在完美的自动方案，积累历史数据很重要。检查URL的长度保护模块（Guards）定期收集爬取中的统计数据发现太
12、突出的网站（例如收集过程过多出现它），就将它放到保护模块中，以后就不考虑来自于它的URL。不爬取动态的内容（unsolved problem），例如由CGI表格查询产生的清除非文本类型的URLs（即它的MIME类型不是text/*）,25,避免在重复的网页上再提取链接,减少爬取中的别名冗余网页（不仅本身开销，还有其中的相对链接v）重复网页的检测：镜像网页和网站检测完全重复的网页（exact duplicates）对比不同URL对应网页的MD5摘要（访问一次磁盘）或者，将相对于网页u的链接v表示为(h(u);v)，其中h(u)是u的内容的散列。这样，两个别名的相同相对链接就有同样的表示，直接放到
13、isUrlVisited中检查检测接近重复的网页（near-duplicates）即使是一个字符的改变也会完全改变MD5摘要例如，网页的转载常伴随有日期或者网站管理者名字的变化解决方案：Shingling（分段，今后介绍）,26,负载监管,跟踪各种系统统计量最近网络连接的性能例如：时延和带宽的估计爬取器可以打开的sockets的上限当前活跃sockets数量高级搜索引擎的一个有机组成部分（built-in,not an extra module）,27,过程管理,负责 从任务池中选工作单元网络资源的调度将请求分发给多个网站（尽量）利用来自负载监管器的数据,28,为每个Web服务器建立一个工作队
14、列,尊重Web服务器为防止拒绝服务（DoS）攻击采取的措施对任何固定IP地址来的客户访问，限制对其响应的速度或者频度限制对一个IP地址的活跃请求数量对每个服务器维护一个请求队列利用HTTP/1.1的持续socket能力在一个较大的网站范围均匀的分布抓取活动在“利用访问的局部性”和“对网站的礼貌性”之间求得平衡,29,文本仓储,爬取器最后的任务将抓得的网页放到一个仓储（repository）中好处：将crawler和搜索引擎系统的其他功能分开，既有效率的好处，也有可靠性好处和网页相关的信息存成两个部分元数据网页内容,30,和网页相关信息的存贮,元数据 包括的域有content-type,last
15、-modified date,content-length,HTTP status code,etc.本质上可以表达成关系但通常是由特别定制的软件来管理，以避免关系数据库的访问开销（以可能的可靠性损失为代价）（我们这里不谈建立索引的问题）,31,网页内容的存贮,典型HTML网页可以压缩到2-4 kB(using zlib)文件系统的block size通常是4-8 kB（对网页太大！），“一个block，一个文件”损失太大因此网页的存贮管理应该由专用存贮管理器来完成提供简单的访问方法（method），用来便于让crawler往里添加网页后边的程序（索引器等）从中获取文档,32,网页存贮,小规模
16、系统能在一台机器的硬盘上放下用存贮管理器（例如，Berkeley DB）在一个文件内，管理基于磁盘的数据库如果后续访问操作是随机的，例如以URL为键，则可以将它配置成hash-table/B-tree。访问开销较大。如果后续访问可以是顺序的，例如索引器，则可以将它配置成一个顺序的网页记录。访问效率较高,33,网页存储,大规模系统仓储分布在多个存储服务器上存储服务器通过高速局域网连到crawler按照URL散列网页到存储服务器,34,大规模爬取器经常同时爬取多个ISP上的网页，并且用一组存储服务器来存放爬来的网页,35,刷新爬来的网页,搜索引擎的索引需要不时有刷新在Web-scale上工作的cr
17、awler总不可能收全所有的网页网页的改变率有一个很高的variance在HTTP协议中有一个“If-modified-since”请求头但是对crawler不适合，检查就很费时解决方案在启动新的一轮爬取时估计哪些网页改变了,36,确定网页的变化,HTTP响应头中的“Expires”有些网页用它来指出过期时间没有这个指示的话，就要来猜对那个网页的改动是否产生了一个新的版本给一个反映网页改动概率的评分Crawler抓取URLs，按照评分递减序假设：recent past predicts the future利用抓取的结果调整概率,37,估计网页变化率,Brewington和Cybenko&Cho的工作 Algorithms for maintaining a crawl in which most pages are fresher than a specified epoch.预先要求爬取器检查网页变化的平均周期小于网页两次修改的平均间隔时间用一个小规模crawler，在两次大规模爬取期间监测快速变化的网站例如，新闻，天气预报，等等将得到的中间索引及时“补丁”到主索引上,38,39,
