在我发表了 为 lychee 添加递归功能的五年尝试 之后，收到了一条非常中肯的提问：

如果递归这么难，其他链接检查工具是怎么做的？明明有不少工具已经会爬网站了！

这个问题让我一头扎进了其他链接检查工具的源码里。关键结论是：它们并没有找到什么我们遗漏的巧妙技巧。它们从第一次提交起就是作为 crawler(爬虫)构建的，而我最初是把 lychee 构建成了一个 stream(流)。

我阅读了我们在 lychee 的 README 中列出的那些支持递归的检查工具的源码：muffet（Go）、LinkChecker（Python）、linkinator（TypeScript）和 broken-link-checker（JavaScript）。本文将拆解每一款工具究竟如何处理递归、为此付出了什么代价，以及这对 lychee 意味着什么。

如果你还没有读过第一篇文章，概要是：lychee 被设计为一次性的单向流水线（inputs → extract → check → output）。递归需要一个环（响应会产生新的输入），而在基于异步、通道的流水线中，环就是巨龙出没的地方。🐲 五年四次尝试之后，要把它正确做出来所需的组件才刚刚到位。

DAG(有向无环图) 与 cycle 的对比

我看过的所有递归检查工具都由相同的三部分构成：

1. 一个可变的工作队列（我们称之为“frontier(待爬队列)”），而不是固定的输入流。发现的 URL 会回到它们来源的同一个队列中。
2. 一个在入队时（请求完成前）就更新的 visited set(已访问集合)，因此两个页面同时发现同一个链接时不会重复提交。
3. 一个回答“是否全部完成？”的原语：WaitGroup(等待组)、可 join 的队列计数器、onIdle() promise 或队列排空事件。

用图来表示，lychee 与其他工具的区别如下：

graph TD
    subgraph crawler["Everyone else: a cycle"]
        direction TB
        CQ[Frontier queue] --> CW[Worker pool]
        CW --> CP[Fetch and parse page]
        CP -->|new links| CQ
        CP --> CR[Results]
    end
    subgraph lychee["lychee: a DAG"]
        direction TB
        LA[Inputs] --> LB[Extractor]
        LB --> LC[Checker]
        LC --> LD[Results]
    end

爬虫天生就带有一条回边。我们的流水线没有，我之前所有失败的尝试，都是试图把这条回边硬塞进一个从未为此设计的图中。

让我们更仔细地看看这种图设计：

graph TD
    Seed[Seed URLs] --> Enq["Enqueue step: is URL in visited set?"]
    Enq -->|yes| Skip[Drop]
    Enq -->|no| Mark["Mark visited, then push"]
    Mark --> Q[Frontier queue]
    Q --> Pool["Worker pool, bounded concurrency"]
    Pool --> FP[Fetch page and extract links]
    FP -->|discovered links| Enq
    FP --> Rec[Results]
    Q -.->|empty AND no worker busy| Stop[Terminate]

注意，已访问检查发生在入队步骤中，与标记操作原子地一起执行，远在 worker 真正发起网络请求之前。这一顺序正是修复困扰 lychee 前四次尝试的去重竞态的全部关键——在那些尝试中，缓存是在检查之后才写入的。

每款工具都使用了它的某个变体。

muffet（Go）：一个 WaitGroup 和一个集合

muffet 在气质上最接近 lychee：一个快速、单二进制、并发的网站检查工具。去重与调度的决策集中在一个方法中（page_checker.go）：

func (c *pageChecker) addPage(p page) {
	if !c.donePages.Add(p.URL().String()) {
		c.daemonManager.Add(func() { c.checkPage(p) })
	}
}

donePages 是一个 concurrentStringSet（由互斥锁保护的 map[string]struct{}）。Add 返回该 URL 是否已存在，因此只有第一次见到的页面才会被调度。去重发生在入队时，由集合的互斥锁同步。这几乎就是上图逐行的代码翻译。

检查一个页面时会并发地获取其所有链接，并把符合条件的链接重新喂回 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)   // recursion: discovered page re-enters the frontier
	}
}(u)

muffet 如何知道已经完成

muffet 对终止的答案是一个围绕 sync.WaitGroup 构建的小型 daemonManager（daemon_manager.go）：

func (m daemonManager) Add(f func()) {
	m.waitGroup.Add(1)
	m.daemons <- func() {
		f()
		m.waitGroup.Done()
	}
}

