Five Years of Trying to Add Recursion to lychee を公開したあと、至極もっともな質問が寄せられた。

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

これをきっかけに、私は他のリンクチェッカーのコードを読み漁るという沼にはまっていった。最大の教訓はこうだ。彼らが私たちが見落としていた巧妙なトリックを見つけていたわけではない。彼らは最初のコミットからクローラーとして作られていたのに対し、私は当初 lychee をストリームとして作っていたのだ。

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

もし前回の記事を読んでいない人向けに要約すると、lychee はワンショットで一方向のパイプライン（inputs → extract → check → output）として設計されていた。再帰にはサイクルが必要になる（レスポンスが新たな入力を生む）。そして非同期でチャネルベースのパイプラインにおけるサイクルこそ、魔物が潜む場所なのだ。🐲 5年と4回の挑戦を経て、適切に実現するために必要なピースがようやく揃ったところだ。

DAG vs. サイクル

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

1. 可変の作業キュー（ここでは「フロンティア」と呼ぶ）、固定の入力ストリームではない。発見された URL は、やって来たのと同じキューに戻される。
2. エンキュー時に（リクエストが完了する前に）更新される visited セット。2つのページが同じリンクを発見しても、両方が登録してしまうことがない。
3. 「すべて終わったか？」に答えるプリミティブ。WaitGroup、合流可能なキューカウンター、onIdle() プロミス、あるいはキュー空状態のイベント。

図で表すと、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]

visited のチェックはエンキューのステップで、マークとアトミックに行われ、ワーカーがネットワークに触れる前に実行されることに注目してほしい。この順序こそが、lychee の1〜4回目の試みを悩ませた重複排除のレースを根本的に修正するものだ。あのときはキャッシュへの書き込みがチェックの後に行われていた。

各ツールはそのバリエーションを使っている。

muffet（Go）：WaitGroup と Set

muffet は精神的に lychee に最も近い。高速で単一バイナリの並行ウェブサイトチェッカーだ。重複排除とスケジューリングの判断は1つのメソッドに集約されている（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) が呼ばれるのは、カウントをゼロより上に保っている実行中のデーモンの中からか、あるいはブートストラップ時だけだ。まだ処理すべき仕事があるのにカウンターが一瞬ゼロになる、という窓が存在しない。Go の WaitGroup はこの不変条件をあまりにも自然に強制するので、分散終了検出とはまったく感じられないが、それこそが正体だ。これは2026年に Kait が lychee にコントリビュートした WaitGroup プリミティブと道徳的に同等のものだ。

トレードオフはどこにあるか

• 並行数は daemon manager では制限されない。Run() はタスクごとに go f() で際限なく goroutine を生成する。実際の制限は下流の semaphore（バッファ付きチャネルによるカウントセマフォ）とホストごとのスロットラープールで行われる。muffet は「フロンティア」と「レートリミッター」を分離している。これは lychee が過去に1つの有界チャネルに両方の役割を持たせようとして欠いていた分離だ。
• 安価な goroutine が多くの仕事を肩代わりしている。リンクごとに goroutine を生成するのは Go では「問題ない」。Rust で同等のこと（リンクごとに tokio::spawn し、それぞれが Send + 'static な状態を要求される）をやろうとすると、Arc<RwLock<…>> に向かわせ、書いたような所有権の苦しみを招いた。
• 拡張性については、muffet はライブラリではなく集中した CLI だ。プラグイン機構はなく、フラグで得られるものがすべてだ。lychee はあえて再利用可能なクレートとして lychee-lib を提供しており、その分ハードルは上がる。あらゆるアーキテクチャ上の選択が公開 API の水準を満たさなければならないからだ。
• スケーラビリティについては、際限のない goroutine とインメモリの visited セットで大規模なサイトまでは快適にスケールするが、ディスク backed なフロンティアはないので、本当に巨大なクロールは 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のバックプレッシャーによるデッドロックそのものであり、設計段階で対処されている。lychee は発見した URL を有界チャネルに push しようとした。チャネルが埋まるとレスポンスハンドラーがブロックし、レスポンスが排出されず、スロットも空かない。デッドロックだ。💥

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 にもない恩恵を受けている。シングルスレッドのイベントループだ。visited セットへのチェックと挿入は、2つのコールバックが同時に実行されることがないため、無料でアトミックになる。

フロンティアは並行数を制限した Queue（p-queue 風の構造）だ。終了判定は check() の中の1行だ（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() と同じ発想だが、プロミスとして表現され、シングルスレッドランタイムに支えられているため、visited セットを守る 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つの文だ。これが、再帰が Node で Rust より簡単である最大の理由だ。単なる言語機能の違いなのだ。

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

HEAD vs GET

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

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

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

トレードオフはどこにあるか

• シングルスレッドは恵みであると同時に上限でもある。データレースはなく、重複排除は自明に正しいが、HTML の解析は1つのイベントループをブロックする 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() もない。キューの drain イベントに乗っかる。ページレベルのキューが空になると 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 コールバックこそが実際にサイトキューにスロットを解放して別のサイトを開始させるものだ。つまり1つのサイトの終了が別のサイトの開始を可能にし、クロール全体の終了がプロセスの終了を可能にする。ページキューからサイトキュー、そしてプロセスへと伝播するイベントのカスケードなのだ。

トレードオフはどこにあるか

• この中では最も行儀の良いウェブ市民だ。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）を見てほしい。どちらも同じアプローチを取っている。プラガブルで必要に応じてディスク backed にもできるキューを持つスケジューラー（フロンティア）、重複フィルター（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（セット＋セマフォ）、LinkChecker（無制限キュー＋スレッド数）、linkinator（p-queue＋delayCache）、BLC（リクエストキュー＋maxSockets）はいずれも「次に何をやるか」と「どれくらいの速さで進むか」を分離している。lychee の初期の試みでは、1つの有界チャネルに両方の役割を持たせようとし、有界チャネルを通るサイクルはデッドロックする。修正策（lychee の HostPool と無制限の作業ソースに対する WaitGroup）は、まさに今目指しているのと同じ分離だ。

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

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

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

だから「他のリンクチェッカーは再帰をどうやっているの？」と聞かれたら、本当の答えはこうだ。彼らはそれを最初からアーキテクチャの一部にし、（WaitGroup や合流可能キュー、アイドルプロミスのような）「分散終了検出」を解かずに終了を解決してくれるランタイムに乗っかったのだ。

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