대규모 시스템 설계 기초 - 9. 웹 크롤러 설계

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

크롤러는 다양하게 이용된다.

• 검색 엔진 인덱싱
  • 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스 생성
• 웹 아카이빙
  • 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
• 웹 마이닝
  • 인터넷에서 유용한 자료를 도출 (주주 총회 자료 or 연차 보고서 저장 등)
• 웹 모니터링
  • 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링

 

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

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

요구사항

정성적 측면

• 규모 확장성 : 웹의 규모는 무척 거대하므로 (수십억개 이상의 페이지가 있다) parallelism을 잘 활용할 수록 효과적인 크롤링이 가능할 것이다
• 안정성 : 웹은 잘못 작성된 HTML, 무반응 서버, 악성 코드 등이 다양하게 숨겨져 있다
• 예절 : 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안 된다.
• 확장성 : 새로운 형태의 컨텐츠를 지원하기 쉬워야 한다

규모 측면

• 매달 10억개의 웹 페이지를 다운로드 한다 (초당 400 페이지 정도로 최대 QPS는 그 2배인 800 정도이다)
• 웹 페이지 크기 평균이 500kb 라면 매달 500TB의 용량이 필요하다
• 크롤링 데이터를 5년간 보관한다면 30PB의 저장 용량이 필요하다

개략적 설계안

• 시작 URL 집합 : 웹 크롤러가 크롤링을 시작하는 출발점
• 미수집 URL 저장소 : 다운로드 할 예정인 URL, FIFO queue라고 생각하면 된다. 자세한 구성은 후술
• 컨텐츠 파서 : 파싱과 검증 절차를 함께 수행한다
• 중복컨텐츠 : 웹에 공개된 연구 결과에 따르면, 29% 가량의 웹 페이지 컨텐츠는 중복이다. 이미 시스템에 저장되어 있는지 알아내는 쉽고 효과적인 방법은 웹 페이지의 해시 값을 비교하는 것이다.
• 이미 방문한 URL : 적절한 DS로는 블룸 필터나 해시 테이블이 널리 사용된다.

상세 설계

DFS vs BFS

웹은 페이지가 node이고 하이퍼링크가 edge인 directed graph와 같다. 이러한 유향 그래프를 탐색하는데 널리 사용되는 방법에는 DFS와 BFS가 있다.

웹 크롤러에서는 DFS가 부적절하다. 웹의 node 깊이가 어느 정도로 깊숙이가게 될지 가늠하게 어려워서다.

따라서 웹 크롤러는 보통 BFS를 사용한다. BFS는 FIFO 큐를 사용하는데 이 구현법에는 2가지 문제가 있다.

1. 특정 페이지에서 링크가 걸려있을때 이 링크는 보통 동일한 domain을 가지게 된다. 이때 링크를 병렬로 처리한다면 특정 domain으로 수많은 요청을 보내게 될 것이다. (고의가 아닌 DDOS 공격을 하는셈)
2. 표준 BFS 알고리즘을 사용하면 URL 간에 우선순위를 두지 않게 된다.

미수집 URL 저장소

미수집 URL 저장소를 활용하면 위와 같은 표준 BFS의 단점을 쉽게 해결할 수 있다. 이 저장소를 잘 구현하면 1) 예의를 갖추면서도 2) URL 사이의 우선순위와 신선도를 잘 구별할 수 있게 된다

아래 그림과 같이 저장소를 그려볼 수 있는데..

(오타가 하나 있다. 순위 결정장채 아래에 후면 큐 선택기가 아니라 전면 큐 선택기이다)

위 그림에서 미수집 URL은 두 단계를 거쳐 실제 수집 절차를 밟게 된다.

1. 전면 큐 선택기 : URL 방문 의 우선 순위를 결정
   1. f1 ~ fn은 우선순위를 구분한다
2. 후면 큐 선택기 : 동일한 domain에 너무 잦은 요청이 가지 않도록 핸들링
   1. b1 ~ bn은 도메인을 나타낸다 (b1 : naver.com / b2 : daum.net )
   2. 매핑 테이블은 특정 URL이 어떤 도메인인지를 매핑해준다

이런 미수집 URL 저장소를 위한 지속성 저장장치로는 hybrid approach를 사용할 수 있다.

대부분의 URL은 디스크에 두되 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 방법이다. 버퍼에 있는 데이터는 주기적으로 디스크에 기록할 것이다.

성능 최적화

• 분산 크롤링 : 크롤링 작업을 여러 서버에 분산하는 방식
• DNS cache : DNS 자체에 들리는 시간을 줄이기 위해 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소의 매핑 정보를 내부 시스템에 캐싱하는 것이다.
• 지역성 : 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방식
• 짧은 타임아웃 : 웹의 응답이 느리거나 아예 없는 경우를 대비하기 위해 timeout 시간을 짧게 가져간다

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

• 중복 컨텐츠 : 해시 or 체크섬 등을 사용한다
• 거미 덫 : 가능한 모든 종류의 크롤링 덫을 피할 수는 없다. 한 가지 옵션으로는 사람이 수작업으로 덫을 확인하고 찾아낸 후에 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두는 것이다
• 데이터 노이즈 : 가능하면 제외해야 한다