가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 9장 ) 웹 크롤러 설계

웹 크롤러 설계 

• 웹 크롤러 
  • 로봇 또는 스파이더라고 불림 
  • 검색 엔진에서 널리 쓰이는 기술
  • 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아냄
  • 사용처 
    • 검색 엔진 인덱싱 
      • 크롤러의 가장 보편적인 옹례 
      • 웹페이지를 모아 검색 엔진을 위한 로컬 인덱스를 생성 
      • ex) Googlebot = 구글 검색 엔진이 사용하는 웹 크롤러 
    • 웹 아카이빙 
      • 나중에 사용할 목적으로 장기보관을 위해 웹에서 정보를 모으는 절차 
    • 웹 마이닝 
      • 인터넷에서 유용한 지식을 도출 
        • = 데이터 마이닝 
      • ex) 금융 기업의 주주총회 자료나 연차보고서를 이용한 기업의 핵심 사업 방향 파악 
    • 웹 모니터링 
      • 저작권이나 상표권이 침해되는 사례 모니터링 등 
  • 복잡도 
    • 웹 크롤러가 처리해야 하는 데이터의 규모에 따라 달라짐 
    • 감당해야 하는 데이터의 규모와 기능을 알아야 함 

 

 

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

• 웹 크롤러의 기본 알고리즘 
  • URL 집합이 입력으로 주어지면, 해당 URL이 가리키는 모든 웹페이지 다운로드 
  • 다운받은 웹 페이지에서 URL 추출 
  • 추출된 URL들을 다운로드 할 URL 목록에 추가하고 위의 과정을 처음부터 반복 
• 요구사항 
  
  • 주된용도 
  • 수집해야 하는 웹페이지의 양 
  • 새로 만들어지는 웹 페이지나 수정된 웹페이지 고려 여부 
  • 수집한 웹페지이의 저장 여부 및 저장 기간
  • 중복된 컨텐츠의 처리 방안 
• 주의해야 하는 속성
  • 규모 확장성 
    • 병렬적 특성을 활용하면 효과적으로 웹 크롤링 가능 
  • 안정성
    • 비정상적 입력이나 환경에 대응할 수 있어야 함 
  • 예절
    • 수집 대상 웹 사이트에 짧은 시간동안 너무 많은 요청을 보내지 않도록 주의 
  • 확장성 
    • 새로운 형태의 콘텐츠를 지원하기 쉬워야 함 
• 개략적 규모 추정 
  • 매달 10억개의 웹페이지 다운 가정
    • QPS = 10억 / 30일 / 24시간 / 3600초 = 대략 400 페이지 / 초 
    • 최대 (Peak) QPS = 2 x QPS = 800
  • 웹 페이지의 크기 평균 = 500k 가정
    • 10억 페이지 x 500k = 500TB/월 
    • 5년간 보관 저장 용량 = 500TB x 12개월 x 5년 = 30PB 

 

 

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

