웹 크롤러 활용 예시

• 검색 엔진 인덱싱 : 검색 엔진을 위한 로컬 인덱스를 만든다.
• 웹 아카이빙 : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차. 국립 도서관이 주로 사용한다.
• 웹 마이닝 : 웹 마이닝을 통해 유용한 지식을 도출해 낸다.
• 웹 모니터링 : 인터넷 저작권 및 상표권 침해 사례를 모니터링할 수 있다.

문제 이해 및 설계 범위 확정

기본 알고리즘

1. URL 집합이 입력, 해다 URL들이 가리키는 모든 웹페이지 다운로드
2. 다운 받은 웹 페이지에서 URL 추출
3. 추출된 URL들을 다운로드할 URL 목록에 추가. 처음부터 반복

웹 크롤러가 만족시켜야 할 속성

• 규모 확장성 : 병행성(parallelism)을 활용하여 효과적으로 웹 크롤링을 한다.
• 안정성 : 잘못 작성된 HTML, 반응 없는 서버, 악성 코드가 붙어 있는 링크 등에 대응할 수 있어야 한다.
• 예절 : 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안된다.
• 확장성 : 새로운 형태의 콘텐츠를 지원하기가 쉬어야 한다. 갑자기 이미지 파일 크롤링 스펙이 추가되어도 유연하게 대응할 수 있어야 한다.

개략적 규모 측정

조회 연산량

• 매달 10억개의 웹 페이지를 다운로드한다.
• QPS = 10억/30일/24시간/3600초 = 대략 400페이지/초
• 최대(peak) QPS = 2 * QPS = 800

저장 용량

• 웹 페이지의 크기 평균은 500k라고 가정
• 10억 페이지 * 500k = 500TB/월
• 1개월치 데이터를 보관하는 데는 500TB, 5년간 보관한다고 가정하면 결국 500TB 12개월 5년 = 30PB의 저장용량이 필요

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

• 개략적 설계안
  

시작 URL 집합

• 웹 크롤러가 크롤링을 시작하는 출발점
• 크롤러가 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직하다. 일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략을 쓴다. 또 다른 방법은 주제별로 다른 시작 URL을 사용하는 것이다. 예를 들어 URL 공간을 쇼핑, 스포츠, 건강 등등의 주제별로 세분화하고 그 각각에 다른 시작 URL을 쓰는 것이다.

미수집 URL 저장소

• 대부분의 현대적 웹 크롤러는 크롤링 상태를 (1) 다운로드 할 URL, 그리고 (2) 다운로드된 URL 두 가지로 나눠 관리한다. 이 중 '다운로드 할 URL'을 저장 관리하는 컴포넌트를 미수집 URL 저장소라 부른다. 이는 FIFO 큐라고 생각하면 된다.

HTML 다운로더

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

도메인 이름 변환기

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

콘텐츠 파서

• 웹 페이지 다운로드 후 파싱(Parsing)과 검증 절차가 필요
• 크롤링 서버 안에 파서를 구현하면 크롤링 과정이 느려지므로 독립된 컴포넌트로 구성

콘텐츠 저장소

• 데이터 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장한다.
• 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄일 것이다.

URL 추출기

• HTML 페이지를 파싱하여 링크들을 골라낸다.

URL 필터

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

URL 저장소

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

웹 크롤러 작업 흐름

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은 버린다.
11. 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다.

상세 설계

DFS를 쓸 것인가, BFS를 쓸 것인가

웹은 유향 그래프(directed graph)이다. 페이지는 노드, 파이퍼링크는 에지라고 보면 된다. 크롤링 프로세스는 이 유향 그래프를 에지를 따라 탐색하는 과정.

• DFS 깊이 우선 탐색법은 그래프 크기가 커지면 얼만큼 깊숙하게 가게 될지 가능이 어려워 좋지 않은 선택일 가능성이 높다.
• 보통 너비 우선 탐색법을 사용한다. BFS는 FIFO 큐를 사용하는 알고리즘이다. 한쪽으로 탐색할 URL을 집어넣고, 다른 쪽으로는 꺼내기만 한다.
• 이 구현 방식에는 두 가지 문제점이 있다.

1. 한 페이지에서 나오는 링크들은 대부분 같은 서버를 사용하므로 단시간에 수많은 트래픽을 발생시키게 된다. 이런 크롤러는 보통 예의 없는 크롤러로 간주된다.
2. 표준적 BFS 알고리즘은 URL 간에 우선순위를 두지 않는다. 하지만 페이지 순위, 사용자 트래픽의 양, 업데이트 빈도 등의 척도로 우선순의를 구별해야 한다.

미수집 URL 저장소

• 미수집 URL 저장소를 통해 위 두가지 문제를 해결한다.

예의

• 예의 바른 크롤러를 만들기 위해 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다. 같은 웹 사이트의 페이지를 다운받는 태스크는 시간차를 두고 실행한다.
• 이를 위해 웹사이트의 호스트 명과 다운로드를 수행하는 작업 스레드 사이의 관계를 만든다.
  

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

우선 순위

• 크롤러 입장에서는 중요한 페이지를 먼저 수집하도록 하는 것이 바람직하다.

