웹 크롤러 설계 면접 퀴즈

크롤러는 처리량 문제로 보이기 쉽습니다. 그런데 계산해 보면 처리량은 남고 대상을 고르게 펴는 것이 어렵습니다.

기능 요구사항과 범위 밖

자바스크립트 실행을 뺀 것이 규모를 정합니다. 브라우저를 띄워 실행하면 페이지 하나당 비용이 수십 배가 되고, 월 10억 페이지 을 감당할 수 없습니다. 그 대신 자바스크립트로만 만들어지는 내용은 못 봅니다.

예산을 초로 바꾼다

월 10억 페이지 은 초당 약 386페이지입니다. 노드 100대 이면 노드당 초당 4페이지라 처리량은 전혀 부담이 아닙니다.

문제는 예의 규칙입니다. 한 호스트에서는 초당 한 번만 가져올 수 있으므로, 초당 386페이지를 내려면 최소 386개 호스트를 동시에 다뤄야 합니다.

이것이 이 설계의 성격을 정합니다. 빠르게 가져오는 문제가 아니라 다룰 호스트를 늘 충분히 확보하는 문제입니다.

저장 규모

페이지가 평균 500KB 이므로 월 500TB 입니다. 보관 누적 30억 페이지 이면 그보다 훨씬 큽니다.

여기서 중복 제거가 저장 비용과 직결됩니다. 같은 내용이 여러 주소로 오는 일이 흔하고, 그것을 걸러내지 못하면 저장량이 몇 배가 됩니다.

예의를 요구사항으로 적는 이유

예의 규칙은 우리가 선택하는 것이 아니라 지켜야 하는 것입니다. 지키지 않으면 상대 사이트에 부담을 주고, 결국 우리 크롤러가 차단됩니다.

차단되면 그 사이트를 영구히 못 보게 됩니다. 크롤러의 자산은 접근 가능한 사이트 목록이고, 예의가 그 자산을 지킵니다.

무엇이 병목인지 먼저 말한다

이 요구사항에서 병목은 셋입니다.

다룰 수 있는 호스트 수
방문할 주소 목록의 크기
저장 비용

처리량과 대역폭은 병목이 아닙니다. 무엇이 병목이 아닌지 말하는 것도 요구사항 정리의 일부입니다. 아니라고 말하지 않으면 뒤에서 그쪽을 최적화하게 됩니다.

앞 단계에서 최소 386개 호스트를 동시에 다뤄야 한다는 결론이 나왔습니다. 그것을 어떻게 만드는지가 이 절입니다.

한 줄에 섞으면 규칙을 지킬 수 없다

방문할 주소를 한 줄에 넣으면 같은 호스트의 주소가 연달아 나옵니다. 큰 사이트에서 나온 주소가 목록의 대부분을 차지하기 때문입니다.

그러면 일꾼들이 같은 호스트를 동시에 두드립니다. 예의 규칙을 지키려면 매번 "이 호스트를 마지막으로 언제 봤나" 를 확인해야 하고, 그 확인이 모든 일꾼 사이에서 공유돼야 합니다.

호스트마다 줄을 따로 세운다

호스트별로 큐를 만들고 한 큐는 한 일꾼만 봅니다. 그러면 그 일꾼이 자기 큐의 간격만 지키면 규칙이 지켜집니다. 일꾼 사이에 공유할 상태가 없어집니다.

호스트 큐를 일꾼에게 배정한다
일꾼은 자기 큐에서 하나 가져와 처리하고 1초 기다린다

규칙 확인이 지역 문제가 되는 것이 이 구조의 값입니다. 앞의 아키타입들에서 반복된 방식이고, 여기서는 호스트가 그 단위입니다.

큐 수가 곧 처리량이다

일꾼 하나가 한 호스트에서 초당 한 페이지를 가져오므로, 동시에 살아 있는 큐 수가 초당 페이지 수입니다.

