[대규모 시스템 설계 기초] 9장 웹 크롤러 설계

9장은 웹 크롤러(web crawler) 설계에 대해 다룬다.

 

웹 크롤러는 로봇 또는 스파이더라고도 부른다. 검색 엔진에서 널리 쓰는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적이다.

 

크롤러 이용

• 검색 엔진 인덱싱(search engine indexing): 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스(local index)를 만듦
• 웹 아카이빙(web archiving): 나중에 사용할 목적으로 장기 보관하기 위해 웹에서 정보를 모으는 절차
• 웹 마이닝(web mining): 인터넷에서 유용한 지식을 도출해 냄
• 웹 모니터링(web monitoring): 인터넷에서 저작권이나 상표권이 침해되는 사례 모니터링

웹 크롤러의 복잡도는 처리해야 데이터의 규모에 따라 달라지기 때문에 데이터의 규모와 기능들을 알아야 한다.

---

1단계 문제 이해 및 설계 범위 확정

웹 크롤러의 기본 알고리즘은 다음과 같다.

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

요구사항

1. 검색 인덱스 용 크롤러를 설계
2.매달 10억 개의 웹 페이지를 수집
3. 새로 만들어진 웹이나 수정된 웹도 고려
4. 수집한 웹은 5년간 저장
5. 중복된 컨텐츠는 무시

 

크롤러를 구현할 때 다음과 같은 속성을 주의해야한다.

• 규모 확장성: 오늘날 웹은 수십 억 개의 페이지가 존재하므로 병행성(paralleism)을 활용하는 것이 효과적이다.
• 안정성(robustness): 잘못 작성된 HTML, 악성 코드가 붙어 있는 링크 등 비정상적 입력이나 환경에 잘 대응할 수 있어야 한다.
• 예절(politeness): 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안된다.
• 확장성(extensibility): 새로운 형태의 콘텐츠를 지원하기가 쉬워야 한다.

개략적 규모 추정

• 매달 10억 개의 웹 페이지 다운로드
• QPS = 10억 / 30 / 24 / 60 / 60 = 400 페이지/초
• 최대 QPS = 2 * QPS = 800
• 웹 페이지의 크기 평균은 500k 로 가정
• 10억 * 500k = 500TB/월
• 500TB * 12 * 5 = 30PB

---

2단계 개략적 설계안 제시 및 동의 구하기

시작 URL 집합

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

 

전체 웹을 크롤링해야하는 경우에는 크롤러가 가능한 한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직하다.

일반적으로 전체 URL 공간을 작은 부분집합으로 나누거나 주제별로 다른 URL을 사용하는 전략을 사용한다.

미수집 URL 저장소

크롤링 상태는 다운로드할 URL, 다운로드된 URL의 두 가지로 나눠 관리한다.

미수집 URL 저장소는 다운로드할 URL을 관리하는 컴포넌트이고, FIFO 큐로 구현되어 있다.

HTML 다운로더

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

도메인 이름 변환기

웹 페이지를 다운받으려면 URL을 IP 주소로 변환하는 절차가 필요함

콘텐츠 파서

웹페이지를 다운로드하면 저장 공간 낭비를 방지하기 위해 파싱과 검증 절차를 거쳐야 한다.

중복 컨텐츠 검증

웹 페이지의 해시 값을 비교하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄인다.

콘텐츠 저장소

콘텐츠 저장소는 HTML 문서를 보관하는 시스템이다.

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

URL 추출기

URL 추출기는 HTML 페이지를 파싱하여 링크를 골라내는 역할을 한다.

URL 필터

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

이미 방문한 URL

이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료 구조(블룸 필터, 해시 테이블) 사용

URL 저장소

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

웹 크롤러 작업 흐름

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

---

3단계 상세 설계

DFS vs BFS

크롤링 프로세스는 페이지가 노드이고, 하이퍼링크가 엣지인 유향 그래프를 탐색하는 과정이다.

그래프 크기가 클 경우 어느 정도로 깊숙이 가게 될지 가늠하기 어렵기 때문에 DFS를 사용하지 않고 주로 BFS를 사용한다.

 

표준적인 큐를 사용하면 다음과 문제가 발생한다.

• 한 페이지에서 나오는 링크의 상당수는 같은 서버이다. 따라서 서버는 수많은 요청으로 과부하게 걸리게 되고 이러한 크롤러를 '예의 없는(impolite)' 크롤러라 한다.
• 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지 않는다.

