ch09 웹 크롤러 설계

4/10/2025

#시스템 디자인

웹 크롤러 설계

웹 크롤러:

로봇(robot), 스파이더(spider) 라고도 함
웹 페이지, 이미지, 비디오, PDF 파일
몇 개 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 콘텐츠를 수집

이용되는 곳

검색 엔진 인덱싱
- 검색 엔진을 위한 로컬 인덱스, Googlebot
웹 아카이빙
- 정보를 모으는 절차, 국립 도서관들
웹 마이닝
- 유용한 지식들 도출, 유명 금융기업들의 주주 총회 자료, 연차 보고서
웹 모니터링
- 저작권, 상표권 침해 사례 모니터링, 디지바크(Digimarc)가 찾아내서 보고

1단계 문제 이해 및 설계 범위 확정

웹 크롤러의 기본 알고리즘

URL 집합이 입력되면, 해당 URL들이 가리키는 모든 웹 페이지 다운로드
다운받은 웹 페이지에서 URL들 추출
추출된 URL들을 다운로드할 URL 목록에 추가, 처음단계부터 다시 반복

요구사항을 얻기 위한 질문

크롤러의 주된 용도 물어보기
수집량 물어보기
새로 생성된, 수정된 페이지 수집 고려 여부
저장 유무 및 기간
중복된 컨텐츠

책에서는 이러한 사례들을 소개한다.

요구사항 중 고려해야 할 것

안정성(robustness) : 비정상적인 입력, 환경에 대응할 수 있어야 한다.
- ex) 잘못 작성된 HTML, 아무 반응이 없는 서버, 장애, 악성코드가 붙어 있는 링크
예절(politeness) : 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내면 안된다.
확장성(extensibility) : 새로운 형태의 콘텐츠를 지원할 수 있어야한다.
- ex) 이미지 파일도 크롤링 할 수 있게 하고 싶은데 전체 시스템을 새로 설계해야 한다면 곤란함

많은 가정을 통해서 추정치를 계산해 보며 면접관과 합의를 진행해야 한다.

개략적 규모 추정

매달 10억개 웹 페이지 다운로드
QPS = 10억(1billion) / 30일 / 24시간 / 3600초 = 대략 400페이지/초
최대 QPS = 2 X QPS = 800
웹 페이지 크기 평균 500k라고 가정
10억 페이지 x 500k = 500TB / 월
1개월치 데이터 500TB로 보관, 5년간 보관한다고 가정하면 500TB X 12개월 X 5년 = 30PB가 필요

요구사항 후 , 개략적 설계를 진행한다.

2단계 개략적 설계안 제시 및 동의 구하기

시작 URL 집합(send URLs)

ex) 대학 웹사이트에서 모든 웹 페이지를 크롤링하기 위한 가장 직관적인 방법
- 도메인 이름이 붙은 모든 페이지의 시작 URL를 쓰는 것
전체 웹을 크롤링 해야 할때
- 가능한 많은 링크를 탐색할 수 있는 URL
일반적인 방법
- 전체 URL 을 작은 부분집합으로 나누는 전략
  - 지역적인 특색
  - 나라별로 인기있는 웹 사이트
  - URL을 쇼핑, 스포츠, 건강 주제별로 세분화하여 시작 URL 쓰기

정답이 없다. 의도가 무엇인지만 면접관에 잘 전달

미수집 URL 저장소(URL Frontier)

대부분의 크롤러는

다운로드할 URL
다운로드된 URL

두가지로 관리한다.

다운로드할 URL을 관리하는 컴포넌트를 미수집 URL 저장소(URL Frontier)라고 한다.
FIFO 큐라고 생각

HTML 다운로더(HTML Downloader)

인터넷에서 웹 페이지를 다운로드하는 컴포넌트. 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공

도메인 이름 변환기(DNS Resolver)

웹페이지를 다운받기위해서는 URL을 IP주소로 변환하는 절차가 필요하다. HTML 다운로더는 이러한 변환을 진행한다.

ex) www.wikipedia.org -> 198.35.26.96 ,,

콘텐츠 파서(Content Parser)

