크롤러의 이용 사례문제 이해 및 설계 범위 확정요구 사항좋은 웹 크롤러의 속성개략적 규모 추정개략적 설계안 제시 및 동의 구하기시작 URL 집합미수집 URL 저장소HTML 다운로더도메인 이름 변환기콘텐츠 파서중복 콘텐츠인가?콘텐츠 저장소URL 추출기URL 필터이미 방문한 URL ? URL 저장소웹 크롤러 작업 흐름상세 설계DFS를 쓸 것인가, BFS 를 쓸것인가미수집 URL 저장소예의우선 순위신선도미수집 URL 저장소를 위한 지속성 저장장치HTML 다운로더Robots.txt성능 최적화안정성확장성문제 있는 컨텐츠 감지 및 회피추가 논의점
크롤러의 이용 사례
- 검색 엔진 인덱싱 : 크롤러의 가장 보편적인 용례로, 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. 일례로 Googlebot 은 구글(Google) 검색 엔진이 사용하는 웹 크롤러다.
- 웹 아카이빙 : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차를 말함. 많은 국립 도서관이 크롤러를 돌려 웹사이트를 아카이빙함
- 웹 마이닝 : 웹의 폭발적 성장세는 데잍 마이닝 업계에 전례 없는 기회,. 웹 마이닝을 통해 인터넷에서 유용한 지식을 도출해 낼 수 있는 것이다. 일례로, 유명 금융 기업들은 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아내기도 함
- 웹 모니터링 : 크롤러를 사용하여 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다.
문제 이해 및 설계 범위 확정
웹 크롤러의 기본 알고리즘은 간단하다
- URL 집합이 입력으로 주어지면, 해당 URL 들이 가리키는 모든 웹페이지를 다운로드한다
- 다운받은 웹 페이지에서 URL들을 추출한다.
- 추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다.
요구 사항
- 검색 엔진 인덱싱에 쓰임
- 매달 10억 개의 웹 페이지를 수집해야 함
- 새로 만들어진 웹 페이지나 수정된 웹페이지도 고려해야 함
- 수집한 웹 페이지는 5년간 저장해두어야 함
- 중복된 콘텐츠를 갖는 페이지는 무시
좋은 웹 크롤러의 속성
- 규모 확장성 : 병행성을 활용하여 수십억 개의 웹 페이지가 존재하는데, 효과적으로 크롤링을 할 수 있다.
- 안정성 : 웹은 함정으로 가득하다. 잘못 작성된 HTML, 아무 반응이 없는 서버, 장애, 악성 코드가 붙어 있는 링크 등이 좋은 예. 크롤러는 이런 비정상적 입력이나 환경에 잘 대응할 수 있어야 한다.
- 예절 : 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안 된다.
- 확장성 : 새로운 형태의 콘텐츠를 지원하기가 쉬워야 한다. 예를 들어, 이미지 파일도 크롤링하고 싶다고 해 보자. 이를 위해 전체 시스템을 새로 설계해야 한다면 곤란할 것
개략적 규모 추정
- 매달 10억 개의 웹 피이즐 다운로드.
- QPS = 10억 / 30일 / 24시간 / 3600초 = 대략 400 페이지/초
- 최대 QPS = 2 * QPS = 800
- 웹 페이지의 크기 평균은 500k 라고 가정
- 10억 페이지 * 500k = 500TB / 월
- 1개월치 데이터를 보관하는 데는 500 TB, 5년간 보관한다고 가정하면 결국 500TB * 12 * 5 = 30PB 의 저장용량이 필요
개략적 설계안 제시 및 동의 구하기
시작 URL 집합
웹크롤러가 크롤링을 시작하는 출발점. 예를 들어, 어떤 대학 웹사이트로부터 찾아 나갈 수 있는 모든 웹 페이지를 크롤링하는 가장 직관적인 방법은 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 쓰는 것
전체 웹을 크롤링해야 하는 경우에는 시작 URL을 고를 때 좀 더 창의적일 필요가 있음. 일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략을 쓴다. 지역적 특색, 나라별로 인기 있는 웹 사이트가 다르다는 점에 착안하는 것. 또 다른 방법은 주제별로 다른 시작 URL을 사용하는 것(쇼핑, 스포츠, 건강 등등의 주제별로 세분화하고 그 각각에 다른 시작 URL을 사용하는 것)
미수집 URL 저장소
대부분의 현대적 웹 크롤러는 크롤링 상태를 다운로드 할 URL, 그리고 다운로드 된 URL의 두 가지로 나눠서 관리한다. 이 중 다운로드 할 URL을 저장 관리하는 컴포넌트를 미수집 URL 저장소라고 부름 (FIFO 큐라고 생각하면 됨)
HTML 다운로더
인터넷에서 웹 페이지를 다운로드하는 컴포넌트. 다운로드 할 페이지의 URL은 미수집 URL 저장소가 제공한다.
도메인 이름 변환기
웹 페이지를 다운받기 위한 URL을 IP 주소로 변환하는 절차를 담당
콘텐츠 파서
웹 페이지를 다운로드 하려면 파싱과 검증 절차를 거쳐야 한다. 이상한 웹 페이지는 문제를 일으킬 수 있는데다 저장 공간만 낭비하게 되기 때문. 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있으므로, 독립된 컴포넌트로 구성
중복 콘텐츠인가?
문자열을 비교하는 것은 가장 간단하지만 비교 대상 문서의 수가 10억개가 넘어가면 느리고 비효율적이게 된다. 효과적인 방법은 웹 페이지의 해시 값을 비교하는 것
콘텐츠 저장소
콘텐츠 저장소는 HTML 문서를 보관하는 시스템. 저장소를 구현하는 데 쓰일 기술을 고를 때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간등을 종합적으로 고려해야 한다.
- 데이터의 양이 너무 많으므로 대부분의 컨텐츠는 디스크에
- 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간 줄이기
URL 추출기
HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다.
URL 필터
URL 필터는 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL 등을 크롤링 대상에서 배제하는 역할을 한다.
이미 방문한 URL ?
이 단계를 구현하기 위해서 이미 방문한 URL 이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료구조를 사용할 것.
해당 자료구조로는 Bloom 필터나 해시 테이블이 널리 쓰인다.
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를 쓸 것인가, BFS 를 쓸것인가
웹 크롤러는 보통 BFS, 즉 너비 우선 탐색법을 사용한다. 그래프 크기가 클 경우 어느 정도로 깊숙이 가게 될지 가늠하기 어려워서다.
BFS 는 FIFO 큐를 사용하는 알고리즘이다. 이 큐의 한쪽으로는 탐색할 URL을 집어넣고, 다른 한쪽으로는 꺼내기만 한다. 하지만 이 구현법에는 다음의 두 가지 문제점이 있다.
- 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다. 결국 크롤러는 같은 호스트에 속한 많은 링크를 다운받느라 바빠지게 되고, 이 때 링크들을 병렬로 처리하게 된다면 위키피디아 서버는 수많은 요청으로 과부하에 걸리게 될 것이다. 이런 크롤러는 보통
impolite 크롤러로 간주된다.
- 표준적 BFS 알고리즘은 URL 간에
우선순위를 두지 않는다. 처리 순서에 있어 모든 페이지를 공평하게 대우한다는 뜻이다. 하지만 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않는다. 그러니 페이지 순위(page rank), 사용자 트래픽의 양, 업데이트 빈도 등 여러 가지 척도에 비추어 처리 우선순위를 구별하는 것이 온당할 것
미수집 URL 저장소
이 저장소를 잘 구현하면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.
예의
웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 한다.
예의 바른 크롤러를 만드는 데 있어서 지켜야 할 한 가지 원칙은, 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다는 것.
- 같은 웹 사이트의 페이지를 다운받는 태스크는 시간차를 두고 실행하도록 하면 됨. 이 요구사항을 만족시키려면 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하고, 각 스레드에서 각 다운로드를 일정 시간을 두고 진행하면 됨
- 큐 라우터 : 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장하는 역할
- 매핑 테이블 : 호스트 이름과 큐 사이의 관계를 보관하는 테이블
- FIFO 큐(b1 ~ bn) : 같은 호스트에 속한 URL은 언제나 같은 큐에 보관된다.
- 큐 선택기 : 큐 선택기는 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드 하도록 지정된 작업 스레드에 전달하는 역할을 한다.
- 작업 스레드 : 작업 스레드는 전달된 URL을 다운로드하는 작업을 수행한다. 전달된 URL은 순차적으로 처리될 것이며, 작업들 사이에는 일정한 지연시간을 둘 수 있다.
우선 순위
애플 제품에 대한 사용자 의견이 올라오는 포럼의 한 페이지가 애플 홈페이지와 같은 중요도를 갖는다고 보기는 어려울 것이다. 크롤러 입장에서는 중요한 페이지 그러니까 애플 홈페이지를 먼저 수집하도록 하는 것이 바람직할 것
유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있을 것
- 순위결정장치 : URL을 입력으로 받아 우선순위를 계산한다.
- 큐 : 우선순위별로 큐가 하나씩 할당되다. 우선순위가 높으면 선택될 확률이 올라간다.
- 큐 선택기 : 임의 큐에서 처리할 URL을 꺼내는 역할을 담당한다. 순위가 높은 큐에서 더 자주 꺼내도록 프로그램되어 있다.
신선도
웹 페이지는 수시로 추가되고 삭제되고 변경된다. 따라서 데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집할 필요가 있다. 그러나 모든 URL을 재수집하는 것은 많은 시간과 자원이 필요한 작업. 최적화하기 위한 전략으로는 아래와 같다.
- 웹 페이지의 변경 이력 활용
- 우선순위를 활용하여 중요한 페이지는 좀 더 자주 재수집
크롤러가 계속적으로 모든 URL을 수집하는 건지? 아님 input을 주고 찾는건지?
미수집 URL 저장소를 위한 지속성 저장장치
검색 엔진을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수억 개에 달함. 그래서 그 모두를 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다.
본 설계안에서는 절충안을 택하여, 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 둔다.버퍼에 있는 데이터는 주기적으로 디스크에 기록
HTML 다운로더
HTML 다운로더는 HTTP 프로토콜을 통해 웹 페이지를 내려 받음
Robots.txt
로봇 제외 프로토콜이라고 부르기도 하는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준적 방법임. 이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어있음
따라서 웹 사이트를 긁어가기 전에 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 한다.
크롤러의 엔진을 설정할 수도 있음. sitemap
성능 최적화
Robots.txt도 중요하지만 HTML 다운로더를 설계할 때는 성능최적화도 아주 중요함
- 분산 크롤링 : 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
- 도메인 이름 변환결과 캐시 : 도메인 이름 변환기는 크롤러 성능의 병목 중 하나. 이는 DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문. 크롤러 스레드 가운데 어느 하나라도 이 작업을 하고 있으면 다른 스레드의 DNS 요청은 전부 블록 된다. 캐시 값 업데이트 위해 정기적으로 크론잡 돌리기 필요.
- 지역성 : 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법. 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간이 줄어들기에
- 짧은 타임아웃: 어떤 웹 서버는 응답이 느리거나 아예 응답하지 않는다. 이런 경우 대기 시간이 길어지면 좋지 않으므로 타임아웃을 줄인다.
안정성
최적화된 성능 뿐 아니라 안정성도 다운로더 설계 시 중요하게 고려해야 할 부분
- 안정 해시 : 다운로더 서버들에 부하를 분산할 때 적용 가능한 기술이다. 이 기술을 이용하면 다운로더 서버를 쉽게 추가하고 삭제할 수 있다.
- 크롤링 상태 및 수집 데이터 저장 : 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적 저장장치에 기록해 두는 것이 바람직하다. 저장된 데이터를 로딩하고 나면 중단되었던 크롤링을 쉽게 재시작할 수 있음
- 예외 처리 : 대규모 시스템에서 에러는 불가피할 뿐 아니라 흔하게 벌어지는 일임. 예외가 발생해도 전체 시스템이 중단되는 일 없이 그 작업을 우아하게 이어나갈 수 있어야 한다.
- 데이터 검증 : 시스템 오류를 방지하기 위한 중요 수단 가운데 하나
확장성
진화하지 않는 시스템은 없기에 이런 시스템을 설계할 때는 새로운 형태의 컨텐츠를 쉽게 지원할 수 있도록 신경 써야 한다.
문제 있는 컨텐츠 감지 및 회피
중복되거나 의미 없는, 또는 유해한 컨텐츠를 어떻게 감지하고 시스템으로부터 차단할지를 살펴본다
- 중복 콘텐츠 : 해시나 체크섬을 사용하면 중복 콘텐츠를 보다 쉽게 탐지할 수 있다
- 거미 덫 : 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지다.
- 가능한 모든 종류의 덫을 피할 수 있는 만능 해결책은 없다. 이런 덫이 설치된 웹 사이트인지를 알아내는 것은 어렵지 않은데, 기이할 정도로 많은 웹 페이지를 가지고 있는 것이 일반적이라서다.
- 하지만 덫을 자동으로 피해가는 알고리즘을 만들어내는 것은 까다롭다.
- 한 가지 방법은 사람이 수작업으로 덫을 확인하고 찾아낸 후에 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두는 것
- 데이터 노이즈 : 광고나 스크립트 코드, 스팸 URL 같은 가치가 없는 컨텐츠는 걸러야 한다.
추가 논의점
서버 렌더링 : 많은 웹사이트가 자바스크립트 등의 기술을 사용해 링크를 즉석에서 만들어 낸다. 그러나 웹 페이지를 그대로 다운받아 파싱하면 그렇게 동적으로 생성되는 링크는 발견할 수 없다.
원치 않는 페이지 필터링 : 스팸 방지 컴포넌트를 두어 품질이 조악하거나 스팸성인 페이지를 걸러내도록 해 두면 좋다.
데이터베이스 다중화 및 샤딩 : 데이터 계층의 가용성, 규모 확장성, 안정성 향상
수평적 규모 확장성 : 대규모의 크롤링을 위해서는 다운로더 서버가 수백 혹은 수천 대가 필요하게 될 수도 있다. 무상태 서버로 만들어야 한다.
가용성, 일관성, 안정성 : 성공적인 대형 시스템을 만들기 위해 필수적으로 고려해야 하는 것들.
데이터 분석 솔루션 : 데이터를 수집하고 분석하는 것은 어느 시스템에게나 중요하다. 시스템을 세밀히 조정하기 위해서는 이런 데이터와 그 분석 결과가 필수적이라서다.