Crawling the Web http://net.pku.edu.cn/~wbia 彭波 pb@net.pku.edu.cn 北京大学信息科学技术学院 9/24/2010

本次课大纲 How to collect data from Web? Build a Crawler High Performance Web Crawler Distributed Crawling/Incremental Crawling State-of-art technology

Build a Crawler!

链接是哪些？

Refer to HTML 4.01 Specification http://www.w3.org/TR/1999/REC-html401-19991224/html40.txt

GET Method in HTTP Refer to RFC 2616 HTTP Made Really Easy

怎样搜集? 网页为节点 网页中的HyperLink为有向边 Crawl == 图遍历, right? <href …> Web是一个有向图 网页为节点 网页中的HyperLink为有向边 Crawl == 图遍历, right?

系统框图 Fetcher Extractor Writer PreProcessor PostProcessor Frontier

Core Algorithms I PROCEDURE SPIDER1(G) Let ROOT := any URL from G Initialize STACK <stack data structure> Let STACK := push(ROOT, STACK) Initialize COLLECTION <big file of URL-page pairs> While STACK is not empty, URLcurr := pop(STACK) PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION

Review of Algorithm I 重复搜集， 遇到回路会无限循环 G如果不连通呢？ G如果大到STACK容纳不下呢？ PROCEDURE SPIDER1(G) Let ROOT := any URL from G Initialize STACK <stack data structure> Let STACK := push(ROOT, STACK) Initialize COLLECTION <big file of URL-page pairs> While STACK is not empty, URLcurr := pop(STACK) PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION 重复搜集， 遇到回路会无限循环 G如果不连通呢？ G如果大到STACK容纳不下呢？ 要控制搜集G的一部分呢？ Completeness is not guaranteed Impossible to guarantee each connected subgraph is sampled How to make it better? more seeds, more diverse seeds, port scanner maybe help

A More Complete Correct Algorithm PROCEDURE SPIDER4(G, {SEEDS}) Initialize COLLECTION <big file of URL-page pairs> Initialize VISITED <big hash-table> For every ROOT in SEEDS Initialize STACK <stack data structure> Let STACK := push(ROOT, STACK) While STACK is not empty, Do URLcurr := pop(STACK) Until URLcurr is not in COLLECTION insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr) STORE(<URLcurr, PAGE>, COLLECTION) For every URLi in PAGE, push(URLi, STACK) Return COLLECTION STACK 用disk-based heap结构实现 Until URLcurr is not in VISITED Given that the bandwidth for conducting crawls is neither infinite nor free, it is becoming essential to crawl the Web in not only a scalable, but efficient way, if some reasonable measure of quality or freshness is to be maintained." [1] ^ a b Edwards, J., McCurley, K. S., and Tomlin, J. A. (2001). "An adaptive model for optimizing performance of an incremental web crawler". In Proceedings of the Tenth Conference on World Wide Web: 106–113. Hong Kong: Elsevier Science. doi:10.1145/371920.371960. .

还存在什么问题呢？ Web规模在不断增长，容量巨大 必须具备高效率 1 billion pages / per month385pages/sec Crawler系统的瓶颈在哪里？ 加更多收集机器是否能解决问题？ 在I/O部分，look-up(), Store()  特别是需要提高网络带宽利用率 当数据量大到那些data structure不能够在内存中放下时 优化 Is url or pages VISITED

还存在什么问题呢？ The real world is not perfect 镜像与重复网页 (mirrors and duplications) url/html 语法错误 服务器陷阱(server traps) 服务器抱怨 法律问题 系统崩溃， 停电… http://flickr.com/photos/try-to-touch/483189630/

URL不唯一性 有多少个ip地址？ 不同url指向的同一个网页 动态网页的参数 IP地址和域名之间的多对多关系 http://www.china-pub.com/browse/?typeid=02&ordertype=1 http://www.china-pub.com/browse/?typeid=02&ordertype=1&nonsense=1 不同url指向的同一个网页 IP地址和域名之间的多对多关系 大规模网站用于负载平衡的技术：内容镜像 “virtual hosting”和“Proxy pass”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持） 动态网页的参数 Session id 上一页/下一页 Ping www.sina.com.cn 返回 121.194.0.205 ---- 121.194.0.209

对URL进行规格化 用一个标准的字符串表示协议(http) 利用canonical主机名字 显式加上一个端口号（80也加上） 查DNS会返回IP和一个canonical名字 显式加上一个端口号（80也加上） 规格化并清理好文档路径 例如将/books/../papers/sigmod1999.ps写成/papers/sigmod1999.ps

Robot exclusion 检查 限制只是对crawlers，一般浏览无妨 在服务器文档根目录中的文件，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可以不遵守）

