재귀는 lychee에서 가장 오래된 미해결 이슈였다. 5년이 넘도록 풀리지 않은 채 그대로 남아 있다.

lychee를 처음 들어봤다면, Rust로 만든 빠르고 비동기적인 링크 검사기라고 보면 된다. 웹사이트나 문서, README, 마크다운 파일을 지정해주면 된다.

2020년 집에서 심심해서 시작한 프로젝트인데, 이제는 약 4만 개의 GitHub 리포지토리가 여기에 의존하고 있다. Google, AWS, Microsoft, Cloudflare 등 많은 곳에서 문서의 링크를 검사하는 데 쓰고 있다.

더 알고 싶다면 관련 강연과 팟캐스트도 참고하면 된다.

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

그 지원 덕분에 밤늦게 틈틈이 코딩하는 대신 프로젝트에 제대로 집중할 시간을 가질 수 있었다.¹ 이제 그 지원이 끝나가는 시점이라 이 글을 쓰기에 적절한 때라고 느껴졌다.

솔직히 말하자면, 가장 요청이 많았던 기능인 재귀는 아직도 출시되지 않았다. :,( 물론 타당한 이유가 있다! 한마디로 “어렵기 때문”이지만, 좀 더 깊이 들어가 보자.

어디서 시작됐나

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

아주 합리적인 요청이었다! 당시 lychee는 이미 빠르고 동시성을 갖춘, 기능도 많은 링크 검사기였다. 도메인 안에서 링크를 따라가는 --recursive 플래그 하나쯤이야 하루 정도면 충분히 붙일 수 있지 않을까?

하지만 5년과 네 번의 본격적인 구현 시도, 여러 개의 버려진 풀 리퀘스트가 지나도록 재귀는 여전히 머지되지 못했다. 이 이슈는 v1.0 마일스톤으로 지정되어 있고 그 전에 출시하고 싶은 마음은 여전히 있다. 하지만 어느 순간부터 재귀는 lychee의 백경이 되어버렸다.

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

재귀 추가가 왜 그렇게 어려운지 이해하려면 lychee가 어떻게 동작하는지부터 알아야 한다. 다음은 2020년 말 당시의 처리 흐름이다:

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

@styfle이 이슈를 열었을 때, 나는 거의 즉시 핵심 문제를 짚었다:

추출기로 돌아가는 연결이 없다.

이 빠진 피드백 루프(검사된 응답에서 입력 큐로 돌아가는 연결)가 문제의 전부라고 해도 과언이 아니다. 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가 늘어난다. 여기까진 괜찮다. 하지만 추출, 전송, 수신이 서로 다른 태스크에서 동시에 일어나기 때문에 카운트가 어긋날 수 있다.

당시에도 나는 이 구현이 마음에 들지 않았다:

솔직히 말하면 큐에 있는 링크 수를 세고 모든 링크 검사가 끝나면 채널을 닫는 현재 구현이 더 이상 별로 마음에 들지 않는다. 미묘한 버그를 일으킬 수 있을 것 같다. 더 나은 방법이 있을 것이다.

그래, 과거의 마티아스여, 카운터가 취약한 이유는 이렇다:

• 새로운 링크는 비동기적으로 발견되므로, 루프가 이미 종료하기로 결정한 뒤에 total_requests가 증가할 수 있다.
• 카운트가 하나만 어긋나도 영원히 멈추거나(카운트가 너무 높으면) 너무 일찍 종료된다(카운트가 너무 낮으면).
• 엎친 데 덮친 격으로 모든 엣지 케이스가 카운팅 로직을 더 복잡하게 만들었다. 캐시된 응답, 실패한 응답, 빈 페이지 등등…

@pawroman이 정말 꼼꼼한 리뷰를 남겨줬다. HashSet 캐시의 메모리 사용량에 대한 세심한 분석(수백만 개 링크까지는 괜찮다), 무한 재귀를 표현하기 위해 부호 있는 depth 값을 쓰자는 제안, 통합 테스트를 추가하자는 조언 등이 포함됐다. 좋은 피드백이었다. 다만 정말 잘못된 부분, 즉 종료를 다루는 접근 방식 자체는 고칠 수 없었다.

결정타

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가 drop돼야 한다. 하지만 재귀 핸들러는 발견된 URL을 다시 넣기 위해 sender를 들고 있다. 그리고 재귀 핸들러는 더 이상 응답이 없을 때만 멈추는데, 그건 더 이상 요청이 없을 때만 일어나고, 그건 컬렉터의 스트림이 끝났을 때만 일어난다. 또 다른 순환 의존성으로 인한 데드락이다.

나는 당시 이렇게 말했다:

지금까지 이 이슈를 볼 시간이 거의 없었지만, 입력 채널이 drop되지 않아 연결이 dangling 상태로 남아서 멈춘다. futures::StreamExt::for_each_concurrent가 끝나면 채널이 자동으로 닫히고 drop될 거라고 생각했다.

@untitaker가 이를 확인했고 사소한 경우에도 데드락을 재현할 수 있었다:

처리할 게 더 이상 없을 때 sender를 drop하려는 거지? 그런데 아직 drop하지 않았으니 for_each_concurrent가 영원히 멈추지 않을까? (그리고 더 복제하려면 sender가 필요하니 drop할 수도 없고)

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

이게 순환 데이터 흐름에 채널을 쓸 때의 핵심이다. 채널은 sender가 drop되는 것을 종료 신호로 사용하지만, 순환에서는 각 단계가 순환을 유지하기 위해 sender를 들고 있어야 하므로 절대 모든 sender를 drop할 수 없다.

이 문제를 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로 고루틴 간에 상태를 공유하는 것이 Golang에서 그렇게 하는 방식이다. 그린 스레드와 고루틴 생명주기를 관리해주는 런타임이 있기 때문이다.

하지만 Rust에서는 tokio::spawn의 Send + 'static 경계, 공유 가변 상태에 대한 빌림 검사기의 거부감, Arc<RwLock<T>>의 비용이 발목을 잡는다. Rust는 “그냥 전부 Arc와 Mutex로 감싸면 된다”는 탈출구를 충분히 고통스럽게 만들어서 결국 막다른 골목이 되게 했다.

2022–2024 😴

2년이 넘는 기간 동안 재귀 이슈에는 이를 원하는 사람들의 댓글이 계속 쌓였다. 사람들은 대안을 제안했다(sitemap 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을 읽을 수 있었다. Wikipedia에서 --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년간 네 번의 시도. 한 걸음 물러서서 보면, 어려움은 몇 가지 범주로 묶을 수 있다고 생각한다:

언제 끝났는지 알기

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

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

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

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

고전적인 해결책들(Dijkstra–Scholten, token passing)은 Tokio의 채널 기반 세계와는 잘 맞지 않는다.

순환

lychee의 아키텍처는 근본적으로 DAG다. 입력은 단계들을 한 방향으로 흐른다. 재귀는 순환을 도입한다. 그리고 채널 기반 시스템에서 순환은 데드락을 일으킨다. 채널이 “모든 sender가 drop됨”을 완료 신호로 쓰는데, 순환에서는 그 조건이 스스로는 절대 충족되지 않기 때문이다.

백프레셔

유계(bounded) 채널은 자연스러운 백프레셔를 제공한다. 체커가 느리면 자리가 날 때까지 sender가 블록된다. 재귀를 원하기 전까지는 아주 좋다. 이제 응답 핸들러가 요청 채널로 보내야 한다. 그 채널이 가득 차면 응답 핸들러가 블록되고, 블록되면 응답이 소비되지 않으며, 응답이 소비되지 않으면 요청 슬롯도 비워지지 않는다.

중복 제거 레이스

우리는 링크를 동시에 검사하므로 여러 페이지가 같은 링크를 가지고 있을 수 있다. 동기화 없이는 여러 태스크가 같은 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은 Wikipedia를 재귀적으로 검사하다가 실수로 자신의 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, 모든 작업이 끝났을 때 발동하는 단일 waiter
• WaitGuard, 각 태스크가 들고 있는 복제 가능한 가드. 마지막 가드가 drop되면 waiter가 완료된다.

핵심은 WaitGuard를 복제할 수 있다는 것이다. 태스크는 하위 태스크(재귀!)를 만들면서도, 재귀 하위 태스크가 들고 있는 가드를 포함한 모든 가드가 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이 체커와 설정(user-agent, 레이트 리미팅, TLS 설정)을 공유하지 않는 별도의 reqwest::Client를 거쳤다. 그 때문에 실제 버그가 발생했다(Wikipedia가 user-agent가 설정되지 않은 입력 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;
    }
}

어려운 부분들(언제 멈출지 알기, 데드락에 걸리지 않기, 서버를 flooding하지 않기)은 애초에 재귀와는 관련 없던 작업들에 의해 이미 해결됐다. 재귀는 이를 위해 만들어지지 않은 파이프라인에 덧붙인 특수 케이스가 아니라, 좋은 아키텍처의 부산물이 된다.

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

오랫동안 나는 우리가 실패했다고 스스로에게 말해왔다. 네 번의 시도, 5년, 겉보기엔 출시된 것도 없다.

하지만 이 모든 걸 글로 쓰면서 생각이 바뀌었다. 모든 시도는 채널 종료 시맨틱, 백프레셔 데드락, 소유권 인체공학, 분산 종료 감지가 뒤섞인 무언가에 부딪혔다. 그 어느 것도 lychee만의 문제가 아니다. 어려운 동시성 시스템 문제다. 우리는 그걸 논할 어휘가 없었을 뿐이고, 내가 보지 않는 사이에 그 프리미티브들이 만들어졌다. 때로는 어떤 기능을 위해 쓰는 가장 중요한 코드가 그 기능을 전혀 언급하지 않는 코드일 때도 있다.

그래서 아니, 우리는 실패하지 않았다고 생각한다. 우리는 비틀거리는 와중에도 올바른 방향으로 나아갔다.

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