웹 크롤러 설계

"가상 면접 사례로 배우는 대규모 시스템 설계 기초"를 읽고 정리한 글입니다 :)

웹 크롤러(Web Crawler)는 로봇(Robot) 또는 스파이더(Spider)라고도 불린다. 검색 엔진에서 널리 쓰는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적이다. 웹 크롤러는 몇개의 웹페이지에서 시작하여 해당 페이지의 링크를 따라나가면서 새로운 콘텐츠를 수집한다.

크롤러는 다양하게 이용되는데, 아래는 그 예시이다.

• 검색 엔진 인덱싱(Search Engine Indexing)
  • 크롤러의 가장 보편적인 용례이다.
  • 크롤러는 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스(Local Index)를 만든다.
• 웹 아카이빙(Web Archiving)
  • 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차를 말한다.
  • 많은 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙하고 있다.
• 웹 마이닝(Web Mining)
  • 웹에서 데이터 마이닝을 수행하는 것
• 웹 모니터링(Web Monitoring)
  • 크롤러를 사용하여 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다.

웹 크롤러의 기본 알고리즘

웹 크롤러의 기본 알고리즘은 간단하다.

1. 탐색을 시작할 URL 집합이 주어지면, 해당 URL이 가리키는 웹페이지들을 다운로드한다.
2. 다운받은 웹 페이지의 링크(URL)들을 추출한다.
3. 추출된 URL을 다운로드할 URL 집합에 추가하고, 위의 과정을 반복한다.

하지만 이 알고리즘만 가지고는 대규모 처리가 가능한 웹 크롤러를 설계할 수 없다.

고려할 요구사항

웹 크롤러를 설계하기 위해선 다양한 요구사항들을 파악해야 한다.

• 웹 크롤러의 용도
• 웹 크롤러의 Throughput
• 수집된 콘텐츠의 저장 여부
• 변경된 콘텐츠의 처리 방법
• 중복된 콘텐츠의 처리 방법
• 규모 확장성
  • 성능 개선을 위한 병렬성 등
• 안정성
  • 네트워크 에러, 잘못된 포맷의 HTML, 악성 코드 등에 잘 대응할 수 있는지
• 예절
  • 크롤러가 수집 대상 웹 사이트에 짧은 시간동안 너무 많은 요청을 보내지 않도록...
  • 콘텐츠의 저작권 문제도 포함될 수 있다.
• 확장성
  • 새로운 형태의 콘텐츠를 지원하기 쉬워야 한다.
  • 예를들어 이미지 파일도 추가로 크롤링하고 싶을 때, 전체 시스템을 새로 설계해야 한다면 곤란하다.

필요한 컴포넌트들을 설계해보자

시작 URL 집합

크롤링을 시작할 URL 집합을 정할 때는, 크롤러가 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직하다. 시작 URL을 무엇으로 쓸지에 대해서는 정답이 없으니, 크롤러의 목적에 따라 적절한 URL을 고르자.

미수집 URL 저장소

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

HTML 다운로더

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

도메인 이름 변환기

도메인을 IP주소로 변환하는 일을 한다.

콘텐츠 파서

다운로드 받은 콘텐츠를 파싱(Parsing)하고 검증(Validation)하는 컴포넌트이다.

중복 여부 확인

중복된 콘텐츠를 계속 저장하게 되면, 저장 공간과 처리 속도에 부정적인 영향이 간다. 중복을 비교하는 효과적인 방법 중 하나는 웹 페이지의 해시 값을 비교하는 것이다.

콘텐츠 저장소

다운로드 받은 콘텐츠를 저장하는 컴포넌트이다.

URL 추출기

콘텐츠에서 URL들을 추출하는 컴포넌트이다.

URL 필터

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

이미 방문한 URL 검증

이전에 방문한 URL이거나 미수집 URL 저장소에 보관된 URL를 검증해야 한다. 이 작업을 할때는 블룸 필터(Bloom Filter) 또는 해시 테이블을 널리 쓴다.

