웹 크롤러
목차
웹 크롤러
•
웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 기술
활용
•
검색 엔진 인덱싱 : 웹 페이지를 모아 로컬 인덱스를 만든다. (Googlebot)
•
웹 아카이빙 : 장기보관을 목적으로 정보를 모음
•
웹 마이닝 : 유용한 지식을 도출
•
웹 모니터링 : 저작권, 상표권 침해 사례 모니터링
알고리즘
1.
URL 집합의 모든 웹 페이지를 다운로드한다.
2.
다운받은 웹 페이지에서 URL들을 추출한다.
3.
추출한 URL로 1부터 반복한다.
속성
•
규모 확장성 : 여러 대의 크롤러로 병렬 수집한다.
•
안정성(robustness) : 비정상적 입력이나 환경에 대응한다.
•
예절(politeness) : 짧은 시간에 너무 많은 요청을 보내면 안된다.
•
확장 : 새로운 형태의 콘텐츠(음악, 영상 등)를 쉽게 지원해야 한다.
•
관리과 재구성 : 여러 지표와 설정을 위한 인터페이스를 정해야 한다.
설계
개력적 설계안
•
seed URLs : 크롤링의 시작 주소 지정
◦
루트 도메인(*.naver.com, *.google.com)을 쓴다.
◦
지역, 주제별로 다른 seed를 사용한다.
•
URL Frontier : 아직 fetch 되지 않은 URL FIFO queue
•
HTML Fetcher : URL Frontier에서 주소를 가져와 웹 페이지를 다운로드한다.
•
DNS Resolver : URL을 IP로 바꾼다.
•
HTML Parser : parsing과 validation을 수행, 불필요한 웹 페이지를 버린다.
•
Duplicate Detection : 웹 페이지의 해시값을 비교해서 중복을 제거한다.
•
Data Storage & Caching : HTML 문서를 저장한다.
•
URL Extractor : 파싱한 HTML 페이지 중 URL을 추출한다. 상대 경로는 절대 경로로 변환한다.
•
URL Filter : 특정 확장자, 오류가 나는 URL, deny list에 있는 URL 등 규칙에 의해 배제한다.
•
URL Lodaer/Detector : 블룸 필터나 해시 테이블로 중복 URL을 제거한다.
•
URL Storage : 이미 방문한 URL을 보관
상세 설계
DFS vs BFS
•
웹은 하이퍼링크로 연결된 방향이 있는 그래프이다.
•
크롤링은 이 그래프를 탐색하는 것이고, DFS 혹은 BFS 알고리즘을 사용한다.
•
웹 그래프의 깊이를 알 수 없으므로 DFS는 적합하지 않다.
•
링크는 같은 서브 도메인을 가리키는 경향이 크기 때문에, BFS(너비 우선 탐색)를 사용하면 한 서버에 많은 부하를 줄 수 있다. (impolite)
•
그래서 페이지 순위, 트래픽 등을 지표로 BFS 큐의 우선순위를 조정한다.
URL Frontier
BFS 알고리즘의 큐를 구현한 컴포넌트이다. politeness와 freshness를 구별한다.
우선순위(Priority)
•
페이지 랭크, 트래픽 양, 갱신 빈도 등의 지표를 사용해 우선순위를 정한다.
•
Priority Router : 우선순위별로 URL을 큐에 넣는다.
•
Priority Selector : 높은 순위부터 데이터를 꺼내 넘긴다.
예의(politeness)
•
예의 바른 크롤러는 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.
•
이를 위해 호스트 이름별로 다른 FIFO 큐를 만들고 이 큐들을 돌아가면서 사용한다.
•
Politeness Router : 호스트별로 URL을 큐에 넣는다.
•
Politeness Selector : 큐를 순회하면서 하나씩 URL을 꺼낸다.
•
Mapping Table : 호스트 이름과 큐를 매핑한다.
신선도(Freshness)
•
이미 같은 페이지도 주기적으로 다시 다운로드한다.
•
웹 페이지 변경 이력, 우선순위를 고려하여 다운로드 주기를 결정한다.
저장장치
URL이 방대하기 때문에 일단 메모리 버퍼에 넣고 천천히 디스크에 저장하는 방식을 쓴다.
HTML Fetcher
Robots.txt
•
로봇 제외 프로토콜이라고도 불리며, 크롤러가 수집해도 되는 페이지 목록을 정한 파일이다.
성능 최적화
•
분산 크롤링 : Politeness Selector는 여러 서버로 URL을 배분한다.
•
DNS Resolver 캐싱 : DNS를 cron job을 통해 주기적으로 캐싱한다.
•
지역성 : 크롤링 서버를 웹 서버가 있는 지역에 둬서 latency를 줄인다.
•
짧은 타임아웃 : 오래 기다리지 말고 빨리빨리 다음 페이지로 넘어간다.
안정성
•
안정 해시 : 부하를 효율적으로 분산한다.
•
크롤링 상태 및 수집 데이터 저장 : 크롤링 서버에 장애가 발생할 경우 쉽게 복구할 수 있다.
•
예외 처리
•
데이터 검증
확장성
•
위 그림처럼 기능별로 컴포넌트를 분리해서 새로운 컴포넌트를 추가하고 변경하기 용이하도록 한다.
문제 있는 콘텐츠 감지 및 회피
•
중복 콘텐츠 : 해시나 체크섬으로 탐지
•
spider trap : 무한히 깊은 URL에 빠지지 않도록 최대 길이를 제한하거나 deny list를 설정한다.
•
데이터 노이즈 : 광고, 스팸 URL 등을 제거한다.
추가 논의
•
Server-side Rendering(Dynamic Rendering) : 요즘은 동적으로 웹사이트를 만들기 때문에 단순히 HTML만 다운로드하면 안되고, 렌더링을 한 다음 파싱해야 한다.
•
원치 않는 페이지 필터링 : 품질이 조악하거나 스팸인 사이트를 거른다.
•
데이터베이스 다중화 및 샤딩 : Data layer의 가용성(HA), 확장성, 안정성이 좋아진다.
•
수평 확장 : 서버를 stateless하게 만들어 수평 확장을 하여 대규모 작업을 수행한다.
•
가용성(HA), 확장성, 안정성 : 사용자 수에 따른 규모 확장성 참조
•
데이터 분석 : 데이터를 분석해 시스템을 세밀하게 조정한다.
출처
•
Designing Web Crawler: System Design Interview Question : https://www.enjoyalgorithms.com/blog/web-crawler