• 구성요소 
  • 시작 URL 집합 
    • 크롤링을 시작하는 출발점 
    • 전체 웹을 크롤링 해야 하는 경우 시작 URL을 고를때 창의적인 방안이 필요 
      • 크롤러가 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직 
      • 일반적으로는 전체 URL 공간을 작은 부분 집합으로 나누는 전략을 사용 
        • ex) 지역적 특색, 나라별 인기 웹사이트가 다름 
        • ex) 주제별 다른 시작 URL을 사용 
  • 웹 크롤링 크롤링 상태 
    • 다운로드 할 URL
      • 미수집 URL 저장소 
      • FIFO(First-In-First-Out) 큐
    • 다운로드 된 URL
  • HTML 다운로더 
    • 웹 페이지를 다운로드 하는 컴포넌트 
  • 도메인 이름 변환기 
    • 웹페이지를 다운받기 위해 URL을 IP 주소로 변환하는 절차 수행 
  • 콘텐츠 파서 
    • 파싱과 검증 절차를 통해 이상항 웹페이지 문제를 방지하고 저장공간을 활용 
    • 크롤링 서버안의 컨텐츠 파서를 구현하면 크롤링 과정이 느려질 수 있으므로 독립 컴포넌트로 구성 
  • 중복 콘텐츠 여부 
    • 중복 콘텐츠를 해결 자료구조
      • 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄임 
      • 웹페이지의 해시값을 비교하는 방법 존재 
  • 콘텐츠 저장소 
    • HTML 문서를 보관하는 시스템 
    • 디스크와 메모리를 동시에 사용하는 저장소를 고려해볼 수 있음 
      • 디스크 
        • 데이터 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장 
      • 메모리 
        • 인기있는 콘텐츠는 메모리에 두어 접근 지연 시간을 줄임 
  • URL 추출기 
    • HTML 페이지를 파싱하여 링크들을 골라내는 역할 
      • 상대경로를 절대 경로로 변환 
        • ex) 상대경로 : /api/v1/members -> 절대경로 : https://test.com/api/v1/members
  • URL 필터 
    • 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL등을 크롤링 대상에서 배제하는 역할 
  • 이미 방문한 URL 처리
    • 이미 방문한 URL과 미수집 URL 저장소에 보관된 URL을 추적하기 위한 자료구조 
      • 이미 방문한 URL인지 추적하면 같은 URL을 여러번 처리하는 일을 방지 
        • 서버 부하 감소, 시스템이 무한 루프에 빠지는 일을 방지 
    • 블룸필터나 해시테이블 
  • URL 저장소 
    • 이미 방문한 URL을 보관하는 저장소 
• 웹 크롤러의 작업 흐름
  • 시작 URL 수집 -> 미수집 URL 저장소 -> HTML 다운로더(도메인 이름 변환기) -> 콘텐츠 파서 -> 중복콘텐츠 (컨텐츠 저장소) 파악 ->  URL 추출기 -> URL 필터 -> URL 저장소를 조회하여 이미 저장소에 저장된 것은 버리고, 저장되지 않았다면 URL저장소와 미수집 저장소에 저장
    1. 시작 URL 들을 미수집 URL 저장소에 저장 
    2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져옴 
    3. HTML 다운로더는 도메인 이름 변환기를 사용하여 URL의 IP 주소를 찾고, 해당 IP 주소로 접속하여 웹페이지 다운 
    4. 콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지 여부 검증 
    5. 이후 중복 콘텐츠 여부를 확인하는 절차 개시 
    6. 중복 콘텐츠인지 확인하기 위해서 해당 페이지가 이미 저장소에 있는지 확인 
       1. 이미 저장소에 있는 콘텐츠인 경우 처리하지 않고 버림 
       2. 저장소에 없는 콘텐츠인 경우 저장소에 저장한 뒤 URL 추출기로 전달 
    7. URL 추출기는 해당 HTML 페이지에서 링크를 골라냄 
    8. 골라낸 링크를 URL 필터로 전달 
    9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달 
    10. 이미 처리한 URL 여부 확인을 위해 URL 저장소에 보관된 URL인지 조회 
        • 이미 저장소에 있는 URL은 버림 
        • 저장소에 없는 URL은 URL 저장소에 저장하고 미수집 URL 저장소에도 전달 

 

 

 

3단계 상세 설계 

• DFS(Depth-First Search) VS BFS(Breath-First Search) 
  • 페이지 = 노드 , 하이퍼링크(URL) = 엣지(edge) 
  • DFS의 경우 그래프 크기가 클 경우 어느정도로 깊숙이 가게 될지 가늠하기 어려우므로 좋은 선택지가 아닐 가능성이 높음 
  • 웹 크롤러는 보통 BFS 너비 우선 탐색범을 사용 
    • FIFO 큐를 사용 
    • 주의 사항 
      • 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아 감 
      • 링크들을 병렬로 처리하게 되면 서버는 수많은 요청으로 과부하게 걸리게 됨 
        • = 예의 없는 크롤러로 간주됨 
      • 표준적 BFS 알고리즘은 URL간에 우선순위를 두지 않음 
        • 모든 웹페이지가 동등한 품질이나 중요성을 갖지 않으므로 페이지 순위, 사용자 트래픽의 양, 업데이트 빈도 등 여러가지 척도에 비추어 처리 우선 순위를 구현해야 함 
        • 미수집 URL 저장소를 활용하면 이런 문제를 쉽게 해결 가능
