这道题本质是图遍历。页面是节点，链接是边。给你一个种子 URL，从它开始把同域名页面全部抓出来。
题目描述
实现一个 Web Crawler：
- 输入：
start_url - 提供辅助函数：
get_urls(url)- 已完成 HTTP 请求和基础解析
- 返回当前页面里的所有超链接
- 目标：
- 只爬取和
start_url同域名 的 URL - 每个 URL 只访问一次
- 返回最终爬到的 URL 列表
- 只爬取和
先写同步版本，再优化成多线程版本。
一、同步版本（BFS）
为什么是 BFS？
- 题目本质是图遍历
- 需要逐层扩展链接，BFS 非常自然
- 配合
visited可避免死循环和重复抓取
核心点
- 用
urlparse抽取起始域名 - 队列做 BFS
visited集合去重- 只把同域链接加入队列
Python 代码（同步）
from collections import deque
from urllib.parse import urlparse
def crawl_sync(start_url, get_urls):
host = urlparse(start_url).netloc
queue = deque([start_url])
visited = {start_url}
result = []
while queue:
url = queue.popleft()
result.append(url)
for nxt in get_urls(url):
if urlparse(nxt).netloc != host:
continue
if nxt in visited:
continue
visited.add(nxt)
queue.append(nxt)
return result
复杂度
- 设同域页面数为 (V)，同域链接总数为 (E)
- 时间复杂度：(O(V + E))
- 空间复杂度：(O(V))
二、优化版本（ThreadPoolExecutor 并发抓取）
同步版本的瓶颈是 I/O 等待（网络请求慢），不是 CPU。最有效优化是并发请求。
设计思路
- 用
ThreadPoolExecutor提交抓取任务 - 维护
future -> url的映射 - 用
as_completed在任务一完成就立刻处理结果 - 新发现 URL 立刻提交，不必等待“整层结束”
这就是面试官常问的：如何在任务就绪后立即处理它。
Python 代码（多线程）
from concurrent.futures import ThreadPoolExecutor, wait, FIRST_COMPLETED
from urllib.parse import urlparse
def crawl_threaded(start_url, get_urls, max_workers=8):
host = urlparse(start_url).netloc
visited = {start_url}
result = []
with ThreadPoolExecutor(max_workers=max_workers) as executor:
in_flight = {executor.submit(get_urls, start_url): start_url}
while in_flight:
done, _ = wait(in_flight.keys(), return_when=FIRST_COMPLETED)
for fut in done:
url = in_flight.pop(fut)
result.append(url)
try:
neighbors = fut.result()
except Exception:
# 面试里可说明：这里可做重试/日志
continue
for nxt in neighbors:
if urlparse(nxt).netloc != host:
continue
if nxt in visited:
continue
visited.add(nxt)
in_flight[executor.submit(get_urls, nxt)] = nxt
return result
为什么不是“分层并发”？
分层并发（每层等全部任务完成再进入下一层）也能做，但吞吐更低。
这里用“谁先完成先处理”的模式，能更快发现新 URL 并持续压满线程池，整体更高效。
三、urlparse 在这题里的作用
urlparse 常用来做三件事：
- 同域过滤（
netloc） - URL 规范化前处理（大小写、端口、路径）
- 防止把相对路径/外链误当目标页面
面试时你可以明确说：
- 判断是否同域，优先比较
scheme + netloc - 更严格时可统一默认端口（80/443）后再比较
四、线程 vs 进程：区别与适用场景
| 对比维度 | 线程（Thread） | 进程（Process） |
|---|---|---|
| 内存 | 共享地址空间 | 独立地址空间 |
| 创建/切换成本 | 低 | 高 |
| Python GIL 影响 | 受影响（CPU 密集不占优） | 不受同一进程 GIL 限制 |
| 适用任务 | I/O 密集（网络、磁盘） | CPU 密集（压缩、模型推理） |
| 本题适配 | ✅ 非常适合 | ❌ 通常不优先 |
结论：Web Crawler 通常是 I/O 密集，优先线程/异步模型。
五、礼貌策略（避免服务器过载）
真实爬虫不能只追求快，还要“礼貌抓取”：
- 遵守
robots.txt - 限速（每秒请求数上限）
- 并发上限（全局 + 每域名）
- 重试+退避（429/5xx 使用指数退避）
- 合理 UA 和联系信息
- 抓取间隔 jitter（避免固定节奏冲击）
简化版限速思路：token bucket 或 sleep 节流。
六、百万级 URL 的分布式系统设计
当规模从“面试代码”升级到“生产爬虫”，架构一般拆成：
URL Frontier（消息队列）
- Kafka / SQS / RabbitMQ
- 存待抓取 URL，支持优先级
Fetcher Worker 集群
- 横向扩展抓取节点
- 节点从队列拉取 URL，调用抓取器
去重服务（URL Dedup）
- Redis/Bloom Filter + 持久化 KV
- 防止重复抓取
内容解析与索引
- 提取正文、标题、出链
- 写入对象存储 + 搜索索引
调度与监控
- 失败重试、死信队列
- 监控 QPS、错误率、队列积压
一致性与容错要点
- URL 去重通常用“最终一致”即可
- 任务至少一次投递（at-least-once）+ 幂等处理
- 单机故障不影响全局进度
七、不同 URL 下的重复内容检测
同一内容可能有多个 URL：
- 参数不同：
?ref=... - 大小写/尾斜杠差异
- 分页或镜像页面
两层去重策略
URL 级去重
- 规范化 URL（去追踪参数、统一大小写、排序 query）
内容级去重
- 对正文做指纹：
- 精确：SHA-256
- 近似：SimHash / MinHash
- 新页面与历史指纹比较，相似度高则判重
- 对正文做指纹：
面试表达建议：
先做 URL 规范化降低重复抓取，再做内容指纹避免“不同 URL 同内容”的存储浪费。
八、面试回答模板（可直接复述）
- 先同步 BFS：
queue + visited + same-host filter - 再并发优化：
ThreadPoolExecutor+FIRST_COMPLETED - 补系统思维：礼貌抓取、重试退避、限流
- 扩展到分布式：frontier 队列 + worker + dedup + 存储
- 最后讲判重：URL 标准化 + 内容指纹
这样回答通常能覆盖 coding + follow-up 的大部分评分点。
常见坑位
- 没有
visited，导致环路死循环 - 只做字符串包含判断域名，误判子串
- 多线程下共享集合未统一访问策略（竞态）
- 无并发上限，瞬间打爆目标站
- 只做 URL 去重，不做内容去重
总结
这题不难，但非常考“工程完整度”：
- 基础分：会写正确 BFS
- 进阶分：能并发并做到任务完成即处理
- 高分：能讲清礼貌策略、分布式扩展、内容去重
如果你按这条主线答，面试官通常会觉得你不仅会写题，也懂真实系统。
🚀 需要 VO / OA 实战辅导？
oavoservice 长期覆盖 Anthropic、Google、Amazon、Meta、TikTok、Uber、Bloomberg 等高频题与面试场景。
微信：Coding0201
可提供：
- ✅ 真题复盘与高频题路线
- ✅ 1v1 模拟面试（算法 + 系统设计）
- ✅ 面试表达与 follow-up 追问专项训练
联系方式
Email: [email protected]
Telegram: @OAVOProxy