9장. 웹 크롤러 설계

개요

웹 크롤러란?

• 로봇 또는 스파이더라고 불리며 검색 엔진에서 널리 쓰이는 기술로 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적이다.
  • 콘텐츠 : 웹 페이지, 이미나, 비디오 PDF파일일 수 있다.
• 몇 개 웹 페이지에서 시작해서 그 링크를 따라 나가면서 새로운 콘텐츠를 수집
• 크롤러는 다양하게 이용됨
  • 검색 엔진 인덱싱 (search engine indexing) : 크롤러의 가장 보편적인 용례로 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. (구글의 검색 엔진이 사용)
  • 웹 아카이빙 (web archiving) : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차를 말하며 대표적으로 미국 국회 도서관이 크롤러를 돌려 웹 사이트를 아카이빙 하고 있음. (미국 국회 도서관 (US Library of Congress), EU 웹 아카이브)
  • 웹 마이닝 (web mining) : 웹의 폭발적 성장세는 데이터 마이닝없계에 전례 없는 기회로 인터넷에서 유용한 지식을 도출해낼 수 있다. (유명 금융 기업들이 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아내기도 함)
  • 웹 모니터링 (web monitoring) : 크롤러를 사용하면 인터넷이나 저작권이나 상표권이 침해되는 사례를 모니터링 할 수 있다. (디지마크사는 웹 크롤러를 사용해 해적판 저작물을 찾아내 보고함

 

웹 크롤러의 기본 알고리즘

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

 

웹 크롤러의 요구 사항에 대한 만족시켜야 할 속성

• 규모 확장성 : 웹은 거대하므로 병행성을 활용하면 효과적으로 웹 크롤링을 할 수 있다.
• 안정성 (robustness) : 잘못 작성된 HTML, 아무 반응 없는 서버, 장애, 악성 코드가 삽입돼 있는 링크 등의 웹 크롤러는 이런 비정상적인 입력이나 환경에 잘 대응할 수 있다.
• 예절 (politeness) : 크롤러는 수집 대상 웹 사이트에 짧은 시간동안 많은 요청을 보내면 안된다.
• 확장성 (extensibility) : 새로운 형태의 콘텐츠를 지원하기가 쉬워야 한다. 이 때문에 전체 시스템을 새로 설계해야하는 일이 없어야 한다.

 

개략적 규모 추정

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

 

개략적 설계

웹 크롤러에 대한 다이어그램

 

설명

시작 URL 집합

• 웹 크롤러가 크롤링을 시작하는 출발점
  • 예를 들어 어떤 대학 웹 사이트로부터 찾아나갈 수 있는 모든 웹페이지를 크롤링하는 가장 직관적인 방법은 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 사용한다.
• 전체 웹을 크롤링 해야 하는 경우네는 크롤러가 가능한 한 많은 링크를 탐색할 수 있는 URL을 선택해야 하는데 일반적으로 전체 URL 공간을 작은 부분 집합으로 나누는 전략을 사용
  • 지역적인 특색, 나라 별로 인기 있는 웹 사이트가 다르다는 점에 착안
• 주제 별로 다른 URL을 사용
  • URL 공간을 쇼핑, 스포츠 건강 등의 주제별로 세분화하고 그 각각에 다른 시작 URL 사용

 

미수집 URL 저장소

• 대부분 웹 크롤러는 크롤러 상태를 다운로드 할 URL, 다운로드 된 URL로 나눠 관리
• 다운로드할 URL을 저장 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier)라고 부른다.
  • 선입선출 큐 (FIFO Queue)

 

HTML 다운로더

• 인터넷에서 웹 페이지를 다운로드하는 컴포넌트로 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공

 

도메인 이름 변환기

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

 

콘텐츠 파서

• 웹페이지를 다운로드하면 파싱(parsing)과 검증 (validation) 절차를 거쳐야 한다.
  • 문제가 있는 웹 페이지 다운로드 시 저장 공간 낭비가 심하기 때문
• 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤릴 과정이 느려지게 될 수 있어 독립된 컴포넌트로 만듦

 

중복 컨텐츠인가?

