[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 9장. 웹 크롤러(Web Crawler) 설계

웹 크롤러란?

로봇(robot) 또는 스파이더(Spider)라고 부름
검색 엔진에서 널리 쓰는 기술로, 웹에 새로 올라오거나 갱신된 컨텐츠르 찾아내는 것이 주된 목적
-> 몇개의 Web Page 에서 시작해서 그 링크를 따라 나가며 새로운 콘텐츠를 수집한다...

크롤러가 이용되는 곳들 ?

1. 검색 엔진 인덱싱(Search Engine Indexing)

크롤러가 제일 보편적으로 사용되는 곳
웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스(local index)를 만듬
ex) Googlebot - 구글(Google) 검색 엔진이 사용하는 웹 크롤러

2. 웹 아카이빙(Web Archiving)

나중에 사용할 목적으로 장기보관을 위해 웹에서 정보를 모으는 절차를 말함
ex) 미국 국회 도서관(US Library of Congress), EU 웹 아카이브 ...

3. 웹 마이닝(Web Mining)

ex) 유명 금융 기업 등에서 크롤러를 사용해서 주주 총회 자료나 연차 보고서(annual report)를 다운받아 기업의 핵심 사업 방향을 알아내기도 한단다

4. 웹 모니터링(Web Monitoring)

인터넷에서 저작권이나 상표권이 침해되는 사례도 모니터링이 가능하다.
ex) 디지마크(Degimarc)사는 웹 크롤러를 사용하여 해적판 저작물을 찾아내서 보고한다고 함..

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

웹 크롤러의 기본 알고리즘

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

근데 크롤러는 생각보다 단순하게 동작하는 게 아니라서.. 어느정도 수준의 규모를 갖는 웹 크롤러를 설계하는 건 쉬운 작업이 아니라고 한다.

웹 크롤러 설계 시에 고려해야할 포인트

1. 규모 확장성: 웹은 거대함.. 그러므로 병행성(parallelism)을 활용하면 보다 효과적으로 웹 크롤링을 할 수 있다.
2. 안정성(robustness)
3. 예절(politeness): 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안됨.
4. 확장성(extensibility): 새로운 형태의 콘텐츠를 지원하기가 쉬워야 함.

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

시작 URL 집합
웹 크롤러가 크롤링을 시작하는 출발점
일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략을 사용함

미수집 URL 저장소
현대 크롤러의 크롤링 상태
= (1) 다운로드할 URL (2) 다운로드된 URL 의 두 가지로 나눠서 관리

미수집 URL 저장소(URL frontier): (2) '다운로드 할 URL' 을 저장하는 컴포넌트

FIFO(First-In-First-Out) 큐(Queue)라고 생각하면 됨.

HTML 다운로더

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

도메인 이름 변환기
웹 페이지 다운 시 URL을 IP 주소로 변환하는 절차가 필요

콘텐츠 파서
웹 페이지를 다운로드 하면 파싱(parsing)과 검증(validation) 절차를 거쳐야 함.
크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있으므로, 독립된 컴포넌트로..

중복 콘텐츠인가?
웹 페이지의 해시 값을 비교하는 것이 제일 효율적

콘텐츠 저장소
HTML 문서를 보관하는 시스템
저장소를 구현하는 데 쓰일 기술을 고를 때에는 1) 저장할 데이터의 유형, 2) 크기, 3) 저장소 접근 빈도, 4) 데이터의 유효 기간 등을 종합적으로 고려해야 함.

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

URL 필터
1) 특정한 콘텐츠 타입이나 2) 파일 확장자를 갖는 URL, 3) 접속 시 오류가 발생하는 URL, 4) 접근 제외 목록(deny list)에 포함된 URL 등을 크롤링 대상에서 제외하는 역할

이미 방문한 URL
해당 자료 구조로 블룸 필터 나 해시 테이블이 널리 사용됨

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

3단계. 상세 설계

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

