웹 크롤러 설계

---

• 웹 크롤러는 로봇, 스파이더라고 부른다.
• 검색엔진에서 널리 쓰는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적
• 이미지나 비디오, PDF 파일 일 수 있음
• 이용사례는 아래와 같다.

  1. 검색 엔진 인덱싱 : 로컬 인덱스를 만듬
  2. 웹 아카이빙 : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
  3. 웹 마이닝 : 인터넷에서 유용한 지식을 도출해 내는 용도로 사용
  4. 웹 모니터링 : 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링 할 수 있음

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

기본 알고리즘

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

하지만 실제 설계시에는 고려할 사항이 무지 많다. 예를 들면, 주된 용도, 목표로 하는 웹 페이지 정도, 저장기간 등등

실제 설계 과정에서 고려사항

1. 규모 확장성

웹은 엄청나게 많고 거대한 양의 데이터가 존재하기 때문에 병행성을 활용해서 효과적으로 크롤링을 하면 좋다.

2. 안정성 (Robustness)

웹은 여러가지 함정으로 존재한다. 예를 들면 잘못된 HTML, 장애, 악성코드, 무응답 등이 존재한다. 따라서 각 케이스에 대해서 잘 대응 할 수 있어야 한다.

3. 예정 (Politeness)

짧은 시간 동안 너무 많은 요청을 보내면 안 된다.

4. 확장성 (Extensibility)

새로운 형태의 콘텐츠를 지원하기 쉬워야 함.

개략적 규모의 추정

• 매달 10억 개의 웹 페이지를 다운 받는다고 가정
• QPS = 400 page / s 로 추정 가능
• 최대 800 이고, 평균적으로 500 페이지라고 가정
• 웹 페이지 크기가 500k이라고 한다면 ~ 5년 보관시 넉넉하게 30 PB 의 저장 용량이 필요되는 것으로 추측

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

고려 사항은 아래와 같음

시작 URL 집합

• 시작 URL 집합은 웹 크롤러가 크롤링을 시작하는 출발점이다.
• 해당 페이지에서 부터 링크를 가져와서 점차 다운로드 페이지 주소를 확대해가는 만큼, 첫 페이지를 좀 더 창의적으로 선정할 필요가 있다.
• 나라나 지역과 관련해서 URL을 설정할 수도 있고, 스포츠 건강 등등의 주제별로 세분화해서 그 각각에 다른 시작 URL을 사용할 수 있다.

미수집 URL 저장소

• 대부분의 현대적인 웹 크롤러는 (1) 다운로드 할 URL (2) 다운로드 된 URL 로 나눠서 관리한다.
• 이 중 (1) 를 미수집 URL 저장소라고 한다.

HTML 다운로더

• 웹 페이지를 다운로드 하는 컴포넌트 이다.

도메인 이름 변환기

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

콘테츠 파서

• 웹 페이지를 다운로드 하면 파싱과 검증 절차를 거쳐야 한다. 이상한 웹 페이지는 문제를 일으킬 수 있는데다 저장공간만 낭비하게 된다.

중복 콘텐츠인지 확인

• 자료구조를 도입해서 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄이는 방식과 같이 최대한 줄이는 것이 효과적이다.
• 대표적으로 웹 페이지의 해시 값을 비교하는 방법이 있다.

콘텐츠 저장소

• HTML 문서를 보관하는 시스템이다.
• 저장소를 구현하는 데 쓰일 기술을 고를 때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효기간 등을 종합적으로 고려할 필요가 있다.
• 예를 들어 데이터 양이 너무 많은 경우 디스크에 저장하고, 인기있는 콘텐츠는 메모리에 두어 접근 지연 시간을 줄일 것이다.

URL 추출기

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

URL 필터

• 특정 콘텐츠 타입이나 파일 확장자를 갖는 URL 이라던지 등등 오류가 날만한 URL 들을 제거하는데 사용한다.

이미 방문한 URL인지 확인

• 자료구조를 활용하여 URL이 이미 방문한 적이 있는지 확인하는 절차이다.