• 우선순위를 나누기 위해 페이지랭크(wiki : https://en.wikipedia.org/wiki/PageRank), 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다.
  

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

• 큐(f1, … fn): 우선순위별로 큐가 하나씩 할당된다.

• 큐 선택기: 임의 큐에서 처리할 URL을 꺼내는 역할을 담당한다. 순위가 높은 큐에서 더 자주 꺼내도록 구성한다.

이 두가지를 조합해서 다음과 같은 설계를 만든다.

신선도

웹 페이지는 수시로 추가되고, 삭제되고, 변경된다. 따라서 데이터의 신선함(freshness)을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집(recrawl)할 필요가 있다. 이 작업을 최소화하기 위해서는 웹페이지의 변경 이력을 활용하거나, 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집 하게 할 수 있다.

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

검색 엔진을 위한 크롤러의 경우, 처리해야 하는 URL 의 수는 수억 개에 달한다. 따라서 절충안을 택하는 것이 좋다. 대부분의 URL은 디스크에 두지만 IO 비용을 위해 메모리 버퍼에 큐를 두게 처리한다. 버퍼에 있는 데이터는 주기적으로 디스크에 기록한다.

HTML 다운로더

Robots.txt

로봇 제외 프로토콜 이라고도 부른다. 이 파일에는 크롤러가 수집해도 되는 페이지 목록 규칙이 들어가 있다. 따라서 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 한다.
Robots.txt 파일을 중복 다운로드 하는 것을 피하기 위해 이 파일은 주기적으로 다시 받아 캐시에 보관한다.

성능 최적화

1. 분산 크롤링
   크롤링 작업을 여러 서버에 분산하고, 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다.

2. 도메인 이름 변환 결과 캐시
   DNS 변환 작업은 요청을 보내고 결과를 받는 동기적 특성 때문에 도메인 이름 변환기는 병목 중 하나이다. DNS 요청이 처리되는 데는 보통 10ms ~ 20ms 가 소요된다. 크롤러 스레드 중 하나라도 이 작업을 하고 있으면 다른 스레드는 전부 블록된다. 따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해두고 주기적으로 갱신하도록 해 놓으면 성능을 효과적으로 높일 수 있다.

3. 지역성
   서버를 지역별로 분산한다. 크롤링 서버가 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간은 줄어들 것이다.

4. 짧은 타임아웃
   어떤 웹 서버는 응답이 느리거나 아예 응답하지 않는다. 이런 경우 대기 시간이 길어지면 좋지 않으므로, 최대 얼마나 기다릴지를 미리 정해두면 좋다.

안정성

• 안정 해시
  다운로더 서버들에 부하를 분산할 때 적용 가능하다. 안정해시를 통해서 서버를 쉽게 추가하고 삭제할 수 있다.

• 크롤링 상태 및 수집 데이터 저장
  장애 발생시에도 쉽게 복구할 수 있도록 크롤링 상태, 수집된 데이터를 지속적 저장장치에 기록한다. 저장된 데이터를 로딩하고 중단된 크롤링을 쉽게 재시작한다.

• 예외 처리
  예외가 발생해도 전체 시스템이 중단되는 일 없이 그 작업을 우아하게 이어나갈 수 있어야 한다.

• 데이터 검증
  시스템 오류를 방지하기 위한 중요 수단.

확장성

새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 만들어야 한다. 새로운 모듈을 끼워 넣음으로써 새로운 형태의 컨텐츠를 지원할 수 있도록 설계한다.
웹모니터는 웹을 모니터링하여 저작권, 상표권이 침해되는 일을 막는 모듈이다.

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

중복이거나 의미 없는, 또는 유해한 콘텐츠를 감지하고 차단하는 방법이다.

1. 중복 컨텐츠
   해시나 체크섬을 사용하면 중복 컨텐츠를 보다 쉽게 탐지할 수 있다.

2. 거미 덫
   크롤러를 무한 루프에 빠뜨리도록 설계한 웹페이지를 거미 덫이라고 한다. 이런 덫은 URL 최대 길이를 제한해서 회피한다. 이런 덫이 설치된 웹 사이트인지 알아내는 것은 어렵지 않은데, 기이할 정도로 많은 웹 페이지를 가지고 있는 것이 일반적이라서이다.
   덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 추가 처리한다

3. 데이터 노이즈
   광고나 스크립트 코드, 스팸 URL 같은 가치없는 컨텐츠는 제외한다.

마무리

추가 논의 사항

• 서버 측 렌더링
  동적으로 생성되는 링크는 웹 페이지를 다운로드 받아서 찾을 수가 없다. 이 문제는 페이지 파싱 전에 서버 렌더링을 적용해서 해결한다.

• 원치 않는 페이지 필터링
  스팸 방지 컴포넌트를 두어 품질이 조악하거나 스팸성인 페이지를 걸러내도록 해 두면 좋다.

• 데이터베이스 다중화 및 샤딩

• 수평적 규모 확장성

• 가용성, 일관성, 안정성

• 데이터 분석 솔루션

---

본 포스트는 알렉스 쉬 저자의 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 기반으로 스터디하며 정리한 내용들입니다.

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초