웹 크롤러의 구조와 구현

웹 크롤러의 구조와 구현

수집기는 다운로더, 저장소, 스케줄러 등 세 모듈로 이루어져 있고 결정적인 모듈은 스케줄러이다.

스케쥴러는 '프론티어(frontier)'로도 알려져 있는 방문할 URL의 큐를 유지하고, 하나 또는 그 이상의 다운로더를 특정 순서로 큐에서 순서대로 나오는 그 URL에 보내게 된다. 

다운로더는 각 URL에 해당하는 내용을 검색해서 구문 분석 후 저장소 모듈에 보내며 나중에 색인화되고 검색하게 된다.

또 저장소 모듈은 해당 페이지에서 검색된 메타데이터를 스케줄러에 제공하게 되는데 메타데이터는 스케줄링 정책을 구동시키는 데 중요한 정보가 된다. 

* 프론티어(frontier)

웹 크롤러는 master/slave 모델을 따르며 Master(Frontier), Slave(Agent), Monitor 세가지의 컴포넌트로 이루어져있다.

Master(Frontier)는 서버역할을 하며 Agent가 수집한 URL을 전송받아 관리하고 필터링된 URL을 다시 Agent로 분배한다.

Slave(Agent)는 Frontier로부터 URL을 전송받아 해당 URL의 웹페이지(HTML)를 처리한다. 웹페이지 처리 결과로 다른 웹페이지에 대한 URL link와 이미지 등의 리소스 URL link를 추출한다. 추출된 모든 URL 링크는 Frontier로 전송한다.

Monitor는 Frontier와 Agent의 동작상태 모니터링 하고 제어기능을 포함한다. 

<고수준의 전형적인 웹 수집기 구조>

밑에 그림은 위의 그림의 스케줄링과 저장소를 세분화한 것이다.

• 스케줄링을 나눠서 장기 스케줄링(Long-term Scheduler)과 단기 스케줄링(Short-term Scheduler)로 구분할 수 있다.

장기 스케줄링 - 품질과 신선도 평가에 따라 다음 방문할 페이지를 결정. 시간 간격 : 몇 시간 혹은 며칠

단기 스케줄링 - 공손도 정책 혹은 네트워크 사용 최적화에 따라 페이지를 재배정. 시간간격 : 몇 초나 몇 분

* 시간간격은 수집기에 설정된 대기 시간에 의존한다.

• 저장소를 세 부분으로 나눠서 (리치)텍스트, 링크, 메타데이터로 구분할 수 있다.

중점 수집기는 페이지 분류를 위한 텍스트를 사용하고 내려받기를 위해 URL을 서열화 한다. 

일반 수집기는 메타데이터와 링크를 사용하여 어떤 페이지를 다음에 내려 받을지 결정한다. 

<웹 수집기의 상세 구조>

수집기의 구현에서 나타나는 실직적 쟁점

대역폭과 저장 용량과는 별도로 수집기의 구현은 많은 쟁점이 있다. 수집기가 여러 다른 시스템과 상호작용을 해야 하고 그 시스템들은 다양한 수준의 표준 준수와 서비스 품질을 가지고 있기 때문이다. 웹 수집에서 가장 큰 쟁점은 다중 자원으로부터 어떻게 페이지를 내려받느냐는 것이다. DNS와 웹 서버의 반응 시간이 매우 다르기 때문에 복잡하고 웹 서버 가동 시간도 보장받기가 어렵다. 며칠이나 몇 주 동안 멈추었다가 재가동하는 웹 서버가 많기 때문이다.

여러 쟁점들

- DNS 해석(DNS Resolution)

DNS는 일시적 DNS 고장과 기형 또는 DNS 기록 오류 등의 DNS 해석의 효율성 문제가 있다. 

수집기가 로컬 DNS를 포화시킬 수 있으므로 대부분의 수집기는 DNS 캐싱을 하는데 즉, 더 자주 해석되는 도메인 이름의 IP 주소를 저장한다. 이런 종류의 캐싱은 포화가 되지 않아도 캐시에서 도메인 이름 해석하는 것은 표준 DNS 해석을 사용하는 것보다 빠르기 때문에 중요하다.

- URL 정규화(URL Canonization)

https://moz.com/blog/canonical-url-tag-the-most-important-advancement-in-seo-practices-since-sitemaps

웹은 기본적으로 동일한 내용을 가리키는 많은 양의 URL을 지니고 있다. 내려받은 이후에 중복이거나 근접중복으로 인식될 수 있지만 슁글링(shingling)을 통해 간단한 문법 규칙의 집합을 URL에 적용함으로써 중복 내려받기를 피할 수 있다. 

