TIL

9장 웹 크롤러 설계

웹 크롤러란

• 웹 크롤러는 로봇(robot) 또는 스파이더(spider)라고 부른다.
• 웹에 새로 올라오거나 갱신된 컨텐츠를 찾아내는 것이 주된 목적
  • 콘텐츠 - 웹 페이지, 이미지, 비디오, PDF 등
• 크롤러는 다양하게 이용된다.
  • 검색 엔진 인덱싱: 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다.
  • 웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
  • 웹 마이닝: 인터넷에서 유용한 지식을 도출할 수 있다. 일례로 금융 기업들은 크롤러로 주주 총회 자료나 연차 보고서를 다운 받아 기업 핵심 사업 방향을 알아낸다.
  • 웹 모니터링: 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다.

웹 크롤러 개략 설계

• 웹 크롤러 기본 알고리즘
  1. URL 집합이 입력으로 주어지면 해당 URL들이 가리키는 모든 웹 페이지를 다운로드
  2. 다운 받은 웹 페이지에서 URL들을 추출
  3. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위 과정을 처음부터 반복
• 웹 크롤러가 만족시켜야 할 속성
  • 규모 확장성: 웹에는 수십억 개의 페이지가 존재하므로 병행성을 활용하여 효과적으로 크롤링해야 한다.
  • 안정성: 크롤러는 비정상적인 입력이나 환경에 잘 대응할 수 있어야 한다. (잘못 작성된 HTML, 반응 없는 서버, 장애, 악성 코드 등)
  • 예절: 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안 된다.
  • 확장성: 새로운 형태의 콘텐츠를 지원하기 쉬워야 한다.

웹 크롤러 컴포넌트

• 시작 URL 집합
  • 크롤링을 시작하는 출발점
  • ex) 어떤 대학 웹 사이트로부터 찾아갈 수 있는 모든 웹 페이지를 크롤링하려면 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 사용
  • 크롤러가 가능한 많은 링크를 탐색할 수 있도록 URL을 골라야 한다.
• 미수집 URL 저장소
  • 웹 크롤러는 크롤링 상태를 다운로드할 URL, 다운로드된 URL 두 가지로 나눠 관리한다.
  • 미수집 URL 저장소는 ‘다운로드할 URL’
  • FIFO 큐
• HTML 다운로더
  • 인터넷에서 웹 페이지를 다운로드하는 컴포넌트
  • 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공
• 도메인 이름 변환기
  • 페이지를 다운하려면 URL을 IP로 변환하는 절차가 필요
• 콘텐츠 파서
  • 웹 페이지를 다운하면 파싱과 검증 절차가 필요
  • 이상한 웹 페이지는 문제를 일으킬 수도 있기 때문
• 중복 콘텐츠인가?
  • 웹 페이지 해시 값을 비교하여 중복 콘텐츠가 저장되는 것을 방지
  • 웹에 공개된 연구 결과에 의하면 29% 가량의 웹 콘텐츠는 중복
• 콘텐츠 저장소
  • HTML 문서를 보관하는 시스템
  • 저장소를 구현할 때 데이터의 유형, 크기, 접근 빈도, 유효 기간 등을 종합적으로 고려해야 한다.
• 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. 중복 콘텐츠인지 확인하기 위해 해당 페이지가 이미 저장소에 있는지 확인
   1. 이미 저장소에 있으면 버린다.
   2. 저장소에 없는 콘텐츠는 저장소에 저장한 뒤 URL 추출기로 전달
7. HTML 페이지에서 링크를 추출
8. 골라낸 링크를 URL 필터로 전달
9. 필터링 후 남은 URL만 중복 URL 판벌 단계로 전달
10. 이미 처리한 URL인지 확인하기 위해 URL 저장소를 살피고 있는 URL은 버린다.
11. 저장소에 없는 URL은 URL 저장소에 저장한 뒤 미수집 URL 저장소에도 전달

상세 설계

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

• 웹은 유향 그래프와 같다.
  • 페이지는 노드, 하이퍼링크는 에지
• DFS는 좋은 선택이 아닐 가능성이 높다.
  • 그래크 크기가 클 경우 어느 정도로 깊숙히 가게 될지 가늠하기 어렵다.
• 웹 크롤러는 보통 BFS를 사용
  • FIFO 큐를 사용하는 알고리즘
• 그러나 BFS 구현법에는 문제점이 있다.
  • 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다.
    • ex) wikipedia.com 페이지에서 추출한 모든 링크는 wikipedia.com/…처럼 위키피디아 서버의 다른 페이지를 참조하는 링크
    • 결국 같은 호스트에 많은 링크를 다운 받느라 바빠지고 해당 서버는 수많은 요청으로 과부하가 걸린다.
    • 예의 없는 크롤러로 간주될 것이다.
  • 표준 BFS 알고리즘은 URL 간 우선순위를 두지 않는다.
    • 모든 웹 페이지가 같은 수준의 품질, 중요성을 갖지 않는다.
    • 페이지 순위, 트래픽 양, 업데이트 빈도 등 척도에 비추어 우선순위를 구별할 필요가 있다.

      미수집 URL 저장소

• 미수집 URL 저장소를 활용하면 BFS에서의 문제를 해결할 수 있다.
  • 예의(politeness)를 갖춘 크롤러 구현 가능
  • URL 사이의 우선순위와 신선도를 구별하는 크롤러 구현 가능

예의

