案例 8：设计网络爬虫

爬虫看起来只是“下载网页、找链接、继续下载”的循环。但放到数十亿网页的规模上，难点就变成了三件事：不把别人的网站打挂（礼貌性）、不重复抓取（去重）、不掉进陷阱（鲁棒性）。

1. 需求澄清

先问清用途：给搜索引擎建索引？做数据挖掘？监控版权？用途决定了抓什么内容、多久重抓一次。下面以通用搜索引擎爬虫为例。

功能需求

• 从一组种子 URL 出发，下载 HTML，提取链接，不断向外扩展
• 存储网页内容，供下游建索引使用
• 定期重新抓取，保持内容新鲜

非功能需求

• 规模：每月 10 亿个网页
• 礼貌：遵守 robots.txt，控制对同一网站的访问频率
• 鲁棒：能处理超时、格式错误的 HTML、重定向循环和爬虫陷阱
• 可伸缩：加机器就能提高吞吐
• 可扩展：以后要抓图片、PDF 时，能插入新的处理模块

范围外：索引构建、排序、JS 动态渲染（可作为追问）。

2. 量级估算

• 10 亿页/月 ≈ 10^9 / (2.6 x 10^6 秒) ≈ 400 页/秒，峰值按 2 倍算约 800 页/秒
• 平均每页 100 KB，下载带宽约 40~80 MB/s
• 存储：每月 100 TB，保存 5 年约 6 PB（压缩后会小很多）
• 累计见过的 URL 可能上百亿。每个存 8 字节指纹，100 亿就是 80 GB

400 页/秒看起来不多，但每次抓取都包含 DNS 解析、建立连接、等待对方响应，单次可能耗时几百毫秒到几秒。所以瓶颈是大量并发的网络 I/O，而不是 CPU。

3. 高层架构

flowchart TD
  accTitle: 网络爬虫的高层架构
  seeds["Seed URLs"] --> frontier["URL Frontier"]
  frontier --> fetcher["Fetcher"]
  fetcher <--> dns[("DNS Cache")]
  fetcher --> cdedup["Content Dedup"] --> store[("Content Store")]
  cdedup --> parser["Parser + Link Extractor"]
  parser --> filter["URL Filter + URL Dedup"] --> frontier

一个 URL 的生命周期：从 Frontier 取出，解析 DNS，下载，判断内容是否重复，存储，解析出新链接，再经过规范化、过滤、去重，新的 URL 回到 Frontier。

4. 深入讨论

4.1 URL Frontier：同时解决优先级和礼貌性

Frontier 不是一个简单的 FIFO 队列，它要同时满足两个目标：

• 优先级：重要的页面先抓，比如链接权重高的、更新频繁的
• 礼貌性：同一个 host 同一时间只有一个连接，两次请求之间留出间隔

常见做法是两层队列：

flowchart TD
  accTitle: URL Frontier 的两层队列
  url["新 URL"] --> prio["Prioritizer"] --> front["Front queues：P1 / P2 / P3 …（按优先级）"]
  front -->|"加权选取"| router["Router：host → back queue"]
  router --> back["Back queues：a.com / b.org / c.net …（一个队列只对应一个 host）"]
  back --> heap["最小堆：(next_allowed_time, back queue id)"]
  heap --> fetcher["Fetcher"]

Fetcher 从最小堆里取出“最早允许访问”的 host，抓完后把它的下次可访问时间设为 now + delay，再放回堆中。delay 可以取 robots.txt 里的 crawl-delay，也可以根据对方响应时间动态调整：响应越慢，说明对方压力越大，间隔就拉得越长。遇到 429 或 503 就指数退避。

Frontier 可能积压几十亿条 URL，不能全放内存：队头留在内存里，其余部分存在磁盘或 KV 存储中，批量读写。

4.2 分布式：按 host 分片

多台机器怎么分工？按 host 的哈希把 URL 分配给节点（用一致性哈希）。这样同一个网站只由一个节点负责，礼貌性在本地就能保证，不需要跨机器协调限速。节点解析出属于其他节点的链接时，攒成一批再转发过去。节点宕机后，它负责的 host 区间由一致性哈希自动转给相邻节点。

按 host 分片还有两个坑：

• 共享主机：一个 IP 上可能托管成千上万个 host（虚拟主机、建站平台）。它们被哈希到不同节点后，各自的礼貌限速互不知情，这台服务器仍会同时收到大量连接。所以 DNS 解析之后还要按 IP 再限速一层，同一 IP 的请求共享访问间隔；跨节点时可以把按 IP 的令牌桶放进共享的 Redis，或者解析后改按 IP 路由。
• 超大站点造成倾斜：一个巨型站点的全部 URL 都落在同一个节点上，这个节点的 Frontier 会比别的节点大得多。礼貌限速本来就压住了单站的抓取速度，所以倾斜主要体现在队列长度和存储上；可以把这类站点固定分给专门的节点，避免拖累同节点上的其他 host。