하지만 비슷한 텍스트를 포함하는 URL을 인식하는 대부분의 규칙이 특정 서버 구현의 부산물이기 때문에 기본 파일(index.html과 같은) 이름을 제거하거나 전형적인 세션 아이디 매개변수, 쿠기기반 세션의 선호 정보 제거하는 방법을 사용하여 중복을 피한다. 

*슁글링(shingling)

- 문서를 정해진 윈도우 사이즈의 슁글(shingle)로 표현하고, 이것을 이용하여 문소의 변경도를 측정. 

- 0~1 사이의 값으로 표현. 

- 슁글 크기에 따른 연산 속도와 정확도 사이의 trade-off가 존재.

문서를 정해진 크기의 토큰으로 자른 슁글을 이용하여 표현하고, 이것을 통하여 중복 문서를 찾아낸다.
출처: http://ra2kstar.tistory.com/104 [초보개발자 이야기.]

- 구문 분석(Parsing)

많은 웹 페이지들이 HTML 언어의 사양을 충실히 지키지 않고 형편없는 코드로 작성되있다. 이런 원인 중 하나는 웹 브라우저는 잘못 코딩이 되어있더라도 HTML이 보이게 하도록 설계되어있기 때문이다. 

엄격한 HTML 구문 분석은 가능하지 않기 때문에 수집기의 구문 분석기 모듈은 HTML 코딩의 오류를 허용해야만 하며 불명확한 경우에도 처리해야 한다. 같은 이유로 웹 페이지를 통한 DOM(Document Object Model) 트리 구축은 대부분의 경우 코딩 오류를 바로잡는 사전 과정이 요구된다.

*DOM - 플랫폼과 언어에 중립적인 인터페이스로 소프트웨어가 문서의 내용, 구조 및 스타일에 동적으로 접근하거나 수정하는 것을 허용한다. 문서는 더 철될 수 있고 처리의 결과를 표현된 페이지로 되돌려 포함시킬 수 있다. 즉 DOM은 Java같은 프로그램언어로부터 온 HTML과 XML 객체를 다루는 상호 동작이 가능한 클래스와 메소드를 제공한다. 

구문 분석 중 정보 추출은 매우 중요하다. 이 과정은 제목과 머릿글(heading) 같은 간단한 HTML 태그 추출로부터 복잡한 자연어 과정까지 있는데 자연어 과정에서 주요한 부분 중 하나로 엔티티 추출이 있다. 엔티티(entity)는 이름이 될 수도 있고 날짜와 다른 임시 엔티티, 지리적 위치 등이 될 수도 있다. 

-소프트(Soft)-404 페이지

http://clownfishcompany.ca/blog/google-webmaster-tools-crawl-errors-report-http-status-codes/

웹상에서 웹 수집기에 가장 손해를 주는 쟁점은 URL이 존재하지 않는지를 알기 어렵다는 것이다. 많은 웹사이트에서 수집기가 존재하지 않는 페이지를 내려받으려 하면 서버는 미리 제작한 오류 페이지로 재전송하여 되돌려 주는데 오류 조건이라는 신호를 응답 헤어데 실어 주지 않는다는 것이 문제다. 404는 페이지가 존재하지 않는 오류의 번호이다. 

'소프트-404' 페이지는 검색엔진의 수집기에 손해를 입히는데 그 이유는 별 내용 없는 곳에 색인을 만들기 때문이다. 이 문제를 완화시키기 위해 몇몇 웹 수집기는 거의 확실히 존재하지 않을 만한 임의 형태의 URL을 요청하고 제대로 된 응답 코드를 받게되면 그 때 검증한다. 또한 소프트 404 페이지는 텍스트 분류기를 통해 이런 페이지가 표현하는 메시지와 연관된 특정 구나 키워드를 학습하여 자동으로 인지할 수 있다.

-중복(Duplicates)

웹상에 복제된(mirrored) 내용이 많이 쓰이고 있다. 이들 중복 중 몇몇은 고의적이고 페이지 복제에 상응하는데 다른 중복은 고의적은 아니고 웹 사이트가 구축된 방식의 부산물이다. 

비고의적 중복의 주 원인은 URL에 내재된 식별자가 사용자의 행동을 추적하기 때문이다. 이들 식별자는 논리적 세션을 탐지하기 위해 사용된다. 웹 수집기의 관점에서 보면 이들 세션 아이디는 중복의 중요한 원인인데 수집기는 두 페이지가 의미적으로 같은 내용이라고 정확하게 알 수 없기 때문이다. 이러한 정보가 사전 지식으로 수집기에 주어지지 않으면 한 사이트에서만 여러 사람의 세션값이 존재할 수 있기 때문에 무한한 수의 URL을 발견할 수 있다. 수집기는 네트워크 자원 낭비를 피하기 위해 내려받기를 중단해야 한다.

