웹 크롤러 설계 (대시설기)

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

크롤러 이용처

• 검색 엔진 인덱싱: 크롤러는 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다.
• 웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차를 말한다.
• 웹 마이닝: 유명 금융 기업들은 크롤러를 사용해 주주총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아낸다.
• 웹 모니터링: 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다.

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

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

웹 크롤러가 만족시켜야할 속성

• 규모 확장성: 병행성을 활용하면 보다 효과적으로 웹 크롤링을 할 수 있다.
• 안정성: 비정상적 입력이나 환경에 잘 대응할 수 있어야 한다.
• 예절: 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안 된다.
• 확장성: 새로운 형태의 콘텐츠를 지원하기가 쉬워야 한다.

개략적 규모 추정

• 매달 10억개의 웹 페이지를 다운로드한다.
• QPS = 10억, 약 400페이지/초
• 최대 QPS = 2 * QPS = 800
• 웹 페이지의 크기 평균은 500k라고 가정
• 10억 페이지 * 500k = 500TB/월
• 1개월치 데이터 보관하는 데는 500TB, 5년간 보관한다면 30PB의 저장용량 필요

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

시작 URL 집합

웹 크롤러가 크롤링을 시작하는 출발점. 크롤러가 가능한 한 많은 링크를 탐색할 수 있도록 골라야 한다.

미수집 URL 저장소

다운로드할 URL을 저장 관리하는 컴포넌트

HTML 다운로더

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

도메인 이름 변환기

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

콘텐츠 파서

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

중복 컨텐츠인가?

29가량의 웹 페이지 콘텐츠는 중복이다. 효과적인 중복 컨텐츠 구분 방법은 웹 페이지의 해시 값을 비교하는 것이다.

콘텐츠 저장소

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

URL 추출기

HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다. 상대 경로는 전부 절대 경로로 변환한다.

URL 필터

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

이미 방문한 URL?

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

해당 자료 구조는 블룸 필터나 해시 테이블이 널리 쓰인다.

• 블룸 필터(Bloom filter)는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조이다.
• 해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다.

URL 저장소

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

3단계 상세 설계

DFS vs BFS

웹은 directed graph 같다. 페이지는 노드이고, 하이퍼링크는 edge라고 보면 된다.

DFS보다는 BFS를 택하는 것이 좋다. 얼마나 깊을지 가늠하기 힘들기 때문

2가지 문제점이 있다.

1. 같은 서버에 요청을 병렬적으로 처리한다면 어마어마한 요청을 보내 impolite 크롤러로 간주될 수 있다.
2. 표준적 BFS는 URL 간에 우선순위를 두지 않는다. 모든 웹 페이지의 중요성을 같게 본다.

미수집 URL 저장소

이 저장소를 잘 구현하면 politeness 크롤러, URL 사이의 중요도를 구분할 수 있는 크롤러를 구현할 수 있다.

예의 바른 크롤러를 만들 때 지켜야할 원칙

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

웹 사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다.

→ 큐 라우터, 매핑 테이블, FIFO 큐, 큐 선택기, 작업 스레드 개념 추가 학습 (p152 - 153)

우선순위

페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다.

신선도

데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집할 필요가 있다.

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

HTML 다운로더

Robots.txt

로봇 제외 프로토콜이라고 부르기도 하는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준적 방법이다. 이 파일은 주기적으로 다시 다운받아 캐시에 보관할 것이다.

성능 최적화

1. 분산 크롤링: 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법이다. 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다.
2. 도메인 이름 변환 결과 캐시: DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡 등을 돌려 주기적으로 갱신하도록 해 놓으면 성능을 효과적으로 높일 수 있다.
3. 지역성: 크롤링 서버를 지역별로 분산하는 방법
4. 짧은 타임아웃: 어떤 서버는 응답이 느리거나 아예 응답하지 않는다.
5. 안정성
   1. 안정 해시
   2. 크롤링 상태 및 수집 데이터 저장
   3. 예외 처리
   4. 데이터 검증
6. 확장성
7. 문제 있는 콘텐츠 감지 및 회피
   1. 중복 컨텐츠: 해시나 체크섬을 사용하면 쉽게 탐지하라 수 있다.
   2. 거미 덫: 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지 (spider.com/foo/bar/foo/bar/foo/bar/ …)
   3. 데이터 노이즈 (광고, 스팸)

4단계 마무리

추가로 논의해보면 좋을 것들

• 서버 측 렌더링
• 원치 않는 페이지 필터링
• 데이터베이스 다중화 및 샤딩
• 수평적 규모 확장성
• 가용성, 일관성, 안정성
• 데이터 분석 솔루션