9. 웹 크롤러 설계

웹 크롤러?

웹 크롤러는 로봇(Robot) 또는 스파이더(Spider)라고도 부르는 검색 엔진에서 널리 쓰는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적이다.

웹 크롤링 동작 예시

몇 개 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 콘텐츠를 수집한다.

검색 엔진 인덱싱(Search engine indexing)
- 가장 보편적인 용례로 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다.
- Googlebot
웹 아카이빙(Web Archiving)
- 장기보관을 목적으로 웹에서 정보를 모으는 절차를 말한다.
- 국립 도서관 등
웹 마이닝(Web mining)
- 인터넷에서 유용한 지식을 도출해 낼 수 있다.
- 금융 기업들의 기업 분석용
웹 모니터링(Web monitoring)
- 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링 할 수 있다.
- 디지마크(Digimarc)사는 크롤러를 통해 해적판 저작물을 찾아내 보고한다.

웹 크롤러의 복잡도는 웹 크롤러가 처리해야 하는 데이터의 규모에 따라 달라지므로 설계할 웹 크롤러가 감당해야 하는 데이터의 규모와 기능들을 알아내야한다.

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

웹 크롤러의 기본 알고리즘은 간단하다.

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

하지만 엄청난 규모 확장성을 갖는 웹 크롤러를 설계하는 것은 매우 어려운 작업이다.

질문을 던져 요구사항을 알아내고 설계 범위를 좁힌다.

Q. 주된 용도는?
- A. 검색 엔진 인덱싱
Q. 매달 수집해야하는 웹 페이지 수
- A. 약 10억개
Q. 새로 만들어진 웹 페이지나 수정된 웹 페이지도 고려해야하는가?
- A. 예
Q. 수집한 웹 페이지는 저장해야하는가?
- A. 5년간 저장
Q. 중복된 콘텐츠는?
- A. 무시해도 괜찮음

질문을 통해 알아낸 요구사항을 명확히 하면서도 좋은 웹 크롤러가 만족시켜야 할 다음과 같은 속성에 주의를 기울여야한다.

규모 확장성
- 웹은 수십억 개의 페이지가 존재하는 것으로 알려진 만큼 매우 거대하므로, 병행성(Parallelism)을 활용하면 보다 효과적으로 웹 크롤링을 수행할 수 있다.
안정성(Robustness)
- 비정상적인 입력이나 황경에 잘 대응할 수 있어야 한다.
- 잘못 작성된 HTML, 반응 없는 서버, 장애, 악성 코드가 붙어있는 링크 등
예절(Politeness)
- 짧은 시간 동안 너무 많은 요청을 보내어 서버에 무리를 주면 안된다.
확장성(Extensibility)
- 새로운 형태의 콘텐츠를 지원하기 쉬워야한다.

개략적 규모 추정

매달 10억 개의 웹 페이지 다운로드
- QPS = 10억 / 30일 / 24시간 / 3600초 = 약 400페이지/s
- 최대(peak) QPS = 2 x QPS = 800
웹 페이지의 평균 크기는 500k로 가정
- 10억 페이지 * 500k = 500TB/월
- 1개월치 = 500TB * 12개월 * 5년 = 30PB

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

크롤러의 작업 흐름

시작 URL 집합

시작 URL 집합은 웹 크롤러가 크롤링을 시작하는 출발점이다.

전체 웹을 크롤링해야 하는 경우 시작 URL을 고를 때 가능한 한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직하다.

일반적으로 전체 URL 공간을 작은 부분집합으로 나누는 전략을 사용
- 지역적인 특색, 즉 지역별로 인기 있는 웹 사이트가 다르다는 점에 착안
주제별로 다른 시작 URL을 사용
- 쇼핑, 스포츠, 건강 등의 주제별로 세분화하고 그 각각에 다른 시작 URL 사용

시작 URL로 무엇을 쓸 것이냐는 질문에 정담은 없으므로 의도가 무엇인지만 정확히 전달해도 충분하다.

미수집 URL 저장소

대부분의 현대적 웹 크롤러는 크롤링 상태를 다운로드할 URL, 다운로드된 URL 두 가지로 나눠 관리한다.

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

HTML 다운로더

HTML 다운로더는 인터넷에서 웹 페이지를 다운로드하는 컴포넌트이다.

다운로드할 페이지의 URL은 미수집 URL 저장소가 제공한다.

도메인 이름 변환기

웹 페이지를 다운받으려면 URL을 IP로 변환하는 절차가 필요하므로, HTML 다운로더는 도메인 이름 변환기를 이용하여 URL에 대응되는 IP 주소를 알아낸다.

콘텐츠 파서

웹 페이지를 다운로드하면 파싱과 검증절차를 거쳐야한다.

크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있으므로 독립된 컴포넌트로 만드는 것이 좋다.

