대규모 시스템 설계 기초 - 9장

9장. 웹 크롤러 설계

• 웹 크롤러는 검색 엔진이 웹 상의 새로운 콘텐츠나 수정된 콘텐츠(웹페이지, 이미지, 동영상, PDF 파일 등)를 발견하는 데에 주로 사용
• 웹 크롤러는 일부 웹 페이지를 수집하는 것부터 시작해서, 그 안의 링크를 따라가며 더 많은 콘텐츠를 수집

 

 

1단계: 문제 이해 및 설계 범위 확장

웹 크롤러의 기본 알고리즘:

1. URL 목록을 입력받아, 해당 웹 페이지를 다운로드
2. 웹 페이지 내의 새로운 URL을 추출
3. 추출한 URL을 다운로드 목록에 추가하고 위 과정을 반복

면접관과 대화를 통해 도출한 요구사항:

 

• 크롤러의 주요 목적: 검색 엔진 색인 생성
• 매월 10억 개의 웹 페이지 수집
• HTML 콘텐츠만 수집
• 새로 추가되거나 수정된 웹 페이지도 고려해야 함
• 수집한 HTML 페이지는 최대 5년간 저장
• 중복 콘텐츠는 무시

좋은 크롤러의 특성:

• 규모 확장성(Scalability): 웹은 매우 방대하기 때문에, 병렬 처리를 통한 효율적인 크롤링이 필수
• 안정성(Robustness): 잘못된 HTML, 응답 없는 서버, 시스템 장애, 악성 링크 등의 상황들을 잘 처리할 수 있어야 함
• 예절(Politeness): 같은 사이트에 너무 자주 요청을 보내서 서버에 부담을 주지 않도록 주의
• 확장성(Extensibility): 향후 이미지, 동영상 등 다양한 유형의 콘텐츠를 수집할 수 있도록 설계가 유연해야 함

 

개략적 규모 추정

• 한 달에 웹 페이지 10억 개를 다운로드 한다고 가정
• QPS(초당 요청 수)를 계산하면, 10억 / 30일 / 24시간 / 3600초 = 약 400 페이지/초
• 피크 시간대의 QPS는 2배인 800 QPS라고 가정
• 웹 페이지 하나 당 평균 크기를 500KB라고 가정
• 한 달에 필요한 용량: 10억 페이지 × 500KB = 500TB
• 저장 기간이 5년이므로, 총 500TB × 12개월 × 5년 = 30PB(페타바이트) 필요

 

 

2단계: 개략적 설계안 제시 및 동의 구하기

 

시작 URL 집합 (seed URLs)

• 크롤러는 수집을 시작할 초기 URL 목록이 필요
• 예를 들어, 특정 대학교 웹사이트를 크롤링하려면, 그 대학교의 메인 도메인을 시작 URL로 사용
• 전 세계 웹을 크롤링할 경우에는 다양한 도메인에서 시작해야 하며, 지역(locality)이나 주제(topic)별로 분류

미수집 URL 저장소 (URL Frontier)

• 미수집 URL 저장소는 앞으로 다운로드할 URL을 담고 있는 대기열
• 일반적으로 FIFO 큐 구조를 사용
• 다운로드할 URL과 이미 다운로드한 URL을 구분하여 저장

HTML 다운로더 (HTML Downloader)

• URL Frontier에서 받은 URL을 사용해 실제로 웹 페이지를 다운로드
• HTTP 요청을 보내 HTML 데이터를 받아옴

도메인 이름 변환기 (DNS Resolver)

• URL을 IP 주소로 변환
• HTML Downloader가 실제 서버에 접근할 수 있게 함

콘텐츠 파서 (Content Parser)

• 웹 페이지를 다운로드한 후, HTML을 파싱해서 콘텐츠가 정상인지 확인
• HTML 구조가 잘못된 경우 저장 공간을 낭비하거나 크롤링 오류를 일으킬 수 있음
• 이 작업은 시간이 오래 걸리므로 별도의 컴포넌트로 분리해 처리

콘텐츠 중복?

• 연구에 따르면 웹 페이지의 약 29%가 중복된 콘텐츠
• 같은 내용을 가진 여러 URL이 존재할 수 있으므로, 이미 저장된 페이지인지 먼저 확인해야 함
• HTML 전체를 문자 단위로 비교하면 너무 느리므로, 보통 해시값을 사용해 비교

콘텐츠 저장소 (Content Storage)

• HTML 콘텐츠를 저장하는 시스템
• 대부분의 데이터는 너무 크기 때문에 디스크에 저장
• 자주 사용되는 콘텐츠는 메모리에 캐시해서 빠르게 접근

URL 추출기 (URL Extractor)

• HTML 문서에서 링크를 찾아 추출
• 상대 경로(relative path)는 절대 경로(absolute URL)로 변환

URL 필터 (URL Filter)

• 크롤링하지 않아도 되는 URL을 걸러냄 (파일 확장자, 접속시 에러가 발생하는 URL, 스팸 URL, 접근 제외 목록의 URL 등)

이미 방문한 URL?