URL 저장소

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

작업 흐름

3단계 - 상세설계

DFS VS BFS

• 깊이 우선 탐색 (DFS) : 완전 탐색의 한 종류로써, stack에 구현체를 넣어서 완전 탐색 하는 알고리즘
• 너비 우선 탐색 (BFS) : queue에 구현체를 넣고, 완전 탐색하는 알고리즘
• URL을 방문하는 것에 있어서 둘중 어떤 완전탐색을 활용할지 고려해본다.
• 두가지 문제점이 존재한다

  1. 같은 페이지를 또 접속하는 문제 (impolite함)
  2. 우선순위가 고려되지 않는다 (page rank, 사용자 트래픽 양, 업데이트 빈도 등 여러가지 척도 고려)

미수집 URL 저장소

• 위 2가지 문제를 해결하기 위한 방법이다.
• 앞으로 다운로드를 해야할 URL을 보관하는 장소이다.

예의

• 수집 대상 서버로 짧은 시간에 너무 많은 요청을 보내면 Denial of Service로 취급받기도 한다.
• 호스트명과 다운로드를 수행할 작업 스레드 사이의 관계를 유지하면 된다.

큐 라우터

• 같은 호스트에 속한 URL은 언제나 같은 큐에 가도록 보장한다

매핑 테이블

• 호스트 이름과 큐 사이의 관계를 보관하는 테이블

큐 선택기

• 큐 선택기 들은 큐를 순회하면서 큐에서 URL을 꺼내서 다운로드를 진행한다

작업 스레드

• 전달된 URL을 다운로드 하는 작업을 수행한다.

우선순위

• 유용성에 따라 URL의 우선순위를 나누는 것이 좋다.
• 페이지 랭크, 트래픽 양, 갱신 정도 등 다양한 척도를 사용할 수 있다.

순위 결정 장치

• URL을 입력받아 우선순위를 계산한다

큐

• 우선 순위별로 큐가 하나씩 할다오딘다. 우선순위가 높은 큐에서 더 자주 꺼내도록 프로그램 한다.

큐 선택기

• 임의 큐에서 처리할 URL을 꺼내는 역할을 담당한다. 순위가 높은 큐에서 더 자주 꺼낸다.

전면큐와 후면큐

HTML 다운로더

• HTTP 프로토콜을 통해 웹 페이지를 내려 받는다

• Robots.txt

  웹 사이트가 크롤러와 소통하는 표준적인 방법이다.
  크롤러가 수집해도 되는 페이지 목록들이 들어있다. 따라서 웹 사이트를 긁어가지 전에 크롤러는 해당 파일에 나열된 규칙을 먼저 확인한다.

성능 최적화

• 분산 크롤링을 이용한 성능 향상

• 도메인 이름 변환 결과 캐시(IP 주소를 캐시함으로써 병목현상을 해결)

• 크롤링 작업을 수행하는 서버를 지역별로 분산하여, 도메인 해당 서버와 가까운 곳에 설치해서 속도 개선

• 짧은 타임 아웃 (응답대기시간) 설정

• 안정성 : 안정해시기술을 통해 다운로더 서버를 쉽게 추가하고 삭제 + 크롤링 상태 및 수집 데이터들을 중앙 서버 또는 스케일 아웃한 서버에 저장해서 쉽게 복구 할 수 있도록 함 + 자세한 예외처리 + 데이터 검증

• 확장성을 고려하여 설계한다. 웹 페이지 트렌드가 변하거나 시스템 변경등을 고려해서 각 구현 기능별 컴포넌트를 잘 설계한다.

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

• 중복 컨텐츠
• 거미 덫 : 무한 루프 빠지지 않도록 설계한다.
• 데이터 노이즈 (광고, 스팸.. 등)

4단계 - 마무리

추가 고려사항은 아래와 같다.

• 서버 측 렌더링
• 원치 않는 페이지 필터링
• 데이터 베이스 다중화 및 샤딩
• 수평적 규모 확장성