웹 크롤러 설계

코딩하는스님·2022년 1월 26일
0
post-thumbnail
  • 웹 크롤러는 검색엔진 등에서 쓰이며, 웹 페이지나 정적인 자원으로부터 콘텐츠를 수집하는 장치이다.

  • 웹페이지에 접속 후 웹페이지에 있는 링크들에 접속하여 재귀적으로 콘텐츠를 수집한다.

  • 용례

    • 검색 엔진 인덱싱
      • 웹 페이지들을 모아 검색 엔진을 위한 로컬 인덱스를 생성한다. (googlebot)
    • 웹 아카이빙
      • 나중에 사용할 목적으로 웹에 있는 정보들을 장기 저장한다.
    • 웹 마이닝
      • 인터넷으로부터 유용한 지식/자원 등을 도출해낸다. (주주 총회/연차 보고서)
    • 웹 모니터링
      • 저작권/상표권 침해를 모니터링한다.
  • 데이터의 규모에 따라 웹 크롤러 설계는 달라질 것이므로 설계할 데이터의 규모와 기능을 알아내야 한다.

문제 이해 및 설계 범위 확정

웹 크롤러의 기본 알고리즘

1. URL 집합이 입력으로 주어지면, URL이 가리키는 모든 웹 페이지를 다운로드한다.
2. 다운받은 웹 페이지 내에 있는 URL 등을 수집한다.
3. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위 작업을 반복한다.

질문

  • 크롤러의 주된 용도는? 검색 엔진 인덱스, 데이터 마이닝, 그 외?
  • 매달 얼마나 많은 데이터를 수집해야되나? 10억 개
  • 신규 페이지나 수정 페이지도 고려해야되나? 그렇다
  • 수집한 페이지를 저장하는가? 그렇다
  • 얼마동안 저장하는가? 5년
  • 중복된 컨텐츠는 어떻게 하는가? 무시

고려해야할 속성

  • 규모 확장성
  • 안정성
  • 예절
  • 확장성

개략적 규모 추정

  • 매달 10억 개의 웹페이지
  • QPS = 10억/30일/24시간/3600초 = 400페이지/초
  • Peak QPS = 2*QPS = 800페이지/초
  • 500kb/웹페이지
  • 10억페이지*500kb = 500TB/월
  • 5년치 데이터 = 500TB * 12개월 * 5년 = 30PB

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

시작 URL 집합

  • 크롤링을 시작하는 출발점이다.
  • 더 많은 링크를 탐색할 수 있도록 URL을 고르는 것이 필요하다.
  • 전체 URL 공간을 작은 부분집합, 주제별로 다른 시작 URL을 고르는 등의 전략을 사용한다.

미수집 URL 저장소

  • 크롤링의 상태는 두가지로 나뉜다.
    1. 다운로드할 URL
    1. 다운로드된 URL
  • 1번에 해당하는 URL을 저장하는 곳이 미수집 URL 저장소이다.
  • 구현은 FIFO Queue를 사용한다.

HTML 다운로더

  • URL에 연결된 HTML을 다운로드한다.

도메인 이름 변환기

  • URL을 IP주소로 변환하는 장치이다. (DNS?)

콘텐츠 파서

  • 웹 페이지 다운로드 후 파싱과 검증의 절차가 필요하다.
  • 크롤링 서버가 아닌 독립된 컴포넌트로서 동작한다.

    나머지는 전부 같은 서버에 있는가?

중복컨텐츠인가?

  • 중복되는 컨텐츠는 불필요한 크롤링 시간을 사용하고, 최악의 경우에는 저장소까지 차지한다.
  • 이를 위해서 문서의 내용을 해싱하여 비교하는 전략을 취한다.

콘텐츠 저장소

  • 저장할 데이터의 유형, 크기, 접근 빈도, 데이터의 유효 기간 등을 고려하여야 한다.
  • 대부분의 컨텐츠는 디스크에서 저장한다.
  • 인기 있는 컨텐츠는 메모리에 둔다.

URL 추출기

  • href에 있는 상대 주소들은 domain 주소를 붙여 절대 주소로 변환한다.
<a href='/wiki/javascript'/>
<!-- https://ko.wikipedia.org/wiki/javascript -->

URL 필터

  • 파일 확장자를 갖는 URL, 오류가 발생하는 URL, deny list URL 등을 제외한다.

이미 방문한 URL?

  • 이미 방문한 URL을 추척하기 위해서는 블룸필터나 해시테이블을 사용한다.

URL 저장소

  • 다운로드 한 URL을 보관하는 저장소이다. (블룸필터나 해시 테이블)

작업흐름

  1. 시작 URL을 미수집 URL 저장소에 저장한다.
  2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
  3. HTML 다운로더는 DNS를 상용하여 URL의 IP를 가져온다.
  4. 컨텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증한다.
  5. 컨텐츠 파싱과 검증이 끝나면 중복 컨텐츠인지 확인한다.
  6. 컨텐츠가 이미 컨텐츠 저장소에 있는지 확인한다.
    • 있으면 처리하지 않고 버린다.
    • 없으면 저장한다.
  7. URL 추출기는 HTML에서 링크들을 골라낸다.
  8. 골라낸 링크는 URL 필터로 보내진다.
  9. 필터링이 끝나고 남은 URL은 중복 체크를 한다.
  10. 중복체크를 통과하면 미수집 URL 저장소에 저장한다.

상세 설계