4.3 DNS 解析与 robots.txt

DNS 是常被低估的瓶颈：很多语言标准库的解析是同步阻塞的，单次耗时几十到几百毫秒。办法是每个节点部署本地 DNS 缓存（按 TTL 过期），并使用异步解析。

robots.txt 也要按 host 缓存：每个 host 第一次抓取前先拉 robots.txt，把解析好的规则缓存起来，一般最多缓存 24 小时再刷新，避免每抓一页都请求一次。拉取失败时按状态码处理：4xx 一般视为没有限制；5xx 或超时则暂停抓取这个 host，稍后重试。

4.4 URL 去重

先规范化，再判重：

• host 转小写，去掉默认端口（:80、:443），去掉 #fragment
• 对 query 参数排序，去掉常见的会话 ID 和跟踪参数
• 把相对路径解析成绝对路径，处理 ./ 和 ../

已见 URL 集合的存储方案：

注意 Bloom filter 的误判方向：它只会把“没见过”错判成“见过”。所以后果是少量页面漏抓，而不会重复抓取。对爬虫来说，这个代价通常可以接受。

4.5 内容去重

不同的 URL 可能指向同一个页面（镜像站、同一篇文章带不同参数）。

• 完全相同：对正文算一个哈希指纹，查重即可
• 几乎相同（只差广告或时间戳）：用 SimHash 这类局部敏感哈希。相似文档的指纹汉明距离很小，比如相差不超过 3 位就视为重复

4.6 爬虫陷阱与鲁棒性

• 无限日历、无限翻页、程序动态生成的链接，会让爬虫陷入无穷无尽的 URL
• 对策：限制 URL 最大长度、最大抓取深度、单个 host 的最大页面数；检测路径中反复出现的片段，比如 /a/b/a/b/a/b
• 设置连接超时和读取超时，限制响应体大小，只接受需要的 Content-Type
• Frontier 和已见集合定期持久化，进程重启后能接着跑

4.7 存储与新鲜度

• 原始页面量大、写一次读几次：把很多页面合并成大文件（类似 WARC 格式）写入对象存储或分布式文件系统，避免海量小文件
• 每个 URL 的元数据（上次抓取时间、内容哈希、HTTP 状态、历史变化频率）存在宽列 KV 存储中
• 重抓策略按历史变化频率自适应：新闻首页可能几分钟一次，个人博客可能几周一次
• 重抓时发起条件请求，带上 If-Modified-Since 或 ETag。内容没变时对方返回 304，省掉整页下载

5. 取舍与常见追问

• BFS 还是 DFS：通常是带优先级的 BFS。DFS 容易在一个网站里越走越深，更容易掉进陷阱
• JS 渲染：用无头浏览器渲染的成本比普通 HTTP 抓取高一到两个数量级，只对确实需要的网站启用，单独走一条流水线
• 公平性：某个大站的 URL 太多时，限制它在前端队列中的份额，避免挤占其他网站

6. 面试答题清单

1. 先确认用途和规模，算出页/秒和存储量
2. 画出 Frontier、Fetcher、Parser、Dedup 构成的循环
3. 重点讲 Frontier 如何同时满足优先级和礼貌性
4. 讲清楚 URL 规范化 + Bloom filter，以及内容去重
5. 主动提到爬虫陷阱和 DNS 瓶颈，这两点常常是加分项

7. 回答分级

礼貌性与调度

• Bad：一个全局 FIFO 队列，按入队顺序抓取，对同一个站点并发猛抓。
• Good：两层队列：前端队列按优先级，后端队列每个 host 一个，用最小堆按下次允许访问的时间取 host；遵守 robots.txt 和 crawl-delay。
• Great：遇到 429/503 指数退避，按对方响应时间动态调整间隔；指出共享主机的问题：成千上万个 host 解析到同一个 IP，DNS 解析之后还要按 IP 再限一次速。

扩展与分片

• Bad：URL 随机分给各节点，各自限速，同一个站点被多个节点同时抓。
• Good：按 host 做一致性哈希，一个站点只归一个节点，礼貌性在本地就能保证；属于其他节点的链接批量转发。
• Great：处理大站倾斜：把大站固定到专用节点，并限制它在前端队列里的占比；DNS 本地缓存并异步解析；frontier 和已见集合定期 checkpoint，重启后能接着跑。

去重与陷阱

• Bad：用完整的 URL 字符串去重，不做规范化；没想到无限日历、无尽分页这类陷阱。
• Good：先规范化 URL，再用指纹或布隆过滤器去重；内容用哈希去掉完全重复的页面；限制 URL 长度、抓取深度和每个 host 的页数。
• Great：说明布隆过滤器的误判只会漏抓少量新页面、不会重复抓取，并算出 100 亿个 URL 约需 12 GB；用 SimHash 识别近似重复；按页面变化频率自适应重抓，用 If-Modified-Since / ETag 省掉没变的下载。

8. 不同级别的期望