再帰はlycheeで最も長く開かれたままの課題だ。かれこれ5年以上、未解決のまま放置されている。

ご存じない方のために説明すると、lycheeはRustで書かれた高速で非同期なリンクチェッカーだ（ちなみに）。ウェブサイトやドキュメント、README、Markdownファイルを指定すればチェックしてくれる。

僕は2020年、家で退屈したのがきっかけで作り始めた。今では約4万のGitHubリポジトリがlycheeに依存している。Google、AWS、Microsoft、Cloudflareなど、多くの企業がドキュメントのリンクチェックに使っている。

詳しく知りたい方向けにトークやポッドキャストでも話している。

lycheeは、オープンで信頼できるインフラのためのNGI Zeroプログラムを通じてNLnetから資金提供を受けた。

その資金のおかげで、夜中にこっそりコードを書くのではなく、腰を据えてプロジェクトに時間を使えるようになった¹。その資金提供もそろそろ終わりを迎えるので、この記事を書くのにちょうどいいタイミングだと感じている。

そして正直に言えることはこれだ。最も要望の多かった機能である再帰が、いまだにリリースされていないということだ。:,( でも、ちゃんとした理由がある。もちろん一言で言えば「難しいから」なのだが、もう少し深掘りしてみよう。

始まり

2020年12月14日、@styfleというユーザーがissue #78を立てた。

至極もっともな要望だ。当時のlycheeはすでに高速で並行処理が可能な、多機能なリンクチェッカーだった。ドメイン内でリンクをたどるためのちょっとした--recursiveフラグを追加するくらい、正直に働けば1日でできるだろうと思えるではないか。

しかし5年が経ち、4回の本格的な実装の試みと、何本もの放棄されたプルリクエストを経ても、再帰はまだマージされていない。このissueはv1.0マイルストーンに紐づけられており、できればそれまでにリリースしたいと思っている。だが、いつの間にかそれはlycheeにとっての白鯨になってしまった。

当初のアーキテクチャが事を難しくした

なぜ再帰の追加がこれほど難しいのかを理解するには、lycheeがどのように処理を行っているかを知る必要がある。こちらが2020年後半当時のフローだ。

基本的には、入力URLからリンク抽出、リンクチェック、そして出力フォーマットへと続く、1本の大きなパイプラインだ。

@styfleがissueを立てたとき、僕はほぼ即座に核心的な問題に気づいた。

extractorへの戻り経路がない。

この欠けているフィードバックループ（チェック済みのレスポンスから入力キューへの戻り）が、問題の核心を一言で表している。lycheeのパイプラインは一回限りの単方向フローとして設計されていた。入力が一方から入り、結果がもう一方から出てきて、入力ストリームが止まればプログラムも終了する。再帰にはサイクルが必要だ。レスポンスが新たな入力を生み出せなければならない。そして非同期でチャネルベースのパイプラインにおけるサイクルこそ、竜が潜む場所なのだ。🐲

このことは初日からわかっていた。ただ、そのサイクルを間違える方法がどれだけたくさんあるかを、ひどく過小評価していたのだ。

試行1：シンプルなカウンター（2021年2月〜12月）

僕の最初の試みはあえて小さくした。アーキテクチャを作り直すつもりはなく、とにかく再帰を動かしたかった。そこで処理を直接main.rsに追加した。アイデアはこうだ。

1. レスポンスを受け取った後、もとの入力ドメインのいずれかに由来するものなら、そこからリンクを抽出する。
2. その新しいリンクをリクエストチャネルに押し戻す。
3. 予想されるリクエスト総数と完了したリクエスト数をカウントし続ける。
4. completed == totalになったら停止する。

成功したレスポンスに対してcollector::collect_links()を呼ぶrecurse()関数を追加し、新しいリクエストをチャネルに送るタスクをspawnして、何件の新しいリクエストを生成したかを返すようにした。プレーンなHashSet<String>を「seen」キャッシュとして使い、同じURLを二度チェックしないようにした。

それに加えて：

• RequestとResponse構造体にrecursion_levelフィールド
• --recursive / -rフラグ
• 最大再帰深度を指定する--depthオプション
• 入力ドメイン内に留まるためのドメインフィルタリング

シンプルだろう？

違う

プログラムが終了しなかったのだ。

終了判定のロジックはwhile curr < total_requestsループだった。

let mut curr = 0;
while curr < total_requests {
    curr += 1;
    let response = recv_resp.recv().await.context("Receive channel closed")?;
    // ... process response, potentially incrementing total_requests
}

レスポンスが届いて新しいリクエストが生成されると、total_requestsは増える。ここまではいい。だが抽出、送信、受信はすべて異なるタスク間で並行して行われるため、カウントがずれる可能性がある。

当時から僕自身、これに満足していなかった。

正直、今の実装にはあまり満足していない。キュー内のリンク数を数えて、すべてのリンクをチェックし終えたらチャネルを閉じるというやり方だからだ。微妙なバグにつながりかねないと思う。もっと良い方法があるはずだ。

そう、その通り、過去のマティアスよ。カウンターが脆い理由はこうだ。

• 新しいリンクは非同期に発見されるため、ループがすでに終了を決めた後でtotal_requestsが増える可能性がある。
• カウントが1つでもずれれば、永遠にハングするか（カウントが大きすぎる）、早すぎる終了になる（カウントが小さすぎる）。
• さらに追い打ちをかけるように、エッジケースのたびにカウントのロジックはより厄介になった。キャッシュされたレスポンス、失敗したレスポンス、空のページ、……。

@pawromanがここで本当に徹底的なレビューをくれた。HashSetキャッシュのメモリ使用量の精密な分析（数百万リンクまでは問題なし）、無限再帰を表現するために符号付きのdepth値を使う提案、統合テストを促す指摘などが含まれていた。良いフィードバックだった。ただ、根本的に間違っていた終了へのアプローチそのものは直せなかった。

とどめの一撃

2021年9月、僕たちは並行性を改善するために、ストリームベースのアーキテクチャへの大きな書き直しを決めた（PR #330）。Collector::collect_linksがVecを返すのではなくStreamを返すように変わり、ClientPool抽象化が削除され、タスク間の通信の形も変わった。collectorが遅延評価になり、巨大なVecを確保しなくて済むようになったので、これは大きな改善だった。しかし同時に、再帰ブランチは壊れ、足元をすくわれることになった。

#330でストリームベースのアプローチを実装し始めたので、これもまた一旦保留にする。すぐにこのブランチに取って代わるかもしれない。再帰サポートを待ってくれているみんなには申し訳ないが、バグのある解決策を早まってマージするより、正しくやりたいと思う。

PR #165は2021年12月にクローズされた。ストリームへのリファクタリングはマージされ、35〜50%の高速化をもたらした。素晴らしい！トレードオフということだろう。

そして言語についての質問をよく受けるので、正直に一言付け加えておくと、ここのカウントの問題はRustのせいではない。goroutineとチャネルを使ったGo版でも、Pythonのasyncio版でも、同じoff-by-oneバグにぶつかるだろう。「レスポンスが処理された」と「新しいリクエストが発見された」の間の競合は、並行再帰クローラーならどれでも本質的に抱えるものだ。RustのStreamトレイトと所有権との組み合わせがストリーミングアーキテクチャを自然なものに感じさせ、それがこの作業を無効にしてしまった。だから、その点はおそらくRust特有と言える。

試行2：チャネルでフィードバックさせる（2022年1月〜7月）

ストリームアーキテクチャが整ったので、再び挑戦してみた。今度は手動でリクエストを数えるのではなく、発見したURLをチャネルを通じてcollectorにフィードバックさせるという方法だ。

collectorは入力チャネルから読み取り、受け取ったものをリクエストのストリームに変換する。再帰は、新たに発見したURLをそのチャネルに送るだけで済む（ほら、フィードバックループだ！）。チャネルが閉じればストリームも自然に閉じる。

入力型を統一して、1つのメソッドでVecでもStreamでも受け取れるようにする試みもした。

pub enum InputType {
    Stream(Pin<Box<dyn Stream<Item = Input>>>),
    Seq(Vec<Input>),
}

またもハングした。だが今回はまったく別の理由だった。

フィードバックループは循環依存を生んだ。

1. collectorが入力チャネルから読み取り、リクエストのストリームを生成する。
2. checkerがリクエストを読み取り、レスポンスを生成する。
3. 再帰ハンドラーがレスポンスを読み取り、新しい入力をcollectorのチャネルに送り返す。

問題がわかるだろうか？

collectorのストリームが終わるには、入力チャネルが閉じなければならない。チャネルが閉じるには、すべてのsenderがdropされなければならない。しかし再帰ハンドラーはsenderを保持している。発見したURLを押し戻すために必要なのだ。そして再帰ハンドラーは、レスポンスがもうなくなったときにしか停止しない。それはリクエストがもうなくなったときにしか起こらず、それはcollectorのストリームが終わったときにしか起こらない。別の循環依存がデッドロックを引き起こしているのだ。

当時、僕はこう述べていた。

これまでこの問題を見る時間がほとんどなかったが、入力チャネルがdropされず、ぶら下がった接続が残るためにハングしている。futures::StreamExt::for_each_concurrentが終わればチャネルは自動的に閉じられ（そしてdropされる）と思っていた。

@untitakerがそれを確認し、自明なケースでもデッドロックを再現できるとした。

もう処理するものがなくなったらsenderをdropしたいということだよね？でもfor_each_concurrentは、まだそれをやっていないから永遠にハングしないか？（そして、さらにクローンするためにsenderが必要だから、できないよね）

空のディレクトリでtime lychee --offline -b . '**/*.htm*' -T1を実行しただけでもデッドロックを再現できる。

これが循環的なデータフローにチャネルを使うことの核心だ。チャネルはsenderのdropを終了シグナルとして使うが、サイクルの中ではすべてのsenderをdropすることは決してできない。各ステージがサイクルを維持するために1つを保持する必要があるからだ。

この問題をTokioのDiscordに持ち込んだところ、返ってきたアドバイスは「この用途でチャネルを使うのをやめろ。代わりにtokio::spawnとセマフォを使え」だった。

パフォーマンスの問題も

デッドロックを無視したとしても、2つ目の問題があった。新しいfrom_chanメソッドは、既存のfromメソッドよりベンチマークで約30%遅かったのだ。余分なチャネルを経由するコストがかかっており、しかもそれは基本的に誰もが使う非再帰のケースでもかかっていた。

チャネルサイクルのデッドロックは、チャネルベースのシステムならどれにも本質的なものだ。Goのチャネルも同じ問題を抱えている。チャネルを閉じるとは、もう誰も送信しないことを知っているという意味だが、サイクルがあるとそれが不可能になる。Erlang/OTPはチャネルセマンティクスの代わりにプロセス監視を使うことでこれを回避している。一方、30%のリグレッションはRust的な側面がある。Rustのゼロコスト抽象化の文化では、使わない機能に対してコストを払わないことが期待されている（僕自身も含めて）。ランタイムが重い言語なら、使わないパスでの30%のリグレッションは見過ごされるかもしれない。Rustでは「使わないものにはコストを払わない」はほとんど道徳的な立場であり、そのリグレッションを僕にとって受け入れ不可能なものにした。

試行3：セマフォ（2022年2月）

試したこと

再帰ループでのチャネル使用を完全にやめ、代わりに以下に手を伸ばした。

• Arc<Semaphore>で並行数を制限する（チャネルの自然なバックプレッシャーの代わり）
• 作業単位ごとのtokio::spawn（for_each_concurrentの代わり）
• 各タスクに渡されるOwnedSemaphorePermit。再帰的なサブタスクをspawnする際に作業を「移譲」できるようにするため

プロトタイプは正直なところ、かなりきれいだった。

const MAX_CONCURRENCY: usize = 10;

fn recurse(permit: OwnedSemaphorePermit, i: usize) -> JoinHandle<()> {
    tokio::spawn(async move {
        handle_input(permit, i).await;
    })
}

async fn handle_input(permit: OwnedSemaphorePermit, i: usize) {
    println!("got = {i}");
    if i % 9 == 0 {
        recurse(permit, 10).await.unwrap();
    }
}

だが問題が何だったかは想像がつくだろう。やはりロックしてしまったのだ。

このモデルを実際のコードベースに持ち込もうとしたとき、所有権の要求があっという間に醜くなった。リンクチェッカーはクライアント設定、キャッシュ、プログレスバー、統計情報、その他いろいろを必要とする。それらすべてをspawnされたタスク間で共有するには、すべてをArc<RwLock<State>>でラップしたくなる。このモデルをブランチで試したが、所有権とSendのせいでかなり醜くなった。

セマフォだけでは足りない

セマフォは並行数制限の問題を解決する。終了の問題には何もしてくれない。tokio::spawnでは、再帰的にspawnされたものを含む、すべてのspawnされたタスクがいつ終わったかを知る組み込みの方法がない。別の協調メカニズムが必要になる。つまり、試行1のカウンターを再発明することになる。ただし今度は無制限に増えるspawnされたタスク群に分散された形で。逃れようとしていたものに逆戻りしたわけだ。

パーミットにも微妙な点がある。for_each_concurrentを生のtokio::spawnに置き換えると、チャネルが無料で提供してくれていた制限付き並行性を失う。セマフォがそれを取り戻してくれるが、パーミットを慎重に管理しなければならない。タスクがパーミットを取得し、子をspawnしてパーミットを移譲すれば、親はそれ以上作業ができない。パーミットをクローンすれば、並行数の上限を簡単に超えてしまう。パーミットのライフサイクルを正確に合わせるのは面倒なのだ。

これは一連の失敗の中で最もRust特有のものだった。セマフォのアプローチはGoでは慣用的だ。sync.WaitGroupにセマフォチャネルを組み合わせ、sync.Mutexで状態をgoroutine間で共有するのがGolangでのやり方だ。Goにはグリーンスレッドと、goroutineのライフサイクルを管理してくれるランタイムがあるからだ。

しかしRustでは、tokio::spawnのSend + 'static境界、共有可変状態に対する借用チェッカーの嫌悪、そしてArc<RwLock<T>>のコストが邪魔をする。Rustは「とりあえず全部ArcとMutexでラップする」という逃げ道を十分に苦痛なものにし、それが行き止まりになったのだ。

2022年〜2024年 😴

2年以上にわたり、再帰のissueにはそれを望む人々からのコメントが集まり続けた。回避策を提案する人もいた（sitemapのURLをxargsでパイプするのが人気だった）。最初にissueを立てた人は自分でツールを作って去っていったが、それは完全に理解できた。

誰かが100ユーロの報奨金を提示した。他の人は、すでに再帰チェックを行うmuffetを指摘した。この間、lycheeが立ち止まっていたわけではない。パフォーマンス、キャッシュ、レート制限、その他多くの機能に多大な作業が費やされた。しかし再帰は部屋の中の象のままだった。

試行4：Gwennが挑む（2025年1月〜3月）

2024年後半、コミュニティのコントリビューターである@gwennlbhが挑戦を引き受けた。彼女の計画はチャネルベースのモデルに戻るものだったが、ひねりがあった。終了のためにチャネルを閉じようとする代わりに、Arc<AtomicUsize>カウンターを使うというものだ。試行1と同じだが、アトミックでタスク間で共有される！

そしてそれはとてもエレガントに見えた。

1. 既存の2つのmpscチャネル（リクエストとレスポンス）を維持する。
2. レスポンスを受け取った後、本文からリンクを抽出して新しいリクエストとして送信する。
3. Arc<AtomicUsize>で残りの作業を追跡する。新しいリクエスト（再帰的なものも含む）が送られたらインクリメントし、レスポンスが処理されたらデクリメントし、ゼロになったら受信ループを抜ける。
4. 既存のキャッシュに頼ってサイクルを回避する（すでに見たURLは再チェックしない）。

これはこれまでで最も機能的な試みだった。実際のウェブサイトで本当に動いたのだ。

lychee -R https://endler.dev \
       --recursed-domains endler.dev

それが形になっていくのを見るのは本当にワクワクしたし、途中で有用な設計ガイダンスを提供しようと努めた。

• デフォルトの再帰深度は5
• 厳密なドメイン一致（サブドメインはチェックしない）
• レート制限は別のPRに延期
• lychee-libの公開APIの破壊的変更は許容

どこで壊れたか

そしてそれは、複数の方向から同時に同じ壁にぶつかった。

1. チャネルのバックプレッシャーによるデッドロック

再帰で大量のリンクが発見されると、レスポンスハンドラーは新しいリクエストをリクエストチャネルに送ろうとした。しかしそのチャネルが（max_concurrencyで制限されて）満杯だと、送信がブロックする。レスポンスハンドラーがブロックすればレスポンスが処理されず、リクエストの空きも生まれない。典型的なバックプレッシャーによるデッドロックだ。

@gwennlbhは「新しいリクエストを送る」作業を別のtokio::spawnでspawnすることでこれを回避し、レスポンス処理とリクエスト送信を分離した。動くには動いたが、これらのバックグラウンドタスクがいくつ積み重なっても制限がなくなる（そして無制限にメモリを使う）ことを意味した。

2. 重複リクエスト

リクエストが並行して処理されるため、同じURLが複数のページで発見され、キャッシュされる前にチャネルに送られてしまう可能性があった。キャッシュのチェックは遅すぎた。リクエストがすでに飛んだ後だったのだ。並行する重複を止めるためのURLごとの同期がなかった。

request-to-responseタスクが並行である性質上、同じリクエストをチャネルに2回送るのを防ぐのは難しいように思える。基本的にあちこちにガードを追加してみたが、それでも重複が発生するように見える。

応急処置としてStats::insertに重複排除チェックが入ったが、それは重複したレポートを止めるだけで、重複したチェックを止めるものではなかった。本当の修正は、HostPoolのURIごとのactive_requestsミューテックスではるか後になってから到来するが、その仕組みはまだ存在しなかった。

3. またもカウンター

Arc<AtomicUsize>カウンターは、本質的には試行1と同じアイデアであり、同じ脆さをもたらした。Ordering::Relaxed（最も弱いメモリ順序）では、スレッドをまたいだインクリメントとデクリメントが並べ替えられる可能性があり、作業が実際に終わる前にカウンターが一瞬ゼロを示すことがあった。Wikipediaで--max-depth=0を指定すると、最後のURLでロックしてしまうのだった。

4. あちこちへの変更

Response型にsubsequent_uris（発見されたリンクのリスト）を追加することは、Responseを構築したり消費したりするほぼすべてのファイルに触れることを意味した。すべてのResponse::new()呼び出しで2つの新しい引数（非再帰ケースではvec![]と0）が必要になった。

5. Collectorが迂回された

レスポンスボディからリンクを抽出するために、コードはchecker内で新しいCollectorをインラインで構築し、--excludeや--include、フラグメントチェックといったユーザーフラグを尊重する設定済みのcollectorを迂回していた。

その道の終わり

2025年1月にエネルギーが爆発した後、事態は停滞した。マージのコンフリクトが積み重なった。CIのリントルールがブランチの足元で変わった。@gwennlbhはWindowsに切り替え、OpenSSL依存関係のビルドができなくなった。2025年3月、彼女は正直にこう書いた。

否定していた部分もあるけど、この作業を続けるモチベーションを失ってしまったのはかなり明らかで […] ごめんなさい T_T

僕は彼女に謝ってほしくなかった。彼女はボランティアとして、複雑な非同期コードベースで、難しい機能に誰よりも遠くまで到達したのだ。むしろ、物事を前に進めるために彼女が費やしてくれた時間に感謝している。

どれくらいがRust特有の問題だったか？半分くらいだと言えるだろう。バックプレッシャーは単に問題領域の一部だ。どの言語の並行クローラーでも出会うものだ。Ordering::Relaxedの罠はある程度Rust特有だ。Rustではメモリ順序を選ばなければならない（Goのsync/atomicもそうだが、ほとんどのGoユーザーは代わりにsync.WaitGroupに手を伸ばす）。

では、なぜこれは本当に難しいのか？

5年で4回の試み。一歩引いてみると、難しさはいくつかのカテゴリーに分類できると思う。

終了をどう知るか

すべての実装が同じ問いに直面した。いつ終わったとわかるのか？

非再帰パイプラインでは答えは簡単だ。入力ストリームが枯渇し、処理中のリクエストが完了したら終わりだ。チャネルのsenderを閉じ、receiverを空にすれば、それで完了だ。

再帰パイプラインでは、すべてのレスポンスが新しい入力を生み出す可能性があるため、入力ストリームが真に枯渇することはない。静止状態（何も進行しておらず、何も新しく生成されない状態）を検出する別の方法が必要になる。

実は、この問題は分散システムでは名前が付いている。✨ 分散終了検出だ。✨

古典的な解決策（Dijkstra–Scholtenやトークンパッシング）は、Tokioのチャネルベースの世界にはうまくマッピングされない。

サイクル

lycheeのアーキテクチャは根本的にDAGだ。入力はステージを通って一方向に流れる。再帰はサイクルを持ち込む。そしてチャネルベースのシステムではサイクルはデッドロックする。チャネルは「すべてのsenderがdropされた」を完了シグナルとして使うが、サイクルではその条件が自力では決して満たされないからだ。

バックプレッシャー

境界付きチャネルは自然なバックプレッシャーをもたらす。checkerが遅ければ、空きができるまでsenderはブロックする。これは素晴らしいのだが、再帰が欲しくなると話が変わる。今度はレスポンスハンドラーがリクエストチャネルに送信する必要が出てくる。そのチャネルが満杯なら、レスポンスハンドラーはブロックする。ブロックすればレスポンスは消費されず、レスポンスが消費されなければリクエストの空きも生まれない。

重複排除の競合

私たちはリンクを並行してチェックするため、複数のページが同じリンクを持つことがある。同期がなければ、複数のタスクが同じURLを発見し、どれかがそれを「seen」としてマークする前に送信してしまう。試行1〜4を通じてキャッシュは役に立たなかった。キャッシュエントリは送信前ではなく、チェック後に書き込まれていたからだ。

漏れのある抽象化

再帰の意識は「あちこち」に住みたがる。Responseは発見されたリンクを持ち運ぶ必要があり、Requestは深度を必要とし、collectorは再帰的な入力を理解する必要があり、統計やフォーマッターは重複を処理する必要がある。

どれくらいがRustのせいなのか？

僕のブログを読んでいる人が本当に知りたいのはこの問いだと思うので、率直に答えよう。僕の正直な見積もりでは……30%くらいだろうか。終了の問題、サイクルの問題、バックプレッシャーの問題は、どれも問題領域そのものの一部だ。GoであれPythonであれJavaであれErlangであれ、並行再帰クローラーならどれでも解決しなければならない。いずれScrapyやColly、その他の成熟したクローリングフレームワークも、分散終了検出とバックプレッシャー管理をやらなければならなかったのだ。

Rustが加えるのは、実装レベルでの摩擦だ。

• 所有権とSend境界が、spawnされたタスク間で状態を共有することを難しくする。Goではgoroutineのクロージャで変数をキャプチャして先に進める。Rustでは非同期の世界ではすべてがArcでラップされ、Send + 'staticであることが求められる。
• アトミックでの明示的なメモリ順序は、並行性の正しさについて考えさせ、同時に「まあ、relaxedでいいや」という誘惑的だが危険な選択を生む。
• Tokioのチャネル終了セマンティクスは、他のいくつかのエコシステムよりも厳格だ。Goのcontext.Contextは、Tokioのチャネルがネイティブには持っていない直交するキャンセル機構を提供してくれる。（TokioではそのためにCancellationTokenを使うことになる。）

一方で、Rustは多くの問題も防いでくれた。

• コンパイラが、可変状態を共有しようとする安全でない試みをすべて捕まえてくれた。Goなら、本番環境やせいぜいrace detectorで見つかる微妙なランタイムバグになっていただろう。
• 型システムを味方につけることで、正しいことを人間工学的にも正しいことにできる。

言い換えれば、Rustは間違ったアプローチを（コンパイラエラーなどで、テストでのデッドロックも含めて）大きく、そして痛みを伴って失敗させ、正しいアプローチをより堅牢で使いやすくしたのだ。

新たな希望

すべての失敗にもかかわらず、2025年から2026年にかけて、この問題を取り巻く土台は静かに変化した。多くの作業、しかもそのほとんどは再帰とは無関係なものが、ようやく本物の実装を手の届くところまでもたらした。

ホストごとのレート制限（2025年12月）

レート制限なしの再帰は危険だ。GwennはWikipediaを再帰的にチェックしている最中に、誤って自分のWiFiルーターをDDoSしてしまい、それを身をもって知ることになった。😬 PR #1929でマージされたホストごとのレート制限により、再帰クロールはサーバーの制限を尊重するようになる。以前は「スコープ外」として軽く考えていたが、実際には非常に重要だ。

根本的なissue（#1605）は、僕が2025年1月6日に立てたものだ。PR #1603（試行4）がオープンしたのと同じ週だった。このタイミングは偶然ではない。本気で再帰を試した瞬間、ホストごとのレート制限の欠如が明白な欠陥として浮かび上がったのだ。同じホストへの並行リクエストが429を吐く原因になり、競合により高並行下でキャッシュが効かなくなり（issue #1593）、多くのホストにまたがるワークロードに対してグローバルな並行数設定が粗すぎるという問題を引き起こした。

修正ではHostPoolが導入された。これはホストごとのリクエストキューで、レート制限、遅延、同時リクエスト数の上限を設定できる。各ホストは独自の設定を持つバケットを持ち、lychee.tomlで設定できる。

[hosts."github.com"]
max_concurrent_requests = 10
request_delay = "100ms"

HostPoolは後に中心的な抽象化となった。PR #2100が入力取得とリンクチェックを統合するために再利用したのとまさに同じHostPoolであり、現在ではすべてのHTTPリクエストが流れる単一のエントリーポイントになっている。

これが再帰にとって重要なのは、HostPoolがホストごとのレート制限、重複排除（各HostのURIごとのactive_requestsミューテックスとHostCacheによる）、そして適切な粒度でのキャッシュを提供し、再帰クロールが良きウェブ市民であり続けられるようにするからだ（レート制限ヘッダーを尊重し、429ではバックオフする）。

WaitGroup（2026年2月）

最近の動きの中で最も重要なのは、KaitによってコントリビュートされPR #2046でマージされたWaitGroupプリミティブだ。これは終了問題を解決するための一歩となる。

WaitGroupは、それ自体がさらにタスクをspawnしうる、動的なタスク集合を待つための仕組みだ。2つの要素からなる。

• WaitGroup。すべての作業が終わったときに発火する単一のwaiter。
• WaitGuard。各タスクが保持するクローン可能なガード。最後のガードがdropされたときにwaiterが完了する。

重要な点は、WaitGuardをクローンできることだ。タスクはサブタスクをspawn（再帰！）できるが、再帰的なサブタスクが保持するものを含むすべてのガードがdropされるまでWaitGroupが完了しないという不変条件を保つ。

これが終了問題をきれいに解決する。

let (waiter, guard) = WaitGroup::new();

// Each request carries a guard clone
send_req.send((guard.clone(), request)).await;

// In the response handler, if recursing:
// the guard is cloned for each new request
for new_request in discovered_links {
    send_req.send((guard.clone(), new_request)).await;
}

// The original guard is dropped when the response is fully processed.
// When ALL guards are dropped (no more work), waiter.wait() returns.

これはすでにlycheeのメインのチェックループに組み込まれている。collect_responses関数はtake_until(waiter.wait())を使って、作業が終わったら受信を停止する。現在のコードには、まさにこれを予期したコメントさえある。

// unused for now, but will be used for recursion eventually. by holding
// an extra `send_req` endpoint, we prevent the natural termination when
// each channel finishes and closes. instead, we rely on the WaitGroup to
// break the cyclic channels.
let _ = send_req;

それこそが、これまでの試みで欠けていたピースだ。

統合されたリクエスト処理（PR #2100、2026年3月にマージ）

PR #2100は、入力URLの取得をリンクチェッカーのHostPoolに統合した。これ以前は、CLIの入力URLはcheckerと設定（user-agent、レート制限、TLS設定）を共有しない別のreqwest::Clientを経由していた。それが現実のバグを引き起こしていた（user-agentが設定されていないためにWikipediaが入力URLに対して403を返していた）。

その後は、入力取得とリンクチェックが同じプールを通るようになった。再帰にとってこれが重要なのは、再帰的に発見されたページも取得して解析する必要があり、他のすべてと同じクライアント設定を使うべきだからだ。

サイトマップ対応（2026年2月）

サイトマップ対応は、多くの再帰ユースケースに対する部分的な解決策だ。sitemap.xmlを解析することで、lycheeは再帰的にクロールすることなくサイト上のすべてのページを発見できる。真の再帰の代替ではない（サイトマップのないサイトには役立たず、動的にリンクされたページも見つけられない）が、多くのユースケースのブロックを解消してくれる。

本来の再帰はどうあるべきか

これらすべてが整った上で、残っているものはこれだ。驚くべきことに、その多くはすでに完了している。

• クロールがいつ終わったかを知ることは、WaitGroupによって解決済みだ。
• 満杯のチャネルでブロックする代わりに後続の作業をspawnすることで、デッドロックは回避される。
• ホストごとのプールがすでにリクエストをペース配分するので、サーバーを叩きすぎることはない。
• lycheeはすでに見たURLをスキップする。これはすべてのページが同じナビやフッターにリンクしているときに重要だ。
• ページを取り戻すことが、残された1つの未解決問題だ。lycheeはチェック後にページを捨ててしまうが、再帰はさらにリンクを見つけるためにHTMLを必要とする。直前のチェックからまだキャッシュに残っているので、ただで再び取得できる。（リクエストメソッドがHEADではなくGETである場合。HEADはボディを返さない。）

それらが揃えば、実際の再帰はほんの数行で済む。チェックされたページが許可されたドメイン上にあり、深度制限内であれば、キャッシュからコンテンツを取得し、リンクを抽出して、同じパイプラインに新しいリクエストとして送り返すだけだ。

if recursive && is_same_domain(&response, &recursion_domains) && depth < max_depth {
    let content = resolver.url_contents(response.url()).await?;  // cache hit
    let links = extractor.extract(&content);
    for req in request::create(links, ...) {
        send_req.send((guard.clone(), Ok(req))).await;
    }
}

難しい部分（いつ止めるか、デッドロックしないこと、サーバーを洪水させないこと）は、そもそも再帰とは無関係な作業によってすでに解決されている。再帰は、そもそもそのために作られていなかったパイプラインに後付けされた特殊ケースではなく、良いアーキテクチャの副産物になるのだ。

で、僕たちは失敗したのか…？

長い間、僕は自分たちを失敗したと思い込んでいた。4回の試み、5年、表向きは何もリリースされていない。

しかしこうしてすべてを書き出してみて、見方が変わった。どの試みも、チャネルの終了セマンティクス、バックプレッシャーによるデッドロック、所有権の使い勝手、分散終了検出といった何らかの組み合わせにぶつかっていた。それらはどれもlychee特有の問題ではない。難しい並行システムの問題なのだ。僕たちにはそれらを語るための語彙が欠けていただけで、僕が見ていない間に、それらのプリミティブは作られていた。ある機能のために書く最も重要なコードは、その機能について一言も触れていないコードであることがあるのだ。

lycheeでの作業に資金を提供してくれたNLnetと、これまでの再帰への取り組みに貢献してくれたすべての人に感謝したい。コードであれ、設計へのフィードバックであれ、精神的なサポートであれ。長い道のりだったが、ゴールにはかつてなく近づいている。