병렬 수집(Parallel Crawling)

웹 수집은 더 나은 확장성과 고장에 대한 내성을 갖기 위해서 다중 스레드를 통해 이루어져야 하며 매우 큰 문서모음에 대해서 분산처리를 해주어야 한다. 

수집 시 다중 스레드 사용하는 이유는 수집기가 사용 가능한 대역폭이 일반적으로 개별 웹 사이트의 대역폭보다 훨씬 크기 때문이다. 이는 수집기가 각 개별 내려받기 스레드가 끝나기를 기다리기 전에 다음 페이지를 요청해야 함을 의미한다. 

분산환경에서 수집기를 실행할 때 가장 중요한 것은 동일 페이지를 두 번 이상 내려받는 것을 피해 웹 서버에 과부하를 주지 말아야 한다는 것이다. 통신 오버헤드를 최소화해야 한다는 것을 목표로 한다. 이상적으로는 매 페이지가 단일 프로세스에 의해 내려받기를 하는 것이다.

완전 분산 수집 시스템은 새로운 URL 발견에 대해 어떤 정책을 요구한다. 새로운 URL을 발견한 프로세스가 그것을 내려받아야 하는지 결정해야하는 것은 할당 함수인데 처음부터 모든 프로ㅔ스에게 알려져 있다. 한 웹 사이트 대부분의 링크가 동일 사이트의 페이지라는 사실을 활용하기 위해서 할당 함수가 동일 호스트 페이지를 한 프로세스에 할당해야 한다. 

효율적인 할당 함수는 다음 세 가지 주요 특성을 가져야 한다.

1. 각 수집 프로세스가 대략 같은 수의 호스트를 가져야 하고(균형 특성)

2. 만일 수집 프로세스의 수가 증가하면 각 프로세스에 할당되는 호스트의 수가 줄어야 하며(반-가변성 contra-variance 특성)

3. 할당은 수집 프로세스를 동적으로 추가하고 제거할 수 있어야 한다는 것.

--> 일관 해싱(consistent hashing)을 사용할 것을 제안.

이는 해싱 버킷을 복제해서 한 버킷을 추가하거나 제거할 때 전체 테이블을 재해싱 하지 않아도 모든 기대하는 특성을 이룰 수 있다. 또한 충돌만 되지 않는다면 두 번 수집되는 페이지가 없다.

* 일관된 해싱(Consistent hashing)      위키백과

https://dzone.com/articles/simple-magic-consistent

 웹서버의 갯수가 변동하는 가운데 요청을 분산하는 방법을 말한다. 해시테이블의 크기가 변할 때, 평균적으로 K/n의 키만 재매핑되면 된다. 즉 노드나 슬롯의 개수가 바뀔 때, 노드의 추가나 삭제를 할 때, 오직 K/n의 아이템만 다시 섞이면 되는 것이다. (n은 전체 노드의 갯수, K는 item의 개수) 기존의 해싱에서는 슬록의 개수 변화가 거의 모든 키가 다시 재매핑돼야만 했다. (키와 슬롯간의 매핑이 모듈러 연산에 의해 정의되었기 때문)

기술

일관된 해싱은 모든 데이터를 hash ring의 각 지점에 매핑 시키는데에 기반을 둔다. 시스템은 각각의 이용가능한 머신을 hash ring의 무수한 랜덤하게 분산된 포인트에 매핑시킨다.

데이터가 어디 위치해야하는지를 찾기 위해서, 시스템은 hash ring상에서의 데이터의 키의 위치를 찾는다. 그후에 처음으로 만나는 버킷에 도달할때까지 hash ring들 돈다. 각각의 버킷은 그 버킷의 포인트와 이전 버킷의 포인트 사이에 존재하는 모든 리소스를 포함한다.

버킷을 추가할때도 비슷한 과정이 일어난다. 버킷을 추가하면서 그 버킷과 그 옆의 버킷 사이의 모든 리소스는 새로운 버킷에 추가된다. 이 리소스들은 더이상 이전의 버킷과 연관되지 않으며, 데이터 선택 메서드에 의해서 이전의 버킷에서 찾아지지 않는다.

각각의 버킷과 연관된 키의 부분들은 버킷이 매핑된 각들의 개수가 변함에따라 바뀔수있다.