9. 웹 크롤러 설계

• 웹 크롤러는 재미있으면서도 고전적인 설계이다
• 검색 엔진에서 널리 쓰이는 기술로, 웹에 새로운 것이 올라오거나 갱신 된 컨텐츠를 찾아내는 것이 주 목적이다
  • 여기서 컨텐츠는 웹 페이지, 동영상, PDF 등을 포괄한다

웹 클롤러의 사용

1. 검색 엔진 인덱싱
   • 크롤러의 가장 보편적인 용례다
   • 웹 페이지를 모아, 검색 엔진을 위한 로컬 인덱스를 만든다
   • 예를들어 GoogleBot은 구글 검색 엔진이 사용하는 웹 크롤러다
2. 웹 아카이빙
   • 나중에 사용할 목적으로 장기 보관하기 위해 웹에서 정보를 모으는 절차를 말한다
   • 대표적으로 미국 국회 도서관, EU 웹 아카이브가 있다
3. 웹 마이닝
   • 웹 마이닝을 통해 인터넷에서 유용한 정보를 추출해 낸다
   • 일례로, 금융 기업들을 크롤러로 주주 총회 자료나 연차 보고서를 다운 받아, 기업의 핵심 사업 방향을 알아내기도 한다
4. 웹 모니터링
   • 크롤러를 사용하면 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링 할 수 있다
   • 일례로 디지마크 사는 웹 크롤러를 사용해 해적판 저작물을 찾아내서 보고한다

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

1. 규모 확장성
2. 안정성
3. 예절
4. 확장성

개략적 규모 추정

• 매달 10억 개의 웹 페이지를 다운로드 한다
• QPS = 10억/30/24/3600 = 대략 400페이지/s
• 최대 QPS = 400 * 2 = 800/s
• 웹 페이지의 평균 크기는 500KB 라고 가정
• 10억 페이지 * 500k = 500TB/Month
  • 500TB * 12 = 6PB/Year
• 페이지를 5년간 보관해야 한다고 가정하면 6PB * 5 = 30PB 의 용량이 필요하다

웹 크롤러의 개략적 설계

시작 URL 집합

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

미수집 URL 저장소

• 다운로드 할 URL을 저장 관리하는 컴포넌트를 말한다
• FIFO Queue 라고 생각하자

HTML 다운로더

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

도메인 이름 변환기

• HTML 다운로더는 도메인 이름 변환기를 사용하여 URL에 대응되는 IP 주소를 알아낸다

콘텐츠 파서

• 웹 페이지를 다운로드하면 파싱과 검증 절차를 거쳐야 한다

중복 컨텐츠 체크

• 웹에 공개된 연구 결과에 따르면 웹 페이지 중 약 30% 가량은 중복 컨텐츠이다
• 자료구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄일 수 있다
• 효과적인 방법으로는 웹 페이지의 해시 값을 비교하는 방법이 있다

콘텐츠 저장소

• HTML 문서를 보관하는 시스템이다
• 콘텐츠 저장소를 구현하는 데 쓰일 기술을 고를 때는 저장할 데이터의 크기, 유형, 저장소 접근 빈도, 데이터의 유효 기간 등을 종합적으로 고려해 봐야 한다
• 디크스와 메모리를 동시에 사용하는 저장소를 택할 수 있다
  • 데이터의 양이 너무 많으므로 대부분의 컨텐츠는 디스크에 저장한다
  • 인기 있는 컨텐츠는 메모리에 두어 접근 지연시간을 줄일 것이다

URL 추출기

• URL 추출기는 HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다
• 상대 경로는 전부 절대 경로로 변환한다

URL 필터

• 다음과 같은 URL들을 필터링하여 크롤링 대상 목록에서 제외하는 역할을 한다
  • 특정한 컨텐츠 다입이나 파일 확장자를 갖는 URL
  • 접속시 오류가 발생하는 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 vs BFS)

• DFS는 좋은 선택지가 아닐 수 있다
  • 웹 페이지의 깊이가 어느정도일 지 가늠이 어렵기 때문이다
• 웹 크롤러는 보통 BFS + FIFO Bi Pass Queue를 사용한다
  • 문제점
    • 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다
      • 따라서 같은 서버로의 요청이 많아지면 예의 없는 크롤러로 간주 될 수 있다
    • 표전 BFS 알고리즘은 처리에 우선순위를 두지 않는다
      • 따라서 페이지 순위, 사용자 트래픽 양, 업데이트 빈도 등 여러가지 척도에 비추어 처리 우선순위를 구별해야 한다

미수집 URL 저장소

• 예의

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

  • 웹 사이트의 hostname과 작업 스레드 사이의 관계를 유지하도록 할 수 있다

    • 다운로드 스레드는 별도 FIFO Queue를 갖고 있어서, 해당 Queue에서 꺼낸 URl만 다운로드 하도록 한다

    • 큐 라우터

      • 같은 호스트에 속한 URL은 언제나 같은 Queue로 가도록 보장하는 역할을 한다

    • 매핑 테이블

      • 호스트 이름과 Queue 사이의 관계를 보관하는 테이블

      호스트	큐
      wikipedia.com	q1
      apple.com	p2

    • FIFO Queue

      • 같은 호스트에 속한 URL은 언제나 같은 Queue에 보관한다

    • Queue 선택기

      • Queue들을 순회하면서 Queue에서 URL을 꺼내 다운로드 할 수 있도록 작업 스레드에 전달하는 역할을 한다

    • 작업 스레드

      • Queue 선택기로부터 전달 받은 URL을 다운로드 하는 작업을 수행한다.
      • 순차적으로 처리하는 것이 기본이며, 작업들 사이에는 일정한 delay를 둘 수 있다