다운로드 후, 파싱(parsing), 검증(validation) 절차를 진행해야 한다. 이상한 웹 페이지는 문제가 발생할 수 있고, 저장공간만 낭비할 수 있다.

크롤링 서버안에 구현하게되면 느려질 수 있어서, 독립된 컴포넌트로 만들었다.

중복 콘텐츠인가?(Content Seen?)

연구 결과에 따르면, 29% 가량의 웹 페이지 콘텐츠는 중복이다.

본 설계안에서는 자료구조를 도입하여 데이터 중복을 줄이고, 데이터 처리 소요 시간을 줄인다.

두 문서를 비교하기 위한 방법

문자열로 비교

단점

문서 수가 많아지면 느리고 비효율적임

방안

해시값으로 비교

콘텐츠 저장소(Content Storage)

HTML문서를 보관하는 시스템이다.

저장소를 구현하는 데 쓰일 기술을 고를 때 고려할 것

데이터 유형, 크기, 저장소 접근 빈도, 데이터 유효기간 등

본 설계안은 디스크와 메모리를 동시에 사용하는 저장소를 선택할 것이다.

데이터 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장
인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄인다.

URL 추출기(Link Extractor)

HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다.

상대 경로에 전부 https://en.wikipedia.org 를 붙여 절대 경로로 변환한다.

URL 필터(URL Filter)

특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL
접속 시 오류가 발생하는 URL
접근 제외 목록에 포함된 URL 배제하는 역할

이미 방문한 URL?(URL Seen?)

이미 방문한 URL 이나 미수집 URL 저장소에 보관된 URL을 추적하기 위한 자료구조를 사용한다. ex) 블룸 필터(bloom filter) , 해시 테이블

같은 URL을 여러 번 처리하는 일을 방지할 수 있다.

서버 부하를 줄이고, 시스템이 무한 루프를 방지할 수 있다.

URL 저장소(URL Storage)

이미 방문한 URL을 보관하는 저장소이다.

웹 크롤러 작업 흐름

시작 URL을 미수집 URL 저장소에 저장
HTML 다운로더는 미수집 URL 저장소에서 URL 목록 가져옴
HTML 다운로더는 도메인 이름 변환기로 IP 주소를 찾아 접속하여 웹페이지를 다운 바음
콘텐츠 파서는 HTML 페이지를 파싱하여 올바른 형식인지 검증
콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인
중복 콘텐츠인지?

이미 저장소에 있는 콘텐츠라면 처리하지 않고 버림
저장소에 없는 콘텐츠라면 저장한뒤 URL 추출기로 전달

URL 추출기는 해당 HTML 페이지에서 링크 고르기
URL 필터로 전달
남은 URL만 중복 URL 판별 단계로 전달
이미 처리한 URL인지 확인하기 위해 URL 저장소에 보관된 URL인지 탐색, 이미 있다면 버림
저장소에 없다면, 미수집 URL 저장소에도 전달

3단계 상세 설계

DFS vs BFS
미수집 URL 저장소
HTML 다운로더
안정성 확보 전략
확장성 확보 전략
문제 있는 콘텐츠 감지 및 회피 전략

DFS를 쓸 것인가, BFS를 쓸 것인가

DFS 을 선택하기 어려운 이유

그래프 크기가 클 경우 어느 정도로 깊숙히 갈지 가늠하기 어렵다.

보통 BFS 너비 우선 탐색법을 선택한다.

또한 FIFO 큐를 사용하기에 한쪽으로는 탐색할 URL을 넣고, 다른 한쪽으로는 꺼내기

문제점

wikipedia.com 에서 추출한 모든 링크는 내부링크이다.

동일한 wikipedia.com 서버의 다른 페이지를 참조하는 링크

크롤러는 같은 호스트에 속한 많은 링크를 다운 받게 되어 바빠지고, 병럴로 처리하게 되면 위키 피디아 서버는 수많은 요청으로 과부하에 걸린다.

'예의 없는 크롤러'

