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

이번 장에서는 웹 크롤러(web crawler)를 설계해보겠다. 웹 크롤러는 검색 엔진에서 널리 쓰이는 기술로, 웹에 새로 올라오거나 갱신된 콘텐츠(웹 페이지, 이미지, 비디오, pdf 등)를 찾아내는 것이 주된 목적이다.

• 웹 크롤러는 몇 개의 엡 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 컨텐츠를 수집한다.
  
• 웹 크롤러 이용 예시
  • 검색 엔진 인덱싱(search engine indexing): 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만듦
    • 가장 보편적 용례
      
    • 일례로 Googlebot은 구글 검색 엔진이 사용하는 웹 크롤러
      
  • 웹 아카이빙(web archiving): 웹 정보를 모으고 이를 장기보관하기 위해 사용
    • 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙 함 (미국 국회 도서관, EU 웹 아카이브 등)
      
  • 웹 마이닝(web mining): 인터넷에서 유용한 지식을 도출, 데이터 마이닝
    • 금융 기업에서 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향 제시
      
  • 웹 모니터링(web monitoring): 인터넷에서 저작권이나 상표권이 침해되는 사례 등을 모니터링
    

문제 이해 및 설계 범위 확정

우선 웹 크롤러의 기본 알고리즘을 알아보자.

웹 크롤러의 기본 알고리즘

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

하지만 실제로는 이렇게 간단히 동작하지는 않고, 큰 규모 확장성을 갖는 웹 크롤러를 설계하는 것은 매우 어렵다. 따라서 이번 장에서는 아래와 같이 비교적 간소화된 요구사항으로 웹 크롤러를 설계해 볼 것이다.

• 규모 확장성: 병행성을 활용하여 거대합 웹을 효과적으로 크롤링할 것
  
• 안정성: 잘못된 HTML, 반응 없는 서버, 장애, 악성코드 링크 등 비정상 입력이나 환경에 잘 대응할 수 있어야 함
  
• 예절: 크롤러는 수집 대상 웹 사이트에 짧은 시간동안 너무 많은 요청을 보내면 안 됨
  
• 확장성: 새로운 형태의 컨텐츠를 지원하기 쉬워야 함 (다양한 파일에 대해서 크롤링 가능해야 하고, 확장 가능해야 함)
  

개략적 규모 추정

• 매달 10억개의 웹 페이지를 다운로드
  • QPS = 10억/30일/24시간/3600초 = 대략 400페이지/초
    
  • 최대(peak) QPS = 2 * QPS = 800
    
• 웹 페이지의 크기 평균은 500k라고 가정
  • 10억 페이지 * 500k = 500TB/월
    
  • 월 500TB를 5년간 보관하면, 500TB 12개월 5년 = 30PB의 저장용량이 필요
    

개략적 설계안 제시

개략적인 설계를 해볼 것인데, 아래의 다이어그램에 등장하는 컴포넌트 각각이 어떤 기능을 수행하는지 살펴보자. 그런 후 에 크롤러의 작업 흐름을 살펴볼 것이다.

• 시작 URL 집합: 웹 크롤러가 작동하는 출발점으로, 특정 도메인 이름이 될 수도 있고, 전체 웹이 될 수도 있다.
  • 특정 도메인이 붙은 모든 페이지의 URL을 시작 URL로 사용할 수 있다.
  • 전체 웹을 크롤링하는 경우에는 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 좋다.
    (전체에서 부분으로 나누는 전략, 또는 주제별로 다른 시작 URL 사용 등)

• 미수집 URL 저장소: 현대적 웹 크롤러는 크롤링 상태를 ‘다운로드 할 URL’ 그리고 ‘다운로드된 URL’의 두 가지로 나눠 관리한다.
  • 다운로드 할 URL을 저장, 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier)라고 부른다. (FIFO 방식)

• HTML 다운로더: 인터넷에서 웹 페이지를 다운로드 하는 컴포넌트로, 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공한다.
  • 도메인 이름 변환기: 웹페이지를 다운받으려면 URL을 IP로 변환하는 절차가 필요하다. HTML 다운로더가 이를 위해 도메인 이름 변환기를 이용한다.
    

• 콘텐츠 파서: 웹 페이지를 다운로드하면 파싱과 검증 절차를 거쳐야한다. 이상한 페이지는 문제를 일으킬 수 있고, 저장 공간만 낭비하기 때문이다.
  • 크롤링 서버 안에 파서를 구현하면 크롤링 과정이 느려질 수 있어 독립된 컴포넌트로 분리하였다.

• 중복 콘텐츠인가?: 웹에 공개된 연구 결과에 따르면, 29% 가량의 웹 페이지 콘텐츠는 중복이다. 따라서 같은 컨텐츠를 여러 번 저장하게 될 수 있다.
  • 자료구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 걸리는 시간을 줄일 수 있다.
    
  • 문자열을 비교하는 방법은 간단하지만 규모가 커질수록 비효율적이다.
    
  • 효과적인 방법은 웹 페이지의 해시 값을 비교하는 것이다.
    