• 우선순위

  1. 순위 연결장치 : URL을 입력으로 받아 우선순위를 계산한다
  2. 우선순위 Queue : 우선순위별로 Queue가 하나씩 할당 된다. 당연히 우선 순위가 높으면 선택 될 확률도 높아진다
  3. 우선순위 Queue 선택기 : 임의 Queue에서 처리할 URL을 꺼내는 역할을 담당한다. 우선 순위가 높은 Queue에서 꺼내는 빈도수를 높게 설정한다

• 신선도

  • 이미 수집한 URL이라도, 재 수집할 필요가 있는 상황이 있다
  • 모든 URL을 재수집 하는 것은 매우 비효율적이기에, 다음과 같은 전략을 수립할 수 있다
    • 웹 페이지의 변경 이력 활융
    • 우선순위를 사용하여 중요한 페이지는 좀 더 자주 재수집

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

  • 검색 엔진을 위한 크롤러의 경우, 처리해야 할 URL의 수는 수억개에 달할 수 있다
  • 그 모든 URL을 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다
  • 반대로 전부 디스크에 저장하는 것도 성능 병목지점이 되기 딱 좋으므로, 좋은 방법이 아니다
  • 따라서 URL은 디스크에 두지만, IO 비용을 줄이기 위해 메모리 버퍼에 Queue를 두는 것으로 절충안을 결정할 수 있다
    • 메모리 버퍼에 있는 데이터는 주기적으로 디스크에 기록 된다

• HTML 다운로더

  • HTTP 프로토콜을 통해 웹 페이지를 다운로드 한다
  • Robots.txt
    • 해당 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있다
    • 따라서 웹 사이트를 크롤링 하기 전에, 크롤러는 해당 파일에 나열 된 규칙을 먼저 확인해야한다
  • 성능 최적화
    1. 분산 크롤링
       • 성능을 높히기 위해 크롤링 작업을 여러 서버에 분산하는 방법이다
       • 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다
       • 이 구성을 위해 URL 공간은 작은 단위로 데이터를 분할하여, 각 서버는 그 중 일부의 컨텐츠를 다운로드 하도록 한다
    2. 도메인 이름 변환 결과 캐시
       • 도메인 이름 변환기는 크롤러의 유명한 성능 병목 지점 중 하나이다
         • DNS 요청을 보내고 결과를 받는 동기적 특성 때문이다
       • 따라서 DNS 조회 결과로 얻어 진 도메인 이름과 IP 주소를 캐시해 놓고, cron job 등으로 주기적인 갱신을 처리하도록 하면, 성능 개선을 얻을 수 있다
    3. 지역성
       • 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간을 줄일 수 있다
       • 크롤링 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용이 가능하다
    4. 짧은 타임아웃
       • 어떤 웹 서버는 응답 시간이 느리거나, 응답하지 않을 수 있다
       • 따라서 max timeout을 설정하여 정해진 시간 동안 서버에 응답이 없을 경우 다음 페이지로 넘어가도록 설계한다
  • 안정성
    • 시스템 안정성을 향상시키는 것 또한 필요하다
    • 안정 해시
      • 다운로더 서버들에 부하를 분산할 때 적용 가능하다
    • 크롤링 상태 및 수집 데이터 저장
      • 장애가 발생 한 이후에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적으로 저장장치에 기록해 두는 것이 바람직하다
      • 저장 된 데이터를 로드하면, 장애로 중단되었던 크롤링을 쉽게 이어서 진행할 수 있다
    • 예외 처리
      • 대규모 시스템에서 error는 불가피하고, 흔하게 벌어지는 일이다
      • 예외가 발생해도 전체 시스템이 중단되지 않고, 그 작업을 이어나갈 수 있어야 한다
    • 데이터 검증
      • 시스템 오류를 방지하기 위한 중요 수단이다
  • 확장성
    • 새로운 형태의 컨텐츠를 쉽게 지원할 수 있도록 신경 써야 한다
  • 문제 있는 컨텐츠 회피
    1. 중복 컨텐츠
       • 해시나 체크섬을 사용하여 중복 컨텐츠를 탐지할 수 있다
    2. 거미 덫
       • 크롤러를 무한 루프에 빠지도록 설계한 덫이다
       • URL 최대 길이를 제안하는 것으로 회피할 수 있지만, 교묘한 거미 덫은 파악이 어려울 수 있다
    3. 데이터 노이즈
       • 가치 없는 데이터를 말한다.
       • 가치 없는 데이터를 제외하도록 설계하면 좋다

마무리

추가 검토 사항

• 서버 측 랜더링
  • JS 기반 웹사이트는 링크를 즉석에서 만들기에 동적으로 생성되는 링크는 발견하기 어려울 수 있다
  • 페이지를 파싱하기 전에 서버 측 랜더링을 적용하면 해결할 수 있다
• 원치 않는 페이치 필터링
  • 스팸 방지 필터링과 같이 품질 나쁘거나 스팸성인 페이지를 걸러내면 좋다
• 데이터베이스 다중화 및 샤딩
  • 다중화 및 샤딩과 같은 기법을 사용하면 data layer의 가용성, 규모 확장성, 안정성이 향상된다
• 수평적 규모 확장성
  • 수평적 규묘 확장성을 달성하는 데 중요한 것은 서버가 상태정보를 유지하지 않도록 하는 것, 즉 무상태 서버로 만드는 것이다
• 가용성, 일관성, 안정성
  • 성공적인 대규모 시스템을 만들기 위한 기본이다
• 데이터 분석 솔루션
  • 데이터를 분석하는 것은 어느 시스템에게나 중요하다.
  • 시스템을 세밀하게 조정하기 위해서는 데이터와 그 분석 결과 도출이 필수적이다