9장. 웹 크롤러 설계

웹 크롤러

로봇 또는 스파이더 라고 부르며, 검색 엔진에서 널리 쓰이는 기술이다. 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적이다. 몇 개의 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 컨텐츠를 수집하는 방식으로 동작한다.

 

사용 예시

- 검색 엔진 인덱싱: 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스로 만든다.

- 웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모은다.

- 웹 마이닝: 인터넷에서 유용한 지식을 도출해낸다.

- 웹 모니터링: 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링 한다.

 

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

 

기본 알고리즘

1. URL 집합이 입력으로 주어지면, 해당 URL 들이 가리키는 모든 웹 페이지를 다운로드한다.

2. 다운받은 웹 페이지에서 URL 들을 추출한다.

3. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다.

 

 

좋은 웹 크롤러의 조건

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

 

웹 크롤러 구성요소

시작 URL

웹 크롤러가 크롤링을 시작하는 출발점

e.g. 대학 웹사이트를 크롤링한다면, 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL 을 시작 URL 로 사용

 

전체 웹을 크롤링해야 한다면 시작 URL을 고를 때 좀 더 창의적일 필요가 있다.

-> 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직하다.

 

일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략을 쓴다.

• 나라 별로 인기 있는 웹 사이트가 다르다는 점에 착안

 

또는 주제별로 다른 시작 URL 을 사용한다.

• 쇼핑, 스포츠, 건강 등등의 주제별로 세분화하고 그 각각에 다른 시작 URL을 사용

 

미수집 URL 저장소

대부분의 현대적 웹 크롤러는 크롤링 상태를 2가지로 나눠 관리한다.

• 다운로드할 URL
• 다운로드된 URL

이 중 다운로드할 URL 을 저장 관리하는 컴포넌트를 미수집 URL 저장소라고 한다. (= FIFO 큐)

 

HTML 다운로더

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

 

도메인 이름 변환기

URL 을 IP 주소로 변환하는 절차 수행

 

콘텐츠 파서

웹 페이지를 다운로드 후 파싱과 검증 절차를 수행한다.

• 이상한 웹 페이지는 문제 유발 가능 및 저장 공간 낭비.
• 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지므로 독립된 컴포넌트로 만드는 걸 권장

 

중복 컨텐츠인가

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

따라서 같은 컨텐츠를 여러 번 저장하지 않도록 하기 위한 자료 구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄인다. -> 이때 효과적인 방법은 웹 페이지의 해시 값을 비교하는 것

 

콘텐츠 저장소

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

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

• 데이터의 양이 많은 경우 대부분의 콘텐츠를 디스크에 저장
• 인기 있는 콘텐츠만 메모리에 두어 접근 지연시간을 줄이는 방법

 

URL 추출기

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

 

URL 필터

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

 

이미 방문한 URL인가

같은 URL을 여러 번 처리하는 일을 방지하여 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지한다.

이때 사용하는 자료 구조로는 블룸 필터나 해시 테이블이 널리 사용된다.

 

URL 저장소

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

 

 

웹 크롤러 작업 흐름

 

1. 시작 URL들을 미수집 URL 저장소에 저장

2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져옴

3. HTML 다운로더는 도메인 이름 변환기를 사용해 URL 의 IP 주소를 알아내고, 해당 IP 주소로 접속해 웹 페이지를 다운

4. 콘텐츠 파서는 다운된 HTML 페이지를 파싱해 올바른 형식을 갖춘 페이지인지 검증

5. 콘텐츠 파싱과 검증이 끝나면 중복 컨텐츠인지 확인

6. 중복 컨텐츠인지 확인하기 위해, 해당 페이지가 이미 저장소에 있는지 확인

   6-1. 이미 저장소에 있는 컨텐츠면 처리하지 않고 버린다.

   6-2. 저장소에 없는 콘텐츠면 저장소에 저장 후 URL 추출기로 전달

7. URL 추출기는 해당 HTML 페이지에서 링크를 골라낸다.

8. 골라낸 링크를 URL 필터로 전달한다.

9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달한다.

10. 이미 처리한 URL인지 확인하기 위해 URL 저장소에 보관된 URL 인지 살핀다. 이미 저장된건 버림

11. 저장소에 없는 URL은 URL 저장소에 저장 및 미수집 URL 저장소에도 전달

 

 

DFS / BFS

웹은 유향 그래프(directed graph)와 같다.

• 노드 = 페이지
• 엣지 = URL

따라서 크롤링 프로세스는 유향 그래프를 엣지를 따라 탐색하는 과정이다.

 

보통은 BFS 방식을 이용하여 탐색하는데, 다음과 같은 두 가지 문제점이 있다.

 

한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다.

• 같은 호스트에 속한 많은 링크를 다운받게 되면서, 대상 서버는 수많은 요청으로 과부하에 걸리게 될 수 있다. 
• 이러한 크롤러는 예의 없는(impolite) 크롤러로 간주된다.

 

URL 간 우선순위가 따로 없다.

