개요
로봇(robot) 혹은 스파이더(spider)라고 불리는 웹 크롤러는 검색 엔진에서 널리 쓰이는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주 목적이다.
위 그림처럼 몇 개의 웹 페이지에서 시작하여 그 링크를 따라가면서 새로운 콘텐츠를 수집한다.
웹 크롤러가 이용되는 분야는 다음과 같다.
•
검색 엔진 인덱싱(search engine indexing) : 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스(local index)를 만든다. 구글에서도 이 목적으로 Googlebot이라는 웹 크롤러을 사용한다.
•
웹 아카이빙(web archiving) : 나중에 사용할 목적으로 장기보관하기 위해 웹 크롤러를 통해 웹에서 정보를 모은다. 많은 국립 도서관이 이 목적으로 웹 크롤러를 사용한다.
•
웹 마이닝(web mining) : 웹을 통해 데이터 마이닝(data mining)을 하는 목적으로, 웹에서 데이터를 모아 유용한 지식을 도출해내는 것을 말한다. 유명 금융 기업들이 주주총회 자료나 연차 보고서를 통해 기업의 핵심 사업 방향을 알아내는데 사용한다.
•
웹 모니터링(web monitoring) : 인터넷에서 저자권이나 상표권이 침해되는 사례를 모니터링하기 위해 웹 크롤링을 사용한다. 디지마크(Digimarc)에서 웹 크롤러를 통해 해적판 저작물을 찾아낸다.
이처럼 다양한 목적으로 사용되는 웹 크롤러는, 웹 크롤러가 처리해야하는 데이터 규모에 따라 복잡도가 달라진다. 따라서 우리가 설계해야할 웹 크롤러가 감당해야하는 데이터 규모와 기능을 알아내는 것이 중요하다.
1단계 문제 이해 및 설계 범위 확정
웹 크롤러의 기본 알고리즘은 간단하다.
1.
URL 집합이 입력으로 주어지면 해당 URL들이 가리키는 모든 웹 페이지를 다운로드한다.
2.
다운받은 웹 페이지에서 URL들을 추출한다.
3.
추출된 URL들을 다운로드 할 URL 목록에 추가하고 위 과정을 반복한다.
알고리즘 자체는 이처럼 간단하지만, 엄청난 규모 확장성을 가지는 웹 크롤러를 설계하는 것은 어려운 일이다. 그러니 설계를 진행하기 전에 질문을 통해 요구사항을 알아내고 설계 범위를 좁혀보자.
지원자:이 크롤러의 주된 용도는 무엇인가요? 검색 엔진 인덱스 생성용인가요? 아니면 데이터 마이닝? 아니면 그 외의 다른 용도가 있나요?
면접관: 검색 엔진 인덱싱에 쓰일 것입니다.
지원자: 매달 얼마나 많은 웹 페이지를 수집해야 하나요?
면접관: 10억 개(1bilion)의 웹 페이지를 수집해야 합니다.
지원자: 새로 만들어진 웹 페이지나 수정된 웹 페이지도 고려해야 하나요?
면접관: 그렇습니다.
지원자: 수집한 웹 페이지는 저장해야 합니까?
면접관: 네. 5년간 저장해 두어야 합니다.
지원자: 중복된 콘텐츠는 어떻게 해야 하나요?
면접관: 중복된 콘텐츠를 갖는 페이지는 무시해도 됩니다.
Plain Text
복사
웹 크롤러는 직관적으로 이해하기 쉽지만, 면접관과 속으로는 다른 가정을 하고 있을 수 있다. 그러니 위처럼 질문으로 요구사항을 명확히 하면서, 다음과 같은 속성에 주의를 기울이는 것이 좋다.
•
규모 확장성 : 웹에는 수십~수천억 개의 페이지가 존재하니, 규모를 확장하여 서버들을 통한 병행성을 활용해 효과적으로 웹 크롤링을 할 수 있다.
•
안정성(robustness) : 웹에는 잘못 작성된 HTML, 아무 반응 없는 서버, 장애, 악성 코드가 포함된 링크 등 함정이 많다. 그러니 웹 크롤러는 이런 비정상적인 입력이나 환경에 잘 대응해야한다.
•
예절(politeness) : 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안된다.
•
확장성(extensibility) : 새로운 형태의 콘텐츠를 지원하기 쉬워야 한다. 이미지 파일만 크롤링하다가 동영상 파일까지 크롤링하고 싶을 때, 전체 시스템을 새로 설계해야하 한다면 곤란하다.
개략적 규모 추정
•
매달 10억 개의 웹 페이지를 다운로드한다.
•
QPS = 10억 / 30일 / 24시간 / 3600초 = 대략 400페이지/초
•
최대(Peak) QPS = 2 * QPS = 800
•
10억 페이지 * 500KB (웹 페이지의 평균 크기 500KB로 가정) = 500TB/월
•
5년간 보관하면 500TB * 12개월 * 5년 = 30PB의 저장용량이 필요
2단계 개략적 설계안 제시 및 동의 구하기
웹 크롤러에 대한 선행 연구를 참고하여 위와 같은 설계안을 제시했다고 가정하고, 위 다이어 그램에서 각각 컴포넌트가 어떤 기능을 수행하는지 살펴보자.
시작 URL 집합
시작 URL 집합은 웹 크롤러가 크롤링을 시작하는 출발점이다. 예시로 대학 웹 사이트를 크롤링하는 가장 직관적인 방법은 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 사용하는 것이다.
전체 웹을 크롤링 해야하는 경우에는 시작 URL은 가능한 많은 링크를 탐색할 수 있도록 고르는 것이 바람직하다. 일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략을 사용하고, 또 다른 방법으로는 주제별로 다른 시작 URL을 사용하는 것이다. 시작 URL을 고르는 것에는 정답은 없으니, 면접관에게 의도만 명확하게 전달하도록 하자.
미수집 URL 저장소
대부분의 현대적인 웹 크롤러는 크롤링 상태를 다운로드 해야하는 URL, 다운로드 된 URL 두 가지로 나누어 관리한다. 이 중 다운로드 해야하는 URL을 저장 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier)라고 부른다. 미수집 URL 저장소는 FIFO의 큐로 동작한다.
HTML 다운로더
HTML 다운로더는 미수집 URL 저장소에서 URL을 받아 인터넷에서 웹 페이지를 다운로드하는 컴포넌트다.
도메인 이름 변환기(DNS)
도메인 이름 변환기는 URL을 IP 주소로 변환하는 컴포넌트이다.
콘텐츠 파서
이상한 웹페이지는 문제를 일으키거나 저장 공간만 낭비하게 만들 수 있기 때문에, 웹 페이지를 다운로드하면 파싱과 검증 절차를 거쳐야 한다. 크롤링이 느려지지 않도록, 이러한 절차를 독립적인 컴포넌트인 콘텐츠 파서를 구현하여 수행한다.
중복 콘텐츠 여부 확인
웹에 공개된 연구 결과에 따르면 29% 가량의 웹 페이지 콘텐츠는 중복인데, 이러한 중복 문제를 해결하기 위해 자료 구조를 도입해 중복을 줄이고 데이터 처리 시간을 줄인다. 두 HTML 문서를 비교하는 방법은 웹 페이지의 해시 값을 만들어 비교하는 것이다.
콘텐츠 저장소
콘텐츠 저장소는 HTML 문서를 보관하는 시스템으로, 데이터의 유형이나 크기, 접근 빈도, 데이터의 유효기간 등을 종합적으로 고려해 설계해야한다. 본 설계에서는 콘텐츠는 디스크에 저장하되, 인기있는 콘텐츠를 메모리에 두어 접근 지연시간을 줄이도록 한다.
URL 추출기
URL 추출기는 HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다.
URL 필터
URL 필터는 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록(deny list)에 포함된 URL 등을 크롤링 대상에서 제외시키는 역할을 한다.
이미 방문한 URL 여부 확인
자료구조를 사용해 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적한다. 이를 통해 여러 번 동일한 URL을 크롤링하는 일을 방지하고 서버의 부하를 줄이며 무한 루프에 빠지는 것을 방지한다. 사용하는 자료구조로는 블룸 필터나 해시 테이블이 널리 사용된다.
URL 저장소
이미 방문한 URL을 보관하는 저장소다.
3단계 상세 설계
중요한 컴포넌트와 그 구현 기술을 심도있게 알아보자.
DFS vs BFS
웹은 페이지를 노드로, 하이퍼링크(URL)을 에지(edge)로 보면 유향 그래프로 볼 수 있다. 따라서 웹 크롤링은 이 유향 그래프 탐색하는 과정인데, 그래프 탐색할 때는 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search) 중 선택할 수 있다.
웹 크롤링에서는 웹 페이지가 어디까지 이어지는지(어느 정도 깊이를 가지는지)를 가늠하기 어렵기 때문에 DFS는 좋은 선택이 아닐 가능성이 높다. 때문에 보통 FIFO 큐를 활용해 BFS 방식을 사용한다. 하지만 BFS에는 두 가지 문제점이 있다.
•
하나의 페이지에서 나오는 링크는 상당수 같은 서버로 되돌아간다. 위 그림처럼 위키피디아에서 추출한 모든 링크는 위키피디아의 다른 페이지를 참조한다. 이렇게 수집한 링크들을 병렬로 처리한다면, 위키피디아에는 수많은 요청으로 과부하가 걸리게 만들어 ‘예의 없는 크롤러’로 간주되게 된다.
•
표준적 BFS 알고리즘은 URL 간에 우선순위를 두지 않는다. 처리 순서에 있어 모든 페이지를 공평하게 대우하는데, 사실 모든 페이지가 같은 수준의 품질이나 같은 수준의 중요성을 갖지는 않는다.
미수집 URL 저장소
BFS의 두 가지 문제는 미수집 URL 저장소를 활용하면 쉽게 해결할 수 있다.
예의
웹 크롤러는 수집 대상 서버로 짧은 시간에 너무 많은 요청을 보내는 것을 삼가야 하는데, 너무 많은 요청을 보내는 것은 무례한 일이고 때로는 DoS(Denial-of-Service) 공격으로 간주되기도 한다.
예의바른 크롤러를 만들기 위해서는 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청하는 것이 중요하다. 웹 사이트의 호스트명(hostname)과 작업 스레드의 관계를 유지하여, 같은 웹 사이트의 페이지를 다운받는 태스크는 시간차를 두고 실행하도록 하는 것이다.
•
큐 라우터 : 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장하는 역할
•
매핑 테이블 : 호스트 이름과 큐 사이의 관계를 보관하는 테이블
•
FIFO 큐 : 같은 호수트에 속한 URL은 언제나 같은 큐에 보관
•
큐 선택기 : 큐들을 순회하면서 URL을 꺼내서 다운로드 하도록 지정된 작업 스레드에 전달
•
작업 스레드 : 전달된 URL을 다운로드
우선순위
애플 홈페이지와 애플 제품에 대한 사용자 의견이 올라오는 포럼이 같은 중요도를 갖는다고 보기 어렵다. 크롤링에서도 유용성에 따라 URL의 우선순위를 나누기 위해 페이지랭크(PageRank), 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다. 이러한 URL의 우선순위를 결정하는 작업은 순위결정장치(prioritizer)가 수행한다.
•
순위결정장치 : URL을 입력 받아 우선순위를 계산
•
큐 : 우선순위별로 큐가 하나씩 할당
•
큐 선택기 : 임의 큐에서 처리할 URL을 꺼내는 역할을 담당. 우선순위가 높은 큐에서 더 자주 꺼내도록 프로그래밍
이전의 설계와 같이 구상한다면 아래와 같이 설계될 것이다.
신선도
웹 페이지는 수시로 추가되고 삭제되고 변경된다. 따라서 이미 다운로드 완료된 페이지라도 주기적으로 재수집(recrawl)할 필요가 있다. 이 작업을 최적화하기 위한 전략으로 다음과 같은 것들이 있다.
•
웹 페이지의 변경 이력(update history) 활용
•
우선순위를 활용하여 중요한 페이지는 더 자주 재수집
미수집 URL 저장소를 위한 지속성 저장장치
검색 엔진을 위한 크롤러의 경우 처리해야 하는 URL의 개수는 수억 개에 달한다. 그러니 URL을 모두 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다. 반대로 모두 디스크에 저장하는 것은 성능 병목지점이 되기 쉬워 이 또한 좋지 않다. 대부분의 URL을 디스크에 두고 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 방식의 절충안이 좋다.
HTML 다운로더
HTML 다운로더는 HTTP 프로토콜을 통해 웹 페이지를 내려받는다. 그 전에 로봇 제외 프로토콜(Robot Exclusion Protocol)을 알아볼 필요가 있다.
Robots.txt
로봇 제외 프로토콜이라고 부르는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준적인 방법이다. 해당 파일에 크롤러가 수집해도 되는 페이지 목록이 들어있고, 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야한다.
https ://www.amazon.com/robots.txt에는 다음과 같은 규칙이 나열되어있다.
User-agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/*/reviews
Disallow: /gp/pdp/rss/*/reviews
Disallow: /gp/cdp/member-reviews/
Disallow: /gp/aw/c/r/
Plain Text
복사
성능 최적화
HTML 다운로더를 설계할 때는 설계 최적화도 아주 중요하다. HTML 다운로더에서 성능 최적화 할 수 있는 여러 기법들이 있다.
1.
분산 크롤링
크롤링 작업에서 URL 공간을 작은 단위로 분할하고 여러 서버에 분산하여 성능을 올리는 방법이다.
2.
도메인 이름 변환 결과 캐시
도메인 이름 변환기는 DNS 요청을 보내고 결과를 받는 작업의 동기성 때문에 크롤러 성능 병목 중 하나이다. DNS 처리가 끝나기 전에는 다음 작업을 진행할 수 없는데, DNS 처리는 보통 10ms에서 200ms 정도 걸린다. 따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소를 캐시에 보관해두고, 크론 잡(cron job) 등을 돌려 주기적으로 갱신하도록하여 성능을 높일 수 있다.
3.
지역성
크롤링 서버가 크롤링 대상 서버와 지역적으로 가깝다면 페이지 다운로드 시간이 줄어들기 때문에, 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법이다.
4.
짧은 타임아웃
어떤 웹 서버는 응답이 느리거나 아예 응답하지 않는데, 이런 경우를 걸러내기 위해 타임아웃을 적당히 조절할 필요가 있다.
안정성
HTML 다운로더 설계시 안정성도 중요하게 고려해야한다. 시스템의 안정성을 향상시키는 접근 방법은 다음과 같다.
•
안정 해시 : 다운로더 서버들에 부하를 분산할 때, 안정 해시를 도입하여 다운로더 서버를 쉽게 추가하고 삭제할 수 있다.
•
크롤링 상태 및 수집 데이터 저장 : 장애가 발생한 경우에도 쉽게 복구할 수 있도록, 크롤링 상태와 수집된 데이터를 지속적 저장장치에 기록해두는 것이 바람직하다.
•
예외 처리 : 대규모 시스템에서 에러는 불가피하고 흔히 벌어지는 일인데, 예외가 발생하더라도 전체 시스템이 중단되는 일 없이 작업을 이어나갈 수 있어야 한다.
•
데이터 검증 : 시스템 오류를 방지하기 위한 중요 수단이다.
확장성
새로운 형태의 콘텐츠가 추가되는 일은 언제든 발생할 수 있기 때문에, 크롤러 역시 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 해야한다.
위처럼 새로운 모듈을 끼워 넣어, 새로운 콘텐츠를 지원할 수 있도록 설계할 수 있다.
문제 있는 콘텐츠 감지 및 회피
1.
중복 콘텐츠
웹 콘텐츠의 30% 가량은 중복인데, 해시나 체크섬(check-sum)을 사용해 중복 콘텐츠를 쉽게 탐지할 수 있다.
2.
거미 덫
거미 덫(spider trap)은 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지이다.
spidertrapexample.com/foo/bar/foo/bar/ foo/bar/…
이처럼 무한히 깊은 디렉토리 구조를 포함하는 링크가 있는 경우가 대표적이다. 이는 URL의 최대 길이를 제한하면 회피할 수 있다.
모든 종류의 덫을 피하는 만능 해결책은 없지만, 일반적으로 이런 덫은 엄청나게 많은 웹 페이지를 가지고 있기 때문에 어렵지 않게 알아낼 수 있다. 하지만 이를 자동으로 피해가는 알고리즘을 만들어내는 것은 까다로운 일이라, 사람이 직접 덫을 확인하고 찾아낸 후 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두어야 한다.
3.
데이터 노이즈
광고나 스팸, 스크립트 코드 등 어떤 콘텐츠는 거의 가치가 없는데, 이런 경우도 가능하면 제외해야 한다.
4단계 마무리
우리는 좋은 크롤러가 갖춰야할 특성인 규모 확장성, 예의, 확장성, 안정성을 알아보았다. 시간이 허락한다면 면접관과 다음의 내용들도 추가로 논의해보는 것이 좋다.
•
서버 측 렌더링(server-side rendering) : 많은 웹사이트가 자바스크립트나 AJAX 등의 기술을 사용해 즉석에서 링크를 만들어 낸다. 그러니 웹 페이지를 다운로드받아서 파싱하면 동적으로 생성되는 링크는 발견할 수 없다. 이 문제는 페이지를 파싱하기 전에 서버 측 렌더링(동적 렌더링)을 적용하면 해결할 수 있다.
•
원치 않는 페이지 필터링 : 저장 공간 등 크롤링에 소요되는 자원을 아끼기 위해, 스팸 방지 컴포넌트를 두어 품질이 조악하거나 스팸성 페이지를 걸러내는 것이 좋다.
•
데이터베이스 다중화 및 샤딩 : 다중화나 샤딩 같은 기법을 적용하여 데이터 계층의 가용성, 규모 확장성, 안정성을 향상 시킬 수 있다.
•
수평적 규모 확장성 : 대규모 크롤링을 위해서는 다운로드 서버가 수백 혹은 수천 대 필요할 수 있다. 무상태 서버를 만들고 수평적 규모 확장성을 달성하는 것이 중요하다.
•
가용성, 일관성, 안정성 : 대형 시스템에서는 가용성과 데이터 일관성, 안정성이 중요하다.
•
데이터 분석 솔루션 : 시스템의 세밀한 조정을 위해서는, 어느 시스템에서나 데이터를 수집하고 분석하는 것이 중요하다.