1. 기본 구성


Master/Slave 모델을 따르며 다음과 같은 컴포넌트로 이루어져 있다.


1.1. Master(Frontier)


서버역할을 하며 Agent가 수집한 URL을 전송받아 관리하게 되며, 필터링된 URL을 다시 Agent로 분배한다.


1.2. Slave(Agent)


Frontier로부터 URL을 전송받아, 해당 URL의 웹페이지(HTML)를 처리한다. 웹페이지 처리 결과로 다른 웹페이

지에 대한 URL Link와 이미지 등의 리소스 URL Link를 추출한다. 추출된 모든 URL Link는 Frontier로 전송

한다.


1.3. Moniotor


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






2. 동작 개요


전체적인 동작개요는 다음 그림과 같다.


<그림 1. 웹 크롤러의 기본 구성도>



2.1. Master(Frontier)


  • 각 Agent가 방문해야 할 URL과 다운로드해야 하는 Resource URL 목록을 보관한다.
  • Agent가 새로 수집한 URL을 전송하면 필터링을 수행한 후 남겨진 URL을 방문해야 할 URL 목록에 추가한다.
  • Agent로 방문해야 할 URL을 분배한다.
  • 방문해야 할 URL목록이 모두 소진될 때 까지 위 3단계를 반복한다.


2.2. Slave(Agent)


  • Frontier로부터 전송받은 URL을 HTTP 프로토콜을 이용해 접근한다.
  • HTTP 응답으로 HTML 문서를 얻어 분석한다.
  • HTML 문서 분석결과로 다음 방문한 URL Link와 수집해야할 Resource URL Link를 추출한다.
  • 새로 수집된 모든 URL을 Frontier로 전송한다.


2.3. Moniotor


  • Frontier와 Agent의 동작상태를 모니터링하며 데이터를 시각적으로 재구성 출력한다.
  • Frontier와 Agent의 이상(anomaly) 상태를 파악한다.
  • Monitor를 통해 Frontier의 일부 기능을 실시간으로 제어할 수 있다.





3. 컴포넌트별 주요 프로세스

3.1. Master(Frontier)

3.1.1. 다음 방문해야할 URL Link 목록을 저장하는 자료구조는 다음과 같다.

<그림 2. URL 저장 자료구조>


