9장. 웹 크롤러 설계

 

웹 크롤러는 로봇 또는 스파이더라고 부른다.

 

웹 크롤러 사용 용도

• 검색 엔진 인덱싱: 크롤러의 가장 보편적인 사례. 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. 구글 봇은 구글 검색 엔진이 사용하는 웹 크롤러다.
• 웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차. 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙하고 있다.
• 웹 마이닝: 웹 마이닝을 통해 인터넷에서 유용한 지식을 도출해 낼 수 있다. 유명 금융 기업들이 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아낸다.
• 웹 모니터링: 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다. 디지마크 사는 웹 크롤러를 사용해 해적판 저작물을 찾아내서 보고한다.

---

문제 이해 및 설계 범위

기본적인 크롤러 알고리즘

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

이처럼 단순하고 크롤러는 동작하지 않는다.

 

좋은 크롤러 특성

면접관과 클로러 기능 요구사항을 명확히하고, 좋은 웹크롤러가 만족시키는 특성도 주의하자.

• 규모의 확장성: 웹에는 수십억 개의 페이지가 존재하는데, 병행성을 활용하면 효과적으로 웹 크롤링을 할 수 있다.
• 안정성: 웹은 함정으로 가득하기 때문에 비정상적 입력이나 환경(악성 코드, 응답 없는 서버)에 잘 대응해야한다.
• 예절: 수집 대상 웹 사이트에 짧은 시간동안 많은 요청을 보내면 안 된다.
• 확장성: 새로운 형태의 콘텐츠를 지원하기 쉬워야 한다. 이미지 파일도 크롤링하고 싶다고 새로 설계하면 곤란하다.

 

개략적 규모 추정

면접관에게 질문하여 합의한 내용.

• 매달 10억 개의 웹 페이지 다운로드
• QPS(Queries Per Second) = 10억 / 30일 / 24시간 / 3600초 = 400 페이지 / 초
• 최대(Peak) QPS= 2 * QPS = 800
• 웹 페이지의 크기 평균은 500k
• 10억 페이지 * 500k = 500TB/월
• 5년간 보관하면 500TB * 12 개월 * 5 년 = 30 PB

---

개략적 설계안

컴포넌트들이 어떤 기능을 수행하는지 살펴보자.

시작 URL 집합

• 웹 크롤러가 크롤링을 시작하는 출발점
• 가능한 많은 링크를 탐색할수 있도록 URL을 고른다
• 전체 URL공간을 작은 부분집합으로 나누거나 주제별로 다른 URL을 고른다

 

미수집 URL 저장소

• 웹 크롤러는 크롤링 상태를 다운로드할 URL과 다운로드된 URL 두 가지로 나눠 관리한다.
• 다운로드할 URL을 저장하고 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier)라고 한다.
• FIFO(First In First Out) 이라고 생각하면 된다.

 

HTML 다운로더

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

 

도메인 이름 변환기

• 웹 페이지를 다운받으려면 URL을 IP 주소로 변환하는 절차가 필요
• URL에 대응하는 IP 주소를 알아낸다.

 

콘텐츠 파서

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

 

중복 콘텐츠

• 웹 페이지는 29% 정도가 중복이다.
• 자료 구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄인다.
• 간단한 방법은 HTML 문서를 문자열로 비교하는 것이지만, 비효율적이다.
• 효과적인 방법은 해시 값을 비교하는것

 

콘텐츠 저장소

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

 

URL 추출기

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

URL 필터

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

 

이미 방문한 URL

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

 

URL 저장소

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

웹 크롤러 작업 흐름

1. 시작 URL을 미수집 URL 저장소에 저장
2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
3. HTML 다운로더는 도메인 이름 변환기를 사용해서 도메인의 IP주소를 알아내고 웹 페이지를 다운로드
4. 콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증
5. 콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인하는 절차를 진행
6. 중복 콘텐츠인지 확인하기 위해서, 해당 페이지가 저장소에 있는지 확인
   • 저장소에 있는 경우, 처리하지 않고 버린다.
   • 저장소에 없는 경우, URL 추출기로 전달
7. URL 추출기는 HTML 페이지에서 링크를 골라낸다.
8. 골라낸 링크를 URL 필터로 전달
9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달
10. 이미지 처리한 URL인지 확인하기 위해 URL 저장소에서 확인
11. 저장소에 없는 URL은 URL 저장소에 저장하고 미수집 URL 저장소에도 전달.

웹 크롤러 작업 흐름

 

---

상세 설계

컴포넌트에서 사용한 구현 기술을 살펴본다.

• DFS vs BFS
• 미수집 URL 저장소
• HTML 다운로더
• 안정성 확보 전략
• 확장성 확보 전략
• 문제 있는 콘텐츠 감지 및 회피 전략

 

DFS vs BFS

• 웹은 유향 그래프(directed graph)
  • 페이지는 노드(node), 하이퍼링크(URL)은 에지(edge)
• 유향 그래프를 탐색하는 알고리즘은 깊이 우선 탐색법(depth-first search, DFS)와 너비우선탐색(breath-frist search, BFS)를 널리 사용
• 그래프 크기가 클 수록  깊이 가늠이 안되기 때문에 DFS는 좋은 선택이 아닐 가능성이 높다.
• BFS는  FIFO 큐를 사용하는 알고리즘으로 한 쪽에는 탐색할 URL을 집어 넣고, 다른 한쪽은 꺼내기만 한다.
• 해당 방법은 두 가지 문제가 있다.
  1. 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아 간다.
     • 특정 페이지에서 추출한 링크는 내부 링크, 즉 동일한 서버의 다른 페이지를 참조한다.
     • 크롤러는 같은 호스트에 속한 많은 링크를 다운받느라 바쁘게 되고, 병렬로 처리하게 되면 해당 서버는 수많은 요청으로 과부하 걸리게 된다.
     • 이런 크롤러는 예의 없는 크롤러로 간주 된다.
  2. 표준적 BFS 알고리즘은 URL 간에 우선순위를 두지 않는다.
     • 처리 순서에 있어 모든 페이지를 공평하게 대우한다.
     • 페이지 순위, 사용자 트래픽의 양,업데이트 빈도 등 여러 가지 척도에 비추어 처리 우선순위를 구별하는 것이 맞다.

 

