再帰（recursion）はlycheeで最も長く開いたままになっている課題です。5年以上、未解決のまま放置されています。

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

私は2020年、家で退屈したのがきっかけで開発を始めました。今では約4万のGitHubリポジトリがlycheeに依存しています。GoogleやAWS、Microsoft、Cloudflareをはじめ、多くの企業がドキュメントのリンクチェックに使っています。

lycheeについてはトークやポッドキャストでも話していますので、詳しく知りたい方はぜひご覧ください。

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

この支援のおかげで、夜中にこっそりコードを書くのではなく、腰を据えてプロジェクトに取り組むことができました。¹ その支援もそろそろ終了を迎えるため、今この記事を書くのにちょうど良いタイミングだと感じています。

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

始まり

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

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

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

初期アーキテクチャが足かせになった

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

基本的には、入力URLからリンク抽出、リンクチェック、出力整形へと続く一本のパイプラインです。

@styfleさんがissueを立てたとき、私はすぐに核心的な問題に気づきました。

extractorへ戻る経路がありません。

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

このことは初日から分かっていました。ただ、循環を誤る方法がどれだけたくさんあるかを、私はひどく過小評価していました。

挑戦その1：シンプルなカウンター（2021年2月〜12月）

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

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

成功したレスポンスに対してcollector::collect_links()を呼び出し、新しいリクエストをチャネルに送るタスクを起動し、作成したリクエスト数を返すrecurse()関数を追加しました。同じURLを二重にチェックしないように、シンプルなHashSet<String>を「確認済み」キャッシュとして使いました。

さらに次のようなものも追加しました。

• 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は増えます。ここまでは順調です。しかし抽出、送信、受信はすべて異なるタスクで並行して行われるため、カウントがずれてしまうのです。

当時から私自身、この実装には満足していませんでした。

正直、今の実装にはあまり満足していません。キュー内のリンク数を数えて、すべてのリンクがチェックされたらチャネルを閉じるというやり方なのですが、微妙なバグを招きそうな気がします。もっと良い方法があるはずです。

そう、過去のMatthiasよ、そのカウンターが脆い理由はこうです。

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

@pawromanさんが非常に丁寧なレビューをしてくれました。HashSetキャッシュのメモリ使用量の精密な分析（数百万リンクまでは問題なし）、無限再帰を表すために符号付きの深さの値を使う提案、統合テストを促す助言などです。素晴らしいフィードバックでした。ただ、根本的に間違っていた終了判定のアプローチそのものは直せませんでした。

とどめの一撃

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

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

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

そして言語についての率直な余談ですが、よく聞かれるので触れておきます。ここでのカウント問題はRustのせいではありません。Goのgoroutineとチャネルで書いても、Pythonのasyncioで書いても、同じオフバイワンのバグにぶつかります。「レスポンス処理」と「新規リクエスト発見」の間の競合は、並行する再帰クローラならどれでも本質的に抱えるものです。RustのStreamトレイトと所有権との相性の良さが、ストリーミングアーキテクチャを自然なものにし、結果としてこの作業を無効にしてしまったのです。そこはRust特有の点かもしれません。

挑戦その2：チャネルでフィードバックする（2022年1月〜7月）

ストリームアーキテクチャが整ったので、再び挑戦することにしました。今度は手作業でリクエストを数えるのではなく、見つかったURLをcollectorに接続されたチャネル経由でフィードバックする方法を試しました。

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

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

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

またハングしました。しかし今度は全く別の理由でした。

フィードバックループが循環依存を生んでしまったのです。

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

問題が分かりますか？

collectorのストリームを終了させるには、入力チャネルを閉じる必要があります。チャネルを閉じるには、すべてのsenderをドロップしなければなりません。しかし再帰ハンドラはsenderを保持しています。見つかったURLを送り返すためにそれが必要だからです。そして再帰ハンドラは、レスポンスがなくなったときにだけ停止しますが、それはリクエストがなくなったときにだけ起こり、リクエストがなくなるのはcollectorのストリームが終了したときにだけ起こります。循環依存によるデッドロックです。

当時も私はそう書いていました。

まだこの問題を深く調べる時間はあまりありませんでしたが、入力チャネルがドロップされないためにハングしています。チャネルはfutures::StreamExt::for_each_concurrentが終われば自動的に閉じられてドロップされると思っていました。

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

処理すべきものがなくなったらsenderをドロップしたいんですよね？でも、まだそれをやっていないからfor_each_concurrentが永遠にハングしませんか？（そして、より多くクローンするためにsenderが必要なので、ドロップできない）

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

これがチャネルを循環データフローに使うことの核心です。チャネルはsenderのドロップを終了シグナルとして使いますが、循環の中では各ステージが循環を維持するためにsenderを保持し続ける必要があるため、すべてのsenderをドロップすることは決してできないのです。

