재귀는 lychee에서 가장 오래 열린 채 남아 있는 이슈였습니다. 5년이 넘도록 해결되지 않은 채 그대로 남아 있습니다.

혹시 lychee를 처음 들어보신다면, lychee는 Rust로 만든 빠르고 비동기적인 링크 검사기입니다(BTW). 웹사이트나 문서, README, 마크다운 파일에 lychee를 실행하면 됩니다.

저는 2020년 집에서 심심해서 이 프로젝트를 시작했습니다. 지금은 약 4만 개의 GitHub 리포지토리가 lychee에 의존하고 있습니다. Google, AWS, Microsoft, Cloudflare를 비롯한 많은 기업이 문서의 링크를 검사하는 데 lychee를 사용합니다.

lychee에 대해 토크와 팟캐스트에서도 이야기한 적이 있으니, 더 자세히 알고 싶으시면 참고해 보시기 바랍니다.

lychee는 개방적이고 신뢰할 수 있는 인프라를 위한 NGI Zero 프로그램을 통해 NLnet의 지원을 받았습니다.

이 지원 덕분에 밤늦게 짬을 내 코딩하는 대신 프로젝트에 제대로 집중할 시간을 확보할 수 있었습니다.¹ 이제 지원이 끝나가는 시점에서 이 글을 쓰는 것이 적절하다고 느껴졌습니다.

