9장 - 웹 크롤러 설계

목표

웹 크롤러는 검색 엔진에 널리 쓰는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 목적이다.

크롤러는 다음과 같은 이유로 다양한게 이용된다.

검색 엔진 인덱싱 : 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다.
웹 아카이빙 : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
웹 마이닝 : 웹에서 데이터를 가져오는 데이터 마이닝을 통해 기업의 핵심 사업 방향을 알아내기도 한다.
웹 모니터링 : 크롤러를 사용해 저작권, 상표권이 침해되는 사례를 모니터링할 수 있다.

크롤러의 복잡도는 처리해하는 데이터의 규모에 따라 달라진다.
우선 웹 크롤러가 감당해야 하는 데이터의 규모와 기능들을 알아내야만 한다.

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

웹 크롤러의 기본 알고리즘은 다음과 같다.

URL 집합이 입력으로 주어지면, 해당 URL들이 가리키는 모든 웹 페이지를 다운로드한다.
다운받은 웹 페이지에서 URL들을 추출한다.
추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다.

하지만 엄청난 규모 확장성을 갖는 웹 크롤러를 설계하는 것은 엄청나게 어렵다. 주어진 인터뷰 시간 동안 완성하기는 불가능할 것이다. 따라서 질문을 통해 설계 범위를 좁히자.

지원자 질문

크롤러의 주된 용도는?
매달 얼마나되는 웹페이지를 수집하는지?
새로 만들어진 웹 페이지나 수정된 웹 페이지도 고려해야하는지?
수집된 웹페이지를 저장해야하는지?
중복된 콘텐츠는 어떻게해야하는지?

면접관 대답

크롤러의 용도는 검색 엔진 인덱싱
매달 10억개의 웹 페이지 수집
새로 만들어지거나 수정된 페이지도 고려 대상
수집된 웹페이지는 5년간 저장
중복된 콘텐츠는 무시

좋은 웹 크롤러가 되기 위해서는 다음과 같은 속성이 중요하다.

규모 확장성 : 병렬(parallelism)을 활용, 효과적인 웹 크롤링
안정성 : 웹은 함정으로 가득하다. 잘못 작성된 HTML, 반응없는 서버, 장애, 악성코드등을 대응할 수 있어야한다.
확장성 : 새로운 형태의 콘텐츠를 지원하기 쉬워야한다.

개략적 규모 측정

매달 10억개의 웹 페이지를 다운
QPS= 10억/30일/24시간/3600초 = 대략 400페이지/초
최대 QPS = 2 X QPS = 800
웹 페이지의 크기 평균은 500K라고 가정 ➡️ 10억 페이지 X 500k = 500TB/월
5년간 보관한다면 500TB X 12개월 X 5년 = 30PB의 저장용량 필요

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

해당 구조는 웹 크롤러에 관한 선행 연구를 참고한 것이다.

이 다이어그램을 통해 컴포넌트 각각이 어떤 기능을 수행하는지 살펴보자.

시작 URL 집합

시작 URL 집합은 웹 크롤러가 크롤링을 시작하는 출발점이다.
전체 웹을 크롤링해야하는 경우 시작 URL을 고를 때 좀 더 창의적인 필요가 있다.
크롤러가 가능한 한 많은 링크를 탐색 할 수 있도록 하는 URL을 고르는 것이 바람직하다.

미수집 URL 저장소

현대적 웹 크롤러는 크롤러 상태를 다운로드할 URL, 다운로드된 URL 두가지로 나눠 관리한다. 이떄 미수집 URL 저장소는 다운로드할 URL을 저장한 후 큐와 같은 방법으로 사용한다.

HTML 다운로더

웹 페이지를 다운로드하는 컴포넌트, 미수집 URL 저장소로 부터 URL받아 사용

도메인 이름 변환기

URL에 대응하는 IP주소를 알아낸다.

콘텐츠 파서

다운로드한 웹페이지를 파싱과 검증 절차를 한다.