BFS 알고리즘이 URL 간의 우선순위를 두지 않는다.
- 모든 페이지를 공평하게 하면, 같은 수준의 품질, 중요성을 갖지 않는다.

페이지 순위, 사용자 트래픽 양, 업데이트 빈도와 같은 척도를 기준으로 우선순위를 구별하는게 좋을 것이다.

미수집 URL 저장소

URL 저장소는 다운로드할 URL을 보관하는 장소이다.

해당 저장소를 잘 구현하면 예의를 갖춘 크롤러 URL 우선순위, 신선도를 잘 구별하는 크롤러 를 잘 구현할 수 있다.

예의

짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야한다.

때로는 DoS 공격으로 간주되기도 한다.

예의바르기 위해 지켜야할 원칙

동일 웹사이트에 대해서는 한 번에 한 페이지만 요청해야 한다.

시간차를 두고 실행하도록 하면 된다.

좋은 방법

각 다운로드 스레드는 별도 FIFO 큐를 가지고 있다.

큐에서 꺼낸 URL만 다운로드를 진행한다.

큐 라우터
- 같은 호스트에 속한 URL은 같은 큐로 전달되도록 하는 역할
매핑 테이블
- 호스트 이름과 큐 사이의 관계를 보관하는 테이블
FIFO 큐
- 같은 호스트에 속한 URL은 언제나 같은 큐에 보관
큐 선택기
- 큐들을 순회하며, URL을 꺼내서 다운하도록 지정된 작업 스레드에 전달
작업 스레드
- 전달된 URL를 다운로드
- 작업 사이에 일정한 지연시간을 설정할 수 있다

우선순위

애플 제품을 크롤링 한다고 했을때, 포럼 페이지 와 애플 홈페이지가 있다고 하면

애플 홈페이지가 더 중요도가 높을 수 있다.

그러면 먼저 수집하도록 하는 것이 바람직할 수 있다.

페이지 랭크 (PageRank), 트래픽 양, 갱신 빈도(update frequency) 등을 사용할 수 있다.

URL 우선순위를 고려하여 변경한 설계

순위결정장치(Prioritizer) : URL 입력 받아 우선순위를 계산
큐 : 우선순위 별로 하나씩 할당됨, 우선순위가 높으면 선택될 확률이 올라감
큐 선택기(Queue selector) : 큐에서 처리할 URL을 꺼낸다. 순위가 높은 큐에 더 자주 꺼내도록 제작되어있음

전면 큐 : 우선순위 결정 과정을 처리
후면 큐 : 크롤러가 예의 바르게 동작할 수 있도록한다.

-> 설명이 조금 부족해보인다. 추가 조사 필요

신선도

새로 추가되거나, 변경되거나, 삭제된 페이지들이 있을 수 있어서 주기적으로 재수집할 필요가 있다.

미수집 URL 저장소를 위한 지속성 저장장치

문제

수억 개에 달하는 URL 수를 메모리로 관리하는 것은 안정성, 규모확장성에서 바람직 하지 않다.

디스크에 전부 저장하는것도 좋지 않다. (성능 병목점)

절충안

대부분의 URL은 디스크에 그리고 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 둔다.

버퍼에 있는 데이터는 주기적으로 디스크에 기록한다.

? : 다른 방법은 어떤게 있을까?

로봇 제외 프로토콜(Robot Exclusion Protocol)

Robots.txt

크롤러가 수집해도 되는 페이지 목록이 들어있다.

긁어가기 전에 해당 파일에 나열된 규칙을 확인해서, 거푸 다운로드?를 하는 것을 피한다.

주기적으로 다운 받아 캐시에 보관

ex) https://www.amazon.com/robots.txt

예시 규칙

