AI 资讯Hacker News·3 天前

其他链接检查器如何实现递归

原标题：How Other Link Checkers Do Recursion

速览

本文探讨了其他链接检查器在处理链接时采用的递归逻辑。了解其实现方式有助于优化链接检测算法。这对提升爬虫效率和准确性具有参考价值。

AI 深度解读

其他链接检查器如何实现递归：深度解析

背景

在作者发布《尝试五年为 lychee 添加递归功能》一文后，收到了一条非常中肯的评论：“如果递归这么难，为什么其他链接检查器能做到？它们早就在爬取网站了！”

这一质疑促使作者深入研究了其他主流链接检查器（Link Checkers）的源码。核心发现是：这些工具并非发现了某种被 lychee 遗漏的“巧妙技巧”，而是从第一个提交开始就被设计为爬虫（Crawler）。相比之下，lychee 最初被构建为一个**流式（Stream）**处理工具。

作者阅读了 lychee 的 README 中列出的几个递归检查器的源码，包括 Go 语言的 muffet、Python 的 LinkChecker、TypeScript 的 linkinator 以及 JavaScript 的 broken-link-checker。这篇文章旨在拆解它们如何处理递归、为此付出的代价，以及对 lychee 未来的启示。

回顾 lychee 的架构，它被设计为一个一次性、单向的管道（输入 → 提取 → 检查 → 输出）。递归需要形成一个循环（响应产生新的输入），而在基于异步通道（channel）的管道中，循环正是“龙穴”所在（意指极难处理）。经过五年和四次尝试，lychee 才终于具备了正确实现递归所需的组件。

核心内容

DAG 与循环：架构的根本差异

所有被研究的递归检查器都基于相同的三个核心部分构建，这与 lychee 的有向无环图（DAG）架构截然不同：

可变的工作队列（Frontier）：不是固定的输入流。发现的 URL 会被重新放回它们来源的同一个队列中。
已访问集合（Visited Set）：在入队时更新（在请求完成之前），确保两个页面发现同一个链接时，只有一个能提交它。
终止检测原语：用于回答“是否所有工作都已完成？”，例如 WaitGroup、可连接队列计数器、anonIdle() 承诺或队列排空事件。

架构对比图解：

其他爬虫（循环结构）：
- 前端队列（Frontier Queue） → 工作池（Worker Pool） → 获取并解析页面（Fetch and Parse） → 新链接回传至前端队列。
- 这是一个闭环，具有“后向边”（back-edge）。
lychee（DAG 结构）：
- 输入（Inputs） → 提取器（Extractor） → 检查器（Checker） → 结果（Results）。
- lychee 的管道没有后向边，之前的失败尝试都是试图强行将这个从未为此设计的图弯曲成循环结构。

递归检查的标准流程图解：

种子 URL 进入 入队步骤：检查 URL 是否在已访问集合中？
如果在 → 跳过。
如果不在 → 标记为已访问，然后推入 前端队列。
前端队列 → 工作池（限制并发数）。
工作池 → 获取页面并提取链接。
发现的链接 → 回到 入队步骤。
提取的链接 → 结果。
当队列为空且无工作线程繁忙时 → 终止。

关键点在于：去重检查发生在入队步骤，与标记原子化操作，且在工作线程触碰网络之前完成。 这种顺序解决了 lychee 前四次尝试中困扰其的去重竞态条件（当时缓存是在检查之后写入的）。

muffet (Go)：WaitGroup 与 Set

muffet 在精神上最接近 lychee：快速、单二进制文件、并发的网站检查器。

去重与调度： 去重和调度决策集中在一个方法中。donePages 是一个并发字符串集合（mutex 保护的 map[string]struct{}）。Add 方法返回 URL 是否已存在，因此页面仅在第一次被看到时才会被调度。去重发生在入队时，由集合的 mutex 同步。

递归实现： 检查页面时会并发获取所有链接，并将符合条件的链接反馈给 addPage 方法，形成后向边（递归）：

go func(u string) {
    defer w.Done()
    status, p, err := c.fetcher.Fetch(u)
    // ...
    if !c.onePageOnly && p != nil && c.linkValidator.Validate(p.URL()) {
        c.addPage(p) // 递归：发现的页面重新进入前端
    }
}(u)

如何知道何时完成： muffet 使用围绕 sync.WaitGroup 构建的 daemonManager 来处理终止。

每个调度的页面增加计数。
每个完成的页面减少计数。
Wait() 在计数归零时返回。
整个爬取过程在 Run() 之前通过一次 addPage 启动，确保计数器在等待之前为正数。

这与作者在前四次尝试中失败的原因相同：缺乏不变量（invariant）。Go 的 WaitGroup 自然地强制执行了这一不变量：waitGroup.Add(1) 仅在已运行的守护进程内部（保持计数大于零）或引导阶段调用。不存在计数器短暂读取为零而工作仍在挂起的情况。这在道德上等同于 lychee 在 2026 年贡献的 WaitGroup 原语。

权衡与代价：

并发未受前端管理器限制：Run() 为每个任务生成一个 goroutine，导致无界 goroutine 生成。实际的限制发生在下游的信号量（buffered-channel counting semaphore）和每主机节流池。muffet 将“前端”与“速率限制器”分离，这正是 lychee 过去试图用一个有界通道同时做两件事时导致死锁的原因。
Goroutine 成本低：在 Go 中，为每个链接生成一个 goroutine 是可以接受的。而在 Rust 中，等效的 tokio::spawn（每个都需要 Send + 'static 状态）正是推动作者使用 Arc<RwLock<…>> 并面临所有权痛苦的原因。
可扩展性：muffet 是一个专注的 CLI，而非库。没有插件接口。lychee 故意提供 lychee-lib 作为可重用 crate，这提高了架构选择的门槛，因为每个选择都必须符合公共 API 的标准。
规模限制：无界 goroutine 加上内存中的已访问集可以舒适地扩展到大型网站，但没有磁盘支持的前端，因此真正的巨大爬取受限于 RAM。这与 lychee 相同。

LinkChecker (Python)：可连接的无界队列

LinkChecker 自 2000 年存在，是一个同步、线程池爬虫。

前端设计： 其前端是手写的 UrlQueue，克隆自 Python 的 queue.Queue，带有 task_done() / join()。其设计注释明确指出：

“注意：不要对队列设置最大大小，因为当所有工作线程都调用 put() 时，这会导致死锁。”

这直接指出了 lychee 第四次尝试中的背压死锁问题。lychee 试图将发现的 URL 推入有界通道；当通道填满时，响应处理程序阻塞，没有响应被排空，没有槽位被释放，导致死锁。

LinkChecker 的答案是“野蛮主义”的：前端是无界的。 背压在其他地方强制执行（固定线程数和每主机节流），从不阻塞既是生产者又是消费者的生产者。

正确的计数器终止： join() 阻塞直到 unfinished_tasks 归零。

def task_done(self, url_data):
    with self.all_tasks_done:
        self.finished_tasks += 1
        self.unfinished_tasks -= 1
        self.in_progress -= 1
        if self.unfinished_tasks <= 0:
            self.all_tasks_done.notify_all()

关键要点

架构起源决定实现难度：其他工具从第一天起就是爬虫（具有

查看原文 →endler.dev