가장 솔직하게 말씀드리자면, 가장 요청이 많았던 기능인 재귀는 아직도 출시되지 못했습니다. :,( 물론 이유는 있습니다! 한마디로 요약하면 “어렵기 때문”이지만, 좀 더 깊이 들어가 보겠습니다.

어디서 시작됐나

2020년 12월 14일, @styfle이라는 사용자가 이슈 #78을 열었습니다:

매우 합리적인 요청이었습니다! 당시 lychee는 이미 빠르고 동시성을 갖춘, 기능이 풍부한 링크 검사기였습니다. 도메인 내부의 링크를 따라가는 --recursive 플래그 하나쯤이야 하루 만에 뚝딱 만들 수 있지 않을까 싶었죠?

하지만 5년이 지나고 네 번의 본격적인 구현 시도와 여러 개의 중단된 풀 리퀘스트가 지난 지금도 재귀 기능은 여전히 머지되지 못했습니다. 이 이슈는 v1.0 마일스톤에 지정되어 있고, 그 전에 꼭 출시하고 싶습니다. 하지만 어느 순간부터 이 이슈는 lychee의 흰 고래가 되어 버렸습니다.

초기 아키텍처가 발목을 잡다

재귀를 추가하는 것이 왜 그렇게 어려운지 이해하려면, lychee가 어떤 방식으로 동작하는지부터 알아야 합니다. 2020년 말 당시의 처리 흐름은 다음과 같았습니다:

기본적으로 입력 URL부터 링크 추출, 링크 검사, 결과 출력까지 이어지는 하나의 거대한 파이프라인이었습니다.

@styfle님이 이슈를 열었을 때, 저는 핵심 문제를 거의 즉시 파악했습니다:

추출기(extractor)로 돌아가는 연결이 없습니다.

이 빠진 피드백 루프(검사된 응답에서 입력 큐로 돌아가는 연결)가 문제의 전부라고 할 수 있습니다. lychee의 파이프라인은 단방향 일회성 흐름으로 설계되었습니다. 입력이 한쪽 끝으로 들어가면 결과가 다른 쪽으로 나오고, 입력 스트림이 끝나면 프로그램도 끝납니다. 재귀에는 사이클이 필요합니다. 응답이 새로운 입력을 만들어내야 합니다. 그리고 비동기 채널 기반 파이프라인에서 사이클이야말로 용이 사는 곳입니다. 🐲

저는 이 문제를 첫날부터 알고 있었습니다. 다만 그 사이클을 잘못 구현하는 방법이 얼마나 많은지를 심각하게 과소평가했을 뿐입니다.

시도 1: 단순 카운터 (2021년 2월 - 12월)

제 첫 번째 시도는 의도적으로 규모를 작게 잡았습니다. 아키텍처를 뜯어고치고 싶지 않았습니다. 그냥 재귀가 동작하게만 하고 싶었습니다! 그래서 main.rs에 직접 처리를 추가했습니다. 아이디어는 이랬습니다:

1. 응답을 받은 뒤, 원래 입력 도메인 중 하나에서 온 것이면 그 응답에서 링크를 추출한다.
2. 그 새로운 링크들을 요청 채널로 다시 밀어 넣는다.
3. 예상되는 전체 요청 수와 완료된 요청 수를 계속 카운트한다.
4. completed == total일 때 멈춘다.

성공적인 응답에 대해 collector::collect_links()를 호출하고, 새로운 요청을 채널로 보내기 위한 태스크를 생성한 뒤, 새로 생성된 요청 수를 반환하는 recurse() 함수를 추가했습니다. 같은 URL을 두 번 검사하지 않도록 단순한 HashSet<String>을 “seen” 캐시로 사용했습니다.

여기에 더해:

• 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가 증가할 수 있습니다.
• 카운트가 하나만 어긋나도 영원히 멈추거나(카운트가 너무 높을 때) 너무 일찍 종료됩니다(카운트가 너무 낮을 때).
• 엎친 데 덮친 격으로, 캐시된 응답, 실패한 응답, 빈 페이지 등 모든 엣지 케이스가 카운팅 로직을 더 복잡하게 만들었습니다.

@pawroman님이 정말 꼼꼼한 리뷰를 남겨 주셨습니다. HashSet 캐시의 메모리 사용량 분석(수백만 개 링크까지는 괜찮음), 무한 재귀를 표현하기 위한 부호 있는 깊이 값 사용 제안, 통합 테스트 제안 등이 포함되어 있었습니다. 좋은 피드백이었습니다. 다만 정작 잘못된 부분, 즉 종료 방식 자체의 문제는 해결할 수 없었습니다.

치명타

2021년 9월, 우리는 더 큰 리팩터링을 하기로 결정했습니다. 동시성을 개선하기 위한 스트림 기반 아키텍처(PR #330)였습니다. Collector::collect_links가 Vec을 반환하던 것을 Stream을 반환하도록 바꾸고, ClientPool 추상화를 제거했으며, 태스크 간 통신 방식을 재편했습니다. 컬렉터가 지연(lazy) 방식으로 동작해 더 이상 거대한 Vec 요청을 할당하지 않아도 된다는 점에서 훌륭한 개선이었습니다. 하지만 그로 인해 재귀 브랜치는 기반이 무너지며 망가져 버렸습니다.

#330에서 스트림 기반 접근을 구현하기 시작했으므로 이 작업을 다시 보류하겠습니다. 곧 이 브랜치를 대체할 수도 있습니다. 재귀 지원이 머지되길 기다리신 모든 분께 죄송하지만, 버그 있는 솔루션을 성급하게 머지하기보다 제대로 만들고 싶습니다.

PR #165는 2021년 12월에 닫혔습니다. 스트림 리팩터링이 머지되었고 35~50%의 속도 향상을 가져왔습니다. 좋네요! 트레이드오프라고 할 수 있겠습니다.

그리고 언어에 대해 자주 질문을 받기 때문에 솔직한 얘기 하나 덧붙이자면, 여기서의 카운팅 문제는 Rust 탓이 아닙니다. 고루틴과 채널을 쓰는 Go 버전이나 Python asyncio 버전이라도 똑같은 off-by-one 버그에 부딪혔을 겁니다. “응답 처리”와 “새 요청 발견” 사이의 경쟁은 동시성을 가진 재귀 크롤러라면 본질적으로 갖는 문제입니다. Rust의 Stream 트레이트와 소유권과의 상호작용 덕분에 스트리밍 아키텍처가 자연스럽게 느껴졌고, 그 점이 작업을 무효화한 Rust 특유의 지점이라고 할 수 있습니다.

시도 2: 채널로 다시 피드백하기 (2022년 1월 - 7월)

스트림 아키텍처가 자리 잡은 뒤, 다시 한번 시도해 보았습니다. 이번에는 요청 수를 손으로 세는 대신, 발견된 URL을 컬렉터에 연결된 채널을 통해 다시 흘려보내는 방식이었습니다.

컬렉터는 입력 채널에서 읽어 들인 것을 요청 스트림으로 변환합니다. 재귀는 새로 발견된 URL을 그 채널로 보내기만 하면 됩니다. (보세요, 피드백 루프입니다!) 스트림은 채널이 닫히면 자연스럽게 종료됩니다.

하나의 메서드가 Vec나 Stream 둘 다 받을 수 있도록 입력 타입을 통합하는 시도도 해 보았습니다:

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

또 멈췄습니다. 하지만 이번에는 완전히 다른 이유 때문이었습니다.

피드백 루프가 순환 의존성을 만들었습니다:

1. 컬렉터가 입력 채널에서 읽어 요청 스트림을 생성합니다.
2. 검사기가 요청을 읽어 응답을 생성합니다.
3. 재귀 핸들러가 응답을 읽어 새로운 입력을 컬렉터 채널로 다시 보냅니다.

문제가 보이시나요?

컬렉터의 스트림이 끝나려면 입력 채널이 닫혀야 합니다. 채널이 닫히려면 모든 송신자(sender)가 드롭되어야 합니다. 하지만 재귀 핸들러는 발견된 URL을 다시 밀어 넣기 위해 송신자를 들고 있습니다. 그리고 재귀 핸들러는 더 이상 응답이 없을 때만 멈추는데, 그건 더 이상 요청이 없을 때만 일어나고, 그건 다시 컬렉터의 스트림이 끝났을 때만 일어납니다. 또 다른 순환 의존성으로 인한 데드락입니다.

당시에도 이렇게 말했습니다:

이 문제를 살펴볼 시간이 거의 없었지만, 입력 채널이 드롭되지 않아 연결이 dangling 상태로 남아서 멈추는 것 같습니다. futures::StreamExt::for_each_concurrent가 끝나면 채널이 자동으로 닫히고 드롭될 줄 알았습니다.

@untitaker님이 이를 확인했고, 아주 단순한 경우에도 데드락을 재현할 수 있었습니다:

처리할 것이 더 이상 없을 때 sender를 드롭하고 싶은 거죠? 그런데 아직 드롭하지 않았기 때문에(그리고 더 복제하려면 sender가 필요하니까) for_each_concurrent가 영원히 멈추지 않을까요? (그리고 sender가 더 필요해서 드롭할 수도 없고요)

빈 디렉터리에서 time lychee --offline -b . '**/*.htm*' -T1로도 데드락을 재현할 수 있습니다.

이것이 순환 데이터 흐름에 채널을 사용할 때의 핵심입니다. 채널은 송신자 드롭을 종료 신호로 사용하지만, 사이클에서는 각 단계가 사이클을 유지하기 위해 송신자를 들고 있어야 하므로 모든 송신자를 드롭할 수 없습니다.

이 문제를 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으로 바꾸면 채널이 무료로 제공하던 제한된 동시성을 잃게 됩니다. 세마포어가 그걸 다시 추가해 주지만, 퍼밋을 신중하게 관리해야 합니다. 태스크가 퍼밋을 획득하고 자식을 생성한 뒤 퍼밋을 넘기면, 부모는 더 이상 작업을 할 수 없습니다. 퍼밋을 복제하면 동시성 제한을 초과할 수 있습니다. 퍼밋 생명주기를 정확히 맞추는 것은 까다롭습니다.

이것이 여러 시도 중 가장 Rust 특유의 실패였습니다. 세마포어 접근법은 Go에서는 관용적입니다. sync.WaitGroup과 세마포어 채널, sync.Mutex를 통해 고루틴 간 상태를 공유하는 것이 Go에서는 그린 스레드와 고루틴 생명주기를 관리해 주는 런타임이 있기 때문에 그렇게 하는 방식입니다.

하지만 Rust에서는 tokio::spawn의 Send + 'static 바운드, 빌림 검사기가 공유 가변 상태를 꺼리는 점, 그리고 Arc<RwLock<T>>의 비용이 방해가 됩니다. Rust는 “그냥 모든 걸 Arc와 Mutex로 감싸기”라는 탈출구를 고통스러울 정도로 어렵게 만들어, 결국 막다른 골목이 되었습니다.

2022–2024 😴

2년이 넘는 동안 재귀 이슈에는 이를 원하는 사람들의 댓글이 계속 쌓였습니다. 사람들은 해결책을 제안했습니다(사이트맵 URL을 xargs로 파이프하는 것이 인기 있는 방법 중 하나였습니다). 이슈를 처음 제기한 분은 직접 도구를 만들고 떠나셨는데, 충분히 이해합니다.

누군가는 100유로 현상금을 내걸었습니다. 다른 이들은 이미 재귀 검사를 지원하는 muffet을 언급했습니다. 이 기간 동안 lychee가 멈춰 있었던 것은 아닙니다. 성능, 캐싱, 속도 제한 등 다른 기능에 많은 작업이 이루어졌습니다. 하지만 재귀는 방 안의 코끼리였습니다.

시도 4: Gwenn의 도전 (2025년 1월 - 3월)

2024년 말, 커뮤니티 기여자인 @gwennlbh님이 다시 도전장을 들었습니다. 그녀의 계획은 채널 기반 모델로 돌아가되, 종료를 위해 채널을 닫으려 하는 대신 Arc<AtomicUsize> 카운터를 사용하는 것이었습니다. 시도 1과 비슷하지만, 원자적이고 태스크 간에 공유된다는 차이가 있었습니다!

그리고 그것은 정말 우아해 보였습니다:

1. 기존의 두 mpsc 채널(요청과 응답)을 유지한다.
2. 응답을 받은 뒤 본문에서 링크를 추출해 새로운 요청으로 보낸다.
3. Arc<AtomicUsize>로 남은 작업을 추적한다 — 새로운 요청(재귀 요청 포함)을 보낼 때 증가시키고, 응답을 처리할 때 감소시키며, 0이 되면 수신 루프를 빠져나간다.
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 뮤텍스와 함께 도착했지만, 그 장치는 아직 존재하지 않았습니다.

3. 또다시 카운터

Arc<AtomicUsize> 카운터는 본질적으로 시도 1과 같은 아이디어이며, 같은 취약성을 가져왔습니다. Ordering::Relaxed(가장 약한 메모리 순서)에서는 스레드 간 증감이 재배열될 수 있어, 작업이 실제로 끝나기 전에 카운터가 잠시 0을 읽을 수 있습니다. 위키피디아에서 --max-depth=0으로 실행하면 바로 마지막 URL에서 멈췄습니다.

4. 곳곳에 퍼진 변경

Response 타입에 subsequent_uris(발견된 링크 목록)를 추가한다는 것은 Response를 생성하거나 소비하는 거의 모든 파일을 건드려야 한다는 의미였습니다. 모든 Response::new() 호출에 두 개의 새로운 인자(비재귀 경우의 vec![]와 0)가 필요했습니다.

5. 컬렉터가 우회되다

응답 본문에서 링크를 추출하기 위해 코드는 검사기 안에서 새로운 Collector를 즉석에서 생성했고, 이는 --exclude, --include, 프래그먼트 검사 같은 사용자 플래그를 존중하는 설정된 컬렉터를 우회하는 것이었습니다.

그 길의 끝

2025년 1월의 에너지 넘치는 돌진 이후, 진행은 느려졌습니다. 머지 충돌이 쌓였습니다. CI 린트 규칙이 브랜치 아래에서 바뀌었습니다. @gwennlbh님은 Windows로 옮긴 뒤 OpenSSL 의존성을 빌드하지 못했습니다. 2025년 3월, 그녀는 솔직하게 이렇게 썼습니다:

어느 정도 부정하고 있었지만, 이 작업을 계속할 의욕을 잃었다는 것이 꽤 분명해요 […] 죄송해요 T_T

저는 그녀가 사과하기를 원치 않았습니다. 그녀는 어려운 기능에 대해, 복잡한 비동기 코드베이스에서, 자원봉사자로서 누구보다 멀리 나아갔습니다. 대신, 앞으로 나아가기 위해 투자해 준 시간에 감사하고 있습니다.

얼마나 많은 문제가 Rust 특유의 것이었을까요? 절반 정도라고 하겠습니다. 배압은 단순히 문제 영역의 일부입니다. 어떤 언어의 동시성 크롤러라도 그 문제를 마주합니다. Ordering::Relaxed 함정은 다소 Rust 특유인데, Rust에서는 메모리 순서를 선택해야 하기 때문입니다(Go의 sync/atomic도 마찬가지지만, 대부분의 Go 개발자는 대신 sync.WaitGroup을 사용합니다).

그래서 왜 이게 실제로 어려운 걸까?

5년간 네 번의 시도. 한 걸음 물러서서 보면, 어려움은 몇 가지 범주로 나눌 수 있다고 생각합니다:

언제 끝났는지 알기

모든 구현은 같은 질문에 직면했습니다. 언제 끝났는지 어떻게 알 수 있을까요?

비재귀 파이프라인에서는 답이 쉽습니다. 입력 스트림이 소진되고 진행 중인 요청이 완료되면 끝입니다. 채널 송신자를 닫고, 수신자를 비우면 끝입니다.

재귀 파이프라인에서는 입력 스트림이 실제로는 절대 소진되지 않습니다. 모든 응답이 새로운 입력을 만들 수 있기 때문입니다. 정지 상태(quiescence), 즉 아무 것도 진행 중이지 않고 새로운 것이 생성되지 않을 상태를 감지하는 별도의 방법이 필요합니다.

알고 보니 이 문제는 분산 시스템에서 이름이 있습니다. 바로 ✨ 분산 종료 감지입니다. ✨

고전적인 해결책(Dijkstra–Scholten, 토큰 패싱)은 Tokio의 채널 기반 세계에 잘 맞지 않습니다.

사이클

lychee의 아키텍처는 근본적으로 DAG입니다. 입력은 스테이지를 통해 한 방향으로 흐릅니다. 재귀는 사이클을 도입합니다. 그리고 채널 기반 시스템에서 사이클은 데드락을 일으킵니다. 채널은 “모든 송신자가 드롭됨”을 완료 신호로 사용하고, 사이클에서는 그 조건이 스스로는 절대 충족되지 않기 때문입니다.

배압

제한된(bounded) 채널은 자연스러운 배압을 제공합니다. 검사기가 느리면 송신자는 공간이 생길 때까지 블로킹됩니다. 재귀를 원하기 전까지는 아주 좋습니다. 이제 응답 핸들러가 요청 채널로 보내야 합니다. 그 채널이 가득 찼다면 응답 핸들러는 블로킹되고, 블로킹되면 응답이 소비되지 않으며, 응답이 소비되지 않으면 요청 슬롯이 비지 않습니다.

중복 제거 경쟁

우리는 링크를 동시에 검사하므로, 여러 페이지가 같은 링크를 가질 수 있습니다. 동기화가 없으면 여러 태스크가 같은 URL을 발견해 그 중 하나라도 “봤음”으로 표시하기 전에 제출합니다. 시도 1~4 동안 캐시는 우리를 구해주지 못했습니다. 캐시 항목이 제출 전이 아니라 검사 후에 작성되었기 때문입니다.

누수되는 추상화

재귀 인식은 “어디에나” 존재하고 싶어 합니다. 응답은 발견된 링크를 들고 있어야 하고, 요청은 깊이를 가져야 하며, 컬렉터는 재귀 입력을 이해해야 하고, 통계와 포매터는 중복을 처리해야 합니다.

얼마나 Rust 탓일까?

제 블로그를 읽는 분들이 정말로 답을 듣고 싶어 하는 질문이 이거라고 생각해서, 직접 말씀드리겠습니다. 솔직한 추정으로는… 약 30% 정도일까요? 종료 문제, 사이클 문제, 배압 문제는 모두 문제 영역 자체의 일부입니다. Go, Python, Java, Erlang 중 어떤 언어로 작성된 동시성 재귀 크롤러라도 이를 해결해야 합니다. 어느 시점에서 Scrapy, Colly 및 다른 성숙한 크롤링 프레임워크들도 모두 분산 종료 감지와 배압 관리를 해야 했습니다.

Rust가 추가하는 것은 구현 수준에서의 마찰입니다:

• 소유권과 Send 바운드는 생성된 태스크 간에 상태를 공유하는 것을 더 어렵게 만듭니다. Go에서는 고루틴 클로저에서 변수를 캡처하고 넘어가면 됩니다. Rust에서는 비동기 영역의 모든 것이 Arc로 감싸지고 Send + 'static이어야 합니다.
• 아토믹에 대한 명시적 메모리 순서는 동시성 정확성에 대해 생각하게 만들지만, “그냥 relaxed를 쓰자”라는 유혹적이고도 위험한 선택을 하게 만들기도 합니다.
• Tokio의 채널 종료 의미론은 다른 일부 생태계보다 엄격합니다. Go의 context.Context는 Tokio 채널이 기본적으로 갖지 못하는 직교적인 취소 메커니즘을 제공합니다. (Tokio에서는 그 용도로 CancellationToken을 사용합니다.)

하지만 반면에 Rust는 많은 문제를 예방해주기도 했습니다:

• 컴파일러가 가변 상태를 공유하려는 모든 안전하지 않은 시도를 잡아냈습니다. Go에서는 그것들이 프로덕션에서 발견되거나 어쩌면 레이스 디텍터로 찾을 미묘한 런타임 버그가 되었을 겁니다.
• 타입 시스템을 우리 편으로 활용하면, 옳은 것이 더 편한 것이 되도록 만들 수 있습니다.

다르게 말하면, Rust는 잘못된 접근법이 시끄럽고 고통스럽게 실패하도록 만들었고(예: 컴파일러 오류, 테스트에서의 데드락), 올바른 접근법은 더 견고하고 인체공학적으로 만들었습니다.

새로운 희망

모든 실패한 시도에도 불구하고, 2025~2026년에 이 문제의 기반이 조용히 바뀌었습니다. 대부분 재귀와는 관련도 없는 여러 작업 덕분에 실제 구현이 마침내 손에 닿을 듯해졌습니다.

호스트별 속도 제한 (2025년 12월)

속도 제한 없는 재귀는 위험합니다. Gwenn님은 위키피디아를 재귀적으로 검사하다 실수로 자신의 WiFi 공유기를 DDoS하면서 이를 몸소 겪었습니다. 😬 PR #1929에서 머지된 호스트별 속도 제한은 재귀 크롤링이 서버 제한을 존중하도록 만듭니다. 저는 이전에 이를 “범위 밖”이라고 치부했지만, 실제로는 매우 중요합니다.

근본적인 이슈(#1605)는 제가 2025년 1월 6일에 연 것으로, PR #1603(시도 4)이 열린 바로 그 주였습니다. 그 타이밍은 우연이 아니었습니다. 재귀를 진짜로 시도하는 순간, 호스트별 속도 제한의 부재가 명백한 공백으로 드러났습니다. 같은 호스트에 대한 동시 요청이 429를 발생시키고, 경쟁 조건으로 인해 높은 동시성에서 캐시가 비효율적이 되며( #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은 스스로 더 많은 태스크를 생성할 수 있는 동적 태스크 집합을 기다리는 메커니즘입니다. 두 부분으로 이루어져 있습니다:

• WaitGroup, 모든 작업이 끝났을 때 실행되는 단일 대기자
• WaitGuard, 각 태스크가 들고 있는 복제 가능한 가드. 마지막 가드가 드롭되면 대기자가 완료됩니다.

핵심은 WaitGuard를 복제할 수 있다는 점입니다. 태스크는 재귀 하위 태스크를 생성하면서도(재귀!) 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이 검사기와 설정(유저 에이전트, 속도 제한, TLS 설정)을 공유하지 않는 별도의 reqwest::Client를 거쳤습니다. 이는 실제 버그를 일으켰습니다(유저 에이전트가 설정되지 않아 입력 URL에 대해 위키피디아가 403을 반환하는 등).

이후에는 입력 가져오기와 링크 검사가 같은 풀을 거치게 됩니다. 재귀에 있어 이는 중요한데, 재귀적으로 발견된 페이지를 가져와 파싱해야 하며, 다른 모든 것과 동일한 클라이언트 설정을 사용해야 하기 때문입니다.

사이트맵 지원 (2026년 2월)

사이트맵 지원은 많은 재귀 사용 사례에 대한 부분적인 해결책입니다. sitemap.xml을 파싱함으로써 lychee는 재귀적으로 크롤링하지 않고도 사이트의 모든 페이지를 발견할 수 있습니다. 진정한 재귀를 대체하는 것은 아니지만(사이트맵이 없는 사이트에는 도움이 되지 않고, 동적으로 링크된 페이지를 찾지 못합니다), 많은 사용 사례의 막힘을 해소해 줍니다.

제대로 된 재귀는 어떤 모습일까

이 모든 것이 갖춰진 상태에서 남은 것은 다음과 같습니다. 놀라운 점은 이미 얼마나 많은 부분이 완료되었는가입니다:

• 크롤링이 언제 끝나는지 아는 문제는 WaitGroup으로 해결되었습니다.
• 가득 찬 채널에서 블로킹하는 대신 후속 작업을 생성(spawn)함으로써 데드락을 피합니다.
• 호스트별 풀이 이미 요청 속도를 조절하므로 서버에 부하를 주지 않습니다.
• lychee는 이미 본 URL을 건너뛰므로, 모든 페이지가 같은 내비게이션과 푸터를 링크할 때 중요합니다.
• 페이지를 다시 가져오는 것이 유일하게 남은 문제입니다. lychee는 검사 후 페이지를 버리지만, 재귀는 더 많은 링크를 찾기 위해 HTML이 필요합니다. 방금 검사가 끝난 캐시에 여전히 남아 있으므로 무료로 다시 가져올 수 있습니다. (요청 메서드가 본문을 반환하지 않는 HEAD가 아니라 GET이라고 가정할 때입니다.)

이것들이 갖춰지면, 실제 재귀는 몇 줄 되지 않습니다. 검사된 페이지가 허용된 도메인에 있고 깊이 제한 안에 있다면, 캐시에서 콘텐츠를 가져와 링크를 추출한 뒤, 새로운 요청으로서 같은 파이프라인으로 다시 보내면 됩니다:

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

어려운 부분(언제 멈출지 알기, 데드락 방지, 서버에 과부하 주지 않기)은 애초에 재귀와 관련 없는 작업들로 이미 해결되었습니다. 재귀는 애초에 재귀를 위해 만들어지지 않은 파이프라인에 끼워 넣은 특수한 경우가 아니라, 좋은 아키텍처의 부산물이 됩니다.

그래서, 우리는 실패한 걸까…?

오랫동안 저는 우리가 실패했다고 스스로에게 말했습니다. 네 번의 시도, 5년, 겉보기에는 출시된 것이 아무것도 없었으니까요.

하지만 이 모든 것을 글로 정리하면서 생각이 바뀌었습니다. 모든 시도는 채널 종료 의미론, 배압 데드락, 소유권 인체공학, 분산 종료 감지 중 일부 조합에 부딪혔습니다. 그 중 어느 것도 lychee만의 문제는 아닙니다. 어려운 동시성 시스템 문제입니다. 우리는 단지 그것들에 대해 이야기할 어휘가 없었을 뿐이고, 제가 눈을 돌리고 있는 사이에 그 프리미티브들이 만들어졌습니다. 때로는 어떤 기능을 위해 작성하는 가장 중요한 코드가 그 기능을 전혀 언급하지 않는 코드일 때도 있습니다.

lychee 작업에 자금을 지원해 준 NLnet과, 코드, 설계 피드백, 정신적 지원을 포함해 수년간 재귀 기능에 기여해 주신 모든 분께 감사드립니다. 긴 여정이었지만, 어느 때보다 결승선에 가까워졌습니다.