• 미수집 URL 저장소 
  • 다운로드 할 URL을 보관 
  • 잘 구현하면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러 구현 가능 
    • 예의 
      • 웹 크롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 함 
      • 너무 많은 요청을 보내는 것은 impolite한 것으로 간주되며 떄로는 DoS(Denial-of-Service)공격으로 간주되기도 함 
      • 동일한 웹 사이트에 대해서는 한번에 한 페이지만 요청해야 함 
      • 웹 사이트의 호스트명과 다운로드를 수행하는 작업 스레드(worker thread) 사이의 관계를 유지 
        • 각 다운로드 스레드는 별도 FIFO를 가지고 해당 큐에서 꺼낸 URL만 다운로드 
        • 큐라우터 (queue router) 
          • 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장 
        • 매핑 테이블 (mapping table)
          • 호스트 이름과 큐 사이의 관계를 보관하는 테이블
        • FIFO 큐 
          • 같은 호스트에 속한 URL은 언제나 같은 큐에 보관됨 
        • 큐 선택기 (queue selector)
          • 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드 하도록 지정된 작업 스레드에 전달 
        • 작업 스레드 (worker thread) 
          • 전달된 URL을 다운로드 하는 작업을 수행 
          • 전달된 URL은 순차적으로 처리되며 작업들 사이에는 일정한 지연시간을 둘 수 있음 
    • 우선순위 
      • 크롤러 입장에서 중요한 페이지를 먼저 수집하도록 하는 것이 바람직 
      • URL의 우선순위 척도 
        • 유용성, 페이지 랭크, 트래픽 양, 갱신빈도 등 다양한 척도를 사용할 수 있음
      • 순위 결정 장치 (prioritizer)
        • URL 우선순위를 정하는 컴포넌트 
        • 순위 결정 장치 (prioritizer) 
          • URL을 입력받아 우선순위 계산 
        • 큐
          • 우선 순위 별로 큐가 하나씩 할당 
          • 우선 순위가 높으면 선택될 확률 증가 
        • 큐 선택기 
          • 임의의 큐에서 처리할 URL을 꺼내는 역할
          • 순위가 높은 큐에서 더 자주 꺼내도록 프로그램됨 
        • 전면 큐 (front queue)
          • 우선 순위 결정 과정을 처리 
        • 후면 큐 (back queue)
          • 크롤러가 예의 바르게 동작하도록 보증 
    • 신선도 
      • 웹페이지는 추가, 삭제, 변경이 많음 
      • 데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집해야 함 
        • 모든 웹페이지를 재수집하는 것은 소모가 많음 
        • 다음의 방안으로 최적화
          • 웹 페이지의 변경 이력을 활용
          • 우선 순위를 활용하여 중요한 페이지를 좀 더 자주 재수집 
    • 미수집 URL 저장소를 위한 지속성 저장 장치 
      • 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 구성 
        • 버퍼에 있는 데이터는 주기적으로 디스크에 기록 