서로 구분될 수 있는 URL(도메인이 서로 다른)을 따로 분리하여 별도의 FIFO에 각각 저장한다.
URL의 구분은 도메인명(예: www.daum.net)을 64bit Hash 알고리즘을 통해 정수로 변환하여 구분 할 수 있다.
(Rabin's fingerprinting algorithm) 또한, 메모리 공간 요구가 무한하게 커지는 것을 막기 위해 일정 크기이상으로 FIFO가 증가하면 Disk로 FIFO의 데이터를 Flush할 수 있어야 한다.

3.1.2. URL 필터

특정 URL 집한에 대한 Allow/Deny 동작을 정의한다. Frontier에는 다양한 필터가 존재하며, 각 필터에 정의된 룰에 따라 URL을 Allow할지 Deny할지 결정한다.

필터 목록은 다음과 같다.

  • URL 패턴 필터 : 특정 문자열을 포함하는 URL을 필터링한다.
  • URL 중복 필터 : 중복되는 URL을 필터링한다.
  • URL 국가 필터 : URL을 포함하는 웹 서버가 위치하는 국가의 코드를 확인하여 필터링한다.
  • 외부 URL 필터 : Tracking 모드로 동작 시 최초 Seed가 아닌 모든 URL을 필터링한다.

* Tracking 모드란, 웹크롤러가 특정 도메인의 페이지만을 수집하도록 설정된 상태를 말한다. 예를들어 웹크롤러에게 www.daum.net을 Tracking하도록 명령하면 웹크롤러는 www.daum.net 도메인의 서브도메인에 대한 페이지만을 수집/분석하고, 해당 도메인외의 URL을 처리하지 않는다.

특히 중복되는 URL을 제거하기 위한 SeenFilter는 메모리 공간의 효율적인 사용을 위해 URL 전체를 Hash 알고리즘을 통해 정수로 변환하여 처리하며, 앞서 처리된 모든 URL에 대한 집합 저장소가 일정 크기 이상으로 증가하면 Disk로 데이터를 Flush 한다.

<그림3. URL Seen Filter>


3.1.3. 접근관리

다수의 Agent가 짧은 시간동안 단일 웹 서버로 접근하는 것을 방지한다.
이것은 짧은 주기동안 크롤링 대상이 되는 웹서버에 과도한 부하를 발생시키지 않기 위해 중요하다. 이런 장치가 없다면 대상 웹 서버에서는 다수의 Agent접근을 DDoS 공격으로 오인할 수 있다.

3.1.4. 크롤러 함정 피하기

때로는 Agent가 의미없는 URL을 무한대로 발생시키는 특정 도메인에 갖혀 빠져나오지 못하는 경우가 발생한다. 
예를들어 웹에 구현된 달력과 같은 경우 각각의 날짜들에 대해 URL Link를 생성하는 경우가 있는데, Agent가 이러한 웹 페이지를 만날경우 의미있는 데이터는 수집하지 못하고 헤메이게 된다. 

이러한 크롤러 함정을 회피하기 위해 앞서 URL Filter에서 URL 패턴에 기반한 URL을 필터링할 수 있는 기법을 사용할 수 있다.
(달력과 같은 경우 calendar등과 같은 키워드가 URL에 포함되어 있으며 처리하지 않도록 한다.)

또는, 크롤링 대상이 되는 도메인에 대한 접근횟수/유효데이터/쓰레기데이터 등과 같이 통계데이터를 실시간으로 작성하고, 유효데이터와 쓰레기데이터의 추출 비율을 계산해 해당 도메인이 크롤러 함정을 포함하고 있는지 유추할 수 있다. 


Master(Frontier)의 주요 특징을 요약하면 다음과 같다.

특징

 요약설명 

 인터넷 자동 크롤링

 초기 Seed URL로부터 추출되는 모든 URL을 따라 크롤링한다.

 그룹 Seed 지정

 초기 Seed URL을 엑셀파일(xls)로 정의하여 입력할수 있다.

 대상지정 크롤링(Tracking)

 초기 Seed URL에 해당하는 URL만을 크롤링한다.

 크롤링 주기 관리

 크롤링 대상이 되는 도메인에 대한 접근 주기를 설정한다.

 도메인별 접근/데이터 수집/통계

 크롤링이 이루어지는 대상 도메인에 대한 접근및 데이터 수집 통계를 생성한다.
 방문할 URL 관리

 Agent부터 전송되어오는 URL을 도메인별로 관리한다.

 URL 핑거프린트 생성 및
 도메인 중복 제거
 URL의 효과적인 관리를위해 64bit Rabin's Hash Code로 변환한다.

 동적 Configuration 지원

 원격접속을 통한 크롤러 설정을 실시간 변경이 가능하다.

 디스크 캐시 및
 디스크/메모리 동기화
 크롤링 데이터를 disk에 저장하며, 효율성을 위해 disk일부를 메모리로 캐쉬한다.
 IP 기반 지역 필터링  IP를 국가코드로 변환하여, 국가별 크롤링을 지원한다.



3.2. Slave(Agent)

3.2.1. 로봇배제표준

로봇배제표준 엔진은 설정파일에 정의되어 있는 고정크기의 캐시맵을 가지고 있으며, LRU알고리즘에 따라 캐시맵을 관리한다. 또한, 설정파일에는 로봇배제표준 기능의 동작 스위치가 정의되어 있다.

<그림4. 로봇배제표준 캐시 맵>

로봇 배제 표준(http://ko.wikipedia.org/wiki/%EB%A1%9C%EB%B4%87_%EB%B0%B0%EC%A0%9C_%ED%91%9C%EC%A4%80)은 웹 사이트에 로봇이 접근하는 것을 방지하기 위한 규약으로, 일반적으로 접근 제한에 대한 설명을 robots.txt에 기술한다. 이 규약은 1994년 6월에 처음 만들어졌고, 아직 이 규약에 대한 RFC는 없다. 이 규약은 권고안이며, 로봇이 robots.txt 파일을 읽고 접근을 중지하는 것을 목적으로 한다. 따라서, 접근 방지 설정을 하였다고 해도, 다른 사람들이 그 파일에 접근할 수 있다.

3.2.2. URL 정규화

물리적으로 동일한 HTML을 문서를 가리키는 URL은 논리적으로 서로 다르게 표현될 수 있다.
예를들어 다음과 같이 서로 다른 URL이지만 물리적으로 동일한 HTML문서를 가리키는 경우가 있을 수 있다.

  • http://www.youdomain.com
  • http://www.youdomain.com:80
  • http://www.youdomain.com/
  • http://www.youdomain.com/index.html

이처럼 하나의 HTML 물리 문서에 논리적으로 서로 다른 형태의 URL이 존재할 수 있기때문에, 정규화를 통해 이들 URL을 하나의 일관된 형태로 표현하는 처리가 필요하다.

3.2.3. Resource 선택 처리

설정파일에는 Agent가 처리할수 있는 Resource Type과 속성(image/*, javascript, css 등등)이 정의되어 있으며, 정의되지 않은 Resource는 수집하지 않는다.

3.2.4. 멀티쓰레드 & Asynchronous I/O

방대한 인터넷에서 주어진 시간동안 최대한 많은 Resource를 수집하기 위해 멀티쓰레드 및 NIO 기법을 최대한 활용한다.

3.2.5. HTML 파싱

HTML 문법은 견고하지 않다. 실제로 빈번하게 HTML문법이 올바르지 않은 HTML 문서를 발견할 수 있는데,  Agent는 이처럼 정확하게 작성되지 않는 HTML문서에 대해서도 Parsing이 가능해야 한다.


Slave(Agent)의 주요 특징을 요약하면 다음과 같다.

 리소스 확장자 구분  리소스의 확장자를 이용하여 리소스 타입을 구분한다.
 리소스 수집 및 리소스 파일명 정규화  정의된 리소스를 수집하며, 수집시간을 기반으로 리소스명을 정규화한다.
 URL 정규화 및 인코딩 적용  추출된 URL을 정규화하고, URL인코딩한다.
 수집 대상 필터링  정의된 리소스가 아니면 수집하지 않는다.
 로봇배제표준 처리  robots.txt를 처리한다.
 링크 추출  HTML문서로부터 새로운 static link를 추출한다.
 파일크기 기반 리소스 필터링  리소스 크기를 이용해 필터링할수 있다.
 HTML 소스 분석  HTML 파서 기능을 제공한다.
 HTTP 헤더 분석  HTTP 헤더 분석을 지원한다.
 비동기 소켓 입출력 및 멀티쓰레딩  시스템의 효율적인 운영을 위해 비동기I/O 및 멀티쓰레딩을 지원한다.






4. 개선된 아키텍처


앞서 설명한 크롤러 아키텍처의 경우 Frontier로 Agent가 수집한 모든 URL이 집중되기 때문에 시간이 지남에 따라 Seen Filter의 앞서 처리된 URL집합 저장소가 과도하게 커지는 경향이 있다. URL집합 저장소가 커지며, 중복 URL을 검사하기 위한 프로세스 타임도 비례해서 증가하게 되며, 이는 전반적으로 크롤링 성능에 악영향을 주게된다. 마찬가지로 앞으로 방문해야 할 URL 집합 역시 시간이 지남에 따라 크기가 커지며 관리에 많은 노력을 기울어야 한다.


또한, Agent가 수집한 대부분의 URL을 전송받고 처리해, 이를 다시 Agent로 처리해야 하므로 Agent와의 네트워크 통신을 유지하는데에도 많은 리소스가 소모된다.


이와 같은 문제를 해결하기 위해 Agent는 모든 URL을 Frontier로 전송하지 않고, 새로발견된 Host URL만을 전송하는 방법을 생각해 볼수 있다.


<그림5. 개선된 크롤러 구성도>


4.1. Master(Frontier)


  • 각 Agent가 방문해야 할 도메인 URL목록을 보관한다.
  • Agent가 새로 수집한 도메인 URL을 전송하면 필터링을 수행한 후 남겨진 URL을 목록에 추가한다.
  • Agent로 도메인 URL을 분배한다.
  • 도메인 URL목록이 모두 소진될 때 까지 위 3단계를 반복한다.



4.2. Slave(Agent)


  • Frontier로부터 전송받은 도메인 URL을 HTTP 프로토콜을 이용해 접근한다.
  • HTTP 응답으로 HTML 문서를 얻어 분석한다.
  • HTML 문서 분석결과로 다음 방문한 URL Link와 수집해야할 Resource URL Link를 추출한다.
  • 새로운 도메인 URL은 Frontier로 전송한다.
  • 새로운 도메인 URL을 제외한 모든 URL은 재귀적으로 Agent로 입력되어 위 처리과정을 따른다.


4.3. Moniotor


2.3.과 동일



이는 결과적으로 Frontier의 작업 일부를 Agent로 옮겨놓은 것인데, Frontier에서는 Agent로 부터 도메인 URL만을 전송 받고 이를 필터링한다. Agent는 Frontier로부터 받은 초기 Seed URL로 부터 시작해 크롤링을 시작하고, 크롤링으로 얻어지는 결과물 URL들은 그것이 Seed URL의 서브 URL인 경우 다시 Agent로 재귀적으로 입력되고, Seed URL에 포함되지 않는 외부 URL이라면 Frontier로 전송하는 방식이다.


Frontier는 이전 방식과 비교해보았을 때, 도메인 URL만을 처리하기 때문에 URL 누적속도가 훨씬 느려지고, Agent와의 네트워크 사용량도 현저히 줄어들게 된다. Agent는 이전과 비교해보았을 때, 추가적으로 서브 URL에 대한 필터링를 수행해야 하므로 추가적인 복잡도를 지니게 된다.


하지만 위 2방식 모두 Frontier로의 중앙집중 방식이기에, Frontier가 다운되며 시스템 전체가 다운되는 치명적인 단점이 있다. 그래서 최근에는 Hadoop과 같은 P2P 클러스터 환경위에서 웹 크롤러를 가동하는 기법들을 찾아볼 수 있다.


http://www.slideshare.net/hadoopusergroup/building-a-scalable-web-crawler-with-hadoop






5. 제약사항


일반적으로 웹크롤러는 다음과 같은 제약사항을 가지고 있다.


5.1. 플래시(*.swf) 및 Javascript 처리 불가


웹크롤러는 기본적으로 HTML문서내의 Anchor 태그를 분석하여 URL을 추출하는데, 현재 많은 웹 페이지들이 플래시 또는 Javascript 기법을 통해 웹 페이지를 Navigate하고 있다. 


플래시 파일에는 이미지, 동영상, 폰트 등 다양한 Resource가 포함될 수 있는데, 이는 크롤러의 HTML 파싱을 통한 URL 추출을 사용할 수 없음을 의미한다. 이 경우 플래시 바이너리 파일을 해독해 URL을 추출해야 하는데, 플래시 바이너리를 해독하는 작업은 주어진 시간내에 최대한 많은 Resource를 수집해야하는 크롤러에는 치명적인 오버헤드를 유발할 수 있다.


마찬가지로 현재 많은 페이지들은 ajax기법을을 통해 HTML 문서의 일부 또는 전체를 비동기적으로 로딩하는데, 이는 크롤러의 일반적인 처리방식을 통해 URL을 추출할 수 없음을 의미하며, 크롤러가 Javascript 코드를 시뮬레이션 해야하는 부담이 있다.




* 참고자료


stanford_IR_ch20.pdf

대용량 검색 엔진을 위한 병렬 웹 크롤러 설계 및 구현.pdf

웹 어플리케이션을 위한 URL 정규화.pdf

Mercator A scalable, extensible Web crawler part1.ppt

Mercator A scalable, extensible Web crawler part2.ppt




'프로젝트 > 웹크롤러' 카테고리의 다른 글

웹크롤러 아키텍처  (2) 2013.04.02
웹크롤러(WebCrawler)  (1) 2009.07.28
Posted by devop

댓글을 달아 주세요

  1. 좋은 글 감사합니다

    2013.04.11 16:18 신고 [ ADDR : EDIT/ DEL : REPLY ]
  2. 잘 읽었습니다~

    2013.07.29 15:58 신고 [ ADDR : EDIT/ DEL : REPLY ]