9장: 웹 크롤러 설계

*<가상 면접 사례로 배우는 대규모 시스템 설계 기초> 을 참고하여 작성한 게시물입니다.

웹 크롤러 설계

웹 크롤러는 로봇 또는 스파이더라고도 부른다. 검색 엔진에서 널리 쓰는 기술로, 웽에 새로 올라오거나 갱신된 콘텐츠(웹 페이지, 이미지, 비디오, pdf 파일...)을 찾아내는 것이다. 이는 몇 개 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 콘텐츠를 수집한다. 웹 크롤러는 다양하게 이용된다.

• 검색 엔진 인덱싱(search engine indexing): 크롤러의 가장 보편적 용례. 크롤러는 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. ex.구글봇
• 웹 아카이빙(web archiving): 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차. 많은 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙하고 있다.
• 웹 마이닝(web mining): 웹의 폭발적 성장세는 데이터 마이닝(data mining) 업계에 전례없는 기회다. 웹 마이닝을 통해 인터넷에서 유용한 지식을 도출해낼 수 있는 것이다. 예로, 유명 금융 기업은 크롤러를 사용해 주주총회자료나 연차보고서를 다운 받아 기업의 핵심 사읍 방향을 알아낸다.
• 웹 모니터링(web monitoring): 크롤러를 사용하면 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다.

웹 크롤러의 복잡도는 데이터 규모에 따라 달라진다.

문제 이해 및 설계 범위 확정

웹 크롤러의 기본 알고리즘은 간단하다. 1)URL 집합이 입력으로 주어지면, 해당 URL들이 가리키는 모든 웹 페이지를 다운로드한다. 2)다운받은 웹 페이지에서 URL들을 추출한다. 3)추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다.
좋은 웹 크롤러가 만족시켜야 할 다음과 같은 속성에 주의를 기울이는 것도 바람직하다.

• 규모 확장성: 웹은 거대하다. 오늘날 웹에는 수십억 개의 페이지가 존재한다. 따라서 병행성(parallelism)을 활용하면 보다 효과적으로 웹 크롤링을 할 수 있을 것이다.
• 안정성(robustness): 웹은 함정으로 가득하다. 잘못 작성된 HTML, 아무 반응이 없는 서버, 장애, 악성 코드가 붙어 있는 링크 등이 그 좋은 예다. 크롤러는 이런 비정상적 입력이나 환경에 잘 대응할 수 있어야 한다.
• 예절(politeness): 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안 된다.
• 확장성(extensibility): 새로운 형태의 콘텐츠를 지원하기가 쉬워야 한다. 예를 들어, 이미지 파일도 크롤링하고 싶다고 해 보자. 이를 위해 전체 시스템을 새로 설계해야 한다면 곤란할 것이다.

개략적 규모 추정

• 매달 10억 개의 웹 페이지를 다운로드한다.
• QPS = 10억/30일/24시간/3500초 = 대략 400페이지/초
• 최대(Peak) QPS = 2*QPS = 800
• 웹 페이지의 크기 평균은 500k라고 가정
• 10억 페이지*500k = 500TB/월.
• 1개월치 데이터를 보관하는 데 500TB, 5년간 보관한다고 가정하면 결국 500TB*12개월*5년 = 30PB

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

