웹 크롤러 란?
- 로봇 또는 스파이더라고 불림
- 웹에 새로 올라오거나 갱신된 콘텐츠(이미지, 비디오, PDF, 웹 페이지 등)를 찾아내는 것이 주된 목적
- 몇 개 웹페이지에서 시작해여 그 링크를 따라 나가면서 새로운 컨텐츠를 수집한다.
- 사용처
- 검색 엔진 인덱싱: 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. (구글 검색 엔진)
- 웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차. (많은 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙 하고 있다.)
- 웹 마이닝: 데이터 마이닝 목적으로 인터넷에서 유용한 지식을 도출 한다. (유명 금융 기업들은 크롤러를 통해 주주 총회 자료 연차 보고서를 다운 받아 사업 방향을 알아내기도 한다.)
- 웹 모니터링: 인터넷에서 저작권이나 상표권이 침해되는 사례 모니터링 가능 (디지마크 사는 웹 크롤러를 사용해 해적판 저작물을 찾아내서 보고 한다.)
- 복잡도는 처리해야 하는 데이터 규모에 따라 천차만별
문제 이해 및 설계 범위 확정
웹 크롤러 기본 알고리즘
- url 집합이 입력으로 주어지면 해당 URL들이 가르키는 모든 웹 페이지를 다운로드 한다.
- 다운받은 웹 페이지에서 URL를 추출한다.
- 추출된 URL들을 다운로드할 URL에 추가하고 위의 과정을 처음 부터 반복한다.
질문을 통해 설계 범위 줄이기
- 용도는? - 검색 엔진 인덱싱
- 매달 얼마나 많은 웹 페이지를 수집해야 하나? - 10억 개의 웹 페이지를 수집
- 새로 만들어진 웹 페이지나 수정된 웹 페이지도 고려해야 하나? - 넵
- 수집한 웹 페이지는 저장해야 하나요? - 5년간 저장
- 중복된 콘테츠는 어떻게 해야 하나요? - 중복 콘텐츠를 갖는 페이지는 무시해도 됩니다.
좋은 웹 크롤러가 만족 시켜야 할 속성
면접관과 크롤러 기능 요구 사항을 명확히 하는 것도 중요하지만 좋은 웹 크롤러가 만족 시켜야할 다음과 같은 속성에 주의를 기울여야 한다.
- 규모 확장성: 오늘날 웹에는 매우 거대하기 때문에 병행성을 활용하면 보다 효과적으로 웹 크롤링 가능
- 안정성: 잘못 작성된 HTML, 아무 반응이 없는 서버, 장애, 악성 코드가 붙어 있는 링크 등 과 같은 비정상적 입력이나 환경에 잘 대응할 수 있어야 한다.
- 예절: 수집 대상 웹사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안된다.
- 확장성: 새로운 형태의 콘텐츠를 지원하기 쉬어야 한다. 예를 들어 이미지 파일도 크로링 하고 싶다고 해서 전체 시스템을 새로 설계하면 곤란하다.
개략적 규모 추정
매달 10억개 웹 페이지 다운로드 가정
웹 페이지 평균 크기는 500k라 가정
- QPS = 10억 / 30 / 24 시간/ 3600초 = 대략 400 per second
- Peak QPS = 400 X 2 = 800 per second
- 10억 x 500k = 500TB/월
- 5년가 보관해야 하므로 500TB x 12 x 5 = 30PB 저장 용량 필요
개략적 설계안 제시 및 동의 구하기
개별 컴포넌트 설명
시작 URL 집합
- 웹 크롤러가 크롤링을 시작하는 출발점
- 시작 URL을 고를때 창의적이어야 가능한 많은 링크를 탐색할 수 있다.
- 지역적 특색 작은 부분 집한/ 주제별로 세분화 하여 다른 시작 url을 사용
미수집 URL 저장소
- 다운로드할 URL 저장소
- FIFO queue
HTML 다운로더
- 인터넷에서 웹 페이지를 다운로드하는 컴포넌트
- 미수집 URL 저장소가 다운로드할 URL을 제공한다.
도메인 이름 변환기
- 다운로드할 웹페이지의 URL을 IP로 변환해 주는 역할
콘텐츠 파서
- 다운로드된 웹페이지 파싱과 검증 담당.
- 이상한 웹페이지는 문제를 일으킬 수 잇고 저장 공간도 낭비하게 되기 때문에 필요하다.
- 또한 콘텐츠 파서 과정이 크롤링 과정에 영향을 주어 느려질 수 있어 독립된 컴포넌트로 분리.
중복 컨텐츠 판단 하는 법
- 현재 웹 상에서 많은 내용이 중복이기 때문에 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄이는게 매우 중요하다.
- 두 HTML 문서를 비교하는 가장 간단한 방법은 문자열을 보고 비교하는 것 하지만 느리고 비효율적
- 웹 페이지의 해시 값을 비교하는 것이 효과적이다.
콘텐츠 저장소
- HTML문서를 보관하는 시스템
- 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간등을 종합적으로 고려해야 한다.
- 설계안의 경우 디스크와 메모리를 동시에 사용하는 저장소를 택할 것이다.
- 데이터 양이 너무 많아 대부분은 디스크에 저장
- 인기 있는 데이터만 메모리에 저장하여 접근 지연시간을 줄인다
URL 추출기
- HTML 페이지를 파싱하여 링크를 골라내는 역할
URL 필터
- 크롤링 대상에서 배제하는 역할
- 접속 시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL, 특정한 콘텐츠 타입이나 파일 확장자를 가지는URL
이미 방문한 URL를 판단하는 법?
- 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL를 추적할 수 있는 자료구조 사용 (블룸 필터, 해시 테이블)
- 이를 통해 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있다.
URL 저장소
- 이미 방문한 URL을 보관하는 저장소
웹 크롤러 작업 흐름
- 시작 URL들을 미수집 URL 저장소에 저장한다.
- HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
- HTML 다운로더는 도메인 이름 변호나기를 사용해 URL의 IP 주소를 알아내고, 해당 IP로 접속하여 웹페이지를 다운로드한다.
- 콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증한다.
- 콘테츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인한다.
- 중복 콘텐츠이지 확인을 위해서 이미 저장소에 있는지 본다.
- 이미 저장소에 있으면 버린다.
- 저장소에 없느 콘텐츠면 저장소에 저장한뒤 URL 추출기로 전달한다.
- URL 추출기는 해당 HTML 페이지에서 링크를 골라낸다.
- 골라낸 링크를 URL 필터로 전달한다.
- 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달한다.
- 이미 처리한 URL인지 확인하기 위하여, URL 저장소에 보관된 URL인지 살피고 이미 있으면 버린다.
- 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다. (그럼 초기에 시작 URL을 넣을떄도 무조건 URL 저장소에 넣는 구조로 해야 겠지?/ 아니면 앞선 설명처럼 URL 저장소 뿐만 아니라 미수집 URL 저장소도 중복 URL를 확인을 위해 검사?)
상세 설계
DFS vs BFS
- 웹은 유향 그래프와 같다. 페이지는 노드, 하이퍼링크는 에지라고 보면된다.
- DFS는 깊이 우선 탐색법으로 그래프 크기가 클 경우 어느 정도로 깊숙히 탐색할지 가늠하기 어려워 좋은 선택이 아닐 수 잇다.
- 보통 웹크롤러는 BFS를 선택하지만 두 가지 문제점이 존재한다.
- 예의 없는 크롤러가 될 수 있다. 왜냐하면 대부부느 한 페이지에서 추출한 모든 링크는 내부 링크 이다. 고로 같은 호스트 속에 많은 링크를 크롤러가 병렬로 요청하여 부하를 줄 수 있기 때문이다.
- URL간에 우선순위를 두지 않는다. 하지만 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖지 않는다. 그러므로 페이지 순위, 사용자 트래픽의 양, 업데이트 빈도 등 여러가지 척도에 비추어 처리 우선순위를 구별해야 한다.
미수집 URL 저장소
예의
- 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것은 무례한 일이면 때로는 DOS 공격으로 간주되기도 한다.
- 예의 바른 크롤러는 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.
반영된 설계
- 큐 라우터: 같은 호스트에 속한 URL은 언제나 같은 큐에 들어가도록 보장한다.
- 매핑 테이블: 호스트 이름과 큐 사이의 관례를 보관한다. wikipedia.com -> b1(큐)
- fifo 큐: 같은 호스트에 속한 URL은 언제나 같은 큐에 보관된다.
- 큐 선택기: 큐 선택기는 큐들을 순회하면서 큐에서 URL을 꺼내서 지정된 작업 스레드에 전달한다.
- 작업 스레드: 작업 스레드는 전달된 URL을 다운로드하는 작업을 수행 필요하다면 작업들 사이에 일정 지연시간을 줄 수 있다.
우선순위
- 모든 페이지가 동일한 우선순위를 가지고 있지는 않다. 따라서 페이지 링크, 트래픽 양, 갱신 빈도 등에 따라 다양한 척도를 기반으로 우선순위를 결정해야 한다.
반영된 설계
- 순위결정장치: URL을 입력으로 받아 우선순위를 계산한다.
- 큐: 우선순위별로 큐를 할당한다. 우선순위가 높으면 선택될 확률도 올라간다.
- 큐 선택기: 큐에서 URL를 꺼내는 역할을 담당하고 순위가 높은 큐에서 더 자주 꺼낸다.
신선도
- 웹 페이지는 수시로 추가되고, 삭제되고, 변경되기 떄문에 주기적으로 재수집 해야 한다.
- 모든 URL를 재수집하는 것은 많은 시간과 자원이 필요하기 때문에 최적화 전략을 이용해야 한다.
- 웹 페이지의 변경 이력활용
- 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집
미수집 URL 저장소를 위한 지속성 저장장치
- 검색 엔진을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수억 개에 달한다.
- 그래서 모두 메모리에 보관하는건 안정성 또는 규모 확장성 측면에서 바람직하지 않다. 그리고 전부 디스크에 저장하면 성능 병목지점이 된다.
- 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것이다. 버퍼에 있는 데이터는 주기적으로 디스크에 기록한다.
HTML 다운로더
- HTTP 프로토콜을 통해 웹 페이지를 내려받는다.
Robots.txt
- 웹사이트가 크롤러와 소통하는 표준적 방법이다.
- 이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있다.
- 매번 다시 다운로드하는 것을 피하기 위해, 이 파일은 주기적으로 다시 다운받아 캐시에 보관한다.
성능 최적화
분산 크롤링
- 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
- 그림에서 큐 선택기 부터 작업 스레드 부분으로 보인다.
도메인 이름 변환 결과 캐시
- DNS resolver는 크롤러 성능 병목 중 하나이다. 왜냐하면 DNS 요청의 결과를 받기 전까지는 다른 작업을 진행할 수 없는 동기적 특성 때문이다.
- 따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡드을 돌려 주기적으로 갱신 하다록 한다.
지역성
- 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간은 줄어들 것이다.
짧은 타임아웃
- 어떤 웹 서버는 응답이 느리거나 아예 응답하지 않을 수 있다. 고로 대기 시간을 정하고 이 시간동안 응답하지 않으면 다운로드르 중단하고 다음 페이지로 넘어간다.
안정성
- 안정해시: 다운로드 서버를 쉽게 추가하고 삭제할 수 있다.
- 크롤링 상태 및 수집 데이터 저장: 장애가 발생한 경우에도 쉽게 복구할 수 있돌고 크롤링 상태와 수집된 데이터를 기록해두는게 좋다. 그럼 저장된 데이터를 기반으로 크로링을 쉽게 재시작할 수 있다.
- 예외처리: 대규모 시스템에서 에러는 흔하게 벌어진다. 그러므로 예외가 발생해도 전체 시스템이 중단되는 일 없이 작업을 이어나갈 수 있어야 한다.
- 데이터 검증: 시스템 오류를 방지하기 위한 중요 수단 이다.
확장성
- 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 해야한다.
- png 다운로더는 png파일을 다운로드하는 플러그인, 웹 모니터는 웹을 모니터링하여 저작권이나 상표권 침해되는 일을 막는 모듈
문제 있는 콘텐츠 감지 및 회피
- 중복 콘텐츠
- 해시나 체크섬 사용하여 판단
- 거미 덫
- 거미 덫은 크롤러가 무한 루프에 빠지도록 설계한 웹 페이지이다. 예)spidertrapexample.com/foo/bar/foo/bar/...
- URL의 최대 길이를 제한하면 회피 가능
- 수작업으로 덫을 확인하고 찾아낸 후에 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 추가한다.
데이터 노이즈
- 광고, 스크립트 코드, 스팸 URL 같은 것들 가치 없는 데이터는 제외 해야 한다.
마무리
서버측 렌더링
- 많은 웹 사이트들이 자바스크립트, ajax를 통해 링크를 동적으로 만들어 내기 때문에 그냥 다운로드 받아서 파싱하면 발견할 수 없다. 그래서 파싱전 서버 측 렌더링을 적용하면 해결 가능.
원치 않는 페이지 필터링
- 크롤링에 소요되는 자원은 유한하기 떄문에 스팸 방지 컴포넌트를 두어 스팸성인 페이지를 걸러내도록 한다.
데이터 베이스 다중화 및 샤딩
- 데이터 계층의 가용성, 규목 확정성, 안정성을 향상 시킬수 있다.
수평적 규모 확정성
- 대규모 크롤링을 위해서는 다운로드 서버를 수백 수천대로 늘려야 할 수 있다. 무상태로 만들어야 쉽게 규모 확장성을 달성할 수 있다.
가용성, 일관성, 안정성
- 성공적인 대형 시스템에서는 꼭 필요한 부분
데이터 분석 솔루션
- 데이터를 수집하고 분석하는건 모든 시스템에서 중요하다.
질문
- URL 공간을 지역적 특색 주제별로 세분화해서 다른 시작 URL을 쓴다?
- hash로 html파일 동일성을 판단한다고 하면 내용의 대부분이 같지만 문자하나만 다르더라도 다르게 취급될텐데.. 더 효과적인 방법이 없나?
- bfs vs dfs
- 항상 bfs가 좋지는 않다. 만약 구체적인 데이터와 그 특정 데이터와 연관된 데이터를 좀 더 빠르게 보고 싶다면 DFS가 더 나은 선택일 수 있다고 한다.
링크 - 5,10문헌을 참고해서 순위결정장치,예의바른 크롤러설계 봐보자
- client side rendering (dynamic page)는 크롤러로 데이터를 얻어가기 어렵다.
