9. 웹 크롤러 설계

웹 크롤러

• 로봇(Robot) 또는 스파이더(Spider)라고 부른다.

• 검색 엔진에 널리 사용되는 기술, 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적

• 웹 페이지 내 글자, 이미지, 비디오, PDF 파일 등 수집

• 페이지 링크 등을 욺겨다니면서 새로운 컨텐츠 수집

활용 용도

• 검색 엔진 인덱싱(Search Engine Indexing) - 크롤러의 가장 보편적 용례

• 웹 아카이빙(Web Archiving) - 나중에 사용할 목적으로 장기보관을 위해 웹에서 정보 수집

• 웹 마이닝(Web Mining) - 유용한 정보(기업 정보, NFT 정보 등) 수집

• 웹 모니터링(Web Monitoring) - 저작권에 침해되는 자료 발견

웹 크롤러의 기능은 다양하고, 설계에 따라서 규모가 달라지기 때문에 이에 대한 요구사항(데이터의 규모, 기능 등)을 명확하게 확인해야 한다

문제 이해 및 설계 범위 확정

요구사항

• 검색 엔진 인덱싱

• 월 10억 개(1B) 웹 페이지 수집

• 새로 만들어진 웹 페이지 및 수정된 웹 페이지 고려

• 저장된 페이지는 5년간 저장

• 중복된 컨텐츠를 갖는 페이지 무시

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

• 병행성(parallelism) - 병렬적으로 수십억개의 페이지를 수집한다.

• 안정성(Robustness) - 웹은 함정(잘못 작성된 HTML, 악성코드 등)이 많기 떄문에, 이런 비정상적인 입력이나 환경에 대응할 수 있어야 한다.

• 예절(Politeness) - 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내선 안된다. (DDOS로 의심사기 좋음)

• 확장성(extensibility) - 새로운 형태(이미지, PDF 등)의 콘텐츠에 대한 지

개략적인 규모 추정

• 매달 10억 개의 웹 페이지 다운로드

• QPS = 10억 / 30일 / 24시간 / 3600초 = 약 400페이지/초

• 최대(Peak) QPS = 2 * QPS = 800

• 웹 페이지 크기의 평균은 500KB로 가정

• 10억 페이지 * 500KB = 500TB/월, 6PB/년

• 5년 동안 페이지 보관 시 30PB 이상의 용량이 필요하다.

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

웹 크롤러의 구조

시작 URL 집합

• 웹 크롤러가 크롤링을 시작하는 출발점

• 크롤러가 가능한 많은 링크를 탐색할 수 있도록 하는 URL를 고르는 것이 바람직

• 전체 URL 공간을 작은 부분 집합으로 나누어서 처리한다.

• 지역적인 특색이나 나라 별 인기있는 웹페이지들, 혹은 카테고리(운동, 보건 등)에 따라 다른 시작 URL을 사용

미수집 URL 저장소

• 다운로드 할 URL, FIFO(First-In-First-Out) 큐로 관리

HTML 다운로더

• 인터넷에서 웹페이지를 다운로드하는 컴포넌트

• 다운로드 할 페이지의 URL은 미수집 URL 저장소가 제공

도메인 이름 변환기

• 웹 페이지를 다운로드 받으려면 URL를 IP로 변환하는 절차가 필요하다.

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

콘텐츠 파서

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

• 이상한 페이지 등은 문제를 일으킬 수 있고 저장 공간을 낭비하게 된다.

• 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있기 때문에, 독립된 컴포넌트로 구현

중복 콘텐츠 확인

• 29% 가량의 웹페이지는 중복

• 웹페이지의 해시값을 비교

콘텐츠 저장소

• HTML 문서를 보관하는 시스템

• 저장소를 구현하는데 쓰일 기술을 고를 때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간 등 종합적으로 고려

• 장기 저장 콘텐츠들은 디스크에 저장, 인기 있는 콘텐츠들은 메모리(캐시)에 두어 지연시간 감소

URL 추출기

• HTML 페이지를 파싱하여 링크를 골라내는 역할

• 상대 경로는 앞에 Origin 주소를 붙여 절대 경로로 변환

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. 중복 콘텐츠인지 확인하기 위해서 해당 페이지가 이미지 저장소에 있는 지 확인한다. (저장소에 있는 콘텐츠는 처리 X, 저장소에 없는 콘텐츠는 저장소에 저장한 뒤 URL 추출기로 전달)

7. URL 추출기는 해당 HTML 페이지에서 링크를 골라낸다.

