웹 크롤러 시스템 디자인

• 서론
• 요구사항
• 개략적 규모 추정
• 개략적 설계
  • 시작 URL 집합 선택
  • 미수집 URL 저장소
  • HTML 다운로더
  • 도메인 이름 변환기
  • 컨텐츠 파서
  • 중복 컨텐츠인가?
  • 컨텐츠 저장소
  • URL 추출기
  • URL 필터
  • 이미 방문한 URL?
  • URL 저장소
• 상세 설계
  • 탐색 방법
  • 예의 있게
  • 우선 순위
• 고려사항
  • 어떻게 해야 효율적으로 크롤링하는 시작 URL을 설정 할 수 있을까?
  • 컨텐츠 저장소에는 어떤 데이터를 저장하고, 어떻게 분산해야할까?
  • 웹 페이지가 중복 컨텐츠임을 어떻게 검증해야할까?
  • URL 필터를 어떻게 구현해야할까?
  • 변경 사항이 생긴 페이지는 어떻게 다시 크롤링할 것인가?
  • 리디렉션을 어떻게 처리할 것인가?
• 참고

서론

이번 글에서는 웹 크롤러 서비스를 디자인하는 글을 작성해보려고 한다.

구글 같은 검색 사이트에서 어떻게 전세계 사이트들을 서빙할 수 있을까? 내가 구글 검색 웹 크롤러 개발자라고 생각해보고 여러가지 관점에서 생각해보자.

글 후반부에는 요구 사항을 추가하여 설계된 서비스를 고도화 해보려고 한다.

요구사항

• 검색 엔진 인덱스 생성용 용도 웹 크롤러
• 수집 양은 매달 10억개의 웹 페이지, 수집 기간은 5년
• 비정상적 입력이나 환경에 대응할 수 있어야함
• 타겟 웹 사이트로 짧은 시간 동안 너무 많은 요청은 전송하면 안됨
• 새로운 형태의 컨텐츠도 지원하기 쉬워야 함

개략적 규모 추정

• QPS = 10억 / (30 * 24 * 3600) = 385/초
• 최대 QPS = 385 * 2 = 770/초
• 웹 페이지 크기 평균 = 500K라고 가정
• 최대 저장 용량 = 500K * 10억 = 500TB/월
• 최대 저장 용량 = 500TB * 5년 = 30PB

개략적 설계

시작 URL 집합 선택

시작 URL 집합은 크롤링할 웹 페이지의 집합이다. 크롤러가 가능한 많은 링크를 탐색할 수 있도록 하는 URL을 선택해야 한다. 아래 고려사항 절에서 좀 더 자세하게 살펴보자.

미수집 URL 저장소

크롤러 입장에서 URL의 상태는 다운로드 해야하는 또는 이미 다운로드 된 상태이다. 이 중 다운로드할 URL 집합을 저장하는 컴포넌트를 미수집 URL 저장소라고 한다.

여러 개의 HTML 병렬로 실행할 수 있도록 큐를 사용하는 것이 좋을 것 같다.

HTML 다운로더

웹 페이지를 다운로드하는 컴포넌트이다. 미수집 URL 저장소로부터 URL을 가져와서 다운로드를 수행한다.

도메인 이름 변환기

URL을 IP 주소로 변환하는 컴포넌트이다. HTML 다운로더는 도메인 이름을 도메인 이름 변환기로 요청하여 IP 주소를 획득하여 HTML을 다운로드한다.

HTML 다운로더 호스트에서 IP 주소를 획득할 수 도 있겠지만, 각 컴포넌트의 역할을 명확히 하기 위해서 도메인 이름 변환기를 따로 두는 것이 좋을 것 같다.

IP 주소를 획득하는 부분이 성능 병목이 될 수 있는데, 이를 위해서는 도메인 쿼리 버퍼나 도메인 캐시를 사용하면 좋을 것 같다. 즉, URL을 모아서 한 번에 도메인 이름 변환기에 요청하고, 한 번에 응답을 받는 것이다. 그리고 도메인 이름 변환기에서는 DNS 서버로 부터 얻은 IP 주소를 도메인 이름과 매핑해놓고 캐시를 유지하고, 크롭 잡으로 주기적으로 갱신하도록 하면 성능을 올릴 수 있을 것이다.

컨텐츠 파서