웹 크롤러의 경우 보통 너비 우선 탐색법(BFS:breath-first search)를 사용
= FIFO(first in first out) 큐를 사용하는 알고리즘
= 한 쪽으로는 탐색할 URL을 집어넣고, 다른 한쪽으로는 꺼내기만 한다.

[ 문제점 ]
1. 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아감.
2. 표준적 BFS 알고리즘은 URL 간에 우선순위를 두지 않는다.
-> 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않는다..
-> 페이지 순위, 사용자 트래픽의 양, 업데이트 빈도 등 여러 가지 척도에 비추어 처리 우선순위를 구별하는게 적합.

미수집 URL 저장소

1. 예의

동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.
-> 이것을 만족 시키려면, 웹사이트의 호스트명(hostname)과 다운로드를 수행하는 작업 스레드(worker thread) 사이의 관계를 유지하면 된다.

• 큐 라우터(Queue Router): 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장하는 역할
• 매핑 테이블(Mapping Table): 호스트 이름과 큐 사이의 관계를 보관하는 테이블
• FIFO 큐(b1부터 bn까지): 같은 호스트에 속한 URL은 언제나 같은 큐에 보관됨
• 큐 선택기: 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달하는 역할
• 작업 스레드: 전달된 URL을 다운로드하는 작업을 수행함. 전달된 URL은 순차적으로 처리될 것이며, 작업 간에 지연시간(delay)을 줄 수 있음

2. 우선순위

• 순위결정장치(priortizer): URL을 입력으로 받아 우선순위를 계산함
• 전면 큐: 우선순위 결정 과정을 처리
• 후면 큐: 크롤러가 예의 바르게 동작하도록 보증

3. 신선도

이 작업을 최적화 하기 위한 전략
1. 웹 페이지의 변경 이력(update history) 활용
2. 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집

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

HTML 다운로더

1. Robot.txt
이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어있음

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

1. 분산 크롤링
   
2. 도메인 이름 변환 캐시
   도메인 이름 변환기(DNS Resolver)는 크롤러 성능의 병목 중 하나이데, 이는 DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문
   -> DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡(cron job) 등을 돌려 주기적으로 갱신하도록 해 놓으면 성능 높일 수 잇음
3. 지역성
4. 짧은 타임아웃

3. 안정성

1. 안정 해시(consistent hashing)
2. 크롤링 상태 미 수집 데이터 저장: 장애가 발생한 경우에도 쉽게 복구할 수 있도록..
3. 예외 처리(Exception handling)
4. 데이터 검증(Data Validation)

4. 확장성

PNG 다운로더와 웹모니터(웹을 모니터링하여 저작권이나 상표권이 침해되는 일을 막는 모듈)

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

1. 중복 컨텐츠
   웹 콘텐츠의 약 30% 가량은 중복
   해시나 체크섬(check-sum)을 사용하면 중복 콘텐츠를 보다 쉽게 탐지 가능
2. 거미 덫(Spider Map)
   크롤러를 무한 루프에 빠트리도록 설계한 웹 페이지
   덫을 자동으로 피해가는 알고리즘을 만들기는 매우 어려움
   = 사람이 수작업으로 덫을 확인하고 찾아낸 후에 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두는 것
3. 데이터 노이즈

4단계. 마무리

추가 논의 포인트

1. 서버 측 렌더링(server-side rendering)
많은 웹 사이트가 자바스크립트(Java Script), AJAX 등의 기술을 사용해서 링크를 즉석에서 만들어 내는데, 웹 페이지를 그냥 있는 그대로 다운 받아서 파싱해보면 동적으로 생성되는 링크는 발견할 수가 없게 된다.
-> 동적 렌더링(dynamic rendering) 으로 해결 가능

2. 원치 않는 페이지 필터링

3. 데이터베이스 다중화 및 샤딩

4. 수평적 규모 확장성(horizontal scalability)
수평적 규모 확장성을 달성하는 데에 가장 중요한 것은 서버가 상태정보를 유지하지 않도록 하는 것, 즉 무상태(stateless) 서버로 만드는 것이다.

5. 가용성, 일관성, 안정성

6. 데이터 분석 솔루션(analytics)