func (m daemonManager) Run() {
	go func() {
		for f := range m.daemons {
			go f()
		}
	}()
	m.waitGroup.Wait()   // <- termination
}

每个被调度的页面都会让计数器加一，每个完成的页面都会让计数器减一；Wait() 在计数归零时返回。整个爬取过程在 Run() 之前通过一次 addPage 启动，因此在任何人等待之前计数器已经是正数。

这和我在尝试 1 和 尝试 4 中尝试过（并失败）的同一个计数器。区别在于不变量：waitGroup.Add(1) 永远只会在一个已经运行、且持有正计数的 daemon 内部被调用（或在启动时）。不存在计数器短暂归零而仍有待处理工作的窗口。Go 的 WaitGroup 如此自然地强制执行这一不变量，以至于它根本不像是 distributed termination detection(分布式终止检测)，但它本质上正是如此。它在道义上等同于 Kait（凯特）在 2026 年为 lychee 贡献的 WaitGroup 原语。

权衡之处

• 并发并非由 daemon 管理器限制。Run() 会为每个任务执行 go f()，产生无界的 goroutine。真正的限流发生在下游的 semaphore(信号量)（一个带缓冲通道的计数信号量）和按主机的限流器池中。muffet 将“frontier”与“限速器”分离了，而 lychee 过去试图用同一个有界通道同时扮演这两个角色，这正是症结所在。
• 廉价的 goroutine 承担了大量繁重工作。在 Go 中为每个链接启动一个 goroutine 是“可以接受”的。在 Rust 中等价的做法（为每个链接执行 tokio::spawn，每个都需要 Send + 'static 状态）正是把我推向 Arc<RwLock<…>> 以及我在文中写到的所有权痛苦的原因。
• 在可扩展性上，muffet 是一个专注的命令行工具，而不是库。它没有插件界面，你得到的就是 flags 提供的功能。lychee 则有意将 lychee-lib 作为可复用的 crate 发布，这抬高了门槛，因为每一个架构决策都必须符合公共 API 的标准。
• 在可伸缩性上，无界的 goroutine 加上内存中的已访问集合可以轻松应对大型站点，但没有基于磁盘的 frontier，因此真正巨大的爬取会受限于内存。和 lychee 一样。

LinkChecker（Python）：可 join 的无界队列

LinkChecker 自 2000 年就已存在。它是一个同步的线程池爬虫。

它的 frontier 是一个手写的 UrlQueue（cache/urlqueue.py），是 Python queue.Queue 的克隆，带有 task_done()/join()。看看最初的设计注释：

def __init__(self, max_allowed_urls=None):
    # Note: don't put a maximum size on the queue since it would
    # lead to deadlocks when all worker threads called put().
    self.queue = collections.deque()
    # ...
    self.unfinished_tasks = 0

它明确指出了曾经困扰我的那种死锁。

这条注释正是我们在 尝试 4 的背压死锁中遇到的问题，并围绕它做了设计。lychee 曾试图把发现的 URL 推入一个有界通道；当通道填满时，响应处理器阻塞，不再排空响应，也无法释放槽位。死锁。💥

LinkChecker 的答案带有野蛮主义色彩：frontier 是无界的。背压在别处强制执行（固定的线程数和按主机的限流），绝不会通过阻塞一个同时也是消费者的生产者来实现。

用计数器正确地实现终止

join() 会阻塞直到 unfinished_tasks 归零（urlqueue.py）：

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()

def join(self, timeout=None):
    with self.all_tasks_done:
        while self.unfinished_tasks:
            self.all_tasks_done.wait()

同样：一个计数器。但 _put 中的递增和 task_done 中的递减都在队列的 Condition 锁内，而 worker 只有在完全处理完一项、包括将其子项入队之后才会调用 task_done。因此子项在父项被标记完成之前就已被计数，不会出现过早归零。这是用互斥锁和条件变量实现的 WaitGroup 语义。

去重，在请求之前

LinkChecker 在入队时就把 URL 写入结果缓存（urlqueue.py）：

def _put(self, url_data):
    key = url_data.cache_url
    cache = url_data.aggregate.result_cache
    if cache.has_result(key):
        return  # already queued/checked -> skip
    # ...
    self.queue.append(url_data)
    self.unfinished_tasks += 1
    # add a None placeholder so this URL is never queued twice
    cache.add_result(key, None)