Server traps 防止系统异常 病态HTML文件 例如，有的网页含有68 kB null字符 误导Crawler的网站 用CGI程序产生无限个网页 用软目录创建的很深的路径 www.troutbums.com/Flyfactory/hatchline/hatchline/hatchline/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/hatchline HTTP服务器中的路径重映射特征

Web Crawler need… 快 Fast 可扩展性 Scalable 友好性 Polite 健壮 Robust Bottleneck? Network utilization 可扩展性 Scalable Parallel , distributed 友好性 Polite DoS（Deny of Service Attack）, robot.txt 健壮 Robust Traps, errors, crash recovery 持续搜集 Continuous Batch or incremental 时新性Freshness

High Performance Web Crawler

系统框图 Fetcher Extractor Writer PreProcessor PostProcessor Frontier

大规模Web Crawler的 一种结构图 Writer Fetcher Extractor Frontier Part 1. DNS resolver Frontier

大规模Web Crawler的 一种结构图 Part 1. DNS resolver

DNS resolver Typical DNS request are synchronized! DNS can take long time to resolve host names Host name may never resolve Question: 同步和异步，阻塞和非阻塞 调用是？ Question:　同步、异步、阻塞和非阻塞的概念

DNS解析 如果不采取措施，DNS地址解析会成为一个重要的瓶颈 怎样提高DNS解析模块的性能？ 局域网中，DNS服务器通常较小，对付几百个工作站的常规操作没问题，但一个crawler产生的压力大很多 通常的DNS解析系统调用是同步调用（synchronized） 避免同时从一个服务器抓许多网页也使DNS的cache能力发挥不出来 怎样提高DNS解析模块的性能？ 并发DNS client 缓存cache dns results 预取prefech client Question: cache的原理，局部性是？

并发的地址解析client 一般系统（例如UNIX）提供的DNS client没有考虑cralwer的需求，带来两个问题： 以gethostbyname()为基础，它不可重入非线程安全 不会考虑在多个DNS server之间分配负载。 因此一个custom client很必要。 专门对付多个请求的并发处理 容许一次发出多个解析请求(multiplexer) 协助在多个DNS server之间做负载分配（例如根据掌握的URL进行适当调度） http://www.chiark.greenend.org.uk/~ian/adns/ Advanced, easy to use, asynchronous-capable DNS client library and utilities.

缓存服务器（DNS Caching Server） Internet的DNS系统会定期刷新，交换更新的域名和IP的信息。 普通的DNS cache一般应该尊重上级DNS服务器带来的域名“过期”的信息，但用于爬取网页的DNS cache不一定如此，以减小开销（让缓存中有些过期的无所谓，但也要注意安排适时刷新） 映射尽量放在内存，可以考虑用一台专门的PC

预取client 为了减少等待查找涉及新主机的地址的时间：尽早将主机名投给DNS系统 步骤 通常用UDP实现 用不着等待解析的完成 分析刚得到的网页 从HREF属性中提取主机名（不是完整的URL） 向缓存服务器提交DNS解析请求 结果放到DNS cache中（后面可能有用，也可能用不上） 通常用UDP实现 非连接，基于包的通信协议，不保证包的投递 用不着等待解析的完成 Asynchronous调用 Asynchronized or unblocked system call?

Asynchronous Concurrent DNS Client send Prefetch HostName() send Send Queue send Cache DnsLookup() recv polling/select recv recv DNS server

大规模爬取器的一种结构图 Part Two: page fetching context

Page fetching 获取一个网页需要多少时间？ Problem: Solutions: 局域网的延迟在1-10ms，带宽为10-1000Mbps,Internet的延迟在100-500ms，带宽为0.010-2 Mbps 在一个网络往返时间RTT为200ms的广域网中，服务器处理时间SPT为100ms，那么TCP上的事务时间就大约500ms（2 RTT+SPT） 网页的发送是分成一系列帧进行的，则发送1个网页的时间量级在(13KB/1500B) * 500ms ≈4s Problem: network connection and transfer overheads Solutions: Multiple concurrent fetches ？ Problem: network connection and transfer overheads

多个并发的抓取 管理多个并发的连接 过多的硬件并行好处不大 两种基本方法 单个下载可能需要几秒钟 同时对不同的HTTP服务器建立许多socket 连接 过多的硬件并行好处不大 抓取的性能瓶颈主要在网络和硬盘 两种基本方法 用多线程/多进程 用异步I/O:带事件处理的非阻塞sockets

