系统设计 Lab
web crawler 在 fetcher 处受 throughput 约束、在 "seen" set 处受内存约束，而 politeness 决定了你能跑多快。
调整目标 crawl rate、打算抓多少页、fetcher worker pool、平均页面大小、覆盖多少个不同 domain，以及 dedup 容忍度。设计会从单线程循环演进到 worker pool、politeness-aware scheduler、Bloom-filter "seen" set，再到 partitioned frontier 配 sharded 内容存储。
分步讲解
一步一步把它想清楚
要点
常规演进场景
从左到右点击，就是预设的演示路径。每张卡片都会改变 workload 输入。
推荐形态
当前架构路径
Seeds / Frontier
Seed URL 启动 crawl 的初始 URL，之后由发现到的 link 接力
URL frontier 存放待抓取的 URL，按优先级和 per-domain queue 排序
Scheduler
Scheduler 挑选下一个可抓取的 URL，同时遵守 robots.txt 和 per-domain rate limit
DNS cache 缓存 host 到 IP 的查询，让解析不致成为隐藏瓶颈
Fetchers
Fetcher pool 从开放 web 下载页面的并发 I/O-bound worker
Parser / dedup
Parser 解析抓回的页面，抽取出站 link 回灌给 frontier
Seen set 拒掉已见过的 URL 和近似重复内容，规模大时通常用 Bloom filter
Content store
Content store 持久存放下载的页面正文，供索引和分析
Store shard 当单个 store 装不下整个语料时，把页面正文分散到多个节点
瓶颈
Fetch throughput vs 目标
Frontier / queue 积压
Seen-set 内存
DNS 查询压力
内容存储
为什么会变
决策权衡
有出处支撑的规则
这些是模型背后那些经得起时间考验的 system design 论断。而 slider 的具体阈值，则被刻意标注为教学用的假设。
crawler 必须用 per-host rate limit 和 robots.txt 来执行 politeness
URL frontier 必须避免猛打任何单个 host；per-domain queue 和 back-off 在对同一服务器的请求之间强制一段礼貌延迟。
Manning & Schütze, IR (Stanford NLP)DNS 解析是隐藏瓶颈，必须 cache
对高 throughput 的 crawler 来说，DNS lookup 是众所周知的瓶颈，所以自建 cache（加异步解析）是标准做法。
Manning & Schütze, IR (Stanford NLP)Bloom filter 以极小空间检测集合成员关系，代价是 false positive
Bloom filter 用每个元素几个 bit 来回答"这个 URL 见过吗？"，而且从不产生 false negative，因此在数十亿 URL 规模下成为标准的 seen-set。
Bloom, CACM 1970可扩展的 crawler 把 frontier 和 seen-set 跨机器 partition
"Web Crawling" 这篇综述描述了如何把 URL frontier 和去重状态跨机器 partition，让 crawler 能向整个 web 规模扩展。
Olston & Najork (Google Research)教学用假设
- fetcher worker 被建模为 I/O bound；throughput 随 worker 数量线性增长，直到 politeness 或 DNS 把它封顶。
- 单节点的 throughput、DNS、内存和存储预算都是保守的教学数字，不是厂商上限。
- Seen-set 内存按 exact hash set 每 URL ~64 bytes、给定容忍度下 Bloom filter 每 URL ~1.5 bytes 计算。