• 시작 URL 집합: 웹 크롤러가 크롤링을 시작하는 출발점. 예로, 어떤 대학 웹사이트로부터 찾아나갈 수 있는 모든 웹 페이지를 크롤링하는 가장 직관적 방법은 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 쓰는 것. 전체 웹을 크롤링해야하는 경우에는 시작 URL을 고를 때 좀 더 창의적일 필요가 있다. 크롤러가 가능한 한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직. 일반적으로는 전체 URL공간을 작은 부분집합으로 나누는 전략을 쓴다. 지역적 특색, 그러니까 나라별로 인기있는 웹사이트가 다르다는 점에서 착안하는 것. 또 다른 방법은 주제별로 다른 시작 URL을 사용하는 것. 시작 URL을 무엇으로 쓸 것이냐는 질문에 정답은 없다.
• 미수집 URL 저장소: 대부분 현대적 웹 크롤러는 크롤링 상태를 (1)다운로드할 URL, (2)다운로드된 URL 두 가지로 나눠 관리한다. 이 중 다운로드할 URL을 저장 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier)라고 부른다. FIFO queue라고 생각하면 된다.
• HTML 다운로더: 인터넷에서 웹 페이지를 다운로드하는 컴포넌트. 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공함.
• 도메인 이름 변환기: 웹 페이지를 다운받으려면 URL을 IP 주소로 변환하는 절차가 필요. HTML 다운로더는 도메인 이름 변환기를 사용하여 URL에 대응되는 IP 주소를 알아낸다.
• 콘텐츠 파서: 웹 페이지 다운로드를 하려면 파싱(parsing)과 검증(validation) 절차를 거쳐야한다. 이상한 웹 페이지는 문제를 일으키거나 저장 공간만 낭비하기 때문. 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려질 수 있으므로 독립 컴포넌트로 만들어진다.
• 중복 콘텐츠인가?: 같은 콘텐츠를 여러 번 저장하게 될 수 있으므로, 이를 해결하기 위한 자료 구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄인다. 이미 시스템에 저장된 콘텐츠임을 알아내기 쉽게하는 것. 비교하는 가장 간단한 방법은 문자열로 보고 비교하는 것이겠지만, 비교 대상 문서의 수가 너무 많으면 느리고 비효율적이어서 적용하기 곤란할 것이다. 효과적 방법은 웹 페이지의 해시 값을 비교하는 것이다.
• 콘텐츠 저장소: 이는 HTML 문서를 보관하는 시스템. 저장소를 구현하는 데 쓰일 기술을 고를때는 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간등을 종합적으로 고려해야 한다. 본 설계안의 경우 디스크와 메모리를 동시에 사용하는 저장소를 택할 것이다. : 데이터의 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장. 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄일 것.
• URL 추출기: HTML 페이지를 파싱하여 링크들을 골라내는 역할. 상대 경로는 전부 절대 경로로 변환.
• URL 필터: 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL 등을 크롤링 대상에서 배제하는 역할.
• 이미 방문한 URL? 이를 구현하기 위해 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료구조 사용. 이미 방문한적있는 URL인지 추적하면 같은 URL을 여러번 처리하는 일을 방지할 수 있으므로 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있다. 해당 자료구조로는 블룸 필터나 해시 테이블이 널리 쓰인다.
• URL 저장소: 이미 방문한 URL을 보관하는 저장소
• 웹 크롤러 작업 흐름: 1)시작 URL들을 미수집 URL 저장소에 저장. 2)HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져옴. 3)HTML 다운로더는 도메인 이름 변환기를 사용하여 URL의 IP 주소를 알아내고 해당 IP 주소로 접속하여 웹 페이지를 다운받음. 4)콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증. 5)콘텐츠 파싱과 검증이 끝나면 중복 콘테느인지 확인하는 절차 개시. 6)중복 콘텐츠인지 확인하기 위해 해당 페이지가 이미 저장소에 있는지 본다. 이미 저장소에 있는 콘텐츠인 경우 저장하지 않고 버리며, 저장소에 없는 콘텐츠인 겨웅에는 저장소에 저장한뒤 URL 추출기로 전달. 7)URL 추출기는 해당 HTML 페이지에서 링크를 골라냄. 8)골라낸 링크를 URL 필터로 전달. 9)필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달. 10)이미 처리한 URL인지 확인하기 위하여 URL 저장소에 보관된 URL인지 살핌. 이미 저장소에 있는 URL은 버림. 11)저장소에 없는 URL은 URL 저장소에 저장할뿐 아니라 미수집 URL 저장소에도 전달함.

상세 설계