8. 골라낸 링크를 URL 필터로 전달한다.

9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달한다.

10. 이미 처리한 URL인지 확인하기 위하여, URL 저장소에 보관된 URL인지 확인한다. 이미 저장소에 있는 URL이라면 버린다.

11. 저장소에 없는 URL은 URL 저장소, 미수집 URL 저장소 각각 저장한다

상세 설계

DFS(Depth-First Search) vs BFS(Breath-First Search)

• 웹은 유향 그래프(Directed Graph) 형태. 페이지는 노드(Node), 하이퍼링크(URL)은 에지(Edge)

• 크롤링 프로세스는 이 유향 그래프를 따라 탐색하는 과정, 탐색할 때 DFS, BFS 알고리즘을 활용한다.

• 깊이 우선 방법, DFS는 웹 페이지의 깊이가 어느 정도로 깊을 지 가늠할 수 없기 때문에 좋은 방법이 아니다.

• BFS를 사용하여 큐에 URL을 넣고 순차적으로 페이지를 방문하여 크롤링하는 방법을 사용한다.

BFS 방법으로 크롤러 설계 시 문제점

• 한 페이지에서 나오는 링크의 상당수는 내부 링크일 가능성이 높다. 그래서 다른 페이지를 순차적으로 읽을 때 같은 서버에 요청이 다수 발생할 수 있다. 분산 처리를 하고 있는 경우, 페이지를 운영하는 서버에 과부하를 줄 수 있다.

• BFS 알고리즘은 노드의 우선 순위를 두지 않는다. 즉 페이지 URL 별 우선순위가 없다. 페이지 별로 다루는 정보, 순위, 사용자 트래픽 양, 업데이트 빈도 등에 따라 우선 순위를 구별하는 작업이 별도로 들어가야 한다.

• BFS를 구현하는 큐를 미수집 URL 저장소로 구현한다. 예의나 우선 순위에 대한 부분을 고려할 수 있다.

미수집 URL 저장소

예의

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

• 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다. 같은 웹 사이트의 페이지를 다운로드 받는 작업은 시간차를 두고 실행하도록 한다.

• 해당 요구사항을 만족시키려면, 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다. 각 다운로드 스레드는 별도 FIFO 큐를 가지고 있어서 해당 큐에서 꺼낸 URL만 다운로드 한다

우선순위

• 유용성에 따라 URL의 우선순위를 나눌 때는 페이지 랭크(Pagerank), 트래픽 양, 갱신 빈도(Update frequency) 등 척도 사용

• URL의 우선 순위를 결정하는 컴포넌트인 순위 결정 장치(prioritizer)를 사용한다.

신선도

• 웹 페이지는 수시로 추가, 삭제, 변경이 이루어지기 때문에 데이터의 신선도가 변경될 가능성이 높다. 이미 다운로드 한 페이지라도 주기적으로 재수집하여 데이터의 신선도를 유지한다.

• 신선도 유지 전략

  • 웹 페이지의 변경 이력 활용

  • 우선 순위를 활용하여 중요한 페이지는 더 자주 수집

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

• 검색 엔진을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수억개인데 이를 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 좋지 않다.

• 전부 디스크에 저장하는 방법은 느려서 성능 병목 지점이 된다.

• 디스크와 메모리 버퍼를 함께 사용하고, 메모리 버퍼에 있는 항목들은 주기적으로 디스크에 기록한다.

HTML 다운로더

Robots.txt

• 웹 사이트가 크롤러와 소통하는 표준 방법, 크롤러가 수집해도 되는 페이지 목록이 들어 있다.

• 그래서 웹 사이트를 긁어가기 전에 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 한다.

성능 최적화 기법

• 분산 크롤링

  • 성능을 높히기 위해 크롤링 작업을 여러 서버에 분산하는 방법. 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다.

  • URL 공간은 작은 단위로 분할하여, 각 서버는 그 중 일부의 다운로드를 담당하도록 한다.

• 도메인 이름 변환 결과 캐시

  • 도메인 이름 변환기(DNS Resolver)는 크롤러의 병목 중 하나. DNS의 요청을 보내고 결과를 받는 작업의 동기적 특성 때문

  • DNS 요청이 처리되는 데는 보통 10~200ms 정도 소요

  • 크롤러 스레드 가운데 어느 하나라도 이 작업을 하고 있으면 다른 스레드의 DNS 요청은 전부 블록된다.

  • DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡 등으로 돌려 주기적으로 갱신

