대규모 웹 크롤러의 큐, 정중함, 중복 제거

대규모 웹 크롤러는 URL을 많이 가져오는 문제가 아니라, 우선순위와 정중함, 중복 제거, 장애 복구를 동시에 만족시키는 분산 시스템 설계 문제다. URL Frontier, robots.txt 처리, Bloom filter와 SimHash, 큐 기반 컴포넌트 분리, at-least-once와 멱등성까지 핵심 메커니즘을 연결해 살펴본다.

Layer: L9
Duration: 길이 미정
Generated: 2026. 5. 25. 오후 4:43:14

원본 문서 읽기 오디오 파일 열기

Script Companion

오디오와 함께 스크립트 보기

01
대규모 웹 크롤러를 볼 때 첫 번째로 붙잡을 점은, 문제가 단순히 URL 개수가 많다는 데 있지 않다는 것이다. SPA 라우터에서 sort, size, color 같은 동적 쿼리 파라미터 조합이 폭증하면 같은 페이지가 수백 개 URL처럼 보일 수 있다. 프론트엔드에서 라우팅 키를 정규화하지 않으면 상태 관리가 흔들리듯, 크롤러도 URL을 정규화하지 않으면 같은 페이지를 반복해서 다운로드한다. 이 현상이 crawler trap의 출발점이다.
02
초기 크롤러는 BFS에 가까운 단일 FIFO 큐로도 설명할 수 있었다. 하지만 웹 페이지의 상대 링크는 같은 호스트의 URL을 연속으로 만들기 쉽고, 여러 worker가 단일 FIFO에서 동시에 dequeue하면 같은 서버에 병렬 요청이 몰린다. Mercator 논문은 이런 요청 집중이 서버를 과부하시키거나 일부 서버를 중단시킬 수 있다고 설명했다. 호스트당 동시 요청 1개 수준의 약한 정중함을 적용한 수천만 문서 크롤에서도 운영자 불만이 발생했다는 점이 중요하다.
03
URL Frontier는 이 한계를 풀기 위한 핵심 구조다. 단순 FIFO가 아니라, 중요한 페이지를 먼저 처리하는 우선순위와 같은 호스트에 동시 접속하지 않는 정중함을 함께 만족해야 한다. Mercator 구조에서는 front-end FIFO queue가 priority를 맡고, back-end FIFO queue와 heap이 강한 politeness를 맡는다. Back queue는 단일 호스트의 URL만 담고, heap은 다음 fetch 가능 시각과 back queue index를 기준으로 정렬한다. Front에서 우선순위를 고르고, Back에서 호스트별 직렬화를 강제하는 식이다.
04
이중 큐 구조가 필요한 이유는 두 제약이 서로 충돌하기 때문이다. Front queue만 있으면 인기 있는 같은 사이트가 연속 선택되어 서버를 압박할 수 있고, Back queue만 있으면 중요한 페이지와 덜 중요한 페이지를 똑같이 처리하게 된다. Mercator의 프로덕션 설정은 crawling thread 수의 약 3배 back queue를 두고, 같은 호스트의 다음 접속을 직전 다운로드 시간보다 10배 긴 시간 뒤로 미뤘다. 이 원리는 K8s controller-runtime의 rate-limiting queue와도 이어진다. URL Frontier의 host key를 namespace와 name 리소스 key로 바꾸면, 특정 리소스 장애가 전체 reconcile 처리량을 잡아먹지 않게 하는 같은 패턴이 보인다.
05
Politeness Policy는 그냥 천천히 요청하는 규칙이 아니라, 명시적 규칙과 측정 기반 적응을 합친 구조다. 명시적 규칙에는 robots.txt의 User-agent, Disallow, Allow, 비표준 확장인 Crawl-delay, meta robots, X-Robots-Tag가 있다. 여기에 응답 시간 증가 시 backoff하는 Mercator 휴리스틱과, HTTP 429의 Retry-After, HTTP 503의 더 긴 cooldown 같은 응답 기반 동작이 붙는다. 직전 fetch가 200ms 걸렸으면 다음 요청은 최소 2초 뒤, 5초 걸렸으면 50초 뒤로 미루는 식이다. 서버가 느릴수록 자동으로 더 정중해진다.
06
HTTP 429를 받았을 때 Retry-After가 있으면 서버가 제시한 시간을 우선한다. 없으면 호스트별 지연 시간을 두 배씩 늘리되, 예를 들어 1시간 같은 상한을 두는 방식으로 지수 backoff를 적용한다. 이 규칙은 외부 API polling에도 그대로 전이된다. API가 X-RateLimit-Remaining을 주더라도 실제 차단은 IP, 계정, resource 단위로 섞일 수 있으므로, 성공 응답 헤더만 믿고 글로벌 rate를 올리는 것은 silent failure의 시작이 될 수 있다. 크롤러의 정중함은 법적, 윤리적 경계와도 연결된다.
07
robots.txt 처리는 캐싱 경계가 특히 중요하다. 호스트당 한 번 받고, unreachable인 경우를 제외하면 24시간을 넘기지 않는 것을 기본으로 삼는다. 파서는 최소 500KiB까지 처리할 수 있어야 하며, 이보다 작은 파일을 잘라 버리면 표준 호환성이 깨진다. 5xx나 네트워크 오류로 robots.txt가 unreachable이면 허용이 아니라 전체 disallow로 취급하고, 404처럼 unavailable이면 접근 가능하다고 볼 수 있다. 캐싱하지 않으면 모든 fetch 전에 robots.txt를 다시 받는 N+1 anti-pattern이 생기므로, 호스트에서 parsed rules와 fetched_at으로 이어지는 매핑을 Redis로 분산 공유한다.
08
중복 URL 검출은 단계별 자료구조를 쌓아 비용을 낮춘다. 첫 단계는 URL 정규화다. 같은 페이지가 여러 URL로 표현되는 문제를 먼저 줄인다. 다음은 메모리 1차 필터인 Bloom filter다. URL 10억 개를 false positive 1% 기준 약 2GB로 표현할 수 있고, 모든 비트가 1이면 이미 봤을 가능성이 있다고 판단한다. 다만 false positive가 있어 실제로는 안 본 새 URL을 놓칠 수 있다. 그래서 Bloom filter가 봤다고 판단한 URL만 Cassandra, ScyllaDB, RocksDB 같은 영구 저장소에서 정확히 확인한다.
09
Mercator는 중복 판정 비용이 왜 병목이 되는지도 수치로 보여준다. 10억 URL checksum 저장에 5GB 이상이 필요하고, 디스크 기반 hash table은 평균 8ms seek 때문에 초당 750회 중복 검사 정도가 한계가 된다. 페이지당 평균 10개 링크라면 초당 75 다운로드 수준으로 막힌다. 그래서 현대 설계는 URL 정규화, 메모리 1차 필터, 영구 저장소 확인을 계층화한다. 분산 환경에서는 URL hash로 샤딩해서 한 URL은 항상 같은 노드가 소유하게 만들고, 영구 저장소 키는 정규화된 URL의 64비트 hash로 저장 공간을 줄인다.
10
URL이 다른데 콘텐츠가 거의 같은 경우에는 콘텐츠 중복을 따로 본다. 연구에 따르면 웹 페이지의 약 30%가 다른 70%의 near-duplicate다. SimHash는 문서를 64비트 fingerprint로 만들고, Hamming distance가 3 이하이면 duplicate로 본다. Google은 2007년 논문에서 80억 페이지 저장소에서 64비트 SimHash와 Hamming distance k=3이 합리적이며, precision과 recall이 둘 다 약 0.75 근처라고 보고했다. 다만 짧은 문서, 한중일 다국어, 코드나 로그 문서, Jaccard 유사도 기준이 명확한 경우에는 MinHash와 LSH, 언어별 tokenizer, 정규화 같은 대안을 선택해야 한다.
11
Fetcher, Parser, Storage, Frontier는 자원 특성이 다르기 때문에 분리해서 스케일링해야 한다. Fetcher는 네트워크 I/O 바운드라 IP 풀과 동시 연결 수가 중요하고, Parser는 HTML과 JS 파싱 때문에 CPU 바운드다. Storage는 디스크 I/O와 네트워크, Frontier는 메모리와 영구 저장소가 핵심이다. 컴포넌트 간 통신은 큐로 이어진다. Fetcher는 raw_pages를 Parser로 보내고, Parser는 discovered_urls를 Frontier로 보내며, parsed_docs를 Storage로 전달한다. 한 컴포넌트가 느려져도 전체가 즉시 멈추지 않고, backpressure는 큐 길이와 lag로 관찰한다.
12
Kafka 기반에서는 raw_pages consumer lag가 10,000 메시지를 넘으면 Parser 인스턴스 스케일 아웃을 검토하고, lag 증가 추이가 5분 내 10% 이상 지속되면 Fetcher rate를 즉시 낮춘다. 하지만 단순히 lag가 N보다 크다는 임계치만으로는 트래픽 스파이크와 장애를 구분하기 어렵다. LinkedIn의 Burrow처럼 offset commit 여부, commit 증가 여부, lag의 지속 증가 여부를 sliding window로 보는 추이 기반 평가가 필요하다. SQS 기반이면 처리 중 메시지와 대기 중 메시지 합계가 비슷한 역할을 한다. ApproximateNumberOfMessagesNotVisible과 ApproximateAgeOfOldestMessage가 같이 증가하면 zombie 처리나 downstream storage hang을 의심한다.
13
분산 크롤러의 장애 복구는 at-least-once delivery와 멱등성으로 설명할 수 있다. URL은 최소 한 번 처리되어야 하지만, 네트워크 타임아웃 뒤 worker가 ack하지 못했는데 실제 처리는 성공한 경우처럼 중복 처리는 반드시 발생한다. 그래서 같은 URL을 두 번 처리해도 결과가 같아야 한다. SQS에서는 visibility timeout 동안 다른 worker가 같은 메시지를 보지 못하고, 만료되면 URL이 재할당된다. timeout은 평균이 아니라 p95 처리 시간과 heartbeat 실패 시간을 기준으로 잡는다. 기본값은 30초이고 ChangeMessageVisibility로 연장할 수 있지만, 최초 수신 시점부터 최대 12시간을 넘길 수 없다.
14
Crawler trap 방어는 크롤러를 끝나지 않는 작업에서 꺼내는 안전장치다. 호스트당 깊이를 5에서 10으로 제한하고, URL 길이가 200자를 넘거나 파라미터가 10개를 넘으면 의심한다. 도메인당 fetch 횟수가 1M URL을 넘으면 일시 정지하고, calendar나 pagination처럼 미래 날짜 패턴이 계속 나오는지도 본다. JavaScript 렌더링도 비용 경계가 있다. 일반 HTML은 단순 fetch와 parse로 충분하지만, SPA나 동적 페이지는 Headless Chromium, Puppeteer, Playwright가 필요할 수 있다. 비용 차이가 10배에서 100배라서 페이지 유형을 분류해 필요한 경우에만 렌더링한다.
15
정리하면 대규모 웹 크롤러는 URL Frontier로 우선순위와 정중함을 분리하고, robots.txt와 응답 기반 backoff로 요청 경계를 지키며, 정규화와 Bloom filter, 영구 저장소, SimHash로 중복을 줄인다. Fetcher, Parser, Storage는 큐로 분리하고, at-least-once와 멱등성을 전제로 장애 복구를 설계한다. 이 구조는 검색 엔진뿐 아니라 외부 API 데이터 수집, 사내 문서 통합 검색, 로그 수집, K8s Operator의 work queue 패턴에도 이어진다. 결국 핵심은 정중하게, 중복 없이, 장애에 강하게 가져오는 것이다.

같은 레이어

L9에서 이어 듣기

원본 문서: content/topics/L9/web-crawler-system-design.md
오디오 파일: /podcasts/l9-web-crawler-system-design.mp3