웹 페이지를 다운로드하면 파싱과 검증 절차(올바른 웹 페이지인지)를 거쳐야한다. 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있다.

중복 컨텐츠인가?

어떻게 하면 웹 페이지가 이미 저장되었는지 확인할 수 있을까? 이를 위해서는 웹 페이지를 저장하는 저장소가 필요하다. 또, 어떻게 웹 페이지가 같은 컨텐츠인지 비교하는 것을 고려해야 한다. 아래 고려사항 절에서 자세히 살펴보자.

컨텐츠 저장소

HTML 자체를 보관하는 저장소이다. 이 저장소는 중복 컨텐츠를 검증하는데 사용된다.

어찌보면 현재 설계된 시스템에서 가장 용량이 많이 차지하는 컴포넌트이다. 30PB의 저장 용량이 필요하다고 추정했는데 하나의 저장소에 모든 데이터를 저장하면, 데이터 조회 속도가 많이 느려질 것 같다.

데이터 조회 속도를 위해 데이터를 저장할 때 분산 저장할 필요가 있고, 어떻게 데이터를 저장할 것인지에 대해서 고려를 해야한다. 아래 고려사항 절에서 자세히 살펴보자.

URL 추출기

파싱된 HTML에서 새로운 URL을 추출하는 컴포넌트이다. 상대 경로는 전부 절대 경로로 변환한다.

URL 필터

URL 추출기에서 추출한 URL을 필터링 하는 컴포넌트이다. 접속 시 오류가 발생하는 URL, 접근 제외 목록, 특정 컨텐츠 타입이나 파일 확장자를 갖는 URL 등을 필터링해야한다.

추출된 URL을 빠르게 필터링해야 하기 때문에, 어떻게 빠르게 필터링할 수 있을까에 대해서 고려해야 한다. 아래 고려사항 절에서 자세히 살펴보자.

이미 방문한 URL?

이미 방문한 URL은 크롤링 대상에서 제외되어야 한다. 이를 위해서는 이미 방문한 URL을 저장하는 자료 구조가 필요하다.

블룸 필터나 해시테이블을 사용할 수 있다.

URL 저장소

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

전반적인 작업 흐름을 그려보면 아래와 같다.

1. 시작 URL들을 미수집 URL 저장소에 저장
2. HTML 다운로더는 미수접 URL 저장소에서 URL 목록을 가져온다
3. HTML 다운로더는 도메인 이름 변환기를 호출하여 IP 주소를 획득한 후, 해당 IP 주소에서 웹 페이지를 다운로드 받는다
4. 컨텐츠 파서는 다운로드 받은 웹 페이지를 파싱하고, 검증한다
5. 컨텐츠 파싱과 검증이 끝나면 중복 컨텐츠 인지 확인한다.
6. 중복 컨텐치 인지 확인하기 위해서, 해당 페이지가 이미 저장소에 있는지 본다. 이미 저장되어 있으면 버리고, 없으면 저장소에 저장한 뒤 URL 추출기로 전달한다
7. URL 추출기는 파싱된 HTML에서 새로운 URL을 추출한다
8. 골라낸 링크 URL를 URL 필터로 전달한다
9. 필터링이 끝난 URL만 중복 URL 판별 단계에 전달한다
10. 이미 처리한 URL인지 확인하기 위하여, URL 저장소에 보관된 URL인지 살핀다. 이미 저장소에 있는 URL은 버린다.
11. 저장소에 없는 URL은 URL 저장소에 저장하고, 미수집 URL 저장소에 전달한다

상세 설계

탐색 방법

웹은 유향 그래프와 같다. 페이지는 노드이고, 하이퍼링크는 엣지라고 보면된다.

그래프 탐색으로 DFS, BFS로 탐색할 수 있는데, BFS가 좋을 것 같다. 왜냐하면 그래프의 깊이를 가늠하기 어렵기 때문이다. BFS는 레벨 단위로 탐색하기 때문에, 레벨이 낮은 페이지를 먼저 탐색할 수 있다. 하지만, BFS로 탐색할 경우에 2가지 문제점이 있다.

Impolite Crawling와 URL 우선순위에 이슈가 있다.

Impolite Crawling부터 살펴보면 크롤러가 너무 많은 요청을 보내서 서버에 부하를 주는 것이다. 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다. 이럴 경우 크롤러는 같은 호스트에 속한 많은 링크를 탐색하게 되는데, 이는 서버에 많은 부하를 줄 수 있다.

