웹 크롤러 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 "웹 크롤러 설계"을 요약한 내용입니다.

• 웹 크롤러는 로봇(robot) 또는 스파이더(spider)라고 부른다.
• 검색 엔진에서 널리 쓰는 기술로, 웹에 새로 올라오거나 갱싱된 콘텐츠를 찾아내는 것이 주된 목적
• 웹 크롤러는 몇 개 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 콘텐츠를 수집한다.
• 크롤러는 다양하게 이용됨
  • 검색 엔진 인덱싱
    • 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다.
  • 웹 아카이빙
    • 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
  • 웹 마이닝
    • 인터넷에서 유용한 지식을 도출 해낼 수 있다.
  • 웹 모니터링
    • 인터넷 저작권이나 상표권이 침해되는 사례를 모니터링 할 수 있다.

1단계 문제 이해 및 설계 범위 확정

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

계략적 규모 추정

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

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

• [그림 9-2]와 같은 설계안을 제시
  1. 시작 URL 집합
  2. 미수집 URL 저장소
  3. HTML 다운로더
  4. 컨텐츠 파서
  5. 중복 컨텐츠 확인
  6. URL 추출기
  7. URL 필터
  8. URL 저장소

시작 URL 집합

• 도메인이 붙은 모든 페이지의 URL을 시작 URL로 사용
• 일반적으로 전체 URL 공간을 작은 부분집합으로 나누는 전략을 사용
  • 지역적인 특색, 나라별로 인기있는 웹 사이트가 다르 다는 점
  • 주제별로 다른 시작 URL을 사용
• 시작 URL을 무엇을 쓸 것이냐는 질문에 정답은 없다.

미수집 URL 저장소

• 웹 크롤러는 크롤링 상태를 1. 다운로드할 URL 2. 다운로드된 URL두가지로 나누어 관리
• 다운로드할 URL을 저장 관리하는 컴포넌트

도메인 이름 변환기

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

콘텐츠 파서

• 웹 페이지를 다운로드하면 파싱과 검증 절차를 거져야한다.
• 크롤링 서버 안에 콘텐츠 파서를 구현하려면 크롤링 과정이 느려지게 될 수 있으므로 독립된 컴포넌트로 만들자

중복 콘텐츠인가?

• 웹에 공개된 연구 결과에 따르면, 29% 가량의 웹 페이지 콘텐츠는 중복이다.
• 웹 페이지의 해시 값을 비교하여 중복 콘텐츠인지 알아 내기

콘텐츠 저장소

• 콘텐츠 저장소는 HTML 문서를 저장하는 시스템
• 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효기간 등을 종합적으로 고려해야함
• 디스크와 메모리를 동시에 사용하는 저장소 선택
  • 데이터 양이 많으므로 대부분 콘텐츠는 디스크에 저장
  • 인기 있는 콘텐츠를 메모리에 두어 접근 지연시간을 줄임

URL 추출기

• URL 추출기는 HTML 페이지를 파싱하여 링크를 골라내는 역활
• [그림 9-3] 링크 추출 사례를 참고
  • 상대 경로는 전부 절대 경로로 변환

URL 필터

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

이미 방문한 URL?

• 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료구조를 사용
• 같은 URL을 여러번 처리하는 일을 방지 할수 있으므로 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있음

URL 저장소

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

3단계 상세 설계

• DFS vs BFS
• 미수집 URL 저장소
• HTML 다운로더
• 안정성 확보 전략
• 확장성 확보 전략
• 문제 있는 콘텐츠 감지 및 회피 전략

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

• DFS(Depth First Search)는 좋은 선택이 아닐 수 있다.
  • 그래프 크기가 클 경우 어느 정도로 깊이 가게될지 가능하기 어렵다
• BFS(Breath First Search)는 웹 크롤리에서 자주 사용
  • 큐의 한쪽으로는 탐색할 URL을 집어넣고, 다른 한쪽으로는 꺼내기만 한다.
  단점
  • 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다.
    • 같은 호스트에 속한 많은 링크를 병렬로 처리한다면 서버는 수많은 요청으로 과부하게 걸리게 될 것
    • 이런 크롤러는 예의 없는 크롤러로 간주
  • 표준적 BFS 알고리즘은 URL간에 우선순위를 두지 않는다.
    • 모든 웹페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지는 않는다.

미수집 URL 저장소

• 미수집 URL 저장소를 활용한다면 몇가지 문제를 좀더 쉽게 해결 가능
• URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현 할 수 있다.
• 예의
  • 웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가해야함
  • 때로는 DoS 공격으로 간주되기도 함
  • 동일한 웹사이트에 대하서는 한번에 한 페이지만 요청하도록 함