多线程方法 逻辑线程（进程） 通常根据经验采用一个预先确定的线程数量 程序设计 操作系统控制的线程（例如pthread），或 并发进程（地址空间分离，好处是相互干扰不大） 通常根据经验采用一个预先确定的线程数量 平均4秒抓取时间下，按带宽100%利用计算，可完成4*100Mb/(8*13KB) ≈ 4000个网页，约启动4000个线程 程序设计 创建一个client socket 将该socket连接到服务器的HTTP服务上 发送HTTP请求 读socket (recv)直到没有更多的东西可读 还可以是通过时间超时判断中止 关闭socket 通常用阻塞的系统调用（简单；等待和计算的重叠靠并发多线程“随机”实现）

多线程：问题 多线程的性能代价（performance penalty） 内存地址空间不够 互斥 共享的工作数据区数据结构的并发访问，用程序的方式协调这种访问的开销可能会更大（线程互斥，或者进程通信，都很复杂） 磁盘访问代价 并发线程在完成抓取后，进行文档存储时会形成大量交叉的，随机磁盘I/O，外部表现就是磁盘不断的寻道，很慢。

异步非阻塞socket和事件处理：单进程 Refer to C10K Problem 异步非阻塞sockets connect, send或recv调用立刻返回，不需要等网络操作的完成（因此可以连续给出多个） 随后可以通过polling来检查完成的状态 “select”系统调用：专门针对非阻塞socket 让调用者挂起，直到数据可以通过socket读/写，或者期限超时 可以同时监管多个sockets的状态，一个可用就返回 select体现了更高效的存储管理：一次select返回一个socket标识 网页抓取的完成不相互影响（自然地序列化了！） 于是在共享的任务池上也不需要加锁或者信号灯！ 缺点： Context维护，编程复杂 Smp无法用，还要多线程

大规模爬取器的一种结构图 Part Three:　Url Distiller

消除已经访问过的URL 检查某个URL是否已经被抓过了 优化方法 在将一个新的URL (规格化后的)放到工作池之前 要很快，不要在这里形成性能瓶颈（检查将要访问磁盘） 符合条件（即未被访问过）的URLs放到crawler的任务中 优化方法 URL用fingerprint (如MD5)来记录，减少内存开销 利用访问的时空局部性--Cache 海量数据的高效率查找表 B-tree Bloom filter Robin Fingerprint .vs. MD5

IsURLVisisted: B-tree实现 一种平衡搜索树，适合基于外存的查找 每个节点和磁盘的block一样大 每个节点可以容纳很多key 每个节点可以有很多子节点，例如1000 树通常很“矮”，于是搜索涉及的节点个数不多 维护节点中数据key的有序性有助于提高查找效率 顺序数据访问将有效利用I/O系统的缓存 思考题： 对URL串作fingerprint节省了存储开销，但破坏了它的局部性，使得缓存命中率下降。设计一种更有效的使用fingerprint方法，改善这一状况。 Why?

IsURLVisisted: Bloom filter Bloom filters are compact data structures for probabilistic representation of a set in order to support membership queries. 查找集合是否包含一个元素（查找表） False Positive 可由参数n(string number), k(hash function number), m(bit-array size)调节 Internet Archive的crawler Heritrix使用的技术 http://crawler.archive.org/ http://www.cl.cam.ac.uk/~ey204/h_files/sp.htm

Simple Example Use a bloom filter of 16 bits h1(key) = key mod 16 h2(key) = key mod 14 + 2 Insert numbers 27, 18, 29 and 28 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Check for 22: H1(22) = 6, h2(22) = 10 (not in filter) Check for 51 H1(51) = 3, h2(51) = 11 (false positive)

在“利用访问的局部性”和“对网站的礼貌性”之间求得平衡

避免在重复的网页上再提取链接 检测完全重复的网页（exact duplicates） 检测接近重复的网页（near-duplicates） 对比不同URL对应网页的MD5摘要（访问一次磁盘） 或者，将相对于网页u的链接v表示为(h(u);v)，其中h(u)是u的内容的散列。这样，两个别名的相同相对链接就有同样的表示，直接放到isUrlVisited中检查 检测接近重复的网页（near-duplicates） 即使是一个字符的改变也会完全改变MD5摘要 例如，网页的转载常伴随有日期或者网站管理者名字的变化 解决方案：Shingling（分段，今后介绍） 减少爬取中的别名冗余网页（不仅本身开销，还有其中的相对链接v） 重复网页的检测：镜像网页和网站

Distributed Crawling

分布式计算 中央控制节点Master-Slave模式 对等Peer-to-peer模式

任务划分问题 M个节点同时执行搜集 问题：如何有效的把N个网站的搜集任务分配到M个机器上去？ 目标：任务分配得均匀（ Balance ） 谁负责http://www.pku.edu.cn/？