この問題をTokioのDiscordで相談したところ、返ってきたアドバイスは「チャネルを使うのをやめて、tokio::spawnとセマフォを使いなさい」でした。

性能問題も

デッドロックを脇に置いても、もう一つ問題がありました。新しいfrom_chanメソッドは、既存のfromメソッドより約30%遅いというベンチマーク結果が出たのです。余計なチャネルの間接化にコストがかかり、しかもそれは再帰を使わない場合でも発生します。つまり、ほぼすべてのユーザーが使うケースでコストがかかるのです。

チャネルによる循環のデッドロックは、チャネルベースのシステムならどれでも本質的に起こり得ます。Goのチャネルでも同じ問題が起きます。チャネルを閉じるには誰ももう送信しないことを知る必要がありますが、循環があるとそれが不可能になります。Erlang/OTPはチャネルのセマンティクスの代わりにプロセス監視を使うことでこれを回避しています。30%の性能低下については、Rust特有の事情があります。Rustのゼロコスト抽象化の文化では、使っていない機能のコストは払わなくてよいと期待されます（私も含めて）。ランタイムが重い言語なら、使わないパスでの30%の低下は見逃されるかもしれません。しかしRustでは「使わないものにはコストを払わない」はほとんど道徳的な原則であり、その低下が採用を見送る決定的な理由になりました。

挑戦その3：セマフォ（2022年2月）

試したこと

再帰ループでのチャネル利用を完全にやめ、代わりに次のものを使いました。

• 並行数を制限するためのArc<Semaphore>（チャネルが本来持つバックプレッシャーの代わり）
• 各処理単位に対するtokio::spawn（for_each_concurrentの代わり）
• 各タスクに渡すOwnedSemaphorePermit。再帰的なサブタスクを起動する際に処理を「譲渡」できるようにするため

プロトタイプ自体は、正直かなりすっきりしていました。

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

しかし、問題が何だったかはお分かりでしょう。やはりロックしてしまったのです。

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

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

セマフォは並行数制限の問題を解決します。しかし終了判定の問題には何もしてくれません。tokio::spawnでは、再帰的に起動されたものも含めて、すべてのタスクが完了したことを知る組み込みの方法がありません。別の調整メカニズムが必要になります。つまり、逃れたかったはずの挑戦その1のカウンターを、今度は無限に増えうるタスク群に分散させて再発明することになるのです。振り出しに戻ってしまいました。

パーミットにも微妙な問題があります。for_each_concurrentを素のtokio::spawnに置き換えると、チャネルが無償で提供してくれていた bounded な並行性が失われます。セマフォでそれを補えますが、パーミットを慎重に管理しなければなりません。タスクがパーミットを取得して子を起動し、パーミットを譲渡すれば、親はそれ以上作業できません。パーミットをクローンすれば、並行数の上限を簡単に超えてしまいます。パーミットのライフサイクルを正確に合わせるのは厄介です。

これは最もRust特有の失敗でした。セマフォによるアプローチはGoでは定石です。sync.WaitGroupにセマフォ用のチャネルを組み合わせ、sync.Mutexで状態をgoroutine間で共有するのが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で起動することで、レスポンス処理とリクエスト送信を分離して回避しました。動作はしましたが、そうしたバックグラウンドタスクがいくつでも積み上がる可能性があり、メモリ使用量が無制限になることを意味していました。

2. リクエストの重複

リクエストが並行して処理されるため、同じURLが複数のページで見つかり、キャッシュされる前にチャネルに送られてしまうことがありました。キャッシュのチェックが遅すぎたのです。リクエストがすでに送信された後でした。並行する重複を防ぐためのURLごとの同期がなかったのです。

リクエストからレスポンスへのタスクが並行して動く性質上、同じリクエストをチャネルに二重に送るのを防ぐのは難しいようです。あらゆる場所にガードを追加してみたのですが、それでも重複が発生してしまいます。

応急処置としてStats::insertに重複排除チェックが入りましたが、これは重複した報告を止めるだけで、重複したチェックを止めるものではありませんでした。本当の修正は、ずっと後にHostPoolのURIごとのactive_requests mutexができてからもたらされましたが、その仕組みはまだ存在しませんでした。

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を空にすれば完了です。

再帰的なパイプラインでは、入力ストリームが真に尽きることはありません。なぜならすべてのレスポンスが新しい入力を生み出すかもしれないからです。別の方法で静止状態を検出する必要があります。何も進行しておらず、これ以上何も生成されない状態です。

実は、この問題には分散システムの分野で名前が付いています。✨分散終了検出（distributed termination detection）✨です。

古典的な解決策（Dijkstra–Scholtenやトークンパッシング）は、Tokioのチャネルベースの世界にはうまく当てはまりません。

循環