• 우선 순위
  • 유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있음
• 신선도
  • 웹페이지는 수시로 추가, 삭제, 변경이 됨으로 이미 다운로드한 페이지라고 해도 주기적으로 재수집 할 필요가 있다.
  • 웹 페이지의 변경 이력 활용
  • 우선순위를 활용하여, 중요한 페이지는 좀더 자주 재수집

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

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

HTML 다운로더

• Robots.txt
  • 로봇 제외 프로토콜이라고 부리기도 하는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준 방법
  • 웹 사이트를 긁어 가기 전에 크롤러는 해당 파일에 나열된 규칙을 먼저 확인 해야함
  • 예제: https://www.amazon.com/robot.txt
    • creatorhub 같은 디렉터리의 내용은 다운 받을 수 없다는 것을 알 수 있음

    Disallow: /creatorhub
    Disallow: /creatorhub/*
    

• 성능 최적화
  • 분산 크롤링
    • 성능을 높이기 위해서는 여러 서버에 분산해서 작업
    • 여러 스레드를 돌려 다운로드 작업을 처리
    • URL 공간은 작은 단위로 분활하여 각 서버는 그중 일부의 다운로드를 담당하도록 함
  • 도메인 이름 변환 결과 캐시
    • DNS는 크롤러 성능의 병록 중 하나
    • DNS 요청의 결과를 받기 전까지는 작업을 진행할 수 없다
    • DNS 조회 결과로 얻어진 도메인 이름과 IP주소 사이의 관계를 캐시에 저장해 놓고 크론 잡 등을 돌려 주기적으로 갱식하다록 해 놓으면 성능을 효과적으로 높일 수 있음
  • 지역성
    • 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간은 줄어 들 것이다.
  • 짧은 타임아웃
    • 어떤 웹 서버는 응답이 느리거나 응답하지 않을 수 있다.
    • 대기 시간을 정해 놓고 서버가 응답하지 않는다면 크롤러는 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어간다
• 안정성
  • 안정 해시: 다운로드 서버들에게 부하를 분산할 때 적용 가능한 기술
  • 크롤링 상태 및 수집 데이터 저장: 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적으로 저장 장치에 기록
  • 예외 처리: 예외가 발생해도 전체 시스템이 주안되는 일이 없어야 한다.
  • 데이터 검증: 시스템 오류를 방지하기 위한 중요한 수단
• 확장성
  • 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경 써야 함
  • 새로운 모듈을 끼워 넣음으로써 새로운 형태의 콘텐츠를 지원할 수 있도록 설계
    • PNG 다운로더
    • 웹 모니터

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

1. 중복 콘텐츠
   1. 해시나 체크섬을 사용하여 중복 컨텐츠를 보다 쉽게 탐지 가능
2. 거미 덫
   1. 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지
      1. https://test.com/foo/bar/foo/bar/foo….
   2. URL의 최대 길이를 제한한다면 회피 가능
   3. 덫을 자동으로 피해가는 알고리즘을 만들어 내는 것은 까다롭다
   4. 사람이 수작업으로 덫을 확인하고 찾아낸 후 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어 두는 것
3. 데이터 노이즈
   1. 광고, 스크립트 코드, 스펨 URL 같은 것은 크롤러에게 도움이 되지 않으므로 가능하다면 제외해야 함

4단계 마무리

• 서버 측 렌더링
  • 많은 웹 사이트가 자바스크립트, AJAX등의 기술을 사용해서 링크를 즉석에서 만든다.
  • 동적으로 생성되는 링크는 발경하기 어려움
  • 페이지를 파싱하기 전에 서버 측 렌더링을 적용하면 해결 가능
• 원치 않는 페이지 필터링
  • 저장 공간 등 크롤링에 소요되는 자원은 유한하기 떄문에 스팸 장지 컨포넌트를 두어 품질을 조악하거나 스팬성인 페이지를 걸러내도록 해두면 좋다
• 데이터베이스 다중화 및 샤딩
  • 다중화나 샤딩 같은 기법을 적용하면 데이터 계층의 가용성, 규모 확장성, 안정성이 향상
• 수평적 규모 확장성
  • 대규모 크롤링을 위해서는 다운로드를 실행할 서버가 수백 혹은 수천 대 필요하게 될 수도 있다.
  • 수평적 규모 확장을 달성하기 위해서는 서버가 상태정보를 유지하지 않도록 하는 무상태 서버로 만드는 것
• 가용성, 일관성, 안정성
  • 대형 시스템을 만들기 위해 필수적으로 고려해야하는 개념
• 데이터 분석 솔루션
  • 데이터를 수집하고 분석하는 것은 어느 시스템이나 중요