중복 콘텐츠인가?

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

따라서 같은 콘텐츠를 여러 번 저장하게 될 수 있으므로 중복을 해결하기 위한 자료 구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄일 수 있다.

두 HTML 문서를 비교하는 가장 간단한 방법은 문서를 문자열로 보고 비교하는 방법을 고려할 수 있지만, 문서의 수가 매우 많은 경우 느리고 비효율적이므로, 대부분 웹 페이지의 해시 값을 비교하여 처리한다.

콘텐츠 저장소

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

저장소를 구현하는 데 쓰일 구술을 고를 때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간 등을 종합적으로 고려한다.

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

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

URL 추출기

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

링크 추출 사례

상대 경로를 모두 절대 경로로 변환한다.

URL 필터

특정 URL을 크롤링 대상에서 배제한다.

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

이미 방문한 URL?

이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료 구조를 활용하여 구현한다.

URL 방문 여부를 추적하여 같은 URL을 여러번 처리하는 일을 방지할 수 있다.
서버 부하를 줄이고 무한 루프에 빠지는 일을 방지할 수 있다.

해시 테이블이나 블룸 필터가 널리 쓰인다.

URL 저장소

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

웹 크롤러 작업 흐름

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

3단계: 상세 설계

가장 중요한 컴포넌트와 그 구현 기술을 심도있게 살펴본다.

DFS vs BFS

웹은 유향 그래프(directed graph)와 같으며, 크롤링 프로세스는 이 유향 그래프를 탐색하는 과정이다.

그래프 탐색에 널리 사용되는 알고리즘은 DFS, BFS 두 가지 알고리즘인데 그래프의 크기가 얼마나 클지 가늠할 수 없으므로 BFS를 주로 사용한다.

BFS

BFS의 문제점

BFS는 FIFO 큐에 탐색할 URL를 추가하는 방식인데, 이러한 구현법에는 두 가지 문제점이 있다.

한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다.
- 같은 호스트에 속한 많은 링크를 다운받게 되는데, 병렬로 처리하게 된다면 수집 대상 서버는 수많은 요청으로 과부하에 걸린다.
- 예의 없는 크롤러로 간주
URL에 우선순위를 두지 않는다.
- 모든 웹 페이지가 같은 수준의 품질, 중요성을 갖지는 않는다.
- 페이지 순위, 트래픽의 양, 업데이트 빈도 등 여러가지 척도에 따라 우선순위를 구별하는 것이 좋을 수 있다.

미수집 URL 저장소

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

예의

웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 한다.

동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.
- 같은 웹 사이트의 페이지를 다운받는 태스크는 시간차를 두고 실행한다.
- 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지한다.
- 각 다운로드 스레드는 별도의 큐를 통해 해당 큐에서 꺼낸 URL만 다운로드한다.

예의 있는 크롤러 설계 예시

큐 라우터
- 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장한다.
매핑 테이블
- 호스트 이름과 큐 사이의 관계를 보관한다.
- 호스트 큐
  wikipedia.com b1
  apple.com b2
  … …
  nike.com bn
FIFO 큐
- 같은 호스트에 속한 URL은 언제나 같은 큐에 보관
큐 선택기
- 큐들을 순회하면서 큐에서 URL을 꺼내어 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달한다.
작업 스레드
- 전달된 URL을 다운로드한다.
- 순차적으로 처리되며, 작업 사이에 일정한 지연시간을 둘 수 있다.

호스트	큐
wikipedia.com	b1
apple.com	b2
…	…
nike.com	bn

우선순위

유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크(PageRank), 트래픽 양, 갱신 빈도(Update Frequency) 등 다양한 척도를 사용할 수 있다.

우선순위를 고려하는 크롤러 설계 예시

순위결정장치
- URL을 입력으로 받아 우선순위를 계산한다.
큐
- 우선순위별로 큐가 하나씩 할당된다.
- 우선순위가 높으면 선택될 확률도 올라간다.
큐 선택기
- 임의 큐에서 처리할 URL을 꺼낸다.
- 순위가 높은 큐에서 더 자주 꺼낸다.

전체 설계

전체 설계

전면 큐(front queue)
- 우선순위 결과 과정을 처리한다.
후면 큐(back queue)
- 크롤러가 예의 바르게 동작하도록 보증한다.

신선도

웹 페이지는 수시로 추가되고, 삭제되고, 변경되므로 데이터의 신선함을 유지하기 위해 이미 다운로드한 페이지라고 해도 주기적으로 재수집할 필요가 있다.

모든 URL을 재수집하는 것은 많은 시간과 자원이 필요한 작업이므로, 이 작업을 최적화하기 위한 전략으로 다음과 같은 것들이 있다.

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

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

검색엔진을 위한 크롤러는 처리해야하는 URL이 수억 개에 달한다.

