[대규모 실시간 데이터 처리 #3] 대규모 시스템 설계 기초. 9장 웹 크롤러 설계

보아즈 멘멘 스터디 중 기록한 내용입니다.

 

 

 

 

목차

웹 크롤러

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

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

3단계 상세 설계

4단계 마무리

 

 

 

 

 

웹 크롤러 web crawler

• 로봇 robot, 스파이더 spider
• 다양하게 이용됨
  • 검색 엔진 인덱싱 search engine indexing: 검색 엔진을 위한 로컬 인덱스. Googlebot
  • 웹 아카이빙 web archiving
  • 웹 마이닝 web mining
  • 웹 모니터링 web monitoring
• 웹 크롤러의 복잡도: 웹 크롤러가 처리해야 하는 데이터의 규모에 따라 달라짐 → 데이터의 규모와 기능 파악 필요

 

 

 

 

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

• 주의 필요 속성
  • 규모 확장성
    • 웹은 거대
    • → 병행성 paralleism 활용
  • 안정성 robustness
    • 비정상적인 입력이나 환경에 잘 대응해야 함
  • 예절 politeness
    • 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청 X
  • 확장성 extensibility
  • 새로운 형태의 콘텐츠 지원 쉬워야 함

개략적 규모 추정

추정치 예시 (면접관과 합의 필요)

• 매달 10억 개의 웹 페이지 다운
  • QPS (Queries Per Second)=10억/30일/24시간/600초= 약 400페이지/초
  • 최대 Peak QPS = 2 × QPS = 800
• 웹 페이지의 크기 평균: 500k
  • 10억 페이지 × 500k = 500TB/월
  • 1개월치 데이터 보관하는데 500TB
  • 5년 보관 → 500TB × 12개월 × 5년 = 30PB

 

 

 

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

시작 URL 집합

• 웹 크롤러가 크롤링을 시작하는 출발점
• 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르기
  • 전체 URL 공간을 작은 부분집합으로 나누는 전략
• 정답 X, 의도 전달 필요

미수집 URL 저장소

• 크롤링 상태 관리
  • 이를 저장 관리하는 컴포넌트를 미수집 URL 저장소 URL frontier 라고 부름
  • FIFO 큐
  • (2) 다운로드된 URL
• (1) 다운로드할 URL

HTML 다운로더

• 인터넷 웹 페이지를 다운로드하는 컴포넌트
• 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공

도메인 이름 변환기

• URL을 IP주소로 변환하는 절차 필요

콘텐츠 파서

• 웹 페이지를 다운로드하면 파싱 parsing과 검증 validation 절차 필요
• 크롤링 서버 안에 콘텐츠 파서 구현 시, 크롤링 과정 느려짐 → 독립적인 컴포넌트

중복 컨텐츠인가?

• 자료 구조 도입 → 데이터 중복 ↓, 데이터 처리 소요시간 ↓
• 효과적인 방법: 웹 페이지의 해시 값 비교

💡 **웹 페이지의 해시 값**

• 해당 페이지의 콘텐츠를 고유하게 식별할 수 있는 고정 길이의 문자열
• 해시 함수: 입력 데이터를 받아 고정 길이의 출력 값을 생성하는 함수
• 동일한 콘텐츠를 가지는 경우, 동일한 해시 함수(예: SHA-256, MD5)를 사용하면 해시 값도 동일

콘텐츠 저장소

• HTML 문서를 보관하는 시스템
• 저장소를 구현하는 데 쓰일 기술 선택 시, 데이터 유형, 크기, 저장소 접근 빈도, 데이터 유효 기간 등을 종합적으로 고려 필요
  • 본 예시, 디스크와 메모리를 동시에 사용하는 저장소 선택
  • 데이터 양 너무 많음 → 대부분의 콘텐츠를 디스크에 저장
  • 인기있는 콘텐츠 → 메모리에 두어 접근 지연시간 ↓

URL 추출기

• HTML 페이지를 파싱하여 링크들을 골라내는 역할
  • 상대 경로 → 절대 경로 변환

URL 필터

• 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL
• 접속 시 오류가 발생하는 URL
• 접근 제외 목록 deny list에 포함된 URL
• 등을 크롤링 대상에서 배제하는 역할

이미 방문한 URL?

• 자료 구조 사용
  • 이미 방문한 URL, 미수집 URL 저장소에 보관된 URL 추적 가능 → 일 여러 번 처리 방지
  • 블룸 필터 bloom filter, 해시 테이블

💡 **블룸 필터**

• 확률형 자료 구조
• 특정 원소가 집합에 속하는지 검사하는데 사용

URL 저장소

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

 

 

 

3단계 상세 설계

DFS(Depth-First Search) vs BFS(Breath-First Search)

• 웹 = 유향 그래프 directed grapth
  • 페이지 = 노드, 하이퍼링크 = 에지 edge
  • 크롤링 프로세스 = 유향 그래프를 에지를 따라 탐색하는 과정
• 웹 크롤러는 보통 BFS 너비 우선 탐색법(breath-first search)을 사용
  • DFS 깊이 우선 탐색법(depth-first search)는 좋은 선택이 아닐 수 있음 (그래프가 클 경우, 어느 정도로 깊이 가게 될지 가늠 어려움)
  • BFS: FIFO 큐를 사용하는 알고리즘
    • 문제점
      • “예의 없는” 크롤러:
        • 한 페이지에서 나오는 링크의 상당수는 같은 서버.
        • 병렬 처리시, 서버는 수많은 요청으로 과부하 발생 가능
      • 우선순위의 부재
        • 표준적 BFS 알고리즘은 URL간 우선 순위 X
        • 모든 웹 페이지가 같은 수준의 중요성 X
        • → 우선 순위 구별 필요

미수집 URL 저장소

• 저장소 구현을 통해, 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도 freshness를 구별하는 크롤러 구현 가능
• 예의
  • 무례한 impolite = 너무 많은 요청을 보내는 것 (종종 Dos Dential-of-Servie 공격으로 간주됨)
  • 동일 웹사이트에 대해서 한 번에 한 페이지만 요청할 것
    • 웹사이트의 호스트명 hostname과 다운로드를 수행하는 작업 스레드 worker thread 사이의 관계 유지
    • 각 다운로드 스레드는 별도의 FIFO 큐를 가짐, 이 큐에서 꺼낸 URL만 다운로드
      • 큐 라우더 queue router: 같은 호스트에 속한 URL은 언제가 같은 큐로 가도록 보장
      • 매핑 테이플 mapping table: 호스트 이름과 큐 사이의 관계를 보관하는 테이블
      • FIFO 큐: 같은 호스트에 속한 URL은 언제나 같은 큐에 보관됨
      • 큐 선택기 queue selector: 큐들을 순회하면서, 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달
      • 작업 스레드 worker thread: 전달된 URL을 다운로드하는 작업 수행
• 우선순위
  • 유용성에 따라 URL의 우선순위를 나눌 때, 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도 사용 가능
  • URL 우선순위 고려 설계
    • 순위결정장치 prioritizer: URL을 입력으로 받아 우선순위 계산
    • 큐: 우선순위별로 큐가 하나씩 할당. 우선순위 ↑, 선택될 확률 ↑
    • 큐 선택기: 큐에서 처리한 URL을 꺼내는 역할. 순위가 높은 큐에서 더 자주 꺼내도록 설정됨
• 전체 설계
  • 전면 큐 front queue: 우선순위 결정 과정 처리
  • 후면 큐 back queue: 예의바르게 동작하도록

• 신선도
  • 데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집 recrawl 필요
    • 모든 URL 재수집 → 시간, 자원 필요 ↑ → 최적화 전략
    • 웹 페이지의 변경 이력 update history 활용
    • 우선순위를 활용하여, 중요 페이지 더 자주 재수집
• 미수집 URL 저장소를 위한 지속성 저장장치
  • 검색 엔진을 위한 크롤러 → 수억개에 달하는 URL을 처리
  • 메모리: 안정성, 규모 확장성이 떨어짐
  • 디스크: 느려서 쉽게 성능 병목지점이 됨
  • 절충안 : 대부분의 URL은 디스크에 두지만 IO비용 절감을 위해, 메모리 버퍼에 큐를 둠
    • 버퍼에 있는 데이터는 주기적으로 디스크에 기록

HTML 다운로더

• HTTP 프로토콜을 통해 웹 페이지를 내려 받음
• Robots.txt
  • 로봇 제외 프로토콜
  • 웹사이트가 크롤러와 소통하는 표준적 방법
  • 크롤링 전, 해당 파일에 나열된 규칙 먼저 확인 필요
• 성능 최적화
  1. 분산 크롤링
     • 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
     • 각 서버는 여러 스레드를 돌려 다운로드 작업 처리
     • URL 공간을 작은 단위로 분할, 각 서버는 그 중 일부의 다운로드를 담당
  2. 도메인 이름 변환 결과 캐시
     • 도메인 이름 변환기 DNS Resolver는 크롤러 성능의 병목 중 하나
     • DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 → 결과 받기 전까지 다음 작업 진행 불가
     • → DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관
     • → 크론 잡 cron job 등을 돌려 주기적으로 갱신하면 성능 향상
  3. 지역성
     • 크롤링 작업 수행 서버를 지역별로 분산하는 방법
       • 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간이 줄어듦
       • 지역성 locality 를 활용하는 전략은 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능
  4. 짧은 타임 아웃
     • 어떤 웹 서버는 응답이 느리거나, 응답 x
       • → 대기 시간 wait time 이 길어지면 좋지 않음
       • → 최대한 얼마나 기다릴지 미리 세팅
       • → 이 시간 동안 서버 응답 X → 해당 페이지 다운 중단 후 다음 페이지 이동

안정성

• 시스템 안정성 향상시키기 위한 접근법
  • 안정 해시 consistent hashing: 다운로더 서버들의 부하를 분산할 때 적용 가능 기술. 다운로더 서버를 쉽게 추가 및 삭제 가능
  • 크롤링 상태 및 수집 데이터 저장: 장애 발생 시 쉽게 복구할 수 있도록, 크롤링 상태 및 수집된 데이터를 지속적 저장장치에 기록
  • 예외 처리 exception handling: 예외 발생 시, 전체 시스템이 중단되는 일 없이 이어나갈 수 있도록
  • 데이터 검증 data validation: 시스템 오류 방지하기 위한 중요 수단 중 하나

확장성

• 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록
  • ex. 확장 모듈: PNG 다운로더, URL 추출기, 웹 모니터 등

문제 있는 콘텐츠 감지 및 회피

• 중복 콘텐츠
  • 웹 콘텐츠 30% 정도는 중복
  • 해시나 체크섬 check-sum 사용 시 중복 콘텐츠를 보다 쉽게 탐지 가능
• 거미 덫 spider trap
  • 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지
  • 모든 종류의 덫을 피할 수 있는 만능 해결책 X
  • → 수작업으로 덫을 확인하고 찾아낸 후 처리
• 데이터 노이즈
  • 어떤 콘텐츠는 거의 가치가 없음
    • ex. 광고, 스크립트 코드, 스팸 URL 등
  • → 제외

 

 

 

4단계 마무리

• 좋은 크롤러의 특성
  • 규모 확장성 scalability, 예의 확장성 extensibility, 안정성 등
• 추가 논의 사항
  • 서버 측 렌더링 server-side rendering
    • 많은 웹사이트가 자바스크립트, AJAX 등의 기술 사용해 링크 즉석 생성
    • → 동적으로 생성되는 링크 발견 불가
    • → 페이지 파싱 전에 서버 측 렌더링(=동적 렌더링)을 적용하면 해결 가능
  • 원치 않는 페이지 필터링
    • 저장공간, 소요 자원 유한
    • → 스팸 방지 컴포넌트를 두어 저품질, 스팸성 페이지 제외
  • 데이터베이스 다중화 및 샤딩
    • 다중화 replication, 샤딩 sharding 기법 적용, 데이터 계층의 가용성, 규모 확장성, 안전성 향상
  • 수평적 규모 확장
    • 크롤링 서버 많이 필요할 수 있는데,
    • 수평적 규모 확장성 달성 시 중요 포인트: 상태 정보를 유지하지 않도록 하는것(=무상태 서버 만드릭)
  • 가용성, 일관성, 안전성
  • 데이터 분석 솔루션