在我發表了 嘗試為 lychee 加入遞迴的五年 之後，收到一個非常中肯的問題：

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

這讓我一頭栽進去，把其他連結檢查工具的原始碼都讀了一遍。最重要的結論是：他們並沒有找到什麼我們沒想到的聰明技巧。他們從第一次提交開始就是以爬蟲的形式打造的，而我一開始是把 lychee 做成串流（stream）。

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

如果你還沒看過 第一篇文章，簡單總結就是：lychee 的架構是一次性、單向的管線（inputs → extract → check → output）。遞迴則需要一個循環（回應會產生新的輸入），而在非同步、基於 channel 的管線中加入循環，正是 惡龍出沒之處。🐲 經過五年、四次嘗試之後，要正確實現它所需的拼圖，直到最近才終於到位。

DAG vs. 循環

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

1. 一個可變的工作佇列（我們就叫它「frontier」），而不是固定的輸入串流。發現的 URL 會回到它們原本來源的同一個佇列中。
2. 一個在入佇列時（在請求完成之前）就更新的已造訪集合，這樣兩個頁面同時發現同一個連結時，就不會重複提交。
3. 一個用來回答「全部都完成了嗎？」的原語：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

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

讓我們更仔細地看看那個圖的設計：

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]

請注意，已造訪檢查發生在 enqueue 階段，與標記動作原子性地一起完成，遠在 worker 接觸網路之前。這個順序正是徹底解決困擾 lychee 前四次嘗試的重複檢查競爭問題的關鍵——在那幾次嘗試中，快取是在檢查之後才寫入的。

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

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（由 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)   // 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 來啟動的，所以在任何人等待之前，計數就已經是正數了。

這正是 同一個計數器——我在 第一次嘗試和 第四次嘗試中嘗試過（而且失敗了）的那一個。差別在於不變量（invariant）：waitGroup.Add(1) 永遠只會在一個已經在執行、並讓計數保持大於零的 daemon 內部被呼叫（或是來自啟動階段）。不會出現計數短暫歸零、但其實還有待處理工作的空窗。Go 的 WaitGroup 如此自然地強制執行這個不變量，以至於你根本不會覺得這是在做分散式終止偵測，但它本質上正是如此。它在精神上等同於 Kait 在 2026 年為 lychee 貢獻的 WaitGroup 原語。

取捨之處

• 並行度並不是由 daemon manager 來限制的。Run() 會為每個任務執行 go f()，產生無限制數量的 goroutine。真正的限流發生在下游的 semaphore（一個用 buffered channel 實作的計數信號量）以及每個主機的限流池。muffet 把「frontier」和「限速器」分開，而這正是 lychee 過去試圖用同一個有界 channel 同時扮演兩種角色時所缺乏的分離。
• 廉價的 goroutine 扛下了大量工作。在 Go 裡，為每個連結產生一個 goroutine 是「沒問題的」。而在 Rust 中等價的做法（每個連結一個 tokio::spawn，每個都需要 Send + 'static 的狀態）正是把我推向 Arc<RwLock<…>> 以及我 曾寫過的所有權之痛的原因。
• 在可擴充性上，muffet 是一個專注的 CLI，而不是一個函式庫。它沒有外掛介面，你只能用旗標提供的功能。lychee 則刻意將 lychee-lib 作為可重用的 crate 來發佈，這提高了門檻，因為每個架構決策都必須符合公開 API 的標準。
• 在可擴展性上，無限制的 goroutine 加上記憶體內的已造訪集合，可以輕鬆應對大型網站，但由於沒有落地儲存的 frontier，真正超大規模的爬取還是會受限於記憶體大小。這點和 lychee 一樣。

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

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

它明確點出了曾經咬到我的那個死鎖。

那段註解就是我們在 第四次嘗試中遇到的背壓死鎖，而且是被明確指出並刻意繞開的。lychee 曾試圖把發現的 URL 推入一個 有界 channel；當它被塞滿時，回應處理器被卡住，沒有回應被消化，也沒有空位被釋放。死鎖。💥

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。因此子項目會在父項目被標記完成之前就被計數，不會出現過早歸零的情況。這就是用 mutex 和條件變數實作的 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 模型可以在少數 OS 執行緒上達到數千個並行請求；LinkChecker 做不到，也不打算這麼做。
• 無界的 frontier 用無限制的記憶體換取不死鎖。明確的「不設最大容量」決策意味著在超大網站上記憶體會不斷增長。有一個 max_allowed_urls 上限和定期的 cleanup() 來緩解這個問題。
• 可擴充性非常出色。LinkChecker 有一套真正的插件系統（linkcheck/plugins/：錨點檢查、SSL、病毒掃描等等）以及眾多的輸出記錄器。它是這幾套中最具可擴充性的，也為此付出了代價：一個龐大、成熟、但有點老派的程式碼庫。
• 在可擴展性上，它受限於 GIL 和執行緒數量，因此原始吞吐量是這幾套中最低的，但正確性和功能覆蓋率很高。

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

