포스팅에 사용된 그림은 책에서 제공하는 그림들 입니다.
검색엔진에서 널리 쓰는 기술인 웹크롤러를 설계해보자.
웹 크롤러는 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적이다.
또한, 크롤러는 아래와 같은데에 이용된다.
검색 엔진 인덱싱(Googlebot은 구글의 검색 엔진이 사용하는 웹 크롤러임)
웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차를 말함. 많은 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙 한다.(미국 국회 도서관의 EU 웹 아카이브)
웹 마이닝: 웹 마이닝을 통해 인터넷에서 유용한 지식을 도출해 낼 수 있다. 일례로, 유명 금융 기업들은 크롤러를 사용해 주주총회 자료나 연차 보고서를 다운 받아 기업의 핵심 사업 방향을 알아내기도 한다.
웹 모니터링: 크롤러를 사용하면 인터넷에서 저작권이나 상푱권이 침해되는 사례를 모니터링 할 수 있따. 일례로 디지마크 회사는 웹 크롤러를 사용해 불법으로 사용된 저작물을 찾아내서 보고한다.
웹 크롤러의 복잡도는 웹 크롤러가 처리해야 하는 데이터의 규모에 따라 달라진다. 몇 시간이면 끝낼 수 있는 작업일 수 도 있고, 별도의 엔지니어링 팀을 꾸려서 지속적으로 관리하고 개선해야 하는 초대형 프로젝트 일 수 도 있다.
웹 크롤러의 기본 알고리즘
기본 알고리즘을 보면 단순해 보이지만, 정말 이렇게 간단할까? 엄청난 규모 확장성을 갖는 웹 크롤러를 설계하는 것은 엄청나게 어려운 작업이다. 가상 면접 사례로 예시를 들어보고, 설계 범위를 좁혀보자.
위와 같은 질문들을 하여 요구사항을 명확히 하는 반면, 웹 크롤러가 만족시켜야 할 속성에 주의를 기울어야 한다.
아래의 추정치는 많은 가정으로부터 나온 것이다. 아래와 같이 추정해보자.
우선 이 다이어그램에 등장하는 컴포넌트 각각이 어떤 기능을 수행하는지 살펴보자.
전체 웹을 크롤링해야 하는 경우에는 시작 URL을 고를 때 크롤러가 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직하다. 일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략을 사용. 또 다른 방법은 주제별로 다른 시작 URL을 사용하는 것이다. 예를 들어 URL공간을 쇼핑, 스포츠, 건강 등등의 주제별로 세분화하고 그 각각에 다른 시작 URL을 사용하는 것.
시작 URL을 무엇으로 쓸 것 인지에 대한 질문에 정답은 없다.
대부분의 현대적 웹 크롤러는 크롤링 상태를
로 나누어 관리한다.
이중 1. 다운로드 할 URL을 관리하는 컴포넌트를 미수집 URL 저장소라고 부른다. 그냥 FIFO큐라고 생각하면 된다.
HTML 다운로더는 인터넷에서 웹 페이지를 다운로드하는 컴포넌트이다. 다운로드할 페이지의 URl은 미수집 URL 저장소가 제공한다.
웹 페이지를 다운받으려면 URL을 IP주소로 변환하는 절차가 필요한데, HTML다운로더는 도메인 이름 변환기를 이용하여 URL에 대응되는 IP주소를 알아낸다.
웹 페이지를 다운로드하면 파싱과 검증 절차를 걸쳐야 하는데, 왜냐하면 이상한 웹 페이지는 문제를 일으킬 수도 있는데다 저장공간만 낭비하게 되기 때문이다. 크롤링 서버 안에 콘텐츠 파서를 구현하면 문제가 될 수 있으므로, 독리보딘 컴포넌트로 만들자.
웹에 공개된 연구 자료에 의하면 29%는 중복된 콘텐츠이다. 중복된 콘텐츠를 피하기 위한 가장 간단한 방법은 두 HTML 파일을 비교하면 되지만, 10억개 정도에 달하는 경우에는 느리고 비효율적이어서 웹 페이지의 해시 값을 비교하는 것이 효율적인 방법일 것이다.
콘텐츠 저장소는 HTML 문서를 보관하는 시스템이다. 저장소를 구현하는데 쓰일 기술을 고를 때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간 등을 고려해야한다. 아래에서 할 설계는 메모리와 디스크를 동시에 사용할 때의 설계 예시다.
URL 추출기는 HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다. 상대 경로는 앞에 도메인 주소를 붙여 절대 경로로 변환한다.
URL 필터는 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL 등을 크롤링 대상에서 배제하는 역할
이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 해야한다. 이미 방문한 적 있는 URL인지 추적하면 같은 URL을 여러 번 처리하는 일을 방지할 수 있으므로 서버 부하를 줄이고 시스템이 무한 루프에 빠지는일을 방지할 수 있다.
해당 방법으로는 블룸 필터나 해시테이블이 가장 널리 쓰인다.
URL 저장소는 이미 방문한 URL을 보관하는 저장소이다.
이제 위에서 보았던 컴포넌트들이 상호 작용하는 작업 흐름 관점에서 살펴보자.
웹은 유향 그래프나 같다. DFS는 그래프의 크기가 어느 정도로 깊숙이 가게 될지 가늠하기 어렵다.
따라서 웹 크롤러는 보통 BFS를 사용한다. BFS는 FIFO 큐를 사용하는 알고리즘이다. 이 큐의 한쪽으로는 탐색한 URL을 집어넣고, 다른 한쪽으로는 꺼내기만 한다. 이렇게 하면 두 가지 문제점이 있다.
wikipedia.com 페이지에서 추출한 모든 링크는 내부 링크, 즉 동일한 wikipedia.com 서버의 다른 페이지를 참조하는 링크다. 결국 크롤러는 같은 호스트에 속한 많은 링크를 다운받느라 바빠지는데 이 때 링크들을 병렬적으로 처리하게 된다면 위키피디아 서버는 수많은 요청으로 과부하에 걸리개 된다. 이런 크롤러를 예의 없는 크롤러로 간주한다.
미수집 URL 저장소를 활용하면 이런 문제를 좀 더 쉽게 처리할 수 있다. URL 저장소는 다운로드할 URL을 보관하는 장소인데, 이 저장소를 잘 구현한다면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다. 미수집 URL 저장소의 구현 방법에 대해서는 논문도 다수 나와 있는데, 이 연구 결과중 중요한 것을 중요해보면 아래와 같이 요약할 수 있다.
웹 크롤러는 수집 대상 서버로 짧은 시간안에 너무 많은 요청을 보내는 것을 삼가해야 한다.
너무 많은 요청을 보내는 것은 ‘무례한’ 일이며, 때로는 이를 Dos공격으로 간주되기도 한다.
아무런 안전장치가 없는 웹 크롤러의 경우, 초당 수천 건의 페이지 요청을 동일한 웹 사이트로 보내어 사이트를 마비시켜버릴 수도 있다.
예의 바른 크롤러를 만드는데 있어서 지켜야할 한가지 원칙
위 요구사항을 만족 시키려면, 웹 사이트의 호스트명과 다운로드를 수행하는 작업 스레드사이의 관계를 유지하면 된다. 즉, 다운로드 스레드는 별도 FIFO 큐를 가지고 있어서, 해당 큐에서 꺼낸 URL만 다운로드한다.
아래는 이 원칙을 지키기 위한 설계를 보여준다.
예를들어, 애플(Apple) 제품에 대한 사용자 의견이 올라오는 포럼의 한 페이지가 애플 홈페이지와 같은 중요도를 갖는다고 보기는 어려울 것이다. 둘다 ‘애플’이 키워드로 등장하기는 했지만, 크롤러 입장에서는 중요한 페이지 즉, 애플의 홈페이지를 먼저 수집하도록 하는 것이 바람직할 것이다.
유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크, 트래픽의 양, 갱신 빈도 등 다양한 척도를 사용할 수 있다. 아래 그림의 순위결정장치는 URL의 우선순위를 정해주는 컴포넌트이다.
아래 그림은 이를 반영한 전체 설계이다. 그림을 보면 두 개의 모듈이 존재하는 것을 볼 수 있다.
웹 페이지는 수시로 추가되고, 삭제되고, 변경된다. 따라서 데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집할 필요가 있다. 그러나 모든 URL을 재수집하는 것은 많은 시간과 자원이 필요한 작업이다. 이 작업을 최적화하기 위한 전략으로는 다음과 같은 것이 있다.
검색 엔진을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수억 개에 달한다. 그러니 그 모두를 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다. 전부 디스크에 저장하는 것도 좋은 방법은 아닌데, 느려서 쉽게 성능 병목지점이 되기 때문이다.
따라서 아래 설계안은 절충안을 택했다. 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것이다. 버퍼에 있는 데이터는 주기적으로 디스크에 기록할 것이다.
HTML 다운로더는 HTTP 프로토콜을 통해 웹 페이지를 내려 받는데, 다운로더에 대해 알아보기 전 로봇 제외 프로토콜 부터 살펴보자.
로봇 제외 프로토콜이라고 부르기도 하는 Robots.txt는 웹 사이트가 크롤러와 소통하는 표준적 방법이다. 이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있다. 따라서 웹 크롤러가 웹 사이트를 긁어 가기 전에 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 한다.
Robots.txt 파일을 거푸 다운로드하는 것을 피하기 위해, 이 파일은 주기적으로 다시 다운받아 캐시에 보관할 것이다. 아마존의 Robotstxt (/https://www.amazon.com/robots.txt) 파일을 예로 보면 다음과 같은 규칙이 나열되어 있다.
💡 아마존의 Robots.txt https://www.amazon.com/robots.txt 아래 디렉터리의 내용은 다운받을 수 없다.User-agent: Googlebot
Disallow: /creatorhub/
Disallow: /rss/people/reviews*
Disallow: /gp/pdp/rss/reviews
Disallow: /gp/cdp/member-reviews
Disallow: /gp/aw/cr
Robots.txt도 중요하지만 HTML 다운로더를 설계할 때는 성능최적화도 아주 중요하다.
아래는 HTML 다운로더에 사용할 수 있는 성능 최적화 기법들이다.
성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법. 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다. 이 구성을 위해 URL 공간은 작은 단위로 분할하여, 각 서버는 그중 일부의 다운로드를 담당하도록 한다. 아래 그림을 봐보자.
도메인 이름 변환기는 크롤러 성능의 병목 중 하나인데, 이는 DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문. DNS 요청의 결과를 받기 전까지는 다음 작업을 진행할 수 없다. DNS 요청이 처리되는 보통 10ms에서 200ms가 소요된다. 크롤러 스레드 가운데 어느 하나라도 이 작업을 하고 있다면 다른 스레드의 DNS 요청은 전부 블록된다. 따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡(cron job)등을 돌려 주기적으로 갱신하도록 해 놓으면 성능을 효과적으로 높일수 있다.
크롤링 작업을 수행하는 서버를 직역별로 분산하는 방법이다. 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간은 줄어들 것이다. 지역성을 활용하는 전략은 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능하다.
어떤 웹 서버는 응답이 느리거나 아예 응답하지 않는다. 이런 경우에 대기시간이 길어지면 좋지 않으므로, 최대 얼마나 기다릴지를 미리 정해두는 것이다. 이 시간 동안 서버가 응답하지 않으면 크롤러는 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어간다.
최적화된 성능뿐 아니라 안정성도 다운로더 설계 시 중요하게 고려해야 할 부분이다. 시스템 안정성을 향상시키기 위한 접근법 가운데 중요한 몇 가지는 아래와 같다.
진화하지 않는 시스템은 없는법이다. 이런 시스템을 설계할 때는 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경 써야 한다. 본 예제의 경우에는 새로운 모듈을 끼워 넣음으로써 새로운 형태의 콘텐츠를 지원할 수 있도록 설계하는 방법을 아래 그림으로 살펴보자.
이번 절에서는 중복이거나 의미 없는, 또는 유해한 콘텐츠를 어떻게 감지하고 시스템으로부터 차단할지 살펴보자.
앞서 살펴본 대로, 웹 콘텐츠의 30%는 중복이다. 해시나 체크섬을 사용하면 중복 콘텐츠를 보다 쉽게 탐지할 수 있다.
거미 덫은 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지이다. 예를 들어, 다음과 같이 무한히 깊은 디렉터리 구조를 포함하는 링크가 있다고 해 보자.
이런 덫은 URL의 최대 길이를 제한하면 회피할 수 있다. 하지만 모든 종류의 덫을 피할 수 있는 만능 해결책은 없다. 이런 덫이 설치된 웹 사이트인지 알아내는 과정은 어렵지 않은데, 기이할 정도로 많은 웹 페이지를 가지고 있는 것이 일반적이라서다. 하지만 덫을 자동으로 피해가는 알고리즘을 만들어 내는 것은 까다롭다.
한 가지 방법은 사람이 수작업으로 덫을 확인하고 찾아낸 후에 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어두는 것이다.
어떤 콘텐츠는 거의 가치가 없다. 광고나 스크립트 코드, 스팸 URL 같은 것이 가치가 없다 라고 볼 수 있다. 이런 콘텐츠는 크롤러에게 도움될것이 없으므로, 가능하다면 제외해야 한다.
이번 장에서 우리는 좋은 크롤러가 갖추어야 하는 특성을 살펴보았다. 규모 확장성, 예의, 확장성, 안정성 등이다. 아울러 크롤러의 설계안을 제시하고, 핵심 컴포넌트에 쓰이는 기술들도 알아보았다. 규모 확장성이 뛰어난 웹 크롤러 설계 작업은 단순하지 않다. 웹이 워낙 방대한 데다, 수없이 많은 덫이 도사리고 있기 때문이다. 추가적으로 웹 크롤러를 설계할 때 생각해보면 좋은것드릉ㄹ 살펴보고 마무리해 보자.