• 어떤 URL이 이미 다운로드되었거나 미수집 URL 저장소에 존재하는지 확인
• 중복 URL을 피하지 않으면 서버 부하가 생기고, 심한 경우 무한 루프에 빠질 수도 있음
• 주로 해시 테이블이나 블룸 필터(Bloom Filter)를 이용해 구현

URL 저장소

• 이미 방문한 URL을 보관하는 저장소

 

웹 크롤러 작업 흐름

 

1. 시작 URL을 미수집 URL 저장소에 저장
2. HTML 다운로더가 미수집 URL 저장소에서 URL 목록을 가져옴
3. HTML 다운로더가 도메인 이름 변환기를 호출하여 각 URL의 IP 주소를 얻은 뒤, 다운로드를 시작
4. 콘텐츠 파서가 HTML 페이지를 파싱하고, 문서가 잘못된 구조인지 검사
5. 콘텐츠가 파싱되고 검증되면, 콘텐츠 중복 확인 단계로 전달
6. 중복 확인을 위해, 해당 HTML 페이지가 이미 저장되어 있는지를 확인
   • 이미 저장되어 있다면, 동일한 콘텐츠가 다른 URL로 이미 처리된 것임을 의미하므로, HTML 페이지 폐기
   • 저장되어 있지 않다면, 시스템은 이전에 이 콘텐츠를 처리한 적이 없으므로, URL 추출기로 전달
7. URL 추출기가 HTML 페이지에서 링크들을 추출
8. 추출된 링크들은 URL 필터로 전달되어 불필요한 항목을 제거
9. 필터링된 링크들은 중복 URL 판별 단계로 전달
10. 중복 URL 판별을 위해, 해당 URL이 이미 URL 저장소에 저장되었는지 확인
    이미 처리된 경우에는 아무 작업도 수행하지 않음
11. 이전에 처리된 적이 없는 URL은 URL 저장소 및 미수집 URL 저장소에 추가되어, 다시 크롤링 대상이 됨

 

 

3단계: 상세 설계

DFS vs BFS

• 웹은 웹 페이지가 노드, 하이퍼링크(URL)가 엣지인 방향 그래프
• 크롤링 과정은 한 웹 페이지에서 다른 페이지로 이동하는 그래프 순회
• DFS는 너무 깊이 들어갈 수 있기 때문에, 일반적으로 웹 크롤러에서 BFS를 사용
• BFS가 사용하는 FIFO 큐의 두 가지 문제점
  • 대부분의 링크가 같은 웹 페이지 내 링크, 즉 같은 서버로 연결됨
    • 예시:
      wikipedia.com의 모든 링크가 내부 링크이므로 크롤러는 계속해서 같은 호스트(wikipedia.com)의 URL을 처리하게 됨
      병렬로 페이지 다운로드를 시도하면 Wikipedia 서버에 과도한 요청이 집중되어 '예의 없는' 크롤러로 간주됨

•  
  • 표준 BFS는 URL의 우선순위를 고려하지 않음
    실제 웹은 모든 페이지가 같은 품질이나 중요도를 갖고 있지 않음
    따라서 페이지 순위(page rank), 웹 트래픽, 업데이트 빈도 등을 기반으로 URL의 우선순위를 설정하는 것이 필요함

미수집 URL 저장소

• 미수집 URL 저장소는 이러한 문제를 해결하기 위한 핵심 데이터 구조
• 미수집 URL 저장소는 다운로드할 URL을 저장하며, 예의(Politeness), 우선순위(Priority), 신선도(Freshness)를 유지
• 예의:
  • 같은 호스트에 짧은 시간 내 여러 요청 금지
  • 설계 구성 요소:
    1. 큐 라우터: 동일 호스트 URL을 같은 큐로 분배
    2. 매핑 테이블: 각 호스트를 하나의 큐에 매핑
    3. FIFO 큐(b1, b2, …): 동일 호스트의 URL만 포함
    4. 큐 선택기: 각 작업 쓰레드는 하나의 큐만 접근
    5. 작업 스레드: 큐에서 URL을 하나씩 처리하며 딜레이를 두고 다운로드

• 우선순위:
  • 페이지 랭크(PageRank), 웹 트래픽, 콘텐츠 변경 빈도 등의 척도로 우선순위 판단
  • 설계 구성 요소:
    • 순위결정장치: URL의 중요도를 계산
    • 우선순위 큐: 우선순위별로 분리된 큐
    • 큐 선택기: 무작위로 큐를 선택하되 높은 우선순위 큐는 더 자주 선택

•  
  •  전체 설계:
    •  전면 큐: 우선순위 관리
    • 후면 큐: 예의 바르게 동작하도록 관리

 

• 신선도:
  • 웹 페이지는 지속적으로 추가, 삭제, 수정됨
  • 웹 크롤러는 데이터를 최신 상태로 유지하기 위해 정기적으로 재수집(recrawl) 해야 함
  • 모든 URL을 재방문하는 것은 리소스를 많이 소모
  • 최적화를 위한 전략:
    • 업데이트 기록 기반 재방문 주기 설정
    • 중요 URL을 우선순위로 더 자주 재방문