URL에 우선순위를 두지 않는다. 즉, 모든 페이지가 동일한 우선순위를 갖는다. 이는 중요한 페이지를 먼저 탐색하지 못하게 한다. 네이버 홈페이지가 크롤링 관점에서 분명히 네이버 블로그 페이지보다 중요하다고 볼 수 있을 것이다.

예의 있게

예의 바르게 요청하려면 어떻게 해야할까? 미수집 URL 저장소에서 시간차를 두고, URL을 가져갈 수 있도록 해야할 것이다.

이 요구사항을 만족시키려면 미수집 URL 저장소는 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지시켜야 한다. 그리고 HTML 다운로더 스레드(or 서버)는 별도 FIFO 큐를 가지고 있어서, 시간차를 두고 해당 큐에서 꺼낸 URL만 다운로드하게 한다.

우선 순위

URL의 우선 순위는 어떻게 매겨야할까? 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있을 것 같다. URL 우선 순위를 매기고, 우선 순위를 부여하는 것에 대해서는 차치하고, 우선순위가 매겨진 URL을 어떻게 크롤링할 것인지에 대해서 생각해보자.

CPU 스케줄링처럼 우선순위 별로 큐를 두고, 우선순위가 높은 큐부터 크롤링하면 좋을 것 같다.

전면 큐에서 입력 URL에 대해서 우선순위를 매기고, 후면 큐에서 예의 있게 동작하도록 한다.

고려사항

어떻게 해야 효율적으로 크롤링하는 시작 URL을 설정 할 수 있을까?

사용자가 검색을 했을때 검색에 알맞는 링크를 반환하기 위해서는 최대한 루트에 있는 페이지를 탐색해야한다. 검색 엔진 관점에서 사용자들이 접속하는, 최신 정보와 아카이빙 정보가 많은 곳을 타겟으로 시작 URL로 시작하는 것이 좋을 것 같다.

• 주요 포털과 디렉토리
  • 구글, 빙, 야후, 네이버 같은 대형 검색 엔진이나 DMOZ, Yahoo! Directory과 같은 디렉토리를 포함시킨다.
• 소셜 미디어와 RSS 피드
  • 실시간 정보와 트렌드를 추적해야 한다면, 트위터, 페이스북, 레딧, 인스타그램과 같은 플랫폼을 활용할 수 있다.
  • 또한 관련있는 RSS 피드를 구독하여 지속적으로 업데이트되는 컨텐츠를 크롤링할 수 있다.
• 특정 주제에 맞춰진 커뮤니티 사이트
  • 특정 주제나 분야에 대해서 정보가 많은 커뮤니티 사이트를 크롤링할 수 있다.
  • 예를 들어, Stack Overflow, Quora, Reddit, Hacker News와 같은 사이트가 있다.

컨텐츠 저장소에는 어떤 데이터를 저장하고, 어떻게 분산해야할까?

검색 엔진을 위한 웹 크롤러 컨텐츠 저장소에는 실제 HTML 문서를 저장할 필요가 있을까? HTML 문서 메타 데이터(URL, 타이틀, 문서 내용 일부, 크롤링 시간, 우선 순위 등)만 저장하면 될 것 같다.

메타 데이터로 저장한다면 어떻게 저장해야할까? RDBMS를 사용할 수도 있고, NoSQL을 사용할 수도 있다. 30PB의 저장 용량이 필요하다고 추정했는데, 읽기/쓰기 연산을 고려했을때 샤딩이 필요할 것 같다. 샤딩 기준은 어떻게 해야할까? 도메인 기준으로 샤딩하는 것이 좋을 것 같다. 도메인 기준으로 샤딩하면, 핫스팟 문제가 발생할 수 있다. 예를 들어, google.com이 dgpr.me보다 훨씬 더 많은 경로를 갖고 있을 것이다. google.com 같은 도메인들이 하나의 샤드에 몰리면 읽기 성능이 저하될 것이다.

이를 해결하기 위해서는 도메인과 추가 정보를 사용하여 샤드에 분산시키는 것이 좋을 것 같다. 예를 들어, 도메인 정보와 경로를 해싱한 결과를 BASE64 인코딩한 값을 레인지로 사용하여 샤딩할 수도 있다. 이 때 해싱 함수를 선택하는 것이 샤딩 핵심 전략이고 고려해봐야 한다.