따라서 모두 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않고, 전부 디스크에 저장하는 것도 성능 병목으로 인해 적절치 않다.

따라서 절충안을 택하여, 대부분의 URL은 디스크에 두고 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것을 고려한다.

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

HTML 다운로더

HTML 다운로더는 HTTP 프로토콜을 통해 웹 페이지를 내려받는다.

Robots.txt

로봇 제외 프로토콜이라고도 부르는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준적 방법이다.

Robots.txt 파일에는 크롤러가 수집해되 되는 페이지 목록이 들어있다.

따라서 웹 사이트를 크롤링 하기 전 해당 파일에 나열된 규칙을 먼저 확인해야 한다.

Robots.txt 파일을 거푸 다운로드하는 것을 피하기 위해, 이 파일은 주기적으로 다운받아 캐시에 보관한다.

성능 최적화

분산 크롤링
- 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법이다.
- 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다.
도메인 이름 변호나 결과 캐시
- 도메인 이름 변환기는 DNS 요청을 보내고 결과를 받는 작업의 동기적 틍성으로 인해 크롤러 성능의 변목 중 하나이다.
- DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡 등을 돌려 주기적으로 갱신하도록 해놓으면 성능을 효과적으로 높힐 수 있다.
지역성
- 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법이다.
- 크롤링 서버가 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간을 줄일 수 있다.
- 이러한 전략은 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능하다.
짧은 타임아웃
- 응답이 느리거나 하지 않는 서버에 대한 요청은 대기시간이 길어지므로, 최대 얼마나 기다릴지를 미리 정해 다운로드를 빨리 중단하여 다음 차례로 넘어간다.

안정성

시스템 안정성을 향상하기 위한 접근법 가운데 중요한 몇가지는 아래와 같다.

안정 해시
- 다운로더 서버들에 부하를 분산할 때 적용 가능
- 다운로더 서버를 쉽게 추가하고 삭제할 수 있다.
크롤링 상태 및 수집 데이터 저장
- 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적 저장장치에 기록해 두는 것이 바람직하다.
- 크롤링을 쉽게 재시작할 수 있을 것이다.
예외 처리
- 대규모 시스템에서 에러는 불가피할 뿐 아니라 흔하게 벌어진다.
- 전체 시스템이 중단되는 일 없이 그 작업을 우아하게 이어나갈 수 있어야 한다.
데이터 검증
- 시스템 오류를 방지하기 위한 종요 수간 가운데 하나이다.

확정성

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

새로운 모듈을 끼워 넣음으로써 새로운 형태의 콘텐츠를 지원할 수 있도록 설계할 수 있다.

확장 모듈 반영 설계

PNG 다운로더
- PNG 파일을 다운로드하는 플러그인 모듈

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

중복이거나 의미 없는, 또는 유해한 콘텐츠를 감지하고 차단해야한다.

중복 콘텐츠
- 해시나 체크섬을 사용하면 중복 콘텐츠를 쉽게 탐지할 수 있다.
거미 덫
- 크롤러를 무한 루프에 빠드리도록 설계한 웹 페이지다.
  - www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/...
- 만능 해결책은 없지만 몇가지 방법이 있다.
  - URL 최대 길이를 제한
  - 수작업으로 덫을 확인하고 착아낸 후 탐색 대상에서 제외하거나 필터 목록에 추가한다.
데이터 노이즈
- 가치가 없는 콘텐츠는 제외한다.
- 광고, 스크립트 코드, 스팸 URL 등

4단계: 마무리

좋은 크롤러는 규모 확정성, 예의, 확장성, 안정성 등을 고려해야한다.

웹이 방대하고, 수없이 많은 덫이 도사리고 있기 때문에 규모 확장성이 뛰어난 웹 크롤러 설계는 단순하지 않다.

서버 측 렌더링
- 비동기를 통해 동적으로 생성되는 링크는 페이지를 파싱하기 전에 서버 측 렌더링을 적용하면 해결할 수 있다.
윈치 않는 페이지 필터링
- 스팸 방지 컴포넌트를 두어 품질이 조악하거나 스팸성인 페이지를 걸러내도록 하면 좋다.
데이터베이스 다중화 및 샤딩
- 다중화나 샤딩 같은 기법을 적용하면 데이터 계층의 가용성, 규모 확장성, 안정성이 향상된다.
수평적 규모 확장성
- 대규모 크롤링을 위해 다운로스 서버가 수천 대 필요하게 될 수 있으므로, 수평적 규모 확장을 위해 무상태 서버로 만드는 것이 중요하다.
가용성, 일관성, 안정성
- 대형 시스템을 만들기 위해 필수적으로 고려해야한다. (1장 복습)
데이터 분석 솔루션
- 데이터르 수집하고 분석하는 것은 어느 시스템에게나 중요하다.