• 콘텐츠 저장소: HTML 문서를 보관하는 시스템으로, 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터 유효 기간 등을 종합적으로 고려하여 설계한다.
  • 본 설계안의 경우 디스크(보통 컨텐츠)와 메모리(접근 빈도수 높은 컨텐츠)를 동시에 쓰는 저장소를 택할 것이다.
    

• URL 추출기: HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다. 아래의 그림은 링크 속 상대경로를 전부 절대경로로 변환하는 예시이다.
• URL 필터: URL 저장소에 저장하기 일부 URL을 크롤링 대상에서 배제하는 역할을 한다.
  • 특정한 컨텐츠 타입이나 파일 확장자를 갖는 URL
    
  • 접속 시 오류가 발생하는 URL
    
  • 접근 제외 목록(deny list) 에 포함된 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인지 확인 (중복이면 버림)
11. 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다.

상세 설계

지금부터는 가장 중요한 컴포넌트와 그 구현 기술을 심도있게 살펴볼 것이다.

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

웹은 페이지가 노드고 하이퍼링크(URL)가 에지인 방향 그래프와같다. 크롤링 프로세스는 이 방향 그래프를 에지를 따라 탐색하는 과정으로 볼 수 있다.

크롤링에서의 DFS vs BFS

DFS의 경우 그래프 크기가 커지면 탐색 깊이를 가늠할 수 없어 좋은 선택지가 아닐 확률이 높다.

BFS는 너비 우선 탐색으로 하위 페이지를 레벨마다 차례차례 탐색하여 보통 웹 크롤링에서 사용된다.

하지만 BFS를 사용했을 때 다음과 두 가지 문제점이 있다.

• 대부분의 웹 페이지에서는, 한 페이지에 나오는 링크의 상당수는 같은 서버로 되돌아간다.
  • 위키피디아 페이지에서 추출한 모든 링크는 내부 링크로, 동일 서버의 다른 페이지를 참조한다.
  • 결국 크롤러는 같은 호스트에 속한 링크를 다운받게 되고, 만약 링크를 병렬로 처리한다면 서버는 수많은 요청으로 과부하에 걸릴 수 있다.
  • 이런 크롤러는 예의 없는 크롤러로 간주된다.
• 일반적인 BFS 알고리즘은 같은 레벨의 URL 간에 우선순위를 두지 않는다.
  • 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않는다.
    
  • 페이지 순위나 사용자 트래픽의 양, 업데이트 빈도 등 여러 척도에 비추어 처리 우선순위를 구분하는 것이 온당하다.
    

미수집 URL 저장소

미수집 URL 저장소를 활용하면 위의 문제를 좀 쉽게 해결할 수 있다. 앞서 살펴본 대로 URL 저장소는 다운로드할 URL을 보관하는 장소다. 이 저장소를 잘 구현하면 예의(politeness) 를 갖추면서, 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.

예의

웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 한다. 너무 많은 요청을 보내는 것은 무례한(impolite) 일이며, DoS(Denial-of-Service)로 간주되기도 한다.

예의 바른 크롤러를 만드는 데 있어서 지켜야 할 원칙은 다음과 같다.

동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.

• 같은 웹 사이트의 페이지를 다운받는 경우, 해당 작업에 시간차를 두고 실행한다.
  
• 각 다운로드 스레드가 별도의 FIFO 큐를 가지고, 해당 큐에서 꺼낸 URL만 다운로드하게 하면 된다.
  

위 아이디어에 대한 설계는 다음과 같다.

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

우선순위

모든 페이지가 같은 중요도를 가지지는 않는다. 유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크(PageRank), 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다.

이번에는 URL 우선순위를 결정하는 컴포넌트인 순위결정장치(prioritizer)에 대해 알아볼 것이다.

• 순위결정장치: URL 을 입력으로 받아 우선순위를 계산한다.
  
• 큐(f1, …fn): 우선순위 별로 큐가 하나씩 할당되며, 우선순위가 높으면 선택될 확률도 올라간다.
  
• 큐 선택기: 임의 큐에서 처리할 URL을 꺼낸다. 순위가 높은 큐에서 더 자주 꺼내도록 프로그램 되어있다.
  

순위결정장치를 반영한 전체 설계는 다음과 같을 것이다. 전면 큐와 후면 큐 두 개의 모듈이 존재한다.

• 전면 큐: 우선순위 결정 과정 처리
  
• 후면 큐: 크롤러가 예의 바르게 동작하도록 보증
  

신선도

웹페이지는 수시로 추가되고, 삭제되고, 변경되므로 데이터의 신선함(freshness)를 유지하기 위해서 이미 다운받은 페이지라고 해도 재수집할 필요가 있다. 이 작업을 최적화하기 위한 전략으로는 다음과 같은 것들이 있다.

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

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