중복 콘텐츠인가?

전체의 29% 가량의 웹 페이지 콘텐츠는 중복이라고 한다.
이 문제를 해결하기 위해 자료구조를 도입하여 중복을 줄이고 처리 소요 시간을 줄인다. → 해시값을 비교하여 중복인지를 처리한다.

콘텐츠 저장소

HTML 문서를 보관하는 시스템
저장소를 구현하는데 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간등을 고려해야한다.
본 설계안의 경우 디스크와 메모리를 동시에 사용한다.

대부분의 콘텐츠는 디스크에 저장
인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄인다.

URL 추출기

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

URL 필터

특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속시 오류가 발생하는 URL, 접근 제어 목록에 포함된 URL등을 크롤링 대상에서 배제하는 역할

이미 방문한 URL

이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료 구조 사용(블룸 필터, 해시 테이블 사용)
서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있다.

URL 저장소

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

웹 크롤러의 작업흐름

시작 URL들을 미수집 URL저장소에 저장한다.
HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
HTML 다운로더는 도메인 이름 변환기를 사용하여 URL의 IP 주소를 알아 내고, 해당 IP 주소로 접속하여 웹 페이지를 다운받는다.
콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증한다.
콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인하는 절차를 개시한다.
중복 콘텐츠인지 확인하기 위해서, 해당 페이지가 이미 저장소에 있는지 본다.
- 이미 저장소에 있는 콘텐츠인 경우에는 처리하지 않고 버린다.
- 저장소에 없는 콘텐츠인 경우에는 저장소에 저장한 뒤 URL 추출기로 전달한다.
URL 추출기는 해당 HTML 페이지에서 링크를 골라낸다.
골라낸 링크를 URL 필터로 전달한다.
필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달한다.
이미 처리한 URL인지 확인하기 위하여, URL 저장소에 보관된 URL인지 살핀다. 이미 저장소에 있는 URL은 버린다.
저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다.

3단계 상세 설계

지금까지 개략적 설계안을 살펴보았다. 이제 컴포넌트와 그 구현 기술을 심도있게 살펴보자.

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

웹은 유향 그래프(directed graph)와 같다. DFS와 BFS가 그래프 탬색으로 사용될 수 있다.
하지만 DFS는 그래프 크기가 클 경우 어느 정도 깊숙이 가게 될지 가늠하기 어렵기 떄문에 좋은 선택이 아니다.

BFS를 사용한 구현법에도 두가지의 문제점이 있다.

한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다.
크롤러는 같은 호스트에 속한 많은 링크를 다운받게 되는데(병렬으로) 제공해주는 서버에 과부하를 걸게된다.
이러한 크롤러를 'impolite' 예의 없는 크롤러로 간주된다.
표준적 BFS 알고리즘은 URL간에 우선순위를 두지 않는다.
모든 페이지를 공평하게 대우하나 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않는다.
페이지 순위, 사용자트래픽의 양, 업데이트 빈도 등 여러 가지 척도에 비추어 처리 우선순위를 구별하여야한다.

미수집 URL 저장소

미수집 URL 저장소에서 위의 문제를 해결할 수 있다.
이 저장소를 잘 구현하면 예의를 잘 갖춘 크롤러, 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.

예의

웹 크롤러는 수집 대상 서버로 짧은 시간에 너무 많은 요청을 보내는 것을 삼가야한다.
➡️ 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청해야한다.
➡️ FIFO큐를 사용하여 큐에서 꺼낸 URL만 다운로드한다.

큐 라우터 : 같은 호스트에 속한 URL을 같은 큐로 가도록 보장
매핑테이블 : 큐 라우터가 사용하는 매핑테이블
큐 선택기 : 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드하도록 작업 스레드에 전달하는 역할
작업 스레드 : 전달된 URL을 다운로드하는 작업

우선순위

우선순위를 나눌때 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다.
순위결정장치를 이용하여 우선순위를 바탕으로 처리할 수 있다.

