lycheeに再帰を導入しようとした5年間を公開したあと、とてももっともな質問をいただきました。

再帰がそんなに難しいのなら、他のリンクチェッカーはどうやって実現しているのですか？ すでにウェブサイトをクロールしているツールはたくさんあるのに！

これをきっかけに、他のリンクチェッカーのコードを読み漁ることになりました。結論から言うと、彼らが私たちが見落としたような巧妙な裏技を見つけていたわけではありません。彼らは最初のコミットからクローラーとして作られていたのに対し、私は当初lycheeをストリームとして作っていたのです。

そこで、lycheeのREADMEで紹介している再帰対応のチェッカーたち、muffet（Go）、LinkChecker（Python）、linkinator（TypeScript）、そしてbroken-link-checker（JavaScript）のソースを読んでみました。本記事では、それぞれが実際にどう再帰を処理しているのか、そこにどんなコストがかかっているのか、そしてそれがlycheeにとって何を意味するのかを分解していきます。

前回の記事をまだ読んでいない方のために要約すると、lycheeは一回限りの単方向パイプライン（inputs → extract → check → output）として設計されていました。再帰にはサイクルが必要です（レスポンスが新たな入力を生みます）。そして非同期かつチャネルベースのパイプラインでサイクルを扱うところにこそ、竜が潜んでいるのです。🐲 5年と4回の挑戦を経て、適切に実現するために必要なピースがようやく揃いました。

DAGとサイクル

私が見たすべての再帰対応チェッカーは、同じ3つの要素でできていました。

1. 可変の作業キュー（「フロンティア」と呼びます）。固定の入力ストリームではありません。発見されたURLは、取り出されたのと同じキューに戻ります。
2. エンキュー時（リクエストが完了する前）に更新される訪問済みセット。これにより、2つのページが同じリンクを見つけても、両方が登録してしまうことがありません。
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]

訪問済みチェックがエンキューの段階で、マークとアトミックに、ワーカーがネットワークに触れる前に行われることに注目してください。この順序こそが、lycheeの試行1〜4を悩ませた重複排除のレースコンディションに対する完全な修正です。あのときはキャッシュへの書き込みがチェックの後に行われていました。

各ツールはこのパターンのバリエーションを使っています。

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
}

スケジュールされたページごとにグループのカウントが1増え、完了するごとに1減ります。Wait()はカウントがゼロになったときに返ります。クロール全体はRun()の前に一度だけaddPageを呼ぶことでブートストラップされるため、誰かが待機する前にカウンターは必ず正の値になっています。

これは私が試行1と試行4で試して（そして失敗した）まさに同じカウンターです。違いは不変条件にあります。waitGroup.Add(1)は、カウントをゼロより大きく保っている実行中のdaemonの中から（あるいはブートストラップ時から）のみ呼ばれます。まだ処理すべき仕事が残っているのに、カウンターが一瞬ゼロになるような隙間は存在しません。GoのWaitGroupはこの不変条件をあまりに自然に保証するため、分散終了検知のようにすら感じられませんが、実際にはまさにそれです。これは2026年にKaitがlycheeにコントリビュートしたWaitGroupプリミティブと本質的に同じものです。

トレードオフ

• 並行数はdaemon managerによって制限されません。Run()はタスクごとにgo f()を実行し、際限なくgoroutineを生成します。実際の制限は下流のsemaphore（バッファ付きチャネルによる計数セマフォ）とホストごとのスロットラープールで行われます。muffetは「フロンティア」と「レートリミッター」を分離していますが、これはまさに、lycheeが過去に一つの有界チャネルに両方の役割を持たせようとして欠いていた分離です。
• 安価なgoroutineが多くの重労働を担っています。リンクごとにgoroutineを生成してもGoでは「まあ大丈夫」で済みます。Rustで同等のこと（リンクごとにtokio::spawnし、それぞれがSend + 'staticな状態を必要とすること）をやろうとすると、Arc<RwLock<…>>へ向かわざるを得ず、私が書いたような所有権の苦労を招きます。
• 拡張性という点では、muffetはライブラリではなく、的を絞ったCLIです。プラグイン機構はなく、フラグで得られるものがすべてです。lycheeは再利用可能なクレートとしてlychee-libをあえて提供しており、その分ハードルは上がります。すべてのアーキテクチャ上の選択が、公開APIの基準を満たさなければならないからです。
• スケーラビリティについては、際限なく増えるgoroutineとインメモリの訪問済みセットにより大規模なサイトでも快適にスケールしますが、ディスクに退避するフロンティアはないため、本当に巨大なクロールはRAMに縛られます。lycheeと同じです。

LinkChecker（Python）：join可能な非有界キュー

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で起きたバックプレッシャーによるデッドロックそのものを指摘し、対策したものです。lycheeは発見したURLを有界チャネルに流し込もうとしました。チャネルが満杯になるとレスポンスハンドラーがブロックし、レスポンスは排出されず、空きスロットも生まれません。デッドロックです。💥

