lychee 저자가 muffet·LinkChecker·linkinator·broken-link-checker 소스를 읽고 내린 결론은 비밀 소스가 없다는 것이다.

Every recursive checker is a worklist plus a visited set plus a quiescence detector.

• frontier — 발견된 URL 이 다시 들어가는 가변 작업 큐. 고정 입력 스트림이 아니다.
• visited set — enqueue 시점에 갱신되는 중복 방지 집합.
• quiescence detector — “이제 다 끝났나”에 답하는 종료 감지자.

그래서 “언어마다 어떻게 구현하나”는 **“각 런타임이 이 셋 중 무엇을 대신 처리하고 무엇을 개발자에게 청구하나”**로 환원된다. 알고리즘은 상수고, 변하는 건 세금이 앉는 위치뿐이다.

	종료 감지	dedup 동기화	대가로 내는 것
Node (이벤트 루프)	공짜 (onIdle·drain)	공짜 (락이 없다)	처리량 — 파싱이 단일 코어를 막고 결과가 인메모리로 팽창
Go (goroutine)	공짜 (WaitGroup)	mutex (직접)	무거운 런타임(GC·스케줄러), unbounded goroutine → RAM
Python (스레드)	직접 (condition var)	직접 (센티넬)	GIL·스레드 천장 → 처리량 최저, unbounded 큐 → RAM
Rust (Tokio)	직접 조립	mutex + borrow checker	Send + 'static 마찰. 대신 레이스가 컴파일조차 안 된다

진짜 갈림길은 첫 커밋에 있다

응답이 새 입력을 만드는 사이클(back-edge)이 크롤러고, inputs → extract → check → output 은 DAG 다. 나머지 넷은 첫 커밋부터 크롤러 모양이었고 lychee 만 스트림으로 시작했다 — 그 차이가 “Five years and four attempts later” 다.

크롤러:  frontier → worker pool → fetch/parse ─┐
             ↑────────── new links ────────────┘   (사이클)

lychee:  inputs → extractor → checker → results     (DAG, back-edge 없음)

파이프라인에 사이클을 나중에 우겨넣는 건 처음부터 사이클을 갖는 것보다 압도적으로 어렵다. 대신 lychee 가 얻은 건 비재귀 경로의 속도다 — 재귀가 1급 요구사항이 아니면 DAG 가 틀린 선택이 아니다. 언어가 아니라 아키텍처 결정이라는 게 요점이다.

종료 감지 — 불변식은 하나뿐

큐가 비어도 in-flight 워커가 새 링크를 밀어넣을 수 있으므로 “큐가 비면 종료”는 틀렸다. 지켜야 하는 건 하나다.

일이 남아 있는 동안 카운터가 순간적으로라도 0 을 읽는 창이 있으면 안 된다.

그래서 자식을 부모가 done 처리되기 전에 카운트하고, bootstrap 에서 최소 1 을 올려둔 뒤 wait 에 진입한다. lychee 의 Attempt 1·4 가 이 불변식을 손으로 지키지 못해 실패했다.

// Go: bootstrap 에서 addPage 1회 → 카운터가 양수인 채로 Wait 진입
func (m daemonManager) Run() {
    go func() { for f := range m.daemons { go f() } }()
    m.waitGroup.Wait() // 카운터 0 → 종료
}

# Python: increment(_put)와 decrement(task_done)가 둘 다 Condition 락 안에 있고,
# task_done 은 자식 enqueue 를 끝낸 뒤에만 불린다 → 이른 0 이 없다
def task_done(self, url_data):
    with self.all_tasks_done:
        self.unfinished_tasks -= 1
        if self.unfinished_tasks <= 0:
            self.all_tasks_done.notify_all()

Node 는 단일 스레드라 카운터 락이 아예 필요 없고 await queue.onIdle() 한 줄이다. Rust 는 2026 에 기여된 WaitGroup 으로 같은 자리에 도달했다 — 같은 아이디어가 런타임마다 다른 옷을 입었을 뿐이다.

중복 제거는 요청 이전, enqueue 시점

두 페이지가 같은 링크를 동시에 발견하면 둘 다 제출된다. 그래서 visited 표시는 enqueue 와 atomic 해야 하고 네트워크 요청보다 먼저여야 한다. 요청을 보낸 뒤에 캐시에 쓰면 그 사이에 중복 제출 창이 열린다 — lychee 가 네 번의 시도 내내 저지른 dedup 레이스의 본체다.

# Python: 요청 이전에 None 센티넬로 URL 을 선점한다
def _put(self, url_data):
    key = url_data.cache_url
    if cache.has_result(key): return    # 이미 큐잉·체크됨
    self.queue.append(url_data)
    self.unfinished_tasks += 1
    cache.add_result(key, None)         # "내 거" 표시. 이후 동시 발견은 no-op

// Node: 세 문장이 통째로 중단 없이 실행된다
const inCache = options.cache.has(url.href)
if (!inCache) {
  options.cache.add(url.href)                 // mark
  options.pendingChecks.set(url.href, checkPromise)
  options.queue.add(() => checkPromise)       // enqueue
}

Node 에서 이게 세 줄로 끝나는 건 설계 실력이 아니라 언어 기능이다. Go·Python 은 mutex 를, Rust 는 mutex 와 borrow checker 협상을 지불한다 — 저자가 “the ~30% ‘Rust tax’ I estimated last time: not the algorithm, but the friction of expressing shared mutable frontier state under Send + 'static” 이라고 부르는 것이 그 값이다.

frontier 와 rate limiter 를 겸하면 데드락

“다음에 뭘 할까”와 “얼마나 빨리 갈까”를 하나의 bounded channel 로 겸하면, 채널이 차는 순간 producer(응답 핸들러)가 블로킹되고 → 응답이 drain 되지 않고 → 슬롯이 안 비워져 영구 정지한다. LinkChecker 의 첫 설계 주석이 이걸 명시적으로 피해 간다.

# Note: don't put a maximum size on the queue since it would
# lead to deadlocks when all worker threads called put().

이 분리는 다섯 구현이 전부 지킨다 — 안 지키면 언어와 무관하게 데드락이다. 대신 unbounded frontier 는 데드락을 메모리 증가와 맞바꾼 것이라, 거대 사이트에서는 URL 상한과 주기적 정리로 완화한다(muffet 도 unbounded goroutine + 인메모리 set 이라 결국 RAM 에 묶인다). 디스크 백드 frontier 를 가진 구현은 이 다섯에 없다.

재귀하려면 body 가 있어야 한다

링크 유효성만 보면 HEAD 가 싸지만, 재귀는 더 많은 링크를 찾기 위해 응답 본문이 필요하다. linkinator 는 크롤할 때 항상 GET 을 쓰는 쪽으로 단순하게 풀었다.

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

lychee 의 계획은 check 단계에서 이미 받은 body 를 캐시에 들고 있다가 재귀 때 재사용하는 것이다 — 같은 제약을 중복 요청 없이 푼다.