• 미수집 URL 저장소를 위한 지속성 저장장치
  • 실제 검색 엔진 크롤링에서는 URL Frontier에 수억 개 URL이 존재 가능
  • 모든 URL을 메모리에 저장하면 지속성이 없고 확장성도 떨어짐
  • 모든 URL을 디스크에 저장하면 느려지고 병목 발생 가능
  • 하이브리드 방식 사용:
    • 대부분 URL은 디스크에 저장 (공간 문제 해결)
    • 메모리 버퍼를 만들어 디스크 읽기/쓰기 부담 최소화
    • 버퍼 내용은 주기적으로 디스크에 기록됨

HTML 다운로더

• robots.txt (로봇 제외 프로토콜):
  • 웹사이트는 크롤러에게 robots.txt 파일을 통해 크롤링 허용 페이지 목록 전달
  • 크롤러는 크롤링 전 robots.txt를 먼저 확인해야 하며, 그 지침을 따라야 함
  • robots.txt를 매번 다운로드하는 것은 비효율적이므로, 캐시 처리 필요
• 성능 최적화
  1. 분산 크롤링
     • 여러 서버에 작업 분산
     • 각 서버는 여러 스레드를 운영하며 일부 URL을 담당
  2. DNS 캐시
     • DNS 요청은 시간 소요 많음 (10~200ms)
     • 도메인-IP 매핑 정보를 캐시에 저장하고 주기적으로 갱신
  3. 지역 분산(Locality)
     • 크롤링 서버를 웹사이트와 가까운 곳에 배치하여 다운로드 속도 향상
     • 캐시, 큐, 저장소도 지역 분산 가능
  4. 짧은 타임아웃 설정
     • 느리거나 응답 없는 서버는 일정 시간 대기 후 건너뜀
• 안정성
  • 안정 해시: 서버 간 부하 분산 및 유연한 노드 추가/제거
  • 크롤 상태 및 수집 데이터 저장: 장애 시 중단된 위치에서 재시작 가능
  • 예외 처리: 장애가 발생해도 시스템이 전체 중단되지 않도록 함
  • 데이터 검증: 잘못된 데이터로 인해 오류 발생 방지
• 확장성
  • 시스템은 새로운 콘텐츠 유형(예: 이미지, 비디오 등)도 처리할 수 있도록 유연해야 함
  • 새로운 모듈을 플러그인 방식으로 쉽게 추가할 수 있도록 설계
  • 예시: 새로운 모듈을 추가하여 새로운 형태의 컨텐츠를 지원
    
    • PNG Downloader: PNG 파일 수집
    • Web Monitor: 저작권 침해 감시용 크롤링

 

• 문제 있는 콘텐츠 감지 및 회피
  1. 중복 콘텐츠
     • 전체 웹 페이지의 약 30%가 중복
     • 해시값 비교로 중복 여부 판단
  2. 거미 덫
     • 무한 루프를 유발 페이지
     • URL 길이 제한 등으로 탐지 가능
     • 덫이 확인되면 해당 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 추가
  3. 노이즈 데이터
     • 광고, 스팸 URL, 코드 조각 등은 가치가 없으므로 필터링 필요

 

 

4단계: 마무리

추가로 논의해볼만한 사항들:

• 서버 측 렌더링
  • 많은 웹사이트들이 JavaScript, AJAX 같은 스크립트를 사용해 실시간으로 링크를 생성
  • 웹 페이지를 직접 다운로드하고 파싱하는 방식으로는 동적으로 생성된 링크를 가져올 수 없음
  • 이 문제를 해결하려면 파싱 전에 서버 측 렌더링(또는 동적 렌더링)을 수행해야 함
• 원치 않는 페이지 필터링
  • 저장 공간 등의 크롤링 자원은 유한하므로, 스팸 페이지나 품질이 낮은 페이지는 필터링이 필요
  • 이를 위해 스팸 방지 컴포넌트를 사용하는 것이 효과적
• 데이터베이스 다중화 및 샤딩
  • 데이터 계층의 가용성, 확장성, 신뢰성을 향상시키기 위해
    데이터를 여러 서버에 복사하는 다중화, 데이터를 분할하여 여러 서버에 분산 저장하는 샤딩 사용
• 수평적 규모 확장
  • 대규모 웹 크롤링에서는 수백 개 또는 수천 개의 서버가 필요할 수 있음
  • 상태 정보는 외부 저장소나 데이터베이스에서 관리하도록 설계해, 무상태 서버로 만들어야 함
• 가용성, 일관성, 안정성
  • 가용성: 시스템이 계속해서 응답할 수 있어야 함
  • 일관성: 사용자에게 항상 정확한 데이터를 제공해야 함
  • 안정성: 장애 발생 시에도 데이터 손실 없이 작동해야 함
• 데이터 분석 솔루션
  • 데이터를 수집하고 분석하는 것은 모든 시스템의 핵심 기능
  • 수집된 데이터는 튜닝 및 최적화를 위해 사용됨