LinkCheckerの答えはいたって力技です。フロンティアは非有界なのです。バックプレッシャーは別の場所（固定のスレッド数とホストごとのスロットリング）で強制され、生産者でもあり消費者でもある主体をブロックすることでは決して制御しません。

カウンターによる終了判定 — 正しいやり方

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を呼びます。つまり子は親が完了とマークされる前にカウントされ、ゼロが早まることはありません。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の試行には欠けていた「修正」です。どのワーカースレッドが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はそれを狙っておらず、そもそもできません。
• 非有界フロンティアは、デッドロックを非有界なメモリ使用と交換しています。「最大サイズなし」という明示的な決定は、巨大なサイトではRAMが膨らむことを意味します。緩和策としてmax_allowed_urlsの上限と定期的なcleanup()が用意されています。
• 拡張性は優れています。LinkCheckerにはちゃんとしたプラグインシステム（linkcheck/plugins/：アンカーチェック、SSL、ウイルススキャンなど）と、多数の出力ロガーがあります。今回紹介する中では最も拡張性が高く、その分、成熟しつつもやや古風な大規模コードベースという代償を払っています。
• スケーラビリティについては、GILに縛られスレッド数にも限りがあるため、生のスループットはここで紹介する中で最も低いですが、正確性と機能カバレッジは高いです。

linkinator（TypeScript）：シングルスレッドのqueue.onIdle()

linkinatorはNode.js製のチェッカーで、GoにもRustにもない恩恵を受けています。シングルスレッドのイベントループです。訪問済みセットへのチェックと挿入は、2つのコールバックが同時に実行されることがないため、ただでアトミックになります。

フロンティアは並行数が制限された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()はライブラリの終了検知機構です。キューが空かつ実行中のタスクがないときに解決します。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ではただの3つの文で済みます。これが、再帰がRustよりもNodeではるかに簡単な最大の理由です。単なる言語の特性なのです。

linkinatorはさらに、`${url}|${parent}`をキーとするrelationshipCacheと、進行中のチェックを待機しつつ、それを参照するすべての親に対して重複するリンク切れを報告できるようにするpendingChecksマップも保持しています。これらの再利用操作自体も同じキューに積まれるため、onIdle()はそれらも正しく待ちます。

HEAD vs GET

linkinatorは末端のリンクにはHEADを使いますが、クロールが必要なときはGETを使います。なぜなら再帰では、さらにリンクを見つけるためにレスポンスボディが必要だからです。

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

これはまさにlycheeに残された未解決の問題です。ボディ付きで取得したページにしか再帰できないのです。linkinatorはクロール時には常にGETしますが、lycheeは直前のチェックでキャッシュに持っているボディを再利用する計画です。

トレードオフ

• シングルスレッドは恵みでもあり上限でもあります。データレースはなく、重複排除も自明に正しいですが、HTMLのパースはただ一つのイベントループをブロックするCPU処理です。数千ページともなれば、単一コアに縛られます。lycheeのマルチスレッドランタイムはパースもチェックも並列に行います。
• インメモリでの結果の膨張という問題を抱えています。ソースには「密に相互リンクされたサイトでの莫大な結果の膨張」について明記されています。results配列、cache、relationshipCacheのすべてがクロールとともに増大します。ドキュメントサイトなら問題ありませんが、巨大なサイトでは重くなります。
• レート制限は事前的ではなく事後的です。429とRetry-Afterに対してホストごとにバックオフするdelayCacheはありますが、lycheeのHostPoolのようなホストごとの並行数上限は一般的にはありません。linkinatorはホストが文句を言うまで叩き続ける可能性がありますが、lycheeは文句を言われる前にペースを調整します。
• 拡張性については、EventEmitter（on('link')やon('pagestart')など）なので、埋め込みやスクリプト化が可能で便利です。lycheeと同じく、まずはライブラリとして作られています。

broken-link-checker（JavaScript）：イベント駆動と2つのキュー

broken-link-checker（BLC）は、イベント駆動のモデルを最も推し進めています。limited-request-queueの上に構築されています。これはmaxSockets（並行数）とrateLimitを持つキューで、そのうち2つをネストしています。サイトレベルのキューが、ページレベルの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をemitしてサイトキューの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は一級市民として扱われます。デフォルトで礼儀正しいクローラーです。
• イベントカスケードは強力ですが扱いが繊細です。終了判定は半ダースものイベントハンドラーと2つのネストされたキューに分散しています。動作はしますが、制御フローはawait queue.onIdle()よりもはるかに追いづらくなっています。これは私が説明した「抽象化の漏れ」問題のJS版であり、再帰への意識が多くのハンドラーに散らばってしまうのです。
• シングルスレッドであり、linkinatorと同じ上限を抱え、さらにサイトごとのインメモリURLCacheもあります。
• 成熟度と勢いという点では、非常に広く使われており（多くのツール群を支えています）、一方で開発のペースは落ち着いています。それでもアーキテクチャは健全で、学ぶ価値があります。