순위결정장치 : 우선순위를 계산한다.
큐(f1...fn) : 우선순위 별로 큐가 하나씩 할당된다. 우선순위가 높으면 선택될 확률도 올라간다.
큐 선택기 : 순위가 높은 큐에서 더 자주 꺼내도록한다.

신선도

웹 페이지는 수시로 추가, 삭제, 변경된다. 신선함을 유지하기 위해 주기적으로 재수집할 필요가 있다.
이 작업을 최적화하기 위한 전략으로는 다음과 같은 것 들이 있다.

웹 페이지의 변경 이력 활용
우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집

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

처리해야하는 URL의 수가 매우 많음으로 메모리에 보관하는 것은 바람직하지않다.
디스크에 모두 보관하는 것도 병목지점으로 작용하기 때문에 좋은 방법이 아니다.

대부분을 디스크에 두되 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 절충안을 사용한다.

HTML 다운로더

Robots.txt

로봇 제외 프로토콜 = Robots.txt는 웹사이트가 크롤러와 소통하는 표준적 방법이다.
웹 사이트를 긁어 가기전에 해당 파일에 규칙을 먼저 확인해야한다.

성능 최적화

아래는 HTML 다운로더에서 사용할 수 있는 성능 최적화 기법들이다.

분산 크롤링 : 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
도메인 이름 변환 결과 캐시 : 도메인 이름 변환기(DNS Resolver)는 성능의 병목 중 하나이다. DNS 요청을 받는 과정이 동기적이기 때문이다. DNS조회 결과를 캐시에 보관해 놓고 cron job(주기적인 배치작업)으로 갱신해놓으면 성능을 줄일 수 있다.
지역성 : 크롤링 하는 서버를 지역별로 분산시켜 물리적 접근시간을 줄인다.
짧은 타임아웃 : 대기 시간을 걸어놓아 무응답 페이지에 대해 대처한다.

안정성

안정 해시 : 다운로드 서버들에 부하를 분산할 때 사용한다.
크롤링 상태 및 수집 데이터 저장 : 장애 발생시 복구를 위한 데이터와 상태를 기록해둔다.
예외 처리 : 에러가 발생해도 전체 시스템이 중단되지 않도록 예외 처리
데이터 검증 : 시스템 오류를 방지

확장성

새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경 써야한다.

모듈 확장 예시

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

중복컨텐츠 : 해시나 체크섬을 사용해 중복 컨텐츠를 보다 쉽게 탐지
거미 덫 : 거미 덫은 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지다. 무한한 디렉터리 구조로 된 링크를 이용하는데 ➡️ URL의 최대 길이를 제한함으로 회피 모든 종류의 덫을 자동으로 회피할 순 없으나 이러한 경우가 많지 않음으로 수작업으로 필터목록에 걸어두는 방식 사용
데이터 노이즈 : 광고, 스크립트 코드, 스팸등을 제외시킨다.

4단계 마무리

좋은 크롤러는 규모 확장성, 예의 , 확장성, 안정성 등을 갖추어야한다.
추가적으로 다음과 같은 항목을 논의해보면 좋다.

서버 측 랜더링 :여러 기술들이 링크를 즉석에서 만들어 낸다. 이러한 경우 크롤링 해보면 동적으로 생성되는 링크는 발견할 수 없다. 이를 서버 측 랜더링을 적용하면 해결할 수 있다.
원치 않는 페이지 필터링 : 크롤링에 소요되는 자원은 유한하기 떄문에 스팸 방지 컴포넌트를 두어 여러 페이지를 걸러내도록 해두면 좋다.
데이터베이스 다중화 및 샤딩
수평적 규모 확장성 : 무상태 서버로 만들어 병렬적 크롤링을 제공한다.
가용성, 일관성, 안전성 : 필수적 고려 요소들이다.
데이터 분석 솔류션 : 시스템을 세밀하게 조정하는 등 여러 데이터와 분석 결과가 중요하다.