미수집 URL 저장소

미수집 URL 저장소를 활용하면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.

 

예의
예의 바른 크롤러를 만드는데 있어서 한 가지 원칙을 지켜야한다.
동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다는 것이다.
 해당 요구사항을 만족시키려면 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다.

 

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

예의

 

 

 

우선순위

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

순위우선결정장치는 URL 우선순위를 정하는 컴포넌트이다.

 

• 순위결정장치: URL을 입력으로 받아 우선순위를 계산
• 큐(f1, ... , fn): 우선순위별로 큐가 하나씩 할당. 우선순위가 높으면 선택될 확률도 올라간다.
• 큐 선택기: 임의 큐에서 처리할 URL을 꺼내는 역할을 담당. 순위가 높은 큐에서 더 자주 꺼내도록 프로그램되어 있다.

우선순위

 

우선순위 + 예의

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

우선순위 + 예의

 

신선도

웹 페이지는 수시로 추가되고, 삭제되고, 변경된다. 데이터의 신섬함을 유지해줘야 한다.

 

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

 

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

• 검색 엔질을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수 억개에 달한다.
• 모두 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직 하지 않다.
• 절충안 방법으로 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것.
• 버퍼에 있는 데이터는 주기적으로 디스크에 기록한다.

 

HTML 다운로더

Robots.txt

• 로봇 제외 프로토콜(Robots.txt)이 있다.
• 웹 사이트가 크롤러와 소통하는 표준적 방법
• 해당 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있다.

 

성능 최적화

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

1. 분산 크롤링
   - 크롤링 작업을 여러 서버에 분산하여 성능을 높이는 방법
   - 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다.
2. 도메인 이름 변화 결과 캐시
   - 도메인 이름 변환기는 크롤러 성능의 병목 중 하나로, DNS 요청을 보내고 결과를 받는 동기적 특성 때문
   - DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡(cron job) 등을 돌려 주기적으로 갱신하도록 하여 성능을 높이기
3. 지역성
   - 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법
   - 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간이 줄어든다.
4. 짧은 타임 아웃
   - 어떤 웹 서버는 응답이 느리거나 아예 응답하지 않는다.
   - 이를 대비하여 미리 최대 얼마나 기다릴지 정해 놓는다.

 

안정성

최적화된 성능뿐 아니라 안정성도 다운로더 설계시 중요하게 고려해야 하는 부분

아래는 안정성을 향상시키기 위한 접근법

 

• 안정 해시: 다운로더 서버에 부하를 분산할 때 적용하는 기술로, 다운로더 서버를 쉽게 추가하고 삭제할 수 있다.
• 클로링 상태 및 수집 데이터 저장: 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적으로 저장 장치에 기록하는 것
• 예외 처리: 에러는 불가피하기 때문에 전체 시스템이 중단되는 일이 없도록 해야한다.
• 데이터 검증: 시스템 오류를 방지하기 위한 중요 방법

 

확장성

새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경써야 한다.

 

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

중복이거나 의미없거나 또는 유해한 콘텐츠를 어떻게 감지하고 차단하는지 살펴보자.

 

• 중복 콘텐츠
  • 해시나, 체크섭을 사용하면 중복 콘텐츠를 쉽게 탐지할 수 있다.
• 거미 덫
  • 크롤러를 무한 루프에 빠드리도록 설계한 웹 페이지
  • 예시) spidertrapexample.com/foo/bar/foo/bar/foo/bar/...
  • 모든 종류의 덫을 피할 수 있는 해결책은 없고, 알고리즘을 만드는 것도 어렵다.
  • 한 가지 방법으로 사람이 수작업으로 덫을 확인하고 URL 필터 목록에 넣는 방법이 있다.

• 데이터 노이즈
  • 콘텐츠가 가치가 없는 광고나 스팸 URL, 스크립트 코드 등이 있다.
  • 가능하면 제외한다.

 

마무리

추가적으로 논의해보면 좋은 것들

• 서버 측 렌더링
  • 많은 웹사이트가 자바스크립트, AJAX 등의 기술을 사용해서 링크를 즉석에서 만들어 낸다.
  • 다운받아서 파싱하면 동적으로 생성되는 링크는 발견할 수 없기 때문에, 파싱하기 전 서버 측 렌더링(동적 렌더링)을 적용하여 해결한다.
• 원치 않는 페이지 필터링
  • 크롤링에 소요되는 자원은 유한하기 때문에 스팸 방지 컴포넌트를 두어 품질이 안 좋거나 스팸성인 페이지는 거른다.
• 데이터베이스 다중화 및 샤딩
  • 해당 기술을 적용하여 데이터 계층의 가용성, 규모 확장성, 안정성이 향상한다.
• 슈평적 규모 확장성
  
  • 수평적 규모 확장을 달성하는데 중요한 것은 서버가 상태정보를 유지하지 않도록 하는 것, 무상태 서버로 만드는 것이다.
• 가용성, 일관성, 안전성
  • 대형 시스템을 만들기 위해 필수적으로 고려해야하는 사항
• 데이터 분석 솔루션
  • 시스템을 세밀하게 조정하기 위해서는 데이터를 수집하고 분석하는 것이 중요하다.