큐가 부족하면 일꾼이 놀고 예산이 남습니다. 그래서 주소 목록이 여러 호스트에 고르게 퍼져 있어야 합니다. 한 호스트의 주소만 많이 들고 있으면 처리량이 나오지 않습니다.

큰 사이트가 목록을 채운다

주소는 대형 사이트에서 압도적으로 많이 나옵니다. 그대로 두면 목록이 소수 호스트로 채워지고, 큐 수가 줄어 처리량이 떨어집니다.

대형 사이트를 다 가져오려는 것과 예산을 채우는 것이 충돌합니다. 요구사항이 넓은 범위를 원한다면 상한을 두는 편이 맞습니다.

간격을 호스트마다 다르게 준다

초당 한 번은 기본값입니다. 큰 사이트는 더 자주 받아도 괜찮고, 작은 사이트는 더 느리게 해야 할 수 있습니다.

상대가 알려 준 간격이 있으면 그것을 따른다
응답이 느려지거나 거절이 오면 간격을 늘린다

상대의 신호에 반응하는 것이 규칙을 숫자로 지키는 것보다 중요합니다. 상대가 힘들어하는데 규칙만 지키고 계속 두드리면 결국 차단됩니다.

호스트별 큐를 만들었습니다. 그 큐를 채우는 주소 목록이 이 절의 주제입니다. 크롤러에서 가장 크고 가장 다루기 어려운 자료입니다.

발견이 크롤보다 빨리 자란다

페이지 하나에서 주소 수십 개가 나옵니다. 월 10억 페이지 을 가져오면 발견되는 주소는 그보다 훨씬 많습니다.

대부분은 이미 본 주소입니다. 사이트 안에서 서로 링크하기 때문입니다. 그래서 목록 관리의 핵심은 담는 것이 아니라 이미 본 것을 걸러내는 것입니다.

본 주소를 어떻게 기억하나

수십억 개의 주소를 그대로 기억할 수는 없습니다. 주소는 길고 개수가 많습니다.

지문만 담아도 메모리에 겨우 들어갑니다. 그래서 값싼 판정 장치를 앞에 두고 거기서 "없다" 고 하면 새 주소로 처리합니다. 키-값 저장소의 읽기 경로에서 본 것과 같은 장치입니다.

드물게 틀리면 이미 본 주소를 새 것으로 여겨 한 번 더 가져옵니다. 반대 방향으로 틀리지 않으므로 놓치는 주소는 없습니다. 이 비대칭이 여기서도 쓸모가 있습니다.

주소를 정규화한다

같은 페이지를 가리키는 주소가 여러 형태로 나옵니다. 끝의 빗금, 대소문자, 순서가 다른 질의 문자열, 추적용 매개변수가 그렇습니다.

정규화하지 않으면 같은 페이지를 여러 번 가져온다
목록도 그만큼 부풀어 오른다

어디까지 정규화할지가 판단입니다. 질의 문자열을 다 버리면 실제로 다른 페이지를 하나로 취급하고, 하나도 안 버리면 추적용 매개변수 때문에 같은 페이지가 수백 개로 늘어납니다.

목록을 어디에 두나

수십억 개를 메모리에 둘 수 없으므로 디스크에 둡니다. 그런데 큐에서 꺼내는 일은 빨라야 합니다.

앞부분만 메모리에 두고 뒤는 디스크에서 채웁니다. 순서대로 읽고 쓰므로 디스크에 유리한 접근입니다. 키-값 저장소에서 본 순차 쓰기의 이유와 같습니다.

목록이 사라지면 다시 시작해야 한다

크롤러를 재시작할 때 목록이 없으면 처음부터 다시 발견해야 합니다. 그러면 이미 가져온 페이지를 또 가져오게 되고 예산이 낭비됩니다.

그래서 목록은 크롤 결과보다 더 중요하게 지킵니다. 페이지는 다시 가져올 수 있지만, 목록을 잃으면 어디까지 했는지를 잃습니다.