那个 add_result(key, None) 哨兵正是 lychee 的尝试中所缺失的“修复”。当任何 worker 线程检查该 URL 时，缓存已经声明“归我了”，因此来自另一个页面的并发发现就成了空操作。

按主机的礼貌性与终止保护

Aggregate（director/aggregator.py）会按主机限流：

@synchronized(_hosts_lock)
def wait_for_host(self, host):
    t = time.time()
    if host in self.times and self.times[host] > t:
        time.sleep(self.times[host] - t)
    # spread requests using maxrequestspersecond
    wait_time = random.uniform(wait_time_min, wait_time_max)
    self.times[host] = time.time() + wait_time

而 abort() 会调用 urlqueue.join(timeout=…)，因此卡住的爬取不会永远挂起。

权衡之处

• 阻塞线程而非异步。默认 10–100 个 Checker 线程中的每一个都通过 requests 执行阻塞式 I/O。简单且久经考验，但并发上限就是线程数，且每个线程都占有一个完整的栈。lychee 的 Tokio 模型可以在少数几个操作系统线程上实现数千个并发在途请求；LinkChecker 不能，也不打算这么做。
• 无界 frontier 用无界内存换取了避免死锁。显式的“无最大长度”决策意味着在巨大站点上内存会增长。有一个 max_allowed_urls 上限和定期的 cleanup() 来缓解。
• 可扩展性出色。LinkChecker 拥有真正的插件系统（linkcheck/plugins/：锚点检查、SSL、病毒扫描等）和多种输出记录器。这是其中可扩展性最强的一款，为此付出了代码库庞大、成熟但略显陈旧的代价。
• 在可伸缩性上，它受 GIL 限制且线程数量有限，因此原始吞吐量是这里最低的，但正确性和功能覆盖率很高。

linkinator（TypeScript）：单线程的 queue.onIdle()

linkinator 是一个 Node.js 检查工具，它享有 Go 和 Rust 都没有的优势：单线程事件循环。对 visited set 的检查与插入是免费原子的，因为不会有两个回调同时运行。

frontier 是一个限并发的 Queue（类似 p-queue 的结构）。终止只需 check() 中的一行（src/index.ts）：

const queue = new Queue({ concurrency: options.concurrency || 100 });
// ... seed the queue ...
// resolve when nothing is queued or running:
await queue.onIdle();

onIdle() 是该库的终止检测：当队列为空且没有任务在执行时它才会 resolve。和 muffet 的 WaitGroup 与 LinkChecker 的 join() 同样的思路，只是表达为一个 promise，并由单线程运行时支撑，因此不需要互斥锁来保护已访问集合。

回边与无竞态的去重

在爬取时，crawl() 会 GET 页面、提取链接，并为每个新 URL 重新进入队列（src/index.ts）：

const inCache = options.cache.has(result.url.href);
if (!inCache) {
    // Mark visited...
    options.cache.add(result.url.href);
    
    // Create the promise for this check
    const checkPromise = (async () => {
        await this.crawl({ url: result.url, /* ... */ });
    })();
    
    // Store the promise.
    // Another page discovering the same URL can wait on this promise
    // instead of enqueuing a duplicate check.
    options.pendingChecks.set(result.url.href, checkPromise);
    
    // Enqueue...
    options.queue.add(() => checkPromise);        
}

由于 JavaScript 是单线程的，整个过程不会被中断地执行。在 Rust 或 Go 中，这是一个必须用互斥锁保护的关键区（且顺序必须正确）；在 Node 中它只是三条语句。这是递归在 Node 中比在 Rust 中更容易的单一最大原因。这只是一个语言特性。

linkinator 还保留了一个以 `${url}|${parent}` 为键的 relationshipCache，以及一个 pendingChecks 映射，因此它可以等待正在进行的检查，同时仍能针对引用它的每个父页面报告重复的失效链接。这些复用操作本身也会被推入同一个队列，因此 onIdle() 也会正确地等待它们。

HEAD 与 GET

linkinator 对叶子链接使用 HEAD，但在需要爬取时会使用 GET，因为递归需要响应体来发现更多链接：

response = await makeRequest(
  options.crawl ? 'GET' : 'HEAD',
  options.url.href, /* ... */
);

