在我發表了 Five Years of Trying to Add Recursion to lychee（《在 lychee 中加入遞迴的五年嘗試》） 之後，收到一個非常中肯的問題：

如果遞迴這麼困難，那其他連結檢查工具是怎麼辦到的？明明已經有很多工具會爬網站了！

這讓我一頭栽進其他連結檢查工具的原始碼中。核心結論是：他們並沒有找到什麼我們沒發現的聰明技巧。他們從第一次提交開始就是以爬蟲的形式打造的，而我當初是把 lychee 做成串流（stream）來建構的。

我去閱讀了我們在 lychee 的 README 中列出的那些支援遞迴的檢查工具的原始碼：muffet（Go）、LinkChecker（Python）、linkinator（TypeScript），以及 broken-link-checker（JavaScript）。這篇文章將拆解每一款工具實際上如何處理遞迴、付出了什麼代價，以及對 lychee 意味著什麼。

如果你還沒看過 第一篇文章，摘要如下：lychee 的架構是一次性、單向的管線（pipeline）（inputs → extract → check → output）。遞迴需要一個循環（回應會產生新的輸入），而在非同步、基於通道（channel）的管線中加入循環，正是 惡龍出沒之處。🐲 經過五年、四次嘗試後，我們真正需要的那些拼圖才剛剛到位。

DAG 與循環

我看過的每一款支援遞迴的檢查工具，都是由相同的三個部分組成：

1. 一個可變的工作佇列（我們稱之為 frontier(待爬佇列)），而非固定的輸入串流。被發現的 URL 會回到它們原本所在的同一個佇列。
2. 一個在入佇列時（在請求完成之前）就會更新的已造訪集合（visited set），因此兩個同時發現同一個連結的頁面，不會重複提交。
3. 一個用來回答「全部完成了嗎？」的 primitive(原語)：WaitGroup、可等待的佇列計數器、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

爬蟲的架構天生就有一條 back-edge(回邊)。我們的管線沒有，而我每一次失敗的嘗試，都是想把這條回邊硬塞進一個從未為此設計的架構圖中。

讓我們更仔細地看看這個架構圖的設計：

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 第 1 到第 4 次嘗試的 deduplication race(去重競爭)的關鍵，在那些嘗試中，快取是在檢查之後才寫入的。

每一款工具都是這個模式的變體。

muffet（Go）：一個 WaitGroup 與一個 Set

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() 就會返回。整個爬取過程以一次 addPage 呼叫在 Run() 之前啟動，因此在任何人等待之前，計數就已經是正數。

這正是與我在 嘗試 1 和 嘗試 4 中嘗試過（並失敗）的同一個計數器。差別在於不變量（invariant）：waitGroup.Add(1) 永遠只會在一個已經在運行、且使計數保持大於零的 daemon 內部被呼叫（或在啟動時）。不存在計數短暫歸零但仍有待處理工作的空窗期。Go 的 WaitGroup 如此自然地強制執行這個不變量，讓人完全不覺得這是在做 distributed termination detection(分散式終止偵測)，但它確實就是。這在精神上等同於 Kait（凱特）在 2026 年貢獻給 lychee 的 WaitGroup 原語。

取捨之處

• 並行度並非由 daemon manager 來限制。Run() 會為每個任務執行 go f()，產生無限制的 goroutine。真正的限流發生在下游的 semaphore（以緩衝通道實現的計數信號量）與每個主機的節流器池中。muffet 將「待爬佇列」與「速率限制器」分開，這正是 lychee 過去試圖用單一有界通道同時扮演兩種角色時所缺乏的區分。
• 廉價的 goroutine 承擔了大量工作。在 Go 中，為每個連結產生一個 goroutine 是「沒問題的」。在 Rust 中等價的做法（每個連結 tokio::spawn 一次，且每個都需要 Send + 'static 狀態）正是把我推向 Arc<RwLock<…>> 與所有權痛苦的原因，我曾在 文章中寫過。
• 在擴充性方面，muffet 是一個專注的 CLI，而非函式庫。它沒有外掛介面；你只能得到旗標（flags）提供的功能。lychee 則刻意將 lychee-lib 作為可重用的 crate 來發佈，這拉高了門檻，因為每個架構決策都必須符合公開 API 的標準。
• 在可擴展性方面，無限制的 goroutine 加上記憶體內的已造訪集合，可以輕鬆應對大型網站，但由於沒有磁碟支援的待爬佇列，真正巨大的爬取仍受限於記憶體（RAM）。這點與 lychee 相同。

LinkChecker（Python）：可等待的無界佇列

LinkChecker 自 2000 年就已存在。它是一個同步的、基於執行緒池的爬蟲。

它的待爬佇列是一個手寫的 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 中遇到的 backpressure deadlock(背壓死結)，而且是刻意被點出並加以規避的。lychee 曾試圖將發現的 URL 推入一個有界通道；當通道填滿時，回應處理器被卡住，沒有回應被排空，也沒有空位被釋放。死結。💥

LinkChecker 的解法帶有粗獷主義的風格：待爬佇列是無界的。背壓（backpressure）在別處強制執行（固定的執行緒數量與按主機的節流），絕不會透過阻塞一個同時也是消費者的生產者來實現。

用計數器實現終止，而且做對了

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 鎖內進行，而且工作器只有在完全處理完一個項目包含將其子項目入佇列後，才會呼叫 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 的嘗試中所缺少的「修正」。當任何工作執行緒檢查該 URL 時，快取早已標示為「已佔有」，因此來自另一個頁面的並行發現就成了無操作（no-op）。