URL 저장소

이미 방문한 URL을 저장하는 컴포넌트이다.

상세하게 설계해보자

탐색 알고리즘

웹은 방향 그래프와 같다. 페이지는 노드이고, 하이퍼링크는 간선인 것이다. DFS와 BFS가 이 그래프 탐색에 널리 사용되는 알고리즘들이다. 하지만 DFS는 웹 크롤러에게는 좋은 방법이 아닐 가능성이 큰데, 일반적으로 웹은 그래프가 매우 크기에 어느 정도로 깊숙히 가게될지 가늠하기가 어렵다.

그래서 웹 크롤러는 보통 BFS를 사용한다. 다만 BFS를 사용하는 경우에도 다음의 문제들이 있다.

• 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다.
  • 예를들어, 위키피디아 페이지에서 추출한 링크는 대부분 같은 위키피디아 서버의 다른 페이지일 것이다.
  • 만약 크롤링을 병렬로 처리할 시, 크롤러가 같은 호스트에 짧은 시간동안 매우 많은 요청을 보낼 것이다.
• 기본적인 BFS 알고리즘은 우선순위가 없다.
  • 모든 웹페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않는다.
  • 페이지 순위(Page Rank), 사용자 트래픽의 양, 업데이트 빈도 등 여러가지 척도로 우선순위를 두는게 좋다.

미수집 URL 저장소

미수집 URL 저장소를 활용하면 위에서 언급한 문제를 쉽게 해결할 수 있다.

우선 수집 대상 서버에 요청의 수를 조절하는 것부터 알아보자. 예의를 갖춘 크롤러를 만드는데 지켜야 할 한가지 원칙은, 동일한 웹 사이트에 대해 한번에 한 페이지만 요청하는 것이다. 이를 위해 같은 웹사이트의 페이지를 다운받는 작업은 시간차를 두고 실행하도록 만들면 된다. 이 요구사항을 만족시키려면 웹사이트의 호스트명과 다운로드를 수행할 작업 스레드 사이의 관계를 만들어주면 된다. 다운로드를 수행할 스레드는 별도의 큐를 가지고 있어, 해당 큐에서 꺼낸 URL만 다운로드한다. 그리고 같은 호스트의 URL들은 항상 같은 큐에만 넣어주면 된다. 그렇다면 해당 호스트에 대한 요청은 항상 시간차가 생긴다는 것을 보장할 수 있다.

우선순위를 지정하는 것도 이와 비슷하게 구현할 수 있다. URL을 지정된 규칙에 따라 우선순위를 정하고, 우선순위에 맞게 각기 다른 큐에 저장한다. 그리고 URL을 꺼내올 때, 우선순위가 높은 큐에서 더 자주 URL을 꺼내도록 구현하면 될 것이다.

위 두가지를 동시에 적용하기 위해 큐 그룹을 여러개 사용할 수 있다. 첫번째 큐그룹에서는 우선순위에 맞게 URL을 저장 및 반환해주는 역할을 하고, 두번째 큐그룹에서는 호스트 별도 URL을 저장하는 역할을 하는 것이다.

신선도

웹 페이지는 수시로 추가되고, 삭제되고, 변경된다. 따라서 데이터의 신선함(Freshness)을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집(Recrawl)할 필요가 있다. 그러나 모든 URL을 재수집하는 것은 많은 시간과 자원이 필요하므로, 다음과 같은 최적화 전략을 쓴다.

• 웹 페이지의 변경 이력(Update History) 활용
• 우선순위를 활용하여, 중요한 페이지는 더 자주 재수집

HTML 다운로더

HTML 다운로더는 HTTP 프로토콜을 통해 웹 페이지를 내려받는다. 다운로더에 대해 설명하기 전에 먼저 로봇 제외 프로토콜(Robot Exclusion Protocol)을 알아야 한다.