• 지역성

  • 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법

  • 크롤링 서버와 크롤링 대상 서버 간 지역적으로 가까우면 페이지 다운로드 시간은 줄어들 것이다.

  • 지역성을 활용하는 전략은 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능하다.

• 짧은 타임아웃

  • 웹 서버 별로 응답이 느리거나, 응답하지 않는 경우도 발생할 수 있다.

  • 대기 시간이 길어지면 수집 시간 또한 길어지기 떄문에, 최대한 얼마나 기다릴 지 타임아웃(Timeout)을 정한다.

  • 응답이 없는 경우, 다른 페이지로 넘어간다.

안정성 확보

• 최적화된 성능 뿐만 아니라 안정성 또한 다운로더 설계 시 중요하게 고려할 요소이다.

• 시스템 안정성을 고려한 방법

  • 안정 해시(Consistent Hashing)

    • 다운로더 서버들에 부하를 분산할 때 적용

  • 크롤링 상태 및 수집 데이터 저장

    • 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터의 지속적 저장장치에 기록

    • 저장된 데이터를 로딩하면 중단되었던 크롤링을 쉽게 재시작할 수 있다.

    • 메타 저장소 등이 이에 해당된다.

  • 예외 처리(Exception Handling)

    • 대규모 분산 환경에서 예기치 못한 에러가 발생할 수 있기 때문에, 데이터 수집에서 정합성에 문제가 발생하지 않는 선에서 예외 처리를 진행해야 한다.

  • 데이터 검증(Data Validation)

    • 시스템 오류를 방지하기 위한 중요 수단

확장성

• 진화하지 않는 시스템은 없는 법이라서, 이런 시스템을 설계할 때는 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 설계해야 한다.

• 어뎁터 패턴을 사용하면 용이하다.

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

• 중복 콘텐츠

  • 통계적으로 웹 콘텐츠의 30%는 중복, 체크섬(Checksum)을 사용하여 중복 콘텐츠를 보다 쉽게 탐지할 수 있다.

• 거미 덪(Spider Trap)

  • 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지

  • 어느정도 예방이나 회피는 가능하나 완벽한 해결책은 없다. 주기적인 모니터링을 통한 예외 상황에 대해서 유연하게 대응할 수 있도록 설계해야 한다.

• 데이터 노이즈

  • 광고, 스크립트 코드, 스팸 URL 같은 것들은 데이터로써 가치가 낮기 때문에 제외해야 한다.

추가 논의 사항

서버 사이드 랜더링(Server-side Rendering)

• 많은 웹 사이트가 자바스크립트, AJAX 등의 기술을 사용해서 링크를 즉석에서 만들어낸다.

• 웹 사이트를 있는 그대로 다운받아서 파싱해보면 찾으려는 링크가 없을 수 있다.

• 페이지 파싱 전, 서버 사이드 랜더링을 적용하여 해결한다.

실제 사례로 서버를 스크래핑하는 경우에, Post 방식을 사용하여 값을 요청하고 자바스크립트 내부에 json 객체를 생성하여 이를 긁어와야 하는 경우가 있었습니다.

원치 않는 페이지 필터링

• 저장 공간 등 크롤링에 소요되는 자원은 유한하기 떄문에 스팸 방지 컴포넌트를 두어 품질이 낮거나 스팸성인 페이지를 필터링하는 기법을 사용한다.

데이터베이스 다중화 및 샤딩

• 다중화(Replication) 및 샤딩(Sharding) 같은 기법을 적용하면 데이터 계층의 가용성, 규모 확장성, 안정성이 향상된다. ⇒ 데이터 계층의 신뢰성이 높아진다.

수평적 규모 확장성(Horizontal Saclability, Scale-Out)

• 대규모의 크롤링을 위해서는 다운로드를 실행할 서버가 수백 혹은 수천 대 필요하게 될 수도 있다.

• 수평적 규모 확장성을 달성하는 데 중요한 것은 서버가 상태정보를 유지하지 않도록 하는 것, 즉 무상태 서버로 만드는 것이다.

• 각 컴포넌트의 역할을 통해서 하나의 역할만을 수행하는 SRP 원칙을 활용하는 것이 중요하다 생각하였고, 크롤링의 경우 컴포넌트가 잘 나뉘어져 있다면 상태 정보는 크게 중요하지 않다 생각됩니다.

데이터 분석 솔루션

• 크롤링 시 발생하는 시스템 정보들에 대해서 수집하고 개선을 위해서 분석하는 작업이 중요하다.

• 이를 통해서 비용, 성능적으로 더욱 효율적인 시스템으로 발전할 수 있다.