这正是lychee 剩下未解决的问题：你只能递归进入那些你用正文获取过的页面。linkinator 在爬取时干脆总是 GET；lychee 则计划复用它在刚刚执行的检查中已缓存在内存中的正文。

权衡之处

• 单线程既是福也是上限。没有数据竞争，去重 trivially 正确，但 HTML 解析是会阻塞唯一事件循环的 CPU 工作。对于数千个页面，你会被限制在单核上。lychee 的多线程运行时则并行地解析和检查。
• 它存在内存中结果膨胀的问题。源码中明确注释了“对于高度互联的站点会产生巨大的结果膨胀”：results 数组、cache 和 relationshipCache 都会随着爬取增长。对于文档站点尚可，对于巨型站点则很重。
• 限流是反应式的，而非主动的。有一个 delayCache 会在收到 429 及 Retry-After 时对主机进行退避，但没有像 lychee 的 HostPool 那样通用的按主机并发上限。linkinator 可能会一直猛击主机直到对方抱怨；lychee 现在则在抱怨之前就主动调节节奏。
• 在可扩展性上，它是一个 EventEmitter（on('link')、on('pagestart') 等），因此可嵌入、可脚本化，这一点很好。它和 lychee 一样，首先是一个库。

broken-link-checker（JavaScript）：事件驱动，使用两个队列

broken-link-checker（BLC）将事件驱动模型推向了极致。它基于 limited-request-queue 构建，该队列具有 maxSockets（并发）和 rateLimit，并且它嵌套了两个这样的队列：一个站点级队列 feeding 一个页面级的 HtmlUrlChecker。

frontier 和去重位于 SiteChecker（lib/public/SiteChecker.js）中。已访问页面在 URLCache 中跟踪，在入队时写入：

#enqueuePage(url, customData, auth) {
    // Mark before crawl to avoid links to self within page. 
    this.#sitePagesChecked.set(url, PAGE_WAS_CHECKED);
    this.#htmlUrlChecker.enqueue(url, customData, auth);
}

递归由一个过滤器控制，该过滤器决定发现的链接是否成为被爬取的页面：

#maybeEnqueuePage(link, customData, auth) {
    const tagGroup = this.#options.tags.recursive[
      this.#options.filterLevel
    ][link.get(HTML_TAG_NAME)] ?? {};
    
    const attrSupported = link.get(HTML_ATTR_NAME) in tagGroup;
    if (!attrSupported ||
        link.get(IS_BROKEN) ||
        !link.get(IS_INTERNAL) ||
        this.#sitePagesChecked.has(rebasedURL) || // dedup check
        !this.#isAllowed(link)) { // robots.txt
          // do nothing
    } else if (this.#options.includePage(rebasedURL)) {
        this.#enqueuePage(rebasedURL, customData, auth);
    }
}

通过事件级联实现终止

BLC 没有计数器，也没有 onIdle()。它依赖队列的排空事件。当页面级队列清空时会触发 END_EVENT，这会让 SiteChecker 发出 SITE_EVENT 并调用站点队列的 done 回调；当站点队列排空时，会触发 REQUEST_QUEUE_END_EVENT。那就是公共的 END_EVENT：

