읽을때 마다 새로운 지식을 알게되는 책이지만, 다음 챕터로 넘어 갈수록 너무 어려워져서 손이가지 않는 책으로 최대한 많이 이해하고 완독을 목표로 정리를 하기위해서 글을 작성하게 되었다.
처음에는 2부 부터 읽다가 왜 1을 읽지 않느냐는 질문을 받고 1부를 읽게되었고 1부 부터 읽는게 필수라고 할정도로 난이도 차이가 있다.
잘근잘근 씹어먹듯, 많은 지식을 남길 수 있도록 열심히 정리해보자!
가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 예스24
웹 크롤러 설계
웹 크롤러는 로봇(robot) 또는 스파이더 (spider)라고도 부른다.
검색 엔진에서 널리 쓰는 기술로 웹에 올라온 컨텐츠(+갱신된 컨텐츠)를 찾아내는 것이 목표입니다.
웹 크롤러는 아래와 같은 방식으로 주로 사용됩니다.
- 검색 엔진 인덱싱 (Search engine indexing)
- 웹 아카이빙 (web archiving)
- 웹 마이닝 (web mining) > 인터넷에서 유용한 지식등릉 도축
- 웹 모니터링 (web monitering) > 인터넷에 저작권이나, 상표권 침해 여부를 확인
웹크롤러의 기본 알고리즘은 다음과 같습니다.
1. URL 집합을 입력으로 주고, 해당 URL 이 가르키는 모든 웹페이지를 다운로드 한다.
2. 다운 받은 웹 페이지에서 URL 을 추출한다.
3. 추출된 URL들을 다운로드 목록 에 추가하고, 위의 과정을 반복한다.
웹크롤러 흐름 따라가기
웹 크롤러가 동작하는방식을 따라가면서 정리해보죠.
시작 URL 집합
웹 크롤링을 시작하는 출발점으로, 처음 크롤링을 시작하는 집합입니다. 각각 어떤 일을 처리하기 위해 크롤러를 사용 하는지에 따라서, 해당 집합을 잘 선택하는것이 중요합니다.
ex) 어떤 웹사이트로부터 찾아 나갈 수 있는 모든 웹페이지를 해당 도메인의 URL 을 시작 URL로 사용합니다.
미 수집 URL 집합
크롤링 싱태를 두가지로 나누어 관리합니다.
1) 다운로드 할 URL
2) 다운로드 된 URL
다운로드를 할 URL 을 저장 관리하는 컴포넌트를 URL 저장소(URL frontier)라고 부릅니다.
- FIFO 방식으로 URL 을 저장하고, 출력합니다.
HTML 다운로더
미수집 URL 로 부터 받은 URL을 인터넷에서 웹페이지를 다운로드한다.
도메인 이름 변환기
웹 페이지를 다운받기 위해 URL 을 IP 로 변환 하는 절차가 필요하다. 다운로드 하기 위한 주소를 알기위한 작업입니다.
컨텐츠 파서
웹페이지를 다운로드 하면 파싱, 검증 절차가 필요합니다. 해당하는 작업을 하기위해 동작합니다. 크롤링 서버 안에 콘텐츠 파서를 구현하면, 크롤링 과정이 느려지기 때문에 독립된 컴포넌트로 구현합니다.
중복 콘텐츠 확인
자료구조를 도입하여 데이터 구조의 중복을 줄이고, 데이터 처리에 소요되는 시간을 줄이기 위해 체크합니다. 중복 콘텐츠를 확인하기 위한 효과적인 방법은 웹페이지의 해시값을 비교하는 방식입니다.
콘텐츠 저장소
HTML 문서를 보관하는 시스템입니다. 유형, 크기, 저장소 접근빈도, 데이터 유효기간을 고려해 콘텐츠를 처리할 수 있어야 합니다.
URL 추출기
HTML 을 파싱하여, URL 을 추출합니다.
URL 필터
특정 콘텐츠 타입이나, 파일 확장자를 갖는 URL, 접속시 오류가 발생하는 URL, 접근 제외 목록 (deny list) 에 포함된 URL 등 크롤링 대상에서 배제하는 역할을 합니다.
방문한 URL
이미 방문한 URL 이나, 미수집 URL 등 저장소에 보관된 URL 을 추적할 수 있도록 하는 자료구조를 사용하여 처리합니다.
URL 저장소
이미 방문한 URL 을 저장하는 저장소 입니다.
다시 한번 정리하자면
구조를 정리하자면 다음과 같습니다.
- 시작 URL 을 미수집 URL 저장소에 저장합니다.
- HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져옵니다.
- 도메인 이름 변환기를 사용하여 URL 의 IP를 알아내고, 해당 IP 주소로 접속하여 웹페이지를 받습니다.
- 콘텐츠 파서는 다운된 HTML 페이지를 파싱하여, 검증합니다.
- 콘텐츠 파싱이 끝나면 중복 콘텐츠 인지 검색합니다.
- 중복 콘텐츠인지 확인하기 위해서, 해당 페이지가 이미 저장소에 있는지 확인합니다.
- 이미 저장소에 있다면, 처리하지 않고 버립니다.
- 저장소에 없는 컨텐츠일 경우 저장소에 저장한뒤 URL 추출기로 전달합니다.
- URL 추출기는 HTML 페이지에서 링크를 골라냅니다.
- 골라낸 링크를 URL 필터로 전달합니다.
- 남은 링크만 중복 URL 판별 단계로 전달합니다.
- 이미 처리한 URL 인지 확인하기 위하여, URL 저장소에 보관된 URL 인지 살핍니다.
- 저장소에 없는 URL 은 URL 저장소에 저장하고, 미수집 URL 저장소에도 전달합니다.
웹페이지 탐색
웹페이지는 유향 그래프와 같다고 할수 있습니다.
그래프 탐색을 위한 방법은 깊이 우선 탐색법(DFS), 너비 우선 탐색법 (BFS) 의 방법이 있습니다.
DFS 는 깊이 우선 탐색법인데, 그래프가 클수록 깊이를 가늠하기 힘들기 때문에 좋은 선택이 아닐 가능성이 높습니다.
보통 너비 우선 탐색을 사용합니다. 아래 이미지 처럼 BFS 는 FIFO 큐를 기반으로 사용하는 알고리즘을 사용합니다.
이미지에서 볼 수 있듯이, 각 페이지를 발견한 순서대로 처리합니다.
다만 문제가 존재하는데 다음과 같습니다.
1. 한페이지에서 나오는 URL 은 상당 수 같은 서버로 되돌아갑니다. 같은 호스트에 속한 많은 링크를 다운 받게 되는데, 이는 동일한 서버에 과부하에 빠지고, 크롤러는 예의없는 크롤러로서 동작하게 됩니다.
2. 표준 BFS 알고리즘은 우선순위를 두지 않고 있는데, 모든 웹페이지는 같은 중요성을 갖고있지 않으므로 페이지에 따라서 우선순위 구별이 필요합니다.
미수집 URL 저장소
미수집 URL 저장소를 이용해, 예의있는 우선순위를 구별할 수 있는 크롤러를 구현 할수 있습니다.
예의있는 크롤러
웹 크롤러는 수집 대상 서버로 짧은시간 안에 너무 많은 요청을 보내는것을 삼가야합니다. 예의있는 크롤러의 원칙은 한번에 한 페이지만 요청한다는 것으로, 같은 웹 사이트의 페이지를 다운 받는 테스크는 시간차를 두고 실행되어야 합니다.
같은 호스트명이 다운로드가 진행중인지를 관리하면서 작업스레드를 수행합니다.
아래와 같은 구조로 적용되면 좋을것같습니다.
큐 라우터 (queue router) : 같은 호스트에 속한 URL 은 언제나 같은 큐로 가도록 보장한다.
큐 선택기 (queue selector): 큐에서 나온 URL 을 지정된 작업 스레드에서 전달하는 작업을한다,
작업스레드 (worker thread): 전달된 URL을 다운로드 하는 작업을 수행한다. 순차적으로 처리되고, 일정지연시간을 둘 수 있다.
우선순위를 적용한다면
특정 척도에 따라서 URL 에 우선순위를 결정하는 방식으로 조금더 효율적으로 크롤링을 진행할 수 있다.
순위결정장치 (prioritizer) : URL 을 입력으로 받아 우선순위를 계산하여 큐에 할당합니다.
큐선택기 (queue selector): 순위가 높은 큐에 있는 URL을 더 자주 꺼내도록 프로그램 되어있다.
두 방식을 합쳐서 결합!
두 방식을 결합하면 다음과 같습니다.
HTML 다운로더
성능 최적화
아래와 같은 방법으로 성능 최적화를 할 수 있습니다.
1. 분산 크롤링으로 적용합니다.
2. 도메인 이름 변환 (URL->IP) 결과 캐싱
3. 지역성을 갖는것
4. 짧은 타임아웃 (응답이 안오는 페이지에대해서 빠르게 컷 하고 다음작업)
안정성
안정 해시(다운로드 서버의 부하를 줄이고 증축과 삭제시 문제없이 작업할 수 있도록 수행), 크롤링 상태 및 수집 데이터 저장(장애 발생시 복구하기위해 수집데이터를 지속적으로 저장),예외처리, 데이터 검증을 통해 다운로더의 안정성을 갖도록 설계할 수 있습니다.
문제있는 콘텐츠 감지 및 회피
- 중복 콘텐츠 감지
해시나 체크섬을 통해 중복콘텐츠를 쉽게 감지할 수 있습니다. - 거미 덫
거미 덫은 크롤러를 무한 루프에 빠뜨리도록 설계된 페이지이다. 이런 페이지는 최대 길이를 제한하는 방법으로 회피할 수 있다. 하지만 모든 종류의 덫은 피할 수 없고, 사람이 수 작업으로 덫을 확인하고 제외하는 방식으로 피할 수 있습니다.
마무리
이 페이지를 통해 크롤러의 원리와 내 블로그는 왜 검색 창에 뜨지 않는가에 대해 이유를 알게 해준 장이였습니다. 세부적으로 더 작업할 수 있는 부분은 책에 더 자세히 설명되어있으니 궁금하면 책을 통해서 한번 더 확인 하면 좋을것같습니다.