로봇 제외 프로토콜이라고 부르기도 하는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준적 방법이다. 이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어있다. 따라서 웹 사이트를 탐색하기 전 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 한다. Robots.txt을 계속 다운로드하는 것을 피하기 위해, 이 파일은 주기적으로 다운로드받아 캐시에 보관하는 것이 좋을 것이다.

HTML 다운로더는 성능 최적화도 중요하다.

성능을 높이는 첫번째 방법은 크롤링 작업을 여러 서버에 분산하는 것이다. 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다.

또, DNS 변환 결과를 캐싱하는 것도 성능 최적화의 방법 중 하나이다. DNS 요청을 보내고 결과를 받는 작업은 동기적이기 때문에, 결과를 받기 전까지는 다음 작업을 진행할 수 없다. 그렇기 때문에 도메인 이름과 IP 주소 사이의 관계를 캐시에 저장하고 주기적으로 갱신하는 것이 좋다.

HTML 다운로더는 안정성도 중요하게 고려해야 한다. 시스템 안정성을 높이기 위한 방법들 가운데 중요한 몇가지는 아래와 같다.

• 안정 해시 : 안정 해시를 통해 다운로더 서버를 쉽게 추가하거나 삭제할 수 있다.
• 크롤링 상태 및 수집 데이터 저장 : 장애가 발생한 경우에도 쉽게 복구할 수 있도록 상태를 지속적으로 저장
• 예외 처리
• 데이터 검증

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

중복이거나 의미가 없는, 또는 유해한 콘텐츠를 감지하고 회피하는 방법을 알아보자

중복 콘텐츠
중복 콘텐츠는 해시나 체크섬(Check-Sum)을 사용하면 쉽게 탐지할 수 있다.

거미 덫
거미 덫(Spider Trap)은 크롤러를 무한 루프에 빠트리도록 설계한 웹 페이지이다. 예를들어 다음과 같이 무한히 깊은 디렉토리 구조를 포함하는 링크가 있다고 가정해보자.

spidertrapexample.com/foo/bar/foo/bar/foo/bar/...

이 경우 별도의 처리가 없다면 크롤러가 무한 루프에 빠질 것이다. 이런 덫은 URL의 최대 길이를 제한하면 회피할 수 있다. 혹은 사람이 수작업으로 덫이 있는 사이트를 탐색 대상에서 제외하는 것도 방법이다.

데이터 노이즈
광고나 스크립트 코드, 스팸 URL 같은 것들을 거의 가치가 없는 콘텐츠이다. 이런 콘텐츠는 크롤러에게 도움될 것이 없으니 가능하다면 제외해야 한다.

더 많은 고려사항들

• Server-Side Rendering
  • 많은 웹사이트가 JS, Ajax 등의 기술을 사용하여 링크를 즉석으로 만들어 낸다.
  • 이 경우 웹 페이지를 그대로 다운받아서 파싱하면 동적으로 생성되는 링크는 발견할 수 없다.
  • 이 문제는 페이지를 파싱하기 전 서버측에서 렌더링을 적용한 다음 파싱을 수행하여 해결할 수 있다.
• 페이지 필터링
  • 품질이 조약하거나 스팸성인 페이지를 걸러낼 수 있도록 설계하자.
• 데이터베이스 다중화 및 샤딩 (Replication, Sharding)
  • 다중화나 샤딩 같은 기법을 적용하여 가용성 및 규모 확장성, 안정성을 챙기자.
• 수평적 규모 확장성(Horizontal Scalability)
  • 대규모 크롤링을 위해 수평적 규모 확장성을 가질 수 있도록 설계하자.
  • 수평적 규모 확장성을 달성하는데 중요한 것은 무상태(Stateless) 서버로 만드는 것이다.
• 데이터 분석 솔루션
  • 크롤링한 데이터들을 제대로 분석하는 것 역시 중요하다.