-
웹 크롤러는 검색엔진 등에서 쓰이며, 웹 페이지나 정적인 자원으로부터 콘텐츠를 수집하는 장치이다.
-
웹페이지에 접속 후 웹페이지에 있는 링크들에 접속하여 재귀적으로 콘텐츠를 수집한다.
-
용례
- 검색 엔진 인덱싱
- 웹 페이지들을 모아 검색 엔진을 위한 로컬 인덱스를 생성한다. (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
- 다운로드된 URL
- 1번에 해당하는 URL을 저장하는 곳이 미수집 URL 저장소이다.
- 구현은 FIFO Queue를 사용한다.
HTML 다운로더
도메인 이름 변환기
- URL을 IP주소로 변환하는 장치이다. (DNS?)
콘텐츠 파서
- 웹 페이지 다운로드 후 파싱과 검증의 절차가 필요하다.
- 크롤링 서버가 아닌 독립된 컴포넌트로서 동작한다.
나머지는 전부 같은 서버에 있는가?
중복컨텐츠인가?
- 중복되는 컨텐츠는 불필요한 크롤링 시간을 사용하고, 최악의 경우에는 저장소까지 차지한다.
- 이를 위해서 문서의 내용을 해싱하여 비교하는 전략을 취한다.
콘텐츠 저장소
- 저장할 데이터의 유형, 크기, 접근 빈도, 데이터의 유효 기간 등을 고려하여야 한다.
- 대부분의 컨텐츠는 디스크에서 저장한다.
- 인기 있는 컨텐츠는 메모리에 둔다.
URL 추출기
- href에 있는 상대 주소들은 domain 주소를 붙여 절대 주소로 변환한다.
<a href='/wiki/javascript'/>
URL 필터
- 파일 확장자를 갖는 URL, 오류가 발생하는 URL, deny list URL 등을 제외한다.
이미 방문한 URL?
- 이미 방문한 URL을 추척하기 위해서는 블룸필터나 해시테이블을 사용한다.
URL 저장소
- 다운로드 한 URL을 보관하는 저장소이다. (블룸필터나 해시 테이블)
작업흐름
- 시작 URL을 미수집 URL 저장소에 저장한다.
- HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
- HTML 다운로더는 DNS를 상용하여 URL의 IP를 가져온다.
- 컨텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증한다.
- 컨텐츠 파싱과 검증이 끝나면 중복 컨텐츠인지 확인한다.
- 컨텐츠가 이미 컨텐츠 저장소에 있는지 확인한다.
- 있으면 처리하지 않고 버린다.
- 없으면 저장한다.
- URL 추출기는 HTML에서 링크들을 골라낸다.
- 골라낸 링크는 URL 필터로 보내진다.
- 필터링이 끝나고 남은 URL은 중복 체크를 한다.
- 중복체크를 통과하면 미수집 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를 줄 수도 있다.
우선순위
신선도
- 웹페이지는 변경이 잦으므로 재수집할 필요가 있다.
- update history나 우선순위를 활용하여 재수집하는 전략을 세우는 것이 좋다.
미수집 URL 저장소를 위한 지속성 저장장치
- 처리해야할 URL을 모두 메모리에 저장하는 것은 안정성/규모 확장성에 맞지 않다.
- 따라서 URL의 대부분은 디스크에 두지만, 메모리 버퍼에 Queue를 두어 IO로 생기는 time을 줄이는 전략을 사용하자.
HTML 다운로더
Robots.txt
- 로봇 제외 프로토콜로서 크롤러가 수집/수집하면 안되는 페이지의 정보를 가지고 있다.
구글
성능 최적화
- 분산 크롤링
- 위에서 queue selector가 쓰레드별로 URL을 할당하던 것을 분산 서버로 처리하여 최적화한 사례
- 도메인 이름 변환 결과 캐시
- DNS 요청을 기다리는 시간 동안 block되므로 캐시에 DNS 요청 결과를 캐싱한다.
- 지역성
- 크롤링을 하는 페이지의 서버와 가까운 곳의 서버로 크롤링을 하여 transport delay를 줄인다.
- 짧은 타임아웃
- 응답이 느린 서버에 대한 타임아웃 값을 짧게 하여 반응성을 높여라
안정성
- 안정해시
- 크롤링 상태 및 수집 데이터 저장
- 장애에 대처할 수 있도록 주기적으로 상태와 데이터를 디스크에 저장한다.
- 예외 처리
- 예외가 발생했을 때, 서버가 죽지 않도록 처리해야 한다.
- 데이터 검증
- 시스템 오류 방지를 위해 크롤링한 데이터를 검증한다.
확장성
- 시스템은 항상 확장을 고려해야 한다.
- 위의 설계에서 나왔던 모든 컴포넌트들은 확장을 할 수 있어야 한다.
문제 있는 컨텐츠 감지 및 회피
마무리
- SSR
- 동적인 페이지는 렌더링 전에는 링크 정보가 없기 때문에 미리 서버에서 렌더링을 한 다음에 링크 정보를 긁어오는 것이 좋다.
전체가 로딩된지는 어떻게 알아야 되나?
- 원치 않는 페이지 필터링
- 안티 스팸 컴포넌트로 불필요한 페이지를 걸러낸다.
- DB 다중화 및 샤딩
- 미수집 URL이나 컨텐츠 저장소 등은 다중화/샤딩을 통해 확장성/안정성을 높인다.
- 수평적 규모 확장성
- scale out을 하기 위해서 각 서버는 stateless 하게 만든다.
참조
알렉스 쉬, 가상 면접 사례로 배우는 대규모 시스템 설계 기초, 인사이트, 2021, 141p-163p