미수집 URL 저장소

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

 

예의

웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가하기 위해 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.

 

해당 규칙을 만족하려면 웹 사이트의 호스트명과 다운로드를 수행하는 워커 스레드 사이의 관계를 유지한다.

• 큐 라우터(queue router): 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장하는 역할
• 매핑 테이블(mapping table):  호스트 이름과 큐 사이의 관계를 보관하는 테이블
• FIFO 큐: 같은 호스트에 속한 URL은 언제나 같은 큐에 보관
• 큐 선택기(queue selector): 큐들을 순회하면서 큐에서 URL을 꺼낸후 다운로드하도록 지정된 워커 스레드에 전달하는 역할
• 워커 스레드(worker thread): 전달된 URL을 순차적으로 다운로드하며, 작업들 사이에 delay를 둘 수 있음

우선순위

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

 

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

 

큐에 URL을 저장하기 전에 prioritizer 를 거치도록 설계한다.

• prioritizer: 입력받은 URL을 우선순위 계산
• queue: 우선순위별로 큐가 하나씩 할당됨
• queue selector: 임의 큐에서 처리할 URL을 꺼내는 역할, 순위가 높은 큐에서 더 자주 꺼내도록 프로그래밍되어 있다.
• front queue: 우선순위 결정 과정을 처리한다.
• back queue: 크롤러가 예의 바르게 동작하도록 보증한다.

prioritizer 설계

신선도

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

 

재수집 작업을 최적화하기 위한 전략은 다음과 같다

• 웹 페이지의 변경 이력(upate history) 활용
• 우선순위가 높은 페이지는 좀 더 자주 재수집

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

검색 엔진 인덱싱 용 크롤러는 수억 개의 URL을 처리해야 한다.

 

따라서 메모리와 디스크를 둘 다 활용하여 대부분의 URL은 디스크에 저장하지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두어 주기적으로 디스크에 기록한다.

HTML 다운로더

Robots.txt

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

 

이 파일에는 크롤러가 수집해도 되는 페이지 목록이 저장되어 있고, 크롤러는 해당 파일에 나열된 규칙을 먼저 확인한다.

 

robots.txt 파일들은 거푸 다운로드하는 것을 피하기 위해, 이 파일은 주기적으로 다시 다운받아 캐시에 보관한다.

 

성능 최적화

1. 분산 크롤링: 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산
2. 도메인 이름 변환 결과 캐시: DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관하여 cron job 등을 돌려 주기적으로 갱신
3. 지역성: 서버를 지역별로 분산
4. 짧은 타임아웃: 응답이 느리거나 응답하지 않는 서버를 대비하기 위해 wait time 을 설정

안정성

• 안정 해시(consistent hashing): 크롤링 서버을 분산할 때 적용
• 크롤링 상태 및 수집 데이터 저장: 서버 장애를 대비하여 수집된 데이터를 지속적으로 저장장치에 기록
• exception handling
• data validation

확장성

시스템은 항상 진화하기 때문에 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 설계해야 한다.

 

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

1. 중복 컨텐츠: 해시나 체크섬을 사용하여 중복 콘텐츠 탐지
2. 거미 덫: URL 최대 길이를 제한 -> 완벽히 회피하기 어렵기 때문에 URL 필터 목록 활용
3. 데이터 노이즈: URL 필터 목록 활용

🤔 거미 덫(spider trap)이란 ?
크롤러를 무한 루프에 빠지도록 설계한 웹 페이지
ex) example.com/foo/bar/foo/bar/foo 

4단계 마무리

추가적으로 논의하면 좋은 것

• 서버 측 렌더링: 많은 웹 사이트는 자바스크립트, AJAX 등의 기술을 사용해서 링크를 즉석으로 만들기 때문에 페이지를 파싱하기 전에 서버측 렌더링을 적용
• 원치 않는 페이지 필터링: 스팸 방지 컴포넌트
• 데이터베이스 다중화 및 샤딩: 가용성, 규모 확정성, 안정성 향상
• 수평적 규모 확장성: 무상태 서버
• 가용성, 일관성, 안정성: 해당 개념은 대형 시스템을 만들기 위해 필수적으로 고려해야 함
• 데이터 분석 솔루션