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