DFS vs BFS

  • 웹은 directed graph로 생각할 수 있다.
    • 노드 : 페이지
    • 엣지 : 하이퍼링크
  • 크롤링에서는 DFS보다는 BFS를 사용한다. (깊이가 어느정도가 될지 가늠할 수 없기 때문이다.)
  • 따라서 FIFO Queue를 사용한 BFS를 사용한다.
    • 현재 페이지에서 링크 목록을 가져와서 Queue에 저장한다.
    • Queue에서 꺼낸 링크목록에 각각 접속하여 링크목록을 가져오고 Queue에 넣는다.
    • 한 한페이지에서는 같은 링크를 포함하고 있는 경우가 많은데, 이 경우에는 요청을 보내지 않게 구현하여 impolite crawler가 되지 않도록 해야된다.
    • Queue로 구현하였기 때문에 우선순위 없이 처리하는데, page rank나 트래픽의 양, 업데이트 빈도 등을 고려하여 Priority queue로 구현하는 것이 더욱 바람직할 것이다.

미수집 URL 저장소

  • 미수집 URL 저장소를 사용하여 polite crawler, 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.

Polite

  • 짧은 시간에 많은 요청을 보내어 크롤링하는 것은 DoS로 간주될 수 있다.
  • 따라서 동일 웹사이트에 대해서는 한번에 한 페이지만 요청하여 처리하는 것이 중요하다.
  • 쓰레드별로 할당하는 domain/hostname을 두면 이를 해결할 수 있다.
    • queue router
      • 같은 hostname의 URL은 언제나 같은 queue로 보내는 역할
    • mapping table
      • hostname과 queue 간의 관계를 보관한다.
    • FIFO queue
      • 같은 hostname을 가진 URL들은 이 queue에 저장된다.
    • queue selector
      • 각각의 queue에서 나온 URL들을 worker thread로 보낸다.
    • worker thread
      • 전달받은 URL을 다운로드하는 역할을 수행하고, 작업 간에 delay를 줄 수도 있다.

우선순위

  • PageRank

  • 트래픽

  • 갱신 빈도

  • 우선순위별로 URL을 처리하기 위해서 hostname queue 앞에 우선순위 queue를 둔다.

    • prioritizer
      • 위의 세가지와 기타 요인들로 URL의 작업 우선 순위를 정하여 queue에 저장한다.
    • queue
      • 우선순위별로 queue가 할당된다.
    • queue selector
      • queue에서 처리할 URL을 꺼낸다.

신선도

  • 웹페이지는 변경이 잦으므로 재수집할 필요가 있다.
  • update history나 우선순위를 활용하여 재수집하는 전략을 세우는 것이 좋다.

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

  • 처리해야할 URL을 모두 메모리에 저장하는 것은 안정성/규모 확장성에 맞지 않다.
  • 따라서 URL의 대부분은 디스크에 두지만, 메모리 버퍼에 Queue를 두어 IO로 생기는 time을 줄이는 전략을 사용하자.

HTML 다운로더

Robots.txt

  • 로봇 제외 프로토콜로서 크롤러가 수집/수집하면 안되는 페이지의 정보를 가지고 있다.
    구글

성능 최적화

  1. 분산 크롤링
    • 위에서 queue selector가 쓰레드별로 URL을 할당하던 것을 분산 서버로 처리하여 최적화한 사례
  2. 도메인 이름 변환 결과 캐시
    • DNS 요청을 기다리는 시간 동안 block되므로 캐시에 DNS 요청 결과를 캐싱한다.
  3. 지역성
    • 크롤링을 하는 페이지의 서버와 가까운 곳의 서버로 크롤링을 하여 transport delay를 줄인다.
  4. 짧은 타임아웃
    • 응답이 느린 서버에 대한 타임아웃 값을 짧게 하여 반응성을 높여라

안정성

  • 안정해시
    • 다운로더 서버에 분산 처리할 때 사용하자.
  • 크롤링 상태 및 수집 데이터 저장
    • 장애에 대처할 수 있도록 주기적으로 상태와 데이터를 디스크에 저장한다.
  • 예외 처리
    • 예외가 발생했을 때, 서버가 죽지 않도록 처리해야 한다.
  • 데이터 검증
    • 시스템 오류 방지를 위해 크롤링한 데이터를 검증한다.

확장성

  • 시스템은 항상 확장을 고려해야 한다.
  • 위의 설계에서 나왔던 모든 컴포넌트들은 확장을 할 수 있어야 한다.

문제 있는 컨텐츠 감지 및 회피

  • 중복

    • 해시나 체크섬을 이용하여 중복을 탐지한다.
  • spider trap

    • 무한 루프에 빠뜨리는 웹페이지
    • 무한히 깊은 url을 탐색하게 하는 웹사이트가 있는데, 이는 url의 최대 길이를 제한하여 회피할 수 있다.
  • 데이터 노이즈

    	- 광고나 스크립트 등은 제외하는 것이 좋다.

마무리

  • SSR
    • 동적인 페이지는 렌더링 전에는 링크 정보가 없기 때문에 미리 서버에서 렌더링을 한 다음에 링크 정보를 긁어오는 것이 좋다.

      전체가 로딩된지는 어떻게 알아야 되나?

  • 원치 않는 페이지 필터링
    • 안티 스팸 컴포넌트로 불필요한 페이지를 걸러낸다.
  • DB 다중화 및 샤딩
    • 미수집 URL이나 컨텐츠 저장소 등은 다중화/샤딩을 통해 확장성/안정성을 높인다.
  • 수평적 규모 확장성
    • scale out을 하기 위해서 각 서버는 stateless 하게 만든다.

참조

알렉스 쉬, 가상 면접 사례로 배우는 대규모 시스템 설계 기초, 인사이트, 2021, 141p-163p

profile
👨🏻‍💻👨🏽‍🦲

0개의 댓글