검색 엔진을 위한 크롤러는 수억개에 달하는 URL을 처리해야 한다. 전부 메모리에 저장하면 안정성과 확장성이 떨어지고, 전부 디스크에 저장하면 느려저서 쉽게 성능 병목지점이 되므로, 본 설계안은 절충안을 택한다.

대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 둔다.
(버퍼에 있는 데이터는 주기적으로 디스크에 기록)

HTML 다운로더

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

Robots.txt

Robots.txt: 로봇 제외 프로토콜로, 웹사이트가 크롤러와 소통하는 표준적인 방법이다.

• 이 파일에는 크롤러가 수집해도 되는 페이지 목록이 담겨있음
  
• 크롤러는 크롤링 전 해당 파일에 나열된 규칙을 먼저 확인
  
• 해당 파일을 계속 다운하는 것을 방지하기 위해 주기적으로 다시 다운받아 캐싱
  
• 아마존 robots.txt: https://www.amazon.com/robots.txt
  

성능 최적화

HTML 다운로더를 설계할 때는 성능최적화도 아주 중요하다. 다음은 HTML 다운로더에 사용할 수 있는 성능 최적화 기법들이다.

1. 분산 크롤링 : 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법이다. 

   • 각 서버는 여러 스레드를 돌려 다운로드 작업 처리
   • URL 공간은 작은 단위로 분할하여, 각 서버는 그중 일부의 다운로드를 담당

2. 도메인 이름 변환 결과 캐시 : DNS 요청과 응답 과정이 동기적이라 크롤러 성능의 병목이 생길 수 있다. 따라서 DNS 조회 결과로 얻은 도메인 이름과 IP 주소 사이의 관계를 캐싱하는 식으로 성능을 개선할 수 있다.

   • 크론 잡(cron job) 등을 돌려 주기적으로 캐시를 갱신하여 성능을 높일 수 있다.
     

3. 지역성: 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법이다. 크롤링 서버(혹은 다른 컴포넌트)가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간이 줄어들것이다.

4. 짧은 타임아웃: 어떤 웹서버는 응답이 느리거나 아예 응답하지 않는데, 이런 경우를 대비해 크롤러가 최대 얼마나 기다릴지를 미리 정해두는 것이다. 타임아웃의 경우 해당 페이지 다운로드를 중단한다.

안정성

• 안정 해시(consistent hashing): 다운로더 서버(분산 HTML 다운로더)들에 부하를 고르게 분산하기 위해 적용 가능
  
• 크롤링 상태 및 수집 데이터 저장: 장애 복구를 위해 크롤링 상태와 수집된 데이터를 지속적으로 저장장치에 기록
  
• 예외 처리: 예외가 발생해도 전체 시스템이 중단되지 않도록 미리 처리
  
• 데이터 검증: 시스템 오류를 방지, 비정상적 입력이나 환경을 대비
  

확장성

본 예제의 경우 확장 모듈을 끼워 넣을므로써 새로운 형태의 컨텐츠를 지원할 수 있도록 설계하였다.

• PNG 다운로더는 PNG 파일을 다운로드 하는 plug-in 모듈
  
• 웹 모니터는 웹을 모니터링하여 저작권이나 상표권이 침해되는 일을 막는 모듈
  

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

1. 중복 컨텐츠: 웹 컨텐츠의 30% 가량은 중복, 해시나 체크섬 등의 방법을 사용해 중복 컨텐츠를 탐지 가능

2. 거미 덫(spider trap): 크롤러를 무한루프에 빠뜨리도록 설계한 웹 페이지

   • 예시) spidertrapexample.com/foo/bar/foo/bar/foo/bar/...
     
   • URL의 최대 길이를 제한
     
   • 사람이 수작업으로 찾아낸 후, 이런 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 거는 방식 사용
     

3. 데이터 노이즈: 가치 없는 콘텐츠는 가능하면 제외하는 것이 좋음

마무리

좋은 크롤러가 갖추어야하는 특성

• 규모 확장성(scalability)
  
• 예의(politeness)
  
• 확장성(extensibility)
  
• 안정성
  
• 문제 있는 콘텐츠 감지 및 회피
  

추가로 논의해보면 좋은 것

• 서버 측 렌더링 (server-side rendering): 웹 페이지를 그냥 있는 그대로 다운받아서 파싱해보면 그렇게 동적으로 생성되는 링크는 발견할 수 없을 것이다. 이 문제는 페이지를 파싱하기 전에 서버 측 렌더링을 적용하면 해결할 수 있다.
  • 파이썬 크롤링 도구인 Selenium은 동적인 크롤링이 가능하게끔 한다.
    
• 원치 않는 페이지 필터링: 스팸 방지 컴포넌트를 두어 품질이 조약하거나 스팸성인 페이지를 필터링
  
• 데이터베이스 다중화 및 샤딩: 다중화나 샤딩 적용 시 데이터 계층 가용성, 규모 확장성, 안정성 향상
  
• 수평적 규모 확장성: 대규모 분산 다운로드 서버로 확장하기 위해 무상태 서버로 구성
  
• 데이터 분석 솔루션(analytics)