웹 크롤러 설계

Q&A

• 주요 목적은?
  • 검색 엔진 설계로 지금은 텍스트 저장이 가장 중요
• 규모는? 전체 웹 또는 몇 개 사이트만?
  • 전체 웹(entire web) - 수십억 개 페이지
• 빈도는? 얼마나 자주 크롤링하나?
  • 전체가 매주 업데이트 -> 이전에 크롤링한 페이지의 업데이트 여부 확인 필요
• 저장할 요소는? 모든 페이지의 복사본을 저장하나?
  • 최소한 html을 저장
  • 지금은 이미지 안해도 되지만 나중에 처리할 수 있도록 설계 확장 할 수 있음
  • 동적 콘텐츠는 나중에

사전 질문

• 크롤러를 어떻게 분산해서 필요한 방대한 규모를 처리할까?
• 전체 웹 크롤링에 어떤 알고리즘 사용할까?
• 어떤 문제와 장애 모드를 예상해서 설계에서 어떻게 처리할까?

시스템 설계

진행 과정

1. 크롤링 시작 url 리스트를 큐에 저장
   • url 해시
2. 큐에 저장된 목록 하나씩 페이지 다운로더로 실행
   • 콘텐츠 저장용 분산 스토리지 시스템
   • Key => url, Value => downloaded stuff
   • 콘텐츠 해시
3. 저장한 페이지에서 url 추출, 정규화
   • 에지 케이스 처리 - http vs. https, 상대 경로, trailing slashes 등
4. 추출한 url 필터링
   • 크롤링 제외 목록 - 악성 코드 사이트, 불법 콘텐츠 서비스 등
   • 통과된 url은 다시 1.의 큐에 저장

고려사항

알고리즘 선택

• 웹페이지는 방향 그래프의 정점, 이 사이의 링크는 그래프의 간선
• 근본적으로 그래프 순회 문제
• 한 페이지에 있는 링크 수는 제한적, 너비를 나타냄, but 인터넷의 깊이는 무한함 -> BFS 사용
  • BFS Breadth First Search, 너비 우선 탐색 - 시작 노드에서 왼쪽 -> 오른쪽으로 가로지르며 레벨에 따라 진행
  • DFS Depth First Search, 깊이 우선 탐색 - 시작 노드에서 한 경로의 끝까지 따라가며 모든 노드 방문 후 돌아오는 방식

큐의 대기 행렬 - 연결 리스트 vs. 배열

• url은 문자열이고 특정 수의 url이 메모리를 얼마나 사용할 지 알 수 없음
• 배열은 미리 공간 할당이 필요하므로 부적합
• 문자열에 관한 포인터 배열도 동일한 문제 있음
• 미리 공간 할당할 필요 없는 연결리스트 사용

리스트 저장 방식

• 메모리에만 저장시 해당 서버 장애 나면 거기 있던 것들 날아감
• 단순하고 낮은 비용 절충시 -> 다음 크롤러 실행할 때 가져오면 됨
• 내용을 잃어버리지 않는 것이 중요하다면 -> 분산 영구 리스트 필요
  1. 분산 데이터베이스의 디스크에 백업
  2. 각 서버에 url 해싱에서 버킷을 처리하는 상시 대기 방식(hot standby)
  3. 1, 2번 섞은 하이브리드 형식 사용

복제 콘텐츠 문제

• 다른 url의 같은 페이지 사본이 있는 경우
  • 해시 계산 또는 다운로드 후 콘텐츠 일부 확인
  • 충돌한 해시 값 저장
  • url 추출기에서 다운로더 이동 전 페이지의 해시값을 본 적 있는지 확인
  • 본 적 없으면 큐에 url 추가
• 많은 페이지에 같은 url이 있는 경우
  • 이미 처리한 url은 url 필터로 제출 여부 확인

사이트가 너무 빨리 크롤링 돼 정지되는 것 방지하는 방법

• 사이트의 모든 페이지에 대한 요청을 한번에 처리하면 웹 서버 다운될 수 있음
• 개별 서버 다운로드를 위해 url 해시
• 해당 사이트의 모든 요청을 동일 서버에서 처리하도록 도메인 이름에서 해시 실행(...?)

시스템 확장시

• 이미지 저장 - 페이지 다운로더 -> 이미지 url 인식방법, html과 이미지 검색, 저장
• csr - url 추출 -> 브라우저에서 html 렌더링 후 새 url 생성되는지 확인

추가 정리

서버 다중화

• 시스템의 가용성 높이기 위해 장비를 다중화 시키는 방법
• Active-Active - 다중화된 장비가 모두 가동되는 방식
• Active-Standby - 하나는 가동, 하나는 준비 상태로 대기
  • Hot Standby standby 가동 후 즉시 이용 가능
  • Warm Standby standby 가동 후 설정에 대한 준비가 필요함
  • Cold Standby standby 정지시켜 두고 필요할 때만 직접 켜서 구성

웹 크롤러(추가 공부 필요)

• Web Crawler Architecture
• URL Assignment Algorithm of Crawler in Distributed System Based on Hash
• TinySearch Engine: Crawler Data Structure Design
• Detecting Near-Duplicates for Web Crawling
• [Bitmap]: How to implement URL deduplication in web crawlers?
• Designing a distributed web crawler

checksum

참고

• 이중화란? 고가용성(HA,High Avaliability)을 위한 이중화
• [네트워크] 체크섬(checksum)