• DFS vs BFS
  • 웹은 유향 그래프(directed graph)와 같다. 페이지는 노드, 하이퍼링크(URL)은 에지(edge). 크롤링 프로세스는 이 유향 그래프를 에지를 따라 탐색하는 과정. DFS는 좋은 선택이 아닐 가능성이 높다. 그래프 크기가 클 경우 어느정도로 깊숙이 가게될지 가늠하기 어려워서이다. 따라서 웹 크롤러는 보통 BFS를 사용한다. 그러나 여기엔 문제점이 있다. 1)한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다. 결국 크롤러는 같은 호스트에 속한 많은 링크를 다운받느라 바빠지게 되는데, 이떄 링크들을 병렬로 처리하게 된다면 해당 서버는 수많은 요청으로 과부하에 걸린다. 이런 크롤러는 보통 예의없는(impolite) 크롤러로 간주된다. 2)표준적 BFS 알고리즘은 URL 간에 우선순위를 두지않는다. 처리 순서에 있어 모든 페이지를 공평하게 대우한다는 뜻. 하지만 모든 웹 페이지가 같은 수준의 품질, 중요성을 갖지는 않는다. 그러니 페이지 순위, 사용자 트래픽 양, 업데이트 빈도 등 여러가지 척도에 비추어 처리 우선순위를 구별하는 것이 온당할 것이다.
• 미수집 URL 저장소
  • 미수집 URL 저장소를 활용하면 문제를 좀 쉽게 해결할 수 있다. 이 저장소를 잘 구현하면 예의(politeness)를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다. 1)예의: 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청하도록 해야한다. 같은 웹 사이트의 페이지 다운 태스크는 시간차를 두고 실행하도록 하면 된다. 이를 만족시키려면 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다. 즉, 각 다운로드 스레드는 별도 FIFO 큐를 갖고 있어, 해당 큐에서 꺼낸 URL만 다운로드한다. 큐 라우터(같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장), 매핑 테이블(호스트 이름과 큐 사이의 관계 보관 테이블), FIFO 큐(같은 호스트에 속한 URL은 언제나 같은 큐에 보관), 큐 선택기(큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달), 작업 스레드(전달된 URL을 다운로드하는 작업 수행. 전달된 URL은 순차처리, 작업 사이에는 일정 지연시간을 둘 수 있음)를 이용해서 설계할 수 있다. 2)우선순위: 유용성에 따라 URL의 우선순위를 나눌때는 페이지랭크, 트래픽양, 갱신 빈도등 다양한 척도를 사용할 수 있을 것이다. 순위결정장치(prioritizer)는 URL 우선순위를 결정하는 컴포넌트다. 순위결정장치(URL을 입력으로 받아 우선순위 계산), 큐(우선순위 별로 큐가 하나씩 할당. 우선순위 높으면 선택 확률 올라감.), 큐 선택기(임의 큐에서 처리할 URL 꺼내는 역할 담당. 순위 높은 큐에서 더 자주 꺼내도록 설계). 를 통해 설계하고, 이를 적용하면 다음 두 모듈이 존재한다: 전면 큐(우선순위 결정 과정 처리), 후면 큐(크롤러가 예의 바르게 동작하도록 보증)
    • 신선도: 데이터의 신선함 유지를 위해서는 다운로드한 페이지라고 해도 주기적으로 재수집할 필요가 있다. 이를 최적화하기 위해서는 웹 페이지 변경이력 활용, 우선순위 활용하여 중요 페이지는 좀 더 자주 재수집하는 방법이 있다.
    • 미수집 URL 저장소를 위한 지속성 저장 장치: 검색 엔진을 위한 크롤러의 경우, 처리해야하는 URL의 수는 수억 개에 달한다. 그러니 그 모두를 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직하지 않다. (병목지점이 되므로) -> 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것이다. 버퍼에 있는 데이터는 주기적으로 디스크에 기록할 것이다.