linkinator 是一個 Node.js 的檢查工具，它享有 Go 和 Rust 都沒有的好處：單執行緒事件循環。對已造訪集合的檢查並插入是免費原子性的，因為不會有兩個回呼同時執行。

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 來表達，並由單執行緒的執行環境支撐，因此不需要 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 中，這是一段必須用 mutex 保護的臨界區（而且還得把順序弄對）；在 Node 中，它就只是三行敘述。這是遞迴在 Node 中比在 Rust 中容易得多的最主要原因。這純粹就是語言特性。

linkinator 還維護了一個以 `${url}|${parent}` 為鍵的 relationshipCache，以及一個 pendingChecks 映射，這樣它就能等待正在進行中的檢查，同時仍針對每個引用它的父頁面回報重複的失效連結。那些重用操作本身也會被推入同一個佇列，因此 onIdle() 也會正確地等待它們完成。

HEAD vs GET

linkinator 對葉節點連結使用 HEAD，但在需要爬取時則使用 GET，因為遞迴需要回應本體才能找到更多連結：

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

這正是 lychee 剩下尚未解決的問題：你只能遞迴進入那些你有用本體（body）抓取過的頁面。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 的佇列，並且嵌套了兩個這樣的佇列：一個站點層級的佇列，餵給頁面層級的 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）、一個有界的下載器池，以及明確的「引擎閒置 → 關閉爬蟲」終止機制。它們解決的正是 lychee 苦苦掙扎的那些問題（分散式終止偵測、背壓、去重），只是背後有著多年專注於爬蟲工程的累積。重點並不是「lychee 應該變成 Scrapy」：而是爬取是一個已經被走得很熟的架構，而 lychee 目前只是站在另一個架構上罷了。

並排比較

2026 年的 lychee 終於在每一欄都能對上。WaitGroup 就是 muffet 的 sync.WaitGroup 和 LinkChecker 的 join()。HostPool 就是 BLC 的 rateLimit／maxSockets 和 LinkChecker 的 wait_for_host。每個 URI 的 active_requests mutex 就是大家在入佇列時的去重機制。

那為什麼我們不能直接照抄就好？

有三個原因，按照它們實際上多大程度上是 lychee 自身問題的順序遞增排列。

它們一開始就是爬蟲；lychee 一開始是串流。

上面每一套工具的核心資料結構中都有回邊。lychee 的核心是一個為 99% 情境最佳化的 DAG（一份檔案／URL 清單，檢查一次、速度要快）。要在管線上事後硬加一個循環，遠比一開始就有循環來得困難。這個問題本質上是架構性的。

frontier 和限速器必須是不同的物件。

muffet（set + semaphore）、LinkChecker（無界佇列 + 執行緒數量）、linkinator（p-queue + delayCache）、BLC（request queue + maxSockets）全都把「下一步要做什麼」和「要跑多快」分開。lychee 早期的嘗試試圖讓同一個有界 channel 同時扮演兩種角色，而透過有界 channel 的循環會死鎖。解法（lychee 的 HostPool 加上在無界工作來源之上的 WaitGroup）正是我們現在追求的同樣分離。

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

兩套 Node 工具都用普通的 Set 來去重，完全不需要上鎖，因為事件循環會序列化存取。Go 和 Python 要付一個 mutex 的代價。Rust 不只要付 mutex，還得跟借用檢查器纏鬥，爭論跨 tokio::spawn 的共享狀態該由誰擁有。那就是我 上次估算的約 30%「Rust 稅」：不是演算法本身，而是要在 Send + 'static 之下表達可變共享 frontier 狀態時的摩擦。

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

所以當有人問「其他連結檢查工具是怎麼做到遞迴的？」真正的答案是：它們從一開始就把遞迴做進架構裡，並且倚靠執行環境（提供像 WaitGroup、可等待佇列、閒置 promise 這類便利設施）來解決終止問題，而不需要去解「分散式終止偵測」這個難題。

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