웹 크롤러 설계

크롤러의 용도 (robot / spider)

1. 검색엔진 인덱싱 (google bot)
2. 웹 아카이빙 (미국 국회도서관, EU 웹 아카이브)
3. 웹 마이닝
   • 유명 금융 기업들은 크롤러를 사용해 주주총회나 연차보고서를 받아 기업의 핵심 사업방향을 알아내기도
4. 웹 모니터링
   • 저작권,상표권침해 모니터링 (Digimarc)

     설계

5. 문제 이해 및 설계 범위 확정.
   • 요구사항
   • URL 을 입력으로 받으면, 모든 웹페이지 다운 > 페이지 내 URL추출 > 반복
   • 목적 : 검색 인덱싱
   • 매달 1억개 웹페이지 수집. = QPS 400page/s
   • 한 페이지당 500kb 라 가정하면, 500TB/Month - 새로 만들어지거나 수정된 웹페이지 고려. - 수집한 페이지 저장 기간은 5년 = 30PB - 중복 컨텐츠 무시. - 고려 사항 - 규모 확장성 : 페이지 양이 많으므로 병행처리를 고려하면 효과적일것. - 안정성 : 비정상적 입력, 오류페이지, 악성코드링크 등에 대응해야한다. - 예절 : 수집대상 서버에 과부하를 주면 안된다. - 확장성 : 새로운 형태의 콘텐츠 지원이 용이해야함.

6. 개략적 설계안 제시 및 동의 구하기.

   1) 시작 URL집합

   크롤링의 출발점, ex) 특정 도메인의 하위 페이지 전체

   • 크롤러가 가능한 많은 링크를 탐색할수있도록 하는 URL을 고르는것이 바람직.
   • 일반적으로 전체 URL 공간을 작은 부분집합으로 나누는 전략을 사용.
   • 주제별로 다른 시작 URL을 사용 하는 전략. 2) 미수집 URL 저장소 (url frontier)

   • 다운로드할 URL을 모아둔 fifo queue

     3) HTML 다운로더

     4) DNS

     5) Contents parser

     파싱과 검증절차, 크롤링 서버안에 있으면 크롤링 과정이 느려질 수있으므로 독립된 컴포넌트로 분리. 6) 중복 컨텐츠 인가

     텍스트 비교는 비효율적, 효과적인 방법은 웹페이지의 해시값을 비교하는것.

     알아보자 7) 콘텐츠 저장소

     데이터 유형, 크기, 접근빈도, 유효기간 등을 고려하여 디스크 + 메모리캐시 사용 8) URL 추출기

     HTML내 링크 추출, 상대경로를 절대경로로 변환한다. 9) URL 필터

     특정 컨텐츠타입, 오류발생 URL, 접근 제외목록 등을 크롤링 대상에서 배제. 이미 방문한 URL 여부는 블룸필터, 해시테이블을 주로 사용. 10) URL 저장소

     다운로드한 URL을 모아두는 저장소.

7. 상세 설계
   • DFS(Depth-First-Search) vs BFS (Breath First Search)
   • 웹은 directed graph와 같다. 페이지(노드) > 링크(엣지) > 페이지(노드) > ..
   • 깊이우선 탐색법(DFS)는 깊이를 모르기때문에, 보통 좋지않음.
   • 너비우선 탐색법(BFS) 보통 사용. FIFO를 사용하여 구현.
     • 보통 동일 도메인으로 요청하기때문에, 대상 서버에 impolite 크롤러로 간주된다.
     • 우선순위가 없는것이 일반적이나, 페이지 순위, 트래픽양, 업데이트 빈도 등 척도로 우선순위를 구별하면 좋음. - 미수집 URL 저장소
   • politeness 크롤러, URL사이의 우선순위와 freshness를 구별하는 크롤러 구현가능.
   • polite 크롤러 (back queue)
     • 동일 웹사이트에 대해 한번에 한페이지만 요청.
     • 같은 호스트에 속한 URL은 언제나 같은큐로 (큐-도메인 매핑테이블 필요)
     • 큐 선택기는 큐를 순회하며 작업스레드에 URL을 할당.
     • 작업 스레드는 페이지를 다운로드하며, delay를 둘 수 있다.

       특정 페이지가 커서 다운이 느려지면 동일 도메인으로 한번에 여러요청이 가능하지않나? 도메인 1개만 큐에 있고, 작업스레드가 여러개인 경우도?

   • 우선순위 (front queue)
     • 트래픽양, 갱신 빈도 등으로 순위결정장치가 URL의 우선순위를 정한다.
     • 우선순위별로 큐가 할당되어있고, 큐 선택기가 우선순위가 높은 큐를 더 많이 조회한다.
   • 신선도
     • 웹페이지의 변경이력 활용/ 우선순위가 높은 페이지는 자주 재수집하여 freshness 유지.
   • 미수집 URL저장소
     • 대부분의 URL은 디스크에 두지만, IO비용을 줄이기 위해 메모리 버퍼에 큐를 두어 속도/안정성 보장. - HTML 다운로더
   • robots.txt
     • 크롤링이 가능한 페이지 목록
     • 캐싱하는것이 좋겠다.
   • 성능 최적화
     • 분산 크롤링
     • DNS결과 캐시
     • 지역성 : 크롤링서버와 대상서버가 지역적으로 가깝게.
     • 짧은 타임아웃 - 안정성 확보 전략
   • 다운로더 서버 분산시 안정해시 설계 적용. (5장 참고)
   • 크롤링 상태 및 수집데이터 저장 : 디스크에 저장해서 쉽게 재시작할수있도록.
   • 예외처리 : 잘
   • 데이터 검증 : > 하긴하는데 어떻게? - 확장성 확보 전략
   • 컨텐츠 타입별로 모듈처럼 추가할수있어야한다. - 문제있는 컨텐츠 감지 및 회피 전략
   • 중복 : 해시, check-sum 사용(11)
   • spider map : 무한 루프에 빠뜨리도록 설계한 웹페이지. URL최대길이 제한,사전에 발견된 사이트 필터링.
   • 데이터 노이즈 : 광고, 스팸 URL등 필터링.
8. 마무리
   • 서버 랜더링 : 페이지 파싱하기전에 서버랜더링을 적용하여 js,ajax로 생성되는 링크를 발견가능.
   • 원치않는 페이지 필터링 : 스팸방지 컴포넌트 추가
   • DB 다중화, 샤딩
   • 수평적 규모 확장성 : stateless 서버
   • 가용성, 일관성,안정성
   • 데이터 분석 솔루션

space/time trade-offs in hash coding with allowable errors rabin fingerprint [checksum] Web crawler design example

• 컨텐츠 중복 검출관련 알고리즘

  Some potential algorithms are Jaccard index and cosine similarity.