{ Hashing 从一个值均匀分布的 hash 函数开始: 把 values 映射到 hash buckets h(name)  a value (e.g., 32-bit integer) 把 values 映射到 hash buckets 一般取模 mod (# buckets) 把 items 放到buckets 冲突，需要 chain解决冲突 h(x) values buckets { … 1 12 8 4 2 3 Some pages here borrowed from http://www.seas.upenn.edu/~zives/cis555/ It’s a nice course! overflow chain 45

在机器间划分Hash Table 简单划分 – 把buckets按组分配到对应机器上去 问题？ 对应表可以发给用户，或者维护一个全局目录 可以控制均匀分配，或者按capacity分配多少 查找十分简单 问题？ 新增加节点，节点crash，节点重新加入， 机器数目变化情况下……. 46

We need… 在一个分布式系统中，无需集中目录，也无需担心节点失效的一种查找元素位置的方法 Consistent Hashing

Basic Ideas 使用一个巨大的hash key空间 SHA-1 hash: 20B, or 160 bits 把它组织成 “circular ring” (在 2160 处回到0) 我们把 objects’ keys (这里是URL) 和nodes’ IP addresses 都hash映射到一个hash key 空间 “www.pku.edu.cn”  SHA-1  K10 130.140.59.2  SHA-1  K12 48

Hashes a Key to its Successor N10 Node ID k112 k11 N100 Circular hash ID Space k30 k99 Key Hash N32 k33 You can read this: http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html And http://www.danga.com/memcached/ k40 N80 k52 k70 k65 N60 49 49

Hashes a Key to its Successor N10 Node ID k112 k11 N100 Circular hash ID Space k30 k99 Key Hash N32 k33 You can read this: http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html And http://www.danga.com/memcached/ k40 N80 k52 k70 k65 N60 N80 is down… 50 50

Incremental Crawling

问题 有限的资源条件下 Crawler系统怎样和变化的Web同步？ 网络带宽，存储空间 如何估计网页变化频率，来预测其更新时间？ 如何度量搜集结果的优劣? 按预测到的更新时间去抓取是最优策略吗？ Cho, J. and Garcia-Molina, H. (2003). Effective page refresh policies for web crawlers. ACM Transactions on Database Systems, 28(4).

State-of-art Crawling Tech

Sitemaps: Above and Beyond the Crawl of Duty Sitemaps! Sitemaps! Uri Schonfeld (Google and UCLA) Narayanan Shivakumar (Google) Copyright Uri Schonfeld, shuri.org April 2009 54

Dream of the Perfect Crawl Users Have High Expectations: Coverage: Every page should be findable Freshness: Latest event, viral video,... Deep Web: ajax, flash, silverlight,.... Search Engines Dream of the perfect crawl: Everything the users want …but efficient: No 404s No duplicates Sitemaps to the rescue...

Sitemaps http://www.sitemaps.org

UniqueCoverage vs Domain Size   46% domains have above 50% UniqueCoverage  12% domains have 90% UniqueCoverage. 46% >50% UniqueCoverage  12% >90% UniqueCoverage. Figure 3 shows how the coverage of domains are distributed by their size. At least 46% of the do- mains have above 50% UniqueCoverage and above 12% have above 90% UniqueCoverage. There is no appar- ent correlation between the size of the domain and UniqueCoverage. 57

Conclusion and Future Work Large scale study, real data You cannot stop Discovery… yet. Presented metrics for freshness and coverage. Sitemaps evaluated for coverage and freshness. Presented Algorithm to combine Sitemaps & Discovery To Be Done Good news: tons of future work Duplicates not solved on web-server side either. Better Pings. Ranking Sitemaps URLs can be a challenge. Copyright Uri Schonfeld, shuri.org April 2009 58

IRLbot: Scaling to 6 Billion Pages and Beyond WWW2008 Best Paper Award! In our recent experiment that lasted 41 days, IRLbot running on a single server successfully crawled 6.3 billion valid HTML pages ($7.6$ billion connection requests) and sustained an average download rate of 319 mb/s (1,789 pages/s)

Challenges We identified several bottlenecks in building an efficient large-scale crawler and presented our solution to these problems Scalability Low-overhead disk-based data structures Reputation and spam Non-BFS crawling order Politeness Real-time reputation to guide the crawling rate

本次课小结 Crawler面临的难题 实现高效率的基本技术 有趣的技术 Scalable, fast, polite, robust, continuous 实现高效率的基本技术 Cache Prefetch Concurrency 多进程/多线程 异步I/O 有趣的技术 Bloom filter Consistent Hashing One Web ， One Dream

下次课内容 Web图和链接分析 Homework 求以下矩阵的特征值和特征向量 2 3 -1 -4 0 -1 -2 1 2 3 -1 -4 0 -1 -2 1 A = 0 1 2 -2 0 1 1 2

Thank You! Q&A