補足：markdown-link-checkと「産業用」クローラーについて

私たちのREADMEではmarkdown-link-checkを再帰対応としていますが、ここにはニュアンスがあります。あちらは生きたウェブサイトをスパイダリングするのではなく、Markdownファイルに対して再帰するのです。HTTPフロンティアも、上で述べた意味での終了問題も存在しません。比較を誠実にするために触れておく価値はありますが、分解して論じるほどではありません。

このパターンを産業規模で見たいなら、Scrapy（Python/Twisted）やColly（Go）を見てください。どちらも同じアプローチをとっています。プラガブルで必要に応じてディスクバックなキューを持つスケジューラー（フロンティア）、dupefilter（HashSetではなくBloom filterが使われることも多い）、有界なダウンローダープール、そして「エンジンがアイドルになったらスパイダーを閉じる」という明示的な終了判定です。これらはlycheeが苦労した問題（分散終了検知、バックプレッシャー、重複排除）をまさに解決しています。ただしそこには何年にもわたるクローラー専用のエンジニアリングの積み重ねがあります。ここでの教訓は「lycheeはScrapyになるべきだ」ではありません。クローリングはよく踏み固められたアーキテクチャであり、lycheeが今たまたま別のアーキテクチャの上に立っている、ということです。

比較表

2026年のlycheeは、ようやくすべての列で肩を並べました。WaitGroupはmuffetのsync.WaitGroupやLinkCheckerのjoin()に、HostPoolはBLCのrateLimit／maxSocketsやLinkCheckerのwait_for_hostに対応します。URIごとのactive_requests mutexは、誰もがやっているエンキュー時の重複排除と同じものです。

では、なぜ単純に真似できなかったのか？

理由は3つあり、lychee側の責任が大きい順に並べています。

彼らはクローラーとして始まり、lycheeはストリームとして始まった。

上で挙げたすべてのツールは、コアとなるデータ構造にバックエッジを持っています。lycheeのコアは99%のケース（ファイルやURLのリストを一度だけ高速にチェックする）に最適化されたDAGでした。最初からサイクルを持っているよりも、後からパイプラインにサイクルを付け足す方がはるかに難しいのです。これは本質的にアーキテクチャの問題です。

フロンティアとレートリミッターは別物でなければならない。

muffet（set＋semaphore）、LinkChecker（非有界キュー＋スレッド数）、linkinator（p-queue＋delayCache）、BLC（request queue＋maxSockets）はいずれも、「次に何をやるか」と「どれくらいの速さで進むか」を分離しています。lycheeの初期の試みでは、一つの有界チャネルに両方の役割を持たせようとし、有界チャネルを経由するサイクルはデッドロックします。修正策（lycheeのHostPoolと、非有界な作業ソースに対するWaitGroup）は、まさに今目指しているのと同じ分離です。

シングルスレッドのランタイムでは重複排除がタダで手に入る。

2つのNode製ツールは、イベントループがアクセスを直列化するため、素のSetでロックなしに重複排除を行います。GoとPythonはmutexのコストを払います。Rustはmutexのコストに加え、tokio::spawnをまたいで共有状態を誰が所有するのかという借用チェッカーとの戦いも強いられます。これが前回見積もった約30%の「Rust税」の正体です。アルゴリズム自体ではなく、Send + 'staticの下で共有・可変なフロンティア状態を表現する際の摩擦なのです。

これらはどれもlycheeの設計を貶めるものではありません。単方向のストリームは、一般的で再帰を必要としないケースにおいて正しい選択でした。だからこそlycheeは高速であり、試行2での30%のチャネル回帰が致命的だったのです。他のツールは、再帰するかどうかに関わらず、毎回の実行でバックエッジのコストを払っています。lycheeはそれを拒否しました。その原則こそが、再帰に5年かかった理由であり、実装されたとしても皆さんが実際に使っているパスを遅くしない理由でもあります。私は、ケーキを持ちつつそれを食べることもできると信じています。すなわち、ワンショットのパイプラインの速さを犠牲にすることなく再帰を支えるクローラーアーキテクチャです。ただそれは「彼らのやっていることを真似すればいい」よりも難しい問題です。なぜなら、ほとんどのリンクチェッカーは、妥協のないパフォーマンスを最優先の目標としてスタートしていないからです。

ですから「他のリンクチェッカーは再帰をどうやっているの？」と誰かに聞かれたら、本当の答えはこうです。彼らはそれを最初からアーキテクチャの一部にし、終了判定を「分散終了検知」を解くことなく解決してくれるランタイム（WaitGroupやjoin可能なキュー、アイドルPromiseといった便利な仕組みを提供するもの）に頼ったのです。

muffet、LinkChecker、linkinator、broken-link-checkerのメンテナの皆さんに感謝します。皆さんのソースを読むことは、クローラーアーキテクチャを学ぶための最も明確な方法であり、私たちは皆、異なるトレードオフを抱えながら同じ船に乗っているのです。