• 동일 웹 사이트에 한 번에 한 페이지만 요청
• 같은 사이트 페이지 다운은 시간차를 두고 실행
• 위 요구사항을 만족시키려면 호스트명과 다운로드 수행 작업 스레드 사이의 관계를 유지하면 된다.
• 다운로드 스레드는 별도 FIFO 큐를 가지고 큐에서 꺼낸 URL만 다운로드한다.
• 설계 컴포넌트
  • 큐 라우터: 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장
  • 매핑 테이블: 호스트 이름과 큐 관계를 보관하는 테이블
  • FIFO 큐: 같은 호스트에 속한 URL은 언제나 같은 큐에 보관
  • 큐 선택기: 큐들을 순회하며 큐에서 URL을 꺼내 URL을 다운로드하도록 지정된 작업 스레드에 전달
  • 작업 스레드: 전달된 URL을 순차적으로 다운로드하는 작업을 수행하며 작업들 사이에는 일정한 지연시간을 둘 수 있다.

우선순위

• URL 우선순위를 나눌 땐 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 이용할 수 있다.
• URL 우선순위를 정하는 컴포넌트는 순위결정장치(prioritizer)
• 설계 컴포넌트
  • 순위결정장치: URL을 입력 받아 우선순위 계산
  • 큐: 우선순위별로 큐가 하나씩 할당되어 우선순위가 높으면 선택될 확률도 올라간다.
  • 큐 선택기: 임의 큐에서 처리할 URL을 꺼내며 순위가 높은 큐에서 더 자주 꺼내게 된다.
• 아래 그림은 이를 반영한 전체 설계다.
  • 전먼 큐: 우선순위 결정 과정 처리
  • 후면 큐: 예의 바르게 동작하도록 보증

신선도

• 웹 페이지는 수시로 변경되기 때문에 주기적으로 재수집할 필요가 있다.
• 재수집 최적화 방법
  • 웹 페이지의 변경 이력 활용
  • 우선순위를 활용하여 중요한 페이지는 자주 재수집

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

• URL을 메모리에 보관하는 것은 바람직하지 않다.
  • 수가 수억 개에 달하기 때문에 모두
  • 안정성, 규모 확장성 측면에서 좋지 않음
• URL을 전부 디스크에 저장하는 것도 느려서 성능 병목 지점이 된다.
• 절충안으로 URL은 디스크에 두지만 IO비용을 줄이기 위해 메모리 버퍼에 큐를 두는 방법도 있다.
  • 버퍼의 데이터는 주기적으로 디스크에 기록

HTML 다운로더

• HTML 다운로더는 HTTP 프로토콜을 통해 웹 페이지를 내려 받는다.
• Robots.txt - 로봇 제외 프로토콜
  • 웹 사이트가 크롤러와 소통하는 표준 방법
  • 이 파일에는 크롤러가 수집해도 되는 페이지 목록이 존재
  • 크롤러는 파일에 나열된 규칙을 먼저 확인해야 한다.
  • 거푸 다운로드하는 것을 피하기 위해 주기적으로 다시 다운 받아 캐시에 보관할 것
• 성능 최적화
  1. 분산 크롤링: 성능 향상을 위해 여러 서버에 크롤링 작업을 분산하는 방법
  2. 도메인 이름 변환 결과 캐시: DNS 병목을 해결하기 위해 도메인-IP 관계를 캐시에 보관해 놓고 크론 잡을 돌려 주기적으로 갱신
  3. 지역성: 크롤링 수행 서버를 지역별로 분산하는 방법
  4. 짧은 타임아웃: 크롤링 대상 서버가 느릴 경우 최대 얼마나 기다릴지 미리 정해두는 것
• 안정성
  • 안정 해시: 다운로더 서버들에 대한 부하 분산 시 적용 가능한 기술
  • 크롤링 상태 및 수집 데이터 저장: 장애 발생 경우에도 쉽게 복구할 수 있도록.
  • 예외 처리: 예외가 발생해도 전체 시스템이 중단되는 일 없이 이어나갈 수 있어야 한다.
  • 데이터 검증: 시스템 오류를 방지하기 위한 중요 수단 중 하나
• 확장성
  • 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 해야 한다.
• 문제 있는 콘텐츠 감지 및 회피
  • 중복 컨텐츠 - 해시나 체크섬을 사용해 탐지 가능
  • 거미 덫 - 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지.
    • URL 최디 길이을 제한하면 회피할 수 있다.
    • 하지만 자동으로 피해가는 알고리즘을 만드는 것은 까다롭다.
    • 사람이 수작업으로 제외하거나 URL 필터 목록에 걸어둘 수도 있다.
  • 데이터 노이즈 - 광고나 스크립트 코드, 스팸 등 가치 없는 콘텐츠는 제외해야 한다.

마무리 - 추가로 논의해볼만한 점

• 서버 측 렌더링
  • 많은 웹사이트가 링크를 즉석에서 만들어낸다. (자바스크립트, AJAX 등 이용)
  • 동적으로 생성된 링크는 그대로 다운해 파싱해도 발견할 수 없다.
  • 파싱하기 전에 서버 측 렌더링을 적용하면 해결할 수 있다. (동적 렌더링)
• 원치 않는 페이지 필터링
  • 크롤링에 소요되는 자원은 유한
  • 스팸 방지 컴포넌트를 두어 스팸성 페이지를 걸러내도록 하면 좋다.
• 데이터베이스 다중화 및 샤딩
  • 데이터 계층의 가용성, 규모 확장성, 안정성이 향상
• 수평적 규모 확장성
  • 대규모 크롤링을 위해 서버가 수백 혹은 수천 대 필요할 수도 있다.
  • 무상태 서버로 만드는 것이 중요
• 가용성, 일관성, 안정성 고려
• 데이터 분석 솔루션