lycheeのアーキテクチャは根本的にDAG（有向非循環グラフ）です。入力は一方向にステージを流れていきます。再帰は循環を持ち込みます。そしてチャネルベースのシステムにおける循環はデッドロックします。チャネルは「すべてのsenderがドロップされた」ことを完了シグナルとして使うため、循環の中ではその条件が自然に満たされることは決してないからです。

バックプレッシャー

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

重複排除の競合

私たちはリンクを並行してチェックするため、複数のページが同じリンクを持っていることがあります。同期がなければ、複数のタスクが同じURLを発見し、どれかが「確認済み」とマークする前に送信してしまいます。挑戦1から4まで、キャッシュは役に立ちませんでした。キャッシュへの書き込みがチェックの後であり、送信の前ではなかったからです。

漏れ出す抽象化

再帰への対応は「あちこち」に及ぶ必要があります。レスポンスは発見されたリンクを保持しなければならず、リクエストは深さを必要とし、collectorは再帰的な入力を理解しなければならず、統計やフォーマッタは重複を処理しなければなりません。

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

このブログを読んでいる方が本当に知りたいのはこのことだと思うので、率直にお答えします。私の正直な見積もりでは……30%くらいでしょうか。終了判定の問題、循環の問題、バックプレッシャーの問題は、すべて問題領域に本来含まれるものです。GoでもPythonでもJavaでもErlangでも、並行な再帰クローラならどれでも解決しなければなりません。ScrapyもCollyも、その他の成熟したクローリングフレームワークも、いつかは分散終了検出とバックプレッシャー管理に取り組まなければなりませんでした。

Rustがもたらすのは実装レベルでの摩擦です。

• 所有権とSend境界により、起動したタスク間で状態を共有するのが難しくなります。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を再帰的にチェックしている最中に、誤って自宅のWi-FiルーターにDoS攻撃をしかけてしまったことで、それを身をもって知りました。😬 ホストごとのレート制限はPR #1929でマージされ、再帰的なクロールがサーバーの制限を守るようにします。私は以前これを「スコープ外」として軽視していましたが、実際には極めて重要です。

根本的な課題（#1605）は、2025年1月6日に私が立てたもので、PR #1603（挑戦その4）が開かれたのと同じ週でした。このタイミングは偶然ではありません。本気で再帰を試した途端、ホストごとのレート制限の欠如が glaring な欠陥として浮かび上がったのです。同じホストへの並行リクエストが429を返し、高い並行性の下では競合によりキャッシュが効かなくなり（issue #1593）、グローバルな並行数設定が多数のホストにまたがるワークロードには粗すぎたのです。

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

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

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

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

WaitGroup（2026年2月）

最近の取り組みで最も重要なのは、Kaitさんが貢献しPR #2046でマージされたWaitGroupプリミティブです。これは終了判定問題を解決するための一歩です。

WaitGroupは、自身がさらにタスクを生成しうるような、動的なタスク集合を待ち合わせるための仕組みです。2つの要素から成ります。

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

肝心なのは、WaitGuardをクローンできることです。タスクはサブタスク（つまり再帰！）を起動しながら、再帰的なサブタスクが保持するものも含めてすべてのガードがドロップされたときにだけWaitGroupが完了するという不変条件を保てます。

これにより終了判定の問題はきれいに解決します。

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

// 各リクエストはガードのクローンを保持する
send_req.send((guard.clone(), request)).await;

// レスポンスハンドラで、再帰する場合:
// ガードは新しい各リクエストのためにクローンされる
for new_request in discovered_links {
    send_req.send((guard.clone(), new_request)).await;
}

// 元のガードはレスポンスの処理が完全に終わったときにドロップされる。
// すべてのガードがドロップされたとき（作業がなくなったとき）、waiter.wait()が返る。

これはすでに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とは設定（ユーザーエージェント、レート制限、TLS設定）を共有しない別のreqwest::Clientを経由していました。これが実際のバグを引き起こしていました（ユーザーエージェントが設定されていないため、入力URLでWikipediaが403を返すなど）。

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

Sitemapサポート（2026年2月）

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

あるべき再帰はどう見えるか

それらを踏まえると、残りは次のとおりです。印象的なのは、そのほとんどがすでに完了していることです。

• クロールがいつ終わるかはWaitGroupで解決済みです。
• 満杯のチャネルでブロックするのではなく後続の処理をspawnすることで、デッドロックは回避できます。
• ホストごとのpoolがすでにリクエストを適切にペース配分するので、サーバーを叩きすぎることもありません。
• lycheeはすでに見たURLをスキップするので、すべてのページが同じナビゲーションとフッターにリンクしていても問題ありません。
• ページの中身を取得することが、唯一残された課題です。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、そして長年にわたりコード、設計のフィードバック、精神的な支えなど、さまざまな形で再帰の取り組みに貢献してくれたすべての方に感謝します。長い道のりでしたが、ゴールはかつてないほど近づいています。