User-agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/* /reviews
Disallow: /gp/pdp/rss/* /reviews
Disallow: /gp/cdp/member-reviews/
Disallow: /gp/aw/c r/

HTML 다운로더 성능 최적화

분산 크롤링

성능을 높이기 위해 크롤링 작업을 여러 서버에 분산
각 서버는 여러 스레드를 돌려 다운로드 작업을 처리
URL 공간은 작은 단위로 분할, 각 서버는 그중 일부의 다운로드를 담당

도메인 이름 변환(DNS Resolve) 결과 캐시

문제

도메인 이름 변환기는 크롤러 성능 병목 지점중 하나가 될 수 있음

DNS 요청 후 결과를 받는 동기적 특성 때문 (10ms - 200ms)

스레드 중 하나라도 이 작업중이면 다른 스레드 DNS 요청은 블록(block) 된다.

방안

DNS 조회 결과로 얻어진 도메인 이름, IP 주소 사이 관계를 캐시에 보관 크론 잡(cron job) 스케줄링으로 주기적으로 갱신하도록

? : 크론 잡 갱신 주기는 어느 정도로 지정하면 좋을까? 도메인이 자주 변경될 일은 없지만,, 그래도 만약 변경되었다면 DNS 변환과정에서 블록 시간을 늘리는 요인이 될 수 있으니,,

지역성

크롤링 작업 수행하는 서버를 지역별로 분산시킨다.

크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간이 줄어들 것이다.

크롤링 서버, 캐시, 큐, 저장소 등 대부분 컴포넌트에 적용 가능하다.

짧은 타임아웃

웹 서버가 응답이 느리거나 응답하지 않게 되면 대기 시간이 길어지므로, 미리 정해두기

응답하지 않으면 크롤러는 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어간다.

? : 그냥 넘어가기만 해도 될까? 다운 받지 못한 페이지 임을 따로 명시해두어야 하지 않을까?

안정성

안정성을 향상시키기 위한 방법

안정 해시 : 다운로더 서버들 부하 분산 , 서버를 쉽게 추가하고 삭제할 수 있음
크롤링 상태 및 수집 데이터 저장 : 장애가 발생해도 복구하기 쉽도록 크롤링 상태와 데이터를 저장장치에 기록해두는 것이 바람직함.
예외 처리 : 예외가 발생해도 전체 시스템이 중단되는 일 없이 작업을 이어나갈 수 있도록
데이터 검증 : 시스템 오류를 방지하기 위해서

확장성

새로운 형태의 콘텐츠가 추가될 때도 시스템 설계를 유지가능하도록

Extension Module 에 모듈을 확장한 것을 볼 수 있다.

PNG Downloader : PNG 파일 다운로드 하는 플러그인 모듈

문제 있는 콘텐츠 감지 및 회피

중복 콘텐츠 해시, 체크섬(check-sum)
거미 덫(spider trap) 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지

방안

URL 최대 길이 제한하여 회피

하지만, 만능 해결책은 없다.

방안2

수작업

덫이 있는 사이트를 확인하면 탐색 대상에서 제외 시키거나 URL 필터 목록에 등록

덫이 있는 사이트 찾는 법

기이할 정도로 페이지가 많음. 자동으로 피해가는 알고리즘을 만들기 까다로움

데이터 노이즈

가치가 없는 콘텐츠 ex) 광고, 스크립트 코드, 스팸 URL

제외되도록

4단계 마무리

면접관과 추가로 논의하면 좋은 사항

서버 측 렌더링(server-side rendering) : js, ajax 와 같은 기술들로 만든 링크들은 동적으로 생성되는 링크를 발견하기 어려움, 페이지를 파싱하기 전 이러한 렌더링을 적용하면 해결할 수 있음
원치 않는 페이지 필터링 : 저장 공간은 유효함, 스팸 방지 컴포넌트를 두어 품질이 낮은 스팸성 페이지는 걸러내도록
데이터베이스 다중화 및 샤딩 : 데이터 계층의 가용성, 규모 확장성, 안정성 향상이 필요
수평적 규모 확장성 : 대규모 크롤링을 하기 위해서 다운로드 서버가 많이 필요할 수 있음. 상태가 유지되지 않고 무상태 서버로 만들어 수평적 규모 확장을 노릴 수 있음
가용성, 일관성, 안정성 : 앞 챕터를 복습하여 고려해보자
데이터 분석 솔루션 : 시스템을 세밀하게 조정하기 위해 데이터 분석 결과를 필수로 사용해야 한다.

다음 챕터