按主機的禮貌性與終止保護

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 模型能在少數 OS 執行緒上達到數千個並行的在途請求；LinkChecker 做不到，也不打算這麼做。
• 無界的待爬佇列以無限的記憶體換取避免死結。「不設最大容量」的明確決策意味著在大型網站上記憶體會持續成長。有一個 max_allowed_urls 上限與定期的 cleanup() 來緩解這個問題。
• 擴充性極佳。LinkChecker 擁有真正的外掛系統（linkcheck/plugins/：錨點檢查、SSL、病毒掃描等）以及多種輸出記錄器。這是其中擴充性最高的一款，代價是一個龐大、成熟、略顯老派的程式碼庫。
• 在可擴展性方面，它受限於 GIL 且受執行緒數量限制，因此原始吞吐量是這幾款中最低的，但正確性與功能涵蓋度很高。

linkinator（TypeScript）：單執行緒的 queue.onIdle()

linkinator 是一個 Node.js 檢查工具，它享有 Go 與 Rust 都沒有的一項優勢：single-threaded event loop(單執行緒事件循環)。對已造訪集合的檢查並插入操作是免費原子性的，因為不會有兩個回呼同時執行。

待爬佇列是一個有並行限制的 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 的形式表達，並由單執行緒的執行環境支撐，因此不需要 Mutex 來保護已造訪集合。

回邊與無競爭的去重

在爬取時，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 中，這是一段必須用互斥鎖保護的 critical section(臨界區)（而且必須把順序處理正確）；在 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 的多執行緒執行環境則能並行解析與檢查。
• 它有記憶體內結果膨脹的問題。原始碼中明確註解了「對於高度互連的網站會出現 massive result inflation」：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 的佇列，並且巢狀了兩個這樣的佇列：一個站點層級的佇列，餵給頁面層級的 HtmlUrlChecker。

待爬佇列與去重邏輯位於 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() 難追蹤得多。這就是我先前描述的 leaky abstraction(抽象洩漏)問題在 JS 中的對應版本——對遞迴的感知被分散到許多處理器中。
• 它是單執行緒的，與 linkinator 有相同的天花板，再加上每個站點記憶體內的 URLCache。
• 就成熟度與動能而言，它被非常廣泛地使用（支撐了許多工具），但開發已趨緩。架構本身仍然穩固，值得研究。

關於 markdown-link-check 與「工業級」爬蟲的補充

我們的 README 將 markdown-link-check 標記為支援遞迴，但其中有些細微差別：它是在 Markdown 檔案之間遞迴，而非透過爬取即時網站。沒有 HTTP 待爬佇列，也沒有上述意義上的終止問題。值得一提以保持比較的誠實，但不值得深入拆解。

如果你想看這個模式在完整工業規模下的樣子，可以看看 Scrapy（Python/Twisted）或 Colly（Go）。兩者都使用相同的方法：一個帶有可插拔、可選磁碟支援佇列的排程器（scheduler，待爬佇列）、一個去重過濾器（dupefilter，往往是 Bloom filter 而非 HashSet）、一個有界的下載器池，以及明確的「引擎閒置 → 關閉爬蟲」終止機制。它們解決的正是 lychee 曾經掙扎的那些問題（distributed termination detection(分散式終止偵測)、背壓（backpressure）、去重），只是背後有著多年專注於爬蟲工程的累積。重點並不是「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 清單，檢查一次、速度要快）。要在管線上硬加一個循環，遠比一開始就有循環來得困難。這個問題本質上是架構性的。

待爬佇列與速率限制器必須是不同的物件。

muffet（集合 + 信號量）、LinkChecker（無界佇列 + 執行緒數量）、linkinator（p-queue + delayCache）、BLC（請求佇列 + maxSockets）全都將「接下來要做什麼」與「要跑多快」分開。lychee 早期的嘗試試圖讓單一有界通道同時扮演兩種角色，而一個經過有界通道的循環會造成死結。修正方案（lychee 的 HostPool 加上在無界工作來源之上的 WaitGroup）正是我們現在追求的同樣分離。

單執行緒執行環境免費獲得去重。

兩款 Node 工具都用一個普通的 Set 加上零鎖定來去重，因為事件循環會將存取序列化。Go 與 Python 付出一個互斥鎖的代價。Rust 則付出一個互斥鎖加上還要與借用檢查器（borrow checker）爭論誰在 tokio::spawn 之間擁有共享狀態。那就是我 上次估算的約 30%「Rust 稅」：不是演算法本身，而是要在 Send + 'static 之下表達共享可變待爬佇列狀態時的摩擦。

這些都不是對 lychee 設計的否定。單向串流對於常見的非遞迴情境是正確的選擇：這就是 lychee 快速的原因，也是 嘗試 2 中 30% 的通道效能衰退會成為致命傷的原因。其他工具無論是否遞迴，每次執行都要為它們的回邊付出代價。lychee 拒絕這麼做，而這個原則正是遞迴花了五年才實現的原因，也是當它最終落地時，不會拖慢大家實際使用的路徑的原因。我相信我們可以魚與熊掌兼得：一個支援遞迴、同時又不犧牲一次性管線速度的爬蟲架構。但這比單純「照抄他們的做法」要困難得多，因為大多數連結檢查工具一開始並沒有把毫不妥協的效能當作首要目標。

所以當有人問「其他連結檢查工具如何實現遞迴？」時，真正的答案是：他們從一開始就將其作為架構的一部分，並依賴一個執行環境（提供了像是 WaitGroup、可等待佇列、閒置 promise 等便利機制）來解決終止問題，而無需去解「分散式終止偵測」這個難題。

感謝 muffet、LinkChecker、linkinator 與 broken-link-checker 的維護者們：閱讀你們的原始碼是目前學習爬蟲架構最清晰的方式，我們都在同一條路上，只是做了不同的取捨。