• HTML 다운로더
  • HTTP 프로토콜을 통해 웹페이지를 내려받는다.
  • robots.txt: 로봇 제외 프로토콜이라고도 불리며, 크롤러가 수집해도 되는 페이지 목록이 들어있다. 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야한다.
  • 성능 최적화: 1)분산 크롤링:크롤링 작업을 여러 서버에 분산하는 것. 각 서버는 여러 스레드를 돌려 다운로드 작업 처리. 이 구성을 위해 URL 공간은 작은 단위로 분할하여, 각 서버는 그중 일부의 다운로드를 담당하도록 한다. (미수집 URL 저장소에서 각 서버에 URL 주소 할당) 2)도메인 이름 변환 결과 캐시: 도메인 이름 변환기(DNS Resolver)는 크롤러 성능의 병목 중 하나인데, 이는 해당 작업의 동기적 특성 떄문. 따라서 DNS 조회 결과로 얻어진 도메인 이름, IP 주소 사이 관계를 캐시에 보관해놓고 크론 잡(cron job) 등을 돌려 주기적으로 갱신하도록 해놓으면 성능을 효과적으로 높일 수 있다. 3)지역성: 크롤링 작업 수행 서버를 지역별로 분산하는 방법. 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운 시간은 줄어든다. 4)짧은 타임아웃: 웹 서버는 응답이 느리거나 아예 응답하지 않는다. 이런 경우 대기 시간이 길어지면 좋지 않으므로, 최대 얼마나 기다릴지를 미리 정해둔다. 이 시간동안 서버가 응답하지 않으면 다음 페이지로 넘어간다.
• 안정성 확보 전략
  • 안정성 향상을 위한 접근법 가운데 중요한 몇가지는 다음과 같다. 1)안정 해시: 다운로더 서버들에 부하를 분산할때 적용 가능한 기술. 이를 이용하면 다운로더 서버를 쉽게 추가하고 삭제할 수 있다. 2)크롤링 상태 및 수집 데이터 저장: 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집 데이터를 지속적 저장장치에 기록해두는 것이 바람직. 3)예외 처리: 예외가 발생해도 전체 시스템이 중단되는 일 없이 그 작업을 이어나갈 수 있도록. 4)데이터 검증: 시스템 오류 방지를 위한 중요 수단 가운데 하나.
• 확장성 확보 전략
  • 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경써야 한다.(ex. PNG 다운로더, 웹 모니터등의 모듈 추가..)
• 문제 있는 콘텐츠 감지 및 회피 전략
  • 1)중복 콘텐츠: 해시나 체크섬을 사용하여 탐지. 2)거미 덫: 크롤러를 무한 루프에 빠뜨리도록 설계한 웹 페이지. URL의 최대 길이를 제한. 그러나 만능 해결책은 없음. 수작업으로 덫 확인하고 찾아낸 후에 덫이 있는 사이트를 크롤러 탐색 대상에서 제외하거나 URL 필터 목록에 걸어둠. 3)데이터 노이즈: 가치 없는 콘텐츠는 제외해야한다.

마무리

추가로 논의해야할 사항은 다음과 같다.

• 서버측 렌더링(server-side rendering): 많은 웹사이트가 JS, AJAX 등의 기술을 사용해 링크를 즉석에서 만들어냄. 그러니 웹 페이지를 그냥 있는 그대로 다운받아서 파싱하면 동적으로 생성되는 링크는 발견할 수 없음. 이를 파싱하기 전에 서버측 렌더링(동적 렌더링, dynamic rendering이라고도 불림)을 적용하여 해결할 수 있다.
• 원치 않는 페이지 필터링: 저장 공간 등 크롤링 소요 자원은 유한하므로 스팸 방지 컴포넌트를 두어 스팸성, 혹은 품질이 조악한 페이지는 걸러내도록 하면 좋다.
• DB 다중화 및 샤딩: 이를 통해 데이터 계층 가용성, 규모 확장성, 안정성이 향상된다.
• 수평적 규모 확장성: 대규모의 크롤링을 위햇는 다운로드를 실행할 서버가 수백 혹은 수천 대 필요하게 될 수도 있다. 수평적 규모 확장성을 달성하는데 중요한 것은 서버가 상태정보를 유지하지 않도록, 즉 stateless 서버로 만드는 것이다.
• 가용성, 일관성, 안정성: 성공적 대형 시스템을 만들기 위해 필수적으로 고려해야하는 것이다.
• 데이터 분석 솔루션: 데이터를 수집, 분석하는 것은 어느 시스템에나 중요.