• 처리 순서에 있어 모든 페이지를 공평하게 대우한다.
• 하지만 모든 웹 페이지가 같은 수준의 품질, 중요성을 갖지는 않는다.
• 따라서 페이지 순위, 사용자 트래픽 양, 업데이트 빈도 등 여러 척도에 비추어 우선순위를 구별하는 것이 온당하다.

 

미수집 URL 저장소

예의

수집 대상 서버로 짧은 시간 안에 너무 많이 요청을 보내는 것은 삼가야 하는데, 이는 무례한 일이며, 때로는 Dos 공격으로 간주되기도 한다.

 

지켜야 할 원칙은, 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청하는 것

이를 지키기 위해서는 같은 웹 사이트의 페이지를 다운받는 태스크는 시간차를 두고 실행하도록 하면 된다.

그러려면 아래와 같이 웹 사이트의 호스트명과 다운로드를 수행하는 작업 스레드(worker thread) 사이의 관계를 유지해야 한다. 

각 다운로드 스레드는 별도 FIFO 큐를 가지고 있어서, 해당 큐에서 꺼낸 URL만 다운로드 해야 한다.

• 큐 라우터: 같은 호스트에 속한 URL 은 언제나 같은 큐로 가도록 보장하는 역할
• 매핑 테이블: 호스트 이름과 큐 사이의 관계를 보관하는 테이블

• FIFO 큐: 같은 호스트에 속한 URL 은 언제나 같은 큐에 보관
• 큐 선택기: 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달하는 역할
• 작업 스레드: 전달된 URL을 다운로드하는 작업 수행. 전달된 URL은 순차적으로 처리될 것이며, 작업들 사이에는 일정한 지연시간을 둘 수 있다.

 

우선순위

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

• 순위결정장치: URL을 입력으로 받아 우선순위를 계산
• 큐: 우선순위별로 큐가 하나씩 할당됨. 우선순위가 높으면 선택될 확률도 올라감
• 큐 선택기: 임의 큐에서 처리할 URL을 꺼내는 역할 담당. 순위가 높은 큐에서 더 자주 꺼내도록 프로그래밍

• 전면 큐: 우선순위 결정 과정을 처리
• 후면 큐: 크롤러가 예의 바르게 동작하도록 보증

 

신선도

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

그러나 모든 URL을 재수집하는 것은 많은 시간과 자원을 필요로 하는 작업이므로, 최적화하기 위한 전략을 사용할 수 있다

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

 

지속성 저장장치

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

• 메모리에 모두 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다.
• 디스크에 모두 보관하는 것은 느려서 쉽게 성능 병목지점이 된다.

따라서 절충안으로, 대부분의 URL 은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것이다.

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

 

HTML 다운로더

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

 

Robots.txt

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

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

 

성능 최적화

1. 분산 크롤링

성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법으로, 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다. 이 구성을 위해 URL 공간은 작은 단위로 분할하여, 각 서버는 그 중 일부의 다운로드를 담당

 

2. 도메인 이름 변환 결과 캐시

DNS 는 크롤러 성능의 병목 중 하나 - DNS 요청과 결과 받는 작업의 동기적 특성 때문. 보통 10ms ~ 200ms 가 소요된다.

따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고, 크론 잡 등을 돌려 주기적으로 갱신하도록 해 놓으면 성능을 효과적으로 높일 수 있다.

 

 

3. 지역성

크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법

크롤링 서버가 크롤링 대상 서버와 지역적으로 가까운면 페이지 다운로드 시간은 줄어들 것

이러한 지역성은 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용이 가능하다.

 

 

4. 짧은 타임아웃

대상 웹 서버의 대기 시간을 최대 얼마까지로 미리 설정. 그 시간 동안 응답하지 않으면 크롤러는 해당 페이지의 다운로드를 중단하고 다음 페이지로 넘어간다.

 

안정성

• 안정 해시를 사용해 다운로더 서버들에 부하를 분산시켜줄 수 있다. -> 다운로더 서버를 쉽게 추가/삭제 가능
• 크롤링 상태 및 수집 데이터 저장: 장애 발생 시 쉽게 복구 가능
• 예외 처리: 예외가 발생해도 전체 시스템이 중단되지 않고 작업을 이어나갈 수 있도록 함
• 데이터 검증: 시스템 오류를 방지하기 위한 중요 수단

 

확장성

새로운 형식의 컨텐츠를 쉽게 지원할 수 있도록 신경써야 함

 

 

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

중복 컨텐츠: 해시나 체크섬을 사용해 탐지

 

거미 덫: 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지

• URL의 최대 길이를 제한해 회피 가능
• 하지만 모든 종류의 덫을 피하는 만능 방법은 없어서, 사람이 수작업으로 덫을 확인해 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두어야 한다.

 

데이터 노이즈

크롤러에게 도움이 되지 않으므로 가능하다면 제외시키기 

e.g. 광고, 스크립트 코드, 스팸 URL 등