웹 페이지가 중복 컨텐츠임을 어떻게 검증해야할까?

빠른 시간에 중복 컨텐츠임을 확인하려면 해시를 사용하는 것이 합리적일 것 같다. 컨텐츠 저장소에서 해시를 계산하여 저장하고, 중복 컨텐츠인지 확인할 때는 해시를 계산하여 비교하면 된다. 해시를 사용할 때 사용되는 입력값은 HTML 문서 메타 데이터(URL, 타이틀, 문서 내용 일부)를 사용할 수 있다.

어떠한 해시를 사용하는 것이 좋을까? MD5, SHA-1, SHA-256 등 다양한 해시 알고리즘이 있지만, 다른 알고리즘에 비해 빠른 시간은 아니지만 충돌이 발생할 확률이 매우 낮은 SHA-256를 사용하는 것이 좋을 것 같다. SHA-256로 해시하는데 10밀리초 가정했을 때, 초당 대략 400개의 웹 페이지를 중복 컨텐츠인지 확인하는데 0.4초 정도가 걸린다. 초당 400개의 웹 페이지를 중복 컨텐츠인지 확인하는 것은 충분한 것 같다.

URL 필터를 어떻게 구현해야할까?

URL 필터링 대상은 트라이 구조로 관리하면 좋을 것 같다. 트라이 구조로 사용하면, 특정 URL 하위 URL을 모두 필터링할 수 있다. 예를 들어, www.google.com은 pass, www.google.com/a는 block, www.google.com/a/b는 pass가 되도록 할 수 있다. 트라이 구조를 DB에 적용한다고 하면, parent id를 사용하여 트리 구조를 표현할 수 있을 것이다.

변경 사항이 생긴 페이지는 어떻게 다시 크롤링할 것인가?

간단하게 컨텐츠 저장소에 저장된 우선 순위가 높은 URL을 대상으로 일정 주기로 cron job을 돌릴 수 있지만, 이럴 경우 기존 웹페이지가 변경되지 않았음에도 웹 크롤링이 수행된다.

이를 해결하는 방법으로 사용자가 검색 엔진을 사용할 때 컨텐츠 저장소가 조회되는데, 변경 여부를 판별하는 것이다. 이를 위해서는 컨텐츠 저장소에 저장된 컨텐츠의 해시를 계산하여 저장해놓고, 검색 엔진에서 컨텐츠 저장소를 조회할 때, 변경 여부를 판별하는 것이다. 변경이 되었다고 판별되면, 미저장 URL 저장소에 저장하고, 크롤링 대상으로 선정하여 재 크롤링을 수행하는 방법으로 해결할 수 있다.

리디렉션을 어떻게 처리할 것인가?

광고 페이지와 같은 경우 리디렉션이 발생하는데 이럴 경우에는 웹 크롤러에서 어떻게 동작해야할까?

가장 간단하게는 웹 크롤러에서 크롤링 대상 사이트로부터 얻은 HTTP Status Code를 확인하여 200 OK가 아니면 HTTP 응답 Location으로 리디렉션된 URL을 크롤링 대상 사이트로 다시 요청하는 것이다.

좀 더 성능을 올린다고 해보면, 도메인 이름 변환기에서 리디렉션을 캐싱하여 처리할 수도 있을 것이다. 도메인 이름 변환기에서 도메인과 리디렉션 정보를 저장하고, HTML 다운로더에서 도메인 이름 변환기에 리디렉션 정보를 요청할 때 캐싱된 리디렉션 정보를 반환하는 방법이다. 이럴 경우, 리디렉션 하는 도메인의 IP 주소를 도메인 이름 변환기로 요청할 경우 리디렉션된 IP 주소를 반환하여, 리디렉션 하는 URL에는 요청을 하지 않고, 바로 리디렉션된 URL을 크롤링 대상 사이트로 요청할 수 있다.

참고

• https://product.kyobobook.co.kr/detail/S000001033116
• https://medium.com/@tonywangcn/the-architecture-of-a-web-crawler-building-a-google-inspired-distributed-web-crawler-part-1-7f4281f9f539
• https://www.enjoyalgorithms.com/blog/web-crawler