• 중복 컨첸츠를 저장하는 문제를 해결하기 위한 자료구조를 도입해 데이터 중복과 처리 시간을 줄인다.
• 웹 페이지의 해시 값을 비교하여 중복 컨텐츠인지 찾아낸다.

 

콘텐츠 저장소

• 콘텐츠 저장소는 HTML 문서를 보관하는 시스템으로 저장소를 구현하는데 쓰일 기술을 고를 때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간 등을 종합적으로 고려해야 한다.
  • 디스크와 메모리를 동시에 사용하는 저장소를 택할 시
    • 데이터 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장
    • 인기있는 콘텐츠는 메모리에 두어 접근 지연 시간을 줄일 것.

 

URL 추출기

• URL 추출기는 HTML 페이지를 파싱하여 링크들을 골라내는 역할로 상대 경로를 전부 절대 경로로 변환
  • 예를 들어 상대경로를 https://en.wikipedia.org를 붙인다.

 

URL 필터

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

 

이미 방문한 URL ?

• 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있는 자료구조 사용
  • 자료구조는 블룸 필터나 해시 테이블이 널리 사용
• 이를 추적하면 같은 URL을 여러 번 처리하는 일을 방지하므로 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있다.

 

URL 저장소

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

 

웹 크롤러 작업 흐름

일련번호를 붙인 다이어그램

 

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

② HTML다운로더는 미수집 URL 저장소에서 URL 목록 조회

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

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

⑤ 콘텐츠 파싱과 검증이 끝나면 중복 콘첸츠인지 확인하는 절차 개시

⑥ 중복 콘텐츠인지 확인하기 위해 해당 페이지가 이미 저장소에 있는지 본다.

   - 이미 저장소에 있는 콘첸츠인 경우 처리하지 않고 버림

   - 저장소에 없는 콘텐츠인 경우 저장소에 저장한 뒤 URL 추출기로 전달.

 

⑦ URL 추출기는 해당 HTML 페이지에서 링크를 골라냄

⑧ 골라낸 링크를 URL 필터로 전달

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

⑩ 이미 처리한 URL인지 확인하기 위해 URL 저장소에 보관된 URL인지 살피고 이미 저장소에 있는 URL은 버린다.

⑪ 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다.

 

상세 설계에서의 구현 기술과 중요한 컴포넌트

DFS와 BSF

• 웹은 유향 그래프와 같다.
  • 페이지는 노드이고 하이퍼링크는 에지
• 크롤링 프로세스는 이 유향 그래프를 에지를 따라 탐생하는 과정으로 DFS와 BFS가 이 그래프 탐색에 널리 사용되는 두가지 알고리즘.
  • DFS(깊이 우선 탐색법, depth-first search은 그래프 크기가 클 경우 어느 정도로 깊숙이 가게될지 가늠하기 어려워 좋은 선택이 아닐 수 있다.)