.on(END_EVENT, () => {
    this.emit(SITE_EVENT, this.#currentPageError, this.#currentSiteURL, this.#currentCustomData);
    this.#currentDone();   // tell the site queue this site is finished
});

这就是它们的终止检测，表达为“请求队列报告为空”。

而按照经典的 Node.js 方式，done 回调才是真正告诉站点队列为另一个站点腾出槽位的东西。因此一个站点的终止使得另一个站点得以启动，而整个爬取的终止则使得进程得以退出。这是一连串从页面队列传播到站点队列再到进程的事件级联。

权衡之处

• 它是其中最遵守网络礼仪的。默认就尊重 robots.txt（getRobotsTxt、isAllowed）、尊重 rel=nofollow，且 rateLimit 加上 maxSockets 是一等公民。这是一个默认就很礼貌的爬虫。
• 事件级联强大但繁琐。终止逻辑分散在半打事件处理器和两个嵌套队列中。它能工作，但控制流比 await queue.onIdle() 难懂得多。这正是 JS 版的“我所描述的抽象泄漏”问题——递归感知被分散到了众多处理器中。
• 它是单线程的，和 linkinator 有同样的上限，再加上每个站点内存中的 URLCache。
• 在成熟度与动能上，它被非常广泛地使用（支撑了大量工具），但开发已放缓。其架构依然健全，值得研究。

关于 markdown-link-check 与“工业级”爬虫的说明

我们的 README 将 markdown-link-check 标记为支持递归，但其中有些细微差别：它递归的是 Markdown 文件，而不是通过爬取线上网站。没有 HTTP frontier，也没有上述意义上的终止问题。值得一提以保证对比的诚实，但不值得拆解。

如果你想在完整的工业级规模上看到这种模式，请看 Scrapy（Python/Twisted）或 Colly（Go）。两者都采用相同的方法：一个带有可插拔、可选基于磁盘的队列的调度器（frontier）、一个去重过滤器（通常是 Bloom filter(布隆过滤器) 而非 HashSet）、一个有界的下载器池，以及显式的“引擎空闲 → 关闭 spider”终止。它们恰好解决了 lychee 所挣扎的问题（分布式终止检测、背压、去重），只是背后有多年专注于爬虫工程的积累。结论并不是“lychee 应该成为 Scrapy”：而是爬取是一个已被充分探索的架构，而 lychee 目前只是站在另一种架构之上。

横向对比

2026 年的 lychee 终于有了逐列对应的匹配。WaitGroup 就是 muffet 的 sync.WaitGroup 和 LinkChecker 的 join()。HostPool 就是 BLC 的 rateLimit/maxSockets 和 LinkChecker 的 wait_for_host。按 URI 的 active_requests 互斥锁就是所有人入队时去重的实现。

那我们为什么不能直接照搬它们？

三个原因，按它们究竟在多大程度上真的是 lychee 自身问题的递增顺序排列。

它们起初就是爬虫；lychee 起初是流。

上面每一款工具在其核心数据结构中都有一条回边。lychee 的核心是一个为 99% 场景优化的 DAG（一个文件/URL 列表，检查一次，快速完成）。在流水线上 retrofitting 一个环，远比一开始就拥有它要难得多。这个问题本质上是架构性的。

frontier 与限速器必须是不同的对象。

muffet（集合 + semaphore）、LinkChecker（无界队列 + 线程数）、linkinator（p-queue + delayCache）、BLC（请求队列 + maxSockets）都将“接下来要做什么”与“以多快的速度去做”分开。lychee 早期的尝试试图让一个有界通道同时扮演这两个角色，而一个带环的有界通道会死锁。修复方案（lychee 的 HostPool 加上一个基于无界工作源的 WaitGroup）正是我们现在所追求的同一种分离。

单线程运行时免费获得去重。

两个 Node 工具都用一个普通的 Set 且零锁就完成了去重，因为事件循环序列化了访问。Go 和 Python 要付出一个互斥锁的代价。Rust 则不仅要付出互斥锁，还要与借用检查器斗争，争论谁在 tokio::spawn 之间拥有共享状态。这就是我上次估算的约 30% “Rust 税”：不是算法本身，而是要在 Send + 'static 约束下表达共享可变 frontier 状态所带来的摩擦。

这些都不是对 lychee 设计的否定。单向流对于常见的非递归场景是正确的选择：这正是 lychee 速度快的原因，也是来自尝试 2 的 30% 通道回归成为 dealbreaker 的原因。其他工具在每次运行中都为它们的回边付出了代价，无论是否递归。lychee 拒绝这样做，而这一原则正是递归花了五年才实现的原因，也是当它落地时不会拖慢每个人实际使用的路径的原因。我相信我们能够鱼与熊掌兼得：一个支持递归的爬虫架构，同时不牺牲一次性流水线的速度。但这比简单地“照搬它们的做法”要难得多，因为大多数链接检查工具从一开始就没有把毫不妥协的性能作为首要目标。

因此，当有人问“其他链接检查工具如何做递归？”时，真正的答案是：它们从一开始就把递归作为架构的一部分，并依赖一个（提供了诸如 WaitGroup、可 join 队列、空闲 promise 等便利的）运行时来解决终止问题，而无需去解决“分布式终止检测”。

感谢 muffet、LinkChecker、linkinator 和 broken-link-checker 的维护者们：阅读你们的源码是学习爬虫架构最清晰的方式，我们都在为同一个目标努力，只是权衡不同而已。