[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 9. 웹 크롤러 설계

• 9장은 웹 크롤러(Web crawler)를 설계에 관련된 내용이다.

1. 크롤러 이용 사례

1. 검색 엔진 인덱싱(search engine indexing)
• 크롤러의 가장 보편적인 용례
• 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스(local index)를 생성
• 예: Googlebot (구글 검색 엔진이 사용하는 웹 크롤러)

2. 웹 아카이빙(web archiving)
• 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
• 만은 국립 도서관이 크롤러를 돌려 웹 페이지를 아카이빙
• 예: 미국 국회 도서관, EU 웹 아카이브 등

3. 웹 마이닝(web mining)
• 인터넷에서 유용한 지식을 도출하기 위해 사용
• 유명 금융 기업들은 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 조사

4. 웹 모니터링(web monitoring)
• 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링
• 예: 디지마크(Digimarc)사의 웹 크롤러 (해적판 저작물 모니터링)

2. 문제 이해 및 설계 범위 확정

2.1. 시스템 요구사항

1. URL 집합이 입력으로 주어지면, 해당 URL들이 가리키는 모든 웹 페이지를 다운로드한다.

2. 다운받은 웹 페이지에서 URL들을 추출한다.

3. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다.

2.2. 개략적 추정

• 크롤러의 주된 용도: 검색 엔진 인덱싱

• 매달 수집할 웹 페이지 수: 10억 개
• QPS: 10억 / 30일 / 24시간 / 3600초 = 대략 400페이지/초
• 최대(Peak) QPS: 2 * QPS = 800
• 새로 만들어진 웹 페이지나 수정된 웹 페이지도 고려
• 중복된 콘텐츠를 갖는 페이지는 무시

• 저장 공간:
• 웹 페이지 크기의 평균: 500k
• 10억 페이지 * 500k = 500TB/월
• 5년간 데이터 보관 시 500TB * 12개월 * 5년 = 30PB 필요

3. 개략적 설계안 제시 및 동의 구하기

3-1. 컴포넌트 역할

1. 시작 URL 집합
• 웹 크롤러가 크롤링을 시작하는 출발점
• 예: 어떤 대학 웹사이트로부터 찾아나갈 수 있는 모든 웹 페이지를 크롤링하는 방법
• 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 쓰는 것
• 예: 전체 웹을 크롤링해야 하는 경우
• 크롤러가 가능한 한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 중요

2. 미수집 URL 저장소
• 대부분의 현대적 웹 크롤러는 크롤링 상태를 두 가지로 나눠서 관리
1. 다운로드할 URL
2. 다운로드된 URL
• 미수집 URL 저장소(URL frontier)은 ‘다운로드할 URL’을 저장 관리하는 컴포넌트
• FIFO 큐로 생각하면 됨.

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

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

5. 콘텐츠 파서
• 웹 페이지를 파싱(parsing)하고 검증(validation)하는 컴포넌트
• 이상한 웹 페이지는 문제를 일으킬 수 있고, 저장 공간만 낭비하기 때문에 검증 필요
• 크롤러 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지기 때문에 독립된 컴포넌트로 둠.

6. 중복 콘텐츠인가?
• 이미 시스템에 저장된 콘텐츠인지 확인
• 두 HTML 문서를 비교하는 방법
1. 문자열 비교: 직관적이지만 느림
2. 해시값 비교: 빠름

7. 콘텐츠 저장소
• HTML 문서를 보관하는 시스템
• 본 설계안에서는 디스크와 메모리를 동시에 사용하는 저장소를 택함.
• 데이터 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장
• 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄임

8. URL 추출기
• HTML 페이지를 파싱해서 링크들을 골라내는 역할
• 상대 경로를 전부 절대 경로로 변환
• 예: <a> 태그 안에 href 속성의 상대 경로들을 모두 아래와 같이 변환
• 예: /about → https://dongho-blog.kro.kr/about

9. URL 필터
• 크롤링 대상에 포함시키지 않을 링크들을 필터링하는 역할
• 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL
• 접속 시 오류가 발생하는 URL
• 접근 제외 목록(deny list)에 포함된 URL

10. 이미 방문한 URL?
• 이미 방문한 적이 있는 URL인지 검사
• 같은 URL을 여러 번 처리하는 일을 방지 → 서버 부하 감소, 시스템 무한 루프 방지
• 자료구조: 해시 테이블 혹은 블룸 필터 사용

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

3-2. 웹 크롤러 작업 흐름

1. 시작 URL들을 미수집 URL 저장소에 저장한다.

2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.

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

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

5. 콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인하는 절차를 개시한다.

6. 중복 콘텐츠인지 확인하기 위해서, 해당 페이지가 이미 컨텐츠 저장소에 있는지 본다.
• 이미 저장소에 있는 콘텐츠의 경우에는 처리하지 않고 버린다.
• 저장소에 없는 콘텐츠인 경우에는 저장소에 저장한 뒤 URL 추출기로 전달한다.

7. URL 추출기는 해당 HTML 페이지에서 링크를 골라낸다.

8. 골라낸 링크를 URL 필터로 전달한다.

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

10. 이미 처리된 URL인지 확인하기 위해서, 해당 URL이 이미 URL 저장소에 있는지 본다.
• 이미 저장소에 있는 URL은 버린다.
• 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다.

4. 상세 설계

• 지금부터는 가장 중요한 컴포넌트와 그 구현 기술을 심도 있게 살펴보자.
• DFS vs BFS
• 미수집 URL 저장소
• HTML 다운로더
• 안정성 확보 전략
• 확장성 확보 전략
• 문제 있는 콘텐츠 감지 및 회피 전략

4.1. DFS vs BFS

• 웹은 유향 그래프(directed graph)
• Node: 페이지
• Edge: 하이퍼링크(URL)

• 크롤링 프로세스는 이 유향 그래프를 에지를 따라 탐색하는 과정

• 그래프 탐색에는 보통 DFS, BFS를 많이 사용

• 웹 크롤러는 보통 BFS 사용 (FIFO 큐 사용)
• DFS는 그래프 크기가 클 경우 어느 정도로 깊숙이 가게 될지 가늠하기 어렵기 때문에 잘 사용하지 않음.

• 문제점
1. 한 페이지에서 나오는 링크의 상당수는 같은 서버로 HTTP 반복 요청
• 한 서버로 요청이 집중 → 트래픽 발생 → 상대 서버 입장에서는 Dos로 인식
• 예의 없는(impolite) 크롤러로 간주



2. URL 간 우선순위 부재
• 표준 BFS 알고리즘은 처리 순서에 있어 모든 페이지를 공평하게 대우
• 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않음.
• 그러니 페이지 순위(page rank), 사용자 트래픽의 양, 업데이트 빈도 등 여러 가지 척도에 비추어 처리 우선순위를 구별하는 것이 온당함.
 

4.2. 미수집 URL 저장소

• URL 저장소는 다운로드할 URL을 보관하는 장소

• 이 저장소를 잘 구현하면 아래 세 가지를 지키는 크롤러를 만들 수 있음.
1. 예의(Politeness): 서버에 과도한 부하를 주지 않는 것
2. 우선순위(Priority): 중요한 페이지를 먼저 크롤링
3. 신선도(Freshness): 이미 크롤링한 페이지도 주기적으로 다시 수집

• 웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 한다.

• 너무 많은 요청을 보내는 것은 무례한 일이며, 때로는 Dos 공격으로 간주되기도 한다.

• 예의 바른 크롤러를 만드는 데 있어서 지켜야 할 한 가지 원칙은 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다는 것이다.

• 이 요구사항을 만족시키려면 웹사이트의 호스트명(hostname)과 다운로드를 수행하는 작업 스레드(worker thread) 사이의 관계를 유지하면 된다. (1대1 대응)

• 아래는 이 아이디어를 응용한 설계를 보여준다.

• 큐 라우터(queue router): 같은 호스트에 속한 URL은 언제나 같은 큐(b1, b2, …, bn)로 가도록 보장하는 역할

• 매핑 테이블(mapping table): 호스트 이름과 큐 사이의 관계를 보관하는 테이블

호스트	큐
naver.com	b1
google.com	b2
…	…
dongho-blog.kro.kr	bn

• FIFO 큐(b1부터 bn까지): 같은 호스트에 속한 URL은 언제나 같은 큐에 보관

• 큐 선택기(queue selector): 큐 선택기는 큐들을 순회하면서 큐에서 URL을 꺼내서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달하는 역할

• 작업 스레드(worker thread): 작업 스레드는 전달된 URL을 다운로드하는 작업을 수행. 전달된 URL은 순차적으로 처리될 것이며, 작업들 사이에는 일정한 지연시간(delay)을 둘 수도 있음.

• 애플(Apple) 제품에 대한 사용자 의견이 올라오는 한 페이지가 애플 홈페이지와 같은 중요도를 갖는다고 보기는 어려울 것이다.

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

• 본 절에서 설명할 순위결정장치(prioritizer)는 URL 우선순위를 정하는 컴포넌트다.

• 아래 그림은 URL 우선순위를 고려하여 변경한 설계를 보여준다.

• 순위결정장치(prioritizier): URL을 입력으로 받아 우선순위를 계산

• 큐(f1, …, fn): 우선순위별로 큐가 하나씩 할당됨. 우선순위가 높으면 선택될 확률도 증가

• 큐 선택기(Queue selector): 임의 큐에서 처리할 URL을 꺼내는 역할을 담당. 순위가 높은 큐에서 더 자주 꺼내도록 프로그램되어 있음.

• 아래는 이를 반영한 전체 설계다. 아래의 두 개 모듈이 존재하는 것을 볼 수 있다.
• 전면 큐(front queue): 우선순위 결정 과정을 처리
• 후면 큐(back queue): 크롤러가 예의 바르게 동작하도록 보증

• 웹 페이지는 수시로 추가되고, 삭제되고, 변경된다.

• 따라서 데이터의 신선함(freshness)을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집(recrawl)할 필요가 있다.

• 그러나 모든 URL을 재수집하는 것은 많은 시간과 자원이 필요한 작업이다.

• 이 작업을 최적화하기 위한 전략으로는 다음과 같은 것들이 있다.
• 웹 페이지의 변경 이력(update history) 활용
• 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집

• 검색 엔진을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수억 개에 달한다.

• 따라서 모두를 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다.

• 전부 디스크에 저장하는 것도 좋은 방법은 아닌데, 느려서 쉽게 성능 병목지점이 되기 때문이다.

• 따라서 본 설계안은 절충안(hybrid approach)을 택했다.
• 대부분의 URL은 디스크에 두되, I/O 비용을 줄이기 위해 메모리 버퍼에 큐를 둔다.
• 버퍼에 있는 데이터는 주기적으로 디스크에 기록할 것이다.

4.3. HTML 다운로더

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

• 다운로더에 대해 알아보기 전에 먼저 로봇 제외 프로토콜(Robot Exclusion Protocol)에 대해 알아보자.

• 로봇 제외 프로토콜

• 웹사이트가 크롤러와 소통하는 표준적 방법

• 이 파일에는 크롤러가 수집해도 되는 페이지 목록들이 들어있음.

• 따라서 웹 사이트를 긁어가기 전에 크롤러는 반드시 해당 파일에 나열된 규칙을 먼저 확인해야 함.

• 이 파일은 주기적으로 다시 다운받아 캐시에 보관해둔다.

User-Agent: *
Allow: /
Disallow: /api/

Sitemap: https://dongho-blog.kro.kr/sitemap.xml

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

1. 분산 크롤링
• 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
• 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리

2. 도메인 이름 변환 결과 캐시
• DNS 요청이 처리되는 데는 보통 10ms ~ 200ms가 소요 (크롤러 병목 가능성)
• 크롤러 스레드 가운데 어느 하나라도 이 작업을 하고 있으면 다른 스레드의 DNS 요청은 전부 블록(block)
• 따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡(cron job) 등을 돌려 주기적으로 갱신 필요

3. 지역성
• 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법
• 크롤링 서버 ↔ 크롤링 대상 서버가 가까우면 페이지 다운로드 시간 감소
• 지역성(locally)을 활용하는 전략은 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능

4. 짧은 타임아웃
• 어떤 웹 서버는 응답이 느리거나 아예 응답하지 않음.
• 이런 경우에는 대기 시간(wait time)이 필요
• 일정 시간 동안 응답하지 않으면 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어감.
 
Q. 재시도 전략은 어떻게 가져갈까?
• 재시도 횟수 제한 (retry_count)
• Exponential Backoff 적용
• 실패할 때마다 재시도 간격을 지수로 증가
• 1회 실패 → 1분 후
• 2회 실패 → 5분 후
• 3회 실패 → 30분 후

4.4. 안정성

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

• 다음은 시스템 안정성을 향상시키기 위한 접근법 중 중요한 몇 가지이다.

• 안정 해시(consistent hashing):
• 다운로더 서버들에 부하를 분산할 때 적용 가능한 기술
• 이 기술을 이용하면 다운로더 서버를 쉽게 추가하고 삭제가 가능
• 책 5장 ‘안정 해시 설계’ 참고

• 크롤링 상태 및 수집 데이터 저장:
• 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적 저장장치에 기록
• 저장된 데이터를 로딩하고 나면 중단되었던 크롤링을 쉽게 재시작 가능

• 예외 처리:
• 대규모 시스템에서 에러(error)는 불가피할뿐 아니라 흔하게 벌어지는 일
• 예외가 발생하더라도 전체 시스템이 중단되지 않도록 해야 함.

• 데이터 검증:
• 시스템 오류를 방지하기 위해 필수!

4.5. 확장성

• 시스템을 설계할 때는 항상 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경 써야 한다.

• 아래는 새로운 모듈을 끼워 넣음으로써 새로운 형태의 콘텐츠를 지원할 수 있도록 설계한 것이다.

• PNG 다운로더: PNG 파일을 다운로드하는 플러그인(plug-in) 모듈

• 웹 모니터: 웹을 모니터링하여 저작권이나 상표권이 침해되는 일을 막는 모듈

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

1. 중복 콘텐츠
• 웹 콘텐츠의 30% 가량은 중복
• 해결: 해시나 체크섬을 사용하면 중복 콘텐츠를 보다 쉽게 탐지 가능

2. 거미 덫
• 거미 덫(spider trap)은 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지
• 예: spidertrapexample.com/foo/bar/foo/bar/foo/bar/...
• 해결: 모든 종류의 덫을 피할 수 있는 만능 해결책은 없음.
• 최선은 URL의 최대 길이를 제한하는 것
• 사람이 수작업으로 덫을 확인하고 크롤러 탐색 대상에서 제외하거나 URl 필터 목록에 걸어두는 것

3. 데이터 노이즈
• 어떤 콘텐츠는 거의 가치가 없음
• 광고나 스크립트 코드, 스팸 URL 같은 것은 가능하면 제외하는 게 좋음.

5. 마무리

• 추가로 논의해보면 좋을 것들
1. 서버 측 렌더링(server-side rendering)
• 현대의 웹사이트는 자바스크립트를 이용해 링크를 즉서에서 만들어 낸다.
• 이 웹 페이지를 그냥 있는 그대로 다운받아서 파싱한다면 동적으로 생성되는 링크는 발견할 수 없다.
• 따라서 페이지를 파싱하기 전에 서버 측 렌더링(동적 렌더링)을 적용하면 해결할 수 있다.
2. 원치 않는 페이지 필터링
• 스팸 방지 컴포넌트를 어떻게 구현할 것인가?
3. 데이터베이스 다중화 및 샤딩
4. 수평적 규모 확장성
5. 가용성, 일관성, 안정성
6. 데이터 분석 솔루션(analytics)