• BFS (너비 우선 탐색법, breath-first search)는 FIFO큐를 사용하는 알고리즘으로 이 큐의 한쪽으로는 탐색할 URL을 넣고 다른 한쪽으로는 꺼내기만 한다.
  • 문제점
    • 한 페이지에서 나오는 링크의 상당 수는 같은 서버로 되돌아간다.
      • 예를들어 wikipedia.com에서  추출한 모든 페이지에서 추출한 모든 링크는 내부 링크 즉 동일 서버에 다른 페이지를 참조하는 링크로 크롤러는 같은 호스트에속한 많은 링크를 다운받느라 바쁘지는데 병렬로 처리하게 되면 이 서버는 수 많은 요청으로 과부하게 걸림 (이런 크롤러를 보통 예의없는 (impolite) 크롤러로 간주
    • 표준적 BFS 알고리즘은 URL간 우선순위를 두지 않음
      • 페이지 순위, 사용자 트래픽의 양, 업데이트 빈도 등 여러 척도에 비추어 처리 우선순위 구별은 필요하다.

 

미수집 URL 저장소

• BFS문제를 쉽게 해결할 수 있다. 왜냐하면 URL을 저장소는 다운로드할 URL을 보관하는 장소로 이 저장소를 잘 구현하면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.

예의 

• 웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 하는데 너무 많은 요청을 보내는 것은 무례한일이며 DoS 공격으로 간주되기도 한다.
• 예의 있는 웹 크롤러를 만들기 위한 원칙은 동일 웹 사이트에 대해 한 번에 한 페이지만 요청해야 한다.
  • 같은 웹 사이트의 페이지를 다운 받는 태스크는 시간 차를 두고 실행하면 되는데 웹 사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다.
  • 각 다운로드 스레드는 별도 FIFO 큐를 가지고 있어 해당 큐에서 꺼낸 URL만 다운로드 한다. 

예의 있는 웹 크롤러를 구현하기 위한 원칙을 적용한 설계

 

• 큐 라우터 (queue router) : 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장하는 역할을 한다.
• 매핑 테이블 (mapping table) : 호스트 이름과 큐 사이의 관계를 보관하는 테이블 (그림 우측 표 참고)
• FIFO 큐 (b1 ~bn) : 같은 호스트에 속한 URL은 언제나 같은 큐에 보관
• 큐 선택기 (queue selector) : 큐 선택기는 큐들을 순회하면서 큐에서 URL을 꺼내 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달하는 역할
• 작업 스레드 (worker thread) : 작업스레드는 전달된 URL을 다운로드하는 작업을 수행하며 전달된 URL은 순차적으로 처리되고 작업들 사이에는 일정한 지연시간(delay)을 둘 수 있다.

 

우선순위

• 유용성에 따라 URL의 우선순위를 나눌 때는 페이지 랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다.
• 순위결정장치(prioritizer)는 URL을 우선순위를 정하는 컴포넌트로 아래 그림은 URL 우선순위를 고려하여 변경한 설계를 보여준다.

• 순위결정장치 (prioritizer) : URL을 입력으로 받아 우선순위 계산
• 큐 (f1 ~ fn) : 우선순위별로 큐가 하나씩 할당
• 큐 선택기 : 임의 큐에서 처리할 URL을 꺼내는 역할 담당. 순위가 높은 큐에서 더 자주 꺼내도록 프로그래밍 되어 있음

전체 설계

 

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

 

신선도

• 웹 페이지는 수시로 추가되고, 삭제되고, 변경되기 때문에 데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집 할 필요가 있다.

• 모든 URL을 재수집하는 것은 많은 시간과 자원이 필요한 작업으로 이 작업을 최적화 하기 위한 전략이 있다.
  • 웹 페이지의 변경 이력을 활용
  • 우선순위를 활용하여 중요한 페이지는 좀 더 자주 재수집

 

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

• 검색 엔진을 위한 크롤러는 처리해야하는 URL의 수가 너무 많아 이 모든 것을 메모리에 보관하는 것은 안정성이나 규모확장성 측면에서 효율적이지 않다. 
• 디스크에 저장하는 방법도 있지만 성능에 지장이 생겨 느려질 수 밖에 없다.
• 대부분의 URL을 디스크에 두지만 IO비용을 줄이기 위해 메모리 버퍼에 큐를 두어 버퍼에 있는 데이터는 주기적으로 디스크에 기록하는 절충안을 우선 선택.

 

HTML 다운로더

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

로봇 제외 프로토콜 (Robot Exclusion Protocol)

• Robots.txt
  • 로봇 제외 프로토콜이라고도 부른다.
  • 크롤러와 소통하는 표준적인 방법이다.
  • 이 파일에는 크롤러가 수집해도 되는 페이지 목록들이 들어 있어 웹 사이트를 긁어 가기 전 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 한다.
  • Robots.txt파일을 거푸 다운로드 하는 것을 피하기 위해 이 파일은 주기적으로 다운받아 캐시에 보관한다.
  • 이 파일은 아래와 같은 규칙이 나열되어 있다고 하면 Creatorhub같은 디렉터리의 내용은 다운 받을 수 없다는 것을 의미한다.

User-agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/*/reviews
Disallow: /gp/cdp/rss/*/reviews
Disallow: /gp/cdp/member-reviews
Disallow: /gp/aw/c r/

 

성능 최적화

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

1. 분산 크롤링

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

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

• 도메인 이름 변환기는 DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문에 크롤러 성능의 병목 중 하나이다.
• DNS 조회 결과를 캐시해 두었다가 크론 잡으로 주기적으로 IP와 도메인 이름을 갱신하여 사용하면 성능을 높을 수 있다.

 

3. 지역성

• 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법.
• 지역적으로 가까우면 페이지 다운로드 시간이 줄어들고, 이는 크롤서버, 캐시, 큐, 저장소 등 대부분 컴포넌트에 적용 가능

 

4. 짧은 타임아웃

• 응답 시간이 긴 웹서버는 최대 얼마나 기다릴지 타임아웃을 지정해두어 설정해놓은 시간 동안 응답하지 않으면 크롤러는 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어간다.

 

안정성

• 안정 해시 (consistent ahshing) : 다운로더 서버들에 부하를 분산할 때 적용 가능한 기술로 다운로더 서버를 쉽게 추가하고 삭제할 수 있다.
• 크롤링 상태 및 수집 데이터 저장 : 장애가 발생해도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적 저장장치에 기록해 둔다. 저장된 데이터를 로딩하고 나면 중단되었던 크롤링을 쉽게 재시작할 수 있다.
• 예외처리(exception handling) : 대규모 시스템에서 에러는 불가피 하므로 예외 발생 시 전체 시스템이 중단되는 일 없이 그 작업을 계속 이어나갈 수 있게 해야한다.
• 데이터 검증(data validation) : 시스템 오류를 방지하기 위한 중요 수단 가운데 하나이다.

 

확장성

• 진화, 발전되지 않는 시스템은 없으므로 새로운 기능이 쉽게 추가될 수 있게 설계해야 한다.
• 아래 그림은 확장성을 고려한 설계 구조이다.

 

• PNG 다운로더는 PNG 파일을 다운도르하는 플러그인 모듈이다.
• 웹모니터는 웹을 모니터링하여 저작권이나 상표권이 침해되는 일을 막는 모듈이다.

 

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

• 중복이거나 의미 없는, 유해한 콘텐츠를 감지하고 시스템으로 부터 차단하는 방법

1. 중복 콘텐츠

• 해시나 체크섬을 사용하여 중복 콘텐츠를 쉽게 탐지한다.

 

2. 거미덫

• 크롤러를 무한 루프에 빠뜨리도록 설계한 웹페이지로 이런 URL은 최대 길이를 제한하면 회피할 수 있다.
• 하지만 가능한 모든 종류의 덫을 피할 수 있는 만능 해결책은 없다.
• 알아내는 것은 어렵지 않으나 기이할 정도로 많은 웹페이지를 가지고 있는 것이 일반적이다.
• 사람이 수작업으로 덫을 확인하고 찾은 후 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두는 방법이 있다.
• 거미 덫 URL의 예
  • spidertrapexample.com/foo/bar/foo/bar...

 

3. 데이터 노이즈

• 광고나 스크립트 코드, 스팸 URL같은 콘텐츠는 가치가 없는데 이런 콘텐츠는 크롤러에게 도움이 되지 않으므로 가능하다면 제외해야 한다.

 

 

마무리

• 서버 측 렌더링 : 많은 웹 사이트가 자바스크립트나 ajax 등의 기술을 사용해서 링크를 즉석에서 만들어내는 동적 URL은 발견할 수 없다. 이는 페이지를 파싱하기 전 서버 측 렌더링(동적 렌더링)을 적용하면 해결할 수 있다.
• 원치 않는 페이지 필터링 : 저장공간 등 크롤링에 소요되는 자원은 유한하기에 스팸 방지 컴포넌트를 두어 품질이 조악하거나 스팸성인 페이지는 걸러내면 좋다.
• DB다중화 및 샤딩 : 다중화나 샤딩 같은 기법 적용 시 데이터 계층의 가용성, 규모 확장성, 안정성이 향상된다.
• 수평적 규모 확장성 : 대규모의 크롤링을 위해 다운로드를 실행할 서버가 수백 혹은 수천 대 필요하게 될 수 있으니 서버가 상태 정보를 유지하지 않는 무상태 서버로 만든다.
• 가용성, 일관성, 안정성 : 성공적인 대형 시스템을 만들기 위한 필수적 요소이다.
• 데이터 분석 솔루션 : 데이터를 수집하고 분석하는 것은 어느 시스템에서나 중요하다. 시스템을 세밀히 조정하기 위해서는 이런 데이터와 그 분석 결과가 필수적이기 때문이다.