• HTML 다운로더 
  • HTTP 프로토콜을 통해 웹 페이지를 내려받음 
  • 로봇 제외 프로토콜 (Robot Exclusion Protocol)
    • Robots.txt
      • 웹 사이트가 크롤러와 소통하는 표준적 방법 
      • 크롤러가 수집해도 되는 페이지 목록, 하면 안되는 페이지 목록 등이 들어있음 
      • 웹 사이트를 긁어가기 전에 크롤러는 해당 페이지에 나열된 규칙을 먼저 확인해야 함 
      • Robots.txt 파일 지속 다운로드 방지를 위해 주기적으로 다시 다운 받아 캐시에 보관 
  • 성능 최적화 
    • 분산 크롤링 
      • 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산 
      • 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리 
      • URL 공간은 작은 단위로 분할하여 각 서버는 그중 일부의 다운로드를 담당 
    • 도메인 이름 변환 결과 캐시 
      • 도메인 이름 변환기 (DNS Resolver)는 크롤러의 성능 병목중 하나 
        • DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문 
        • DNS 요청이 처리되는데 보통 10ms ~ 200ms 소요
        • 크롤러 스레드 가운데 어느 하나라도 이 작업을 하고 있으면 다른 스레드의 DNS 요청은 전부 블록 처리됨 
      • DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해놓고 크론잡 등을 통해 주기적으로 갱신해 성능 향상 가능 
    • 지역성 
      • 크롤링 작업 수행 서버를 지역별로 분산 
        • 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간을 줄어듬 
        • 지역성을 활용하는 전략은 크롤서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능 
    • 짧은 타임아웃 
      • 응답 대기 시간이 길어지면 좋지 않으므로 최대 얼마나 기다릴지 미리 정해 두는 것 
        • 서버가 응답하지 않으면 크롤러는 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어감 
• 안정성 확보 전략
  
  • 안정 해시 (consistent hashing) 
    • 다운로더 서버들이 부하를 분산할 때 적용 가능 
  • 크롤링 상태 및 수집 데이터 저장 
    • 크롤링 상태와 수집된 데이터를 지속적으로 저장장치에 기록해 장애 발생 경우에도 쉽게 복구할 수 있도록 구성 
      • 중단시 쉽게 재시작 포인트로 재시작 가능 
  • 예외 처리 (exception handling)
    • 예외가 발생해도 전체 시스템이 중단되는 일 없이 그 작업을 우아하게 이어나갈 수 있어야 함 
  • 데이터 검증 (data validation) 
    • 시스템 오류를 방지하기 위한 중요 수단 가운데 하나 
• 확장성 확복 전략 
  • 새로운 모듈을 끼워넣을 수 있도록 컴포넌트를 모듈화 하는 것이 중요 
    • URL 다운로더를 PNG 다운로더 등으로 컴포넌트화 
• 문제가 있는 콘텐츠 감지 및 회피 전략 
  • 중복 컨텐츠 
    • 웹 콘텐츠의 약 30% 가량은 중복 
    • 해시나 체크섬을 사용하면 중복 컨텐츠를 쉽게 탐지 가능 
  • 거미 덫 (spider trap) 
    • 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지 
    • URL의 최대 길이를 제한하는 등의 방법으로 회피는 가능하지만, 만능 해결책은 없음 
      • 사람이 수작업으로 덫을 확인하고 찾아낸 후 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어둘 수 있음 
  • 데이터 노이즈 
    • 광고나, 스크립트 코드, 스팸 URL 처럼 도움되지 않는 컨텐츠는 가능한 제외처리 

 

 

 

 

4단계 마무리 

• 추가 논의 대상 
  • 서버 측 렌더링 (server-side rendering) 
    • ajax, javascript 등을 이용하여 동적으로 생성되는 링크는 발견이 불가능 
      • 페이지를 파싱하기 전에 서버 측 렌더링 (동적 렌더링)을 적용하면 해결 가능 
  • 원치 않는 페이지 필터링 
    • 스팸 방지(anti-spam) 컴포넌트를 두어 품질이 안좋은 페이지를 걸러낼 수 있도록 할 수 있음 
  • 데이터베이스 다중화 및 샤딩 
    • 다중화나 샤딩 같은 기법을 통해 데이터 계층의 가용성, 규모 확장성, 안정성을 향상 가능 
  • 수평적 규모 확장성 
    • 서버가 상태 정보를 유지하지 않도록, 무상태 서버로 만들어 수평적 확장을 통해 대규모 크롤링 제공 가능 
  • 가용성, 일관성, 안정성 
  • 데이터 분석 솔루션 
    • 데이터와 분석 결과를 이용해 시스템을 세밀히 조정