많은 수의 URL을 효율적으로 검색합니다.

Question

나는 수백 개의 웹 사이트를 크롤링해야하는 웹 크롤러를 만들고 있습니다. 내 크롤러는 이미 크롤링 된 URL 목록을 보관합니다. 크롤러가 새 페이지를 크롤링 할 때마다 이미 크롤링 된 URL 목록을 먼저 검색하고 크롤러가 이미 나열되어 있으면 크롤러가 다음 URL로 건너 뛰는 식으로 진행됩니다. URL이 크롤링되면 목록에 추가됩니다.

현재 이진 검색을 사용하여 URL 목록을 검색하고 있지만 일단 목록이 커지면 검색 속도가 매우 느려집니다. 그래서, 내 질문에 어떤 URL 목록을 검색하는 데 사용할 수있는 알고리즘입니다 (약 20k 100k 매일 목록 크기 증가).

크롤러는 현재 Python으로 코딩되어 있습니다. 하지만 C++이나 다른 더 나은 언어로 이식 할 것입니다.

Answer 1

크롤링 된 목록의 크기를 어느 정도 결정해야합니다. 최대 수천만 개의 항목까지 해시지도 또는 사전에 URL을 저장하면 O (1) 조회가 제공됩니다.

평균 URL 길이가 약 80 자 (분산 크롤러를 실행했을 때의 5 년 전의 경험) 인 경우 기가 바이트 당 약 1 천만 개의 URL 만 얻게됩니다. 따라서 어느 정도의 시간이 지나면 데이터를 압축하거나 다시 크롤링 할 수 있다고 생각해야합니다. 하루에 100,000 개의 URL 만 추가하는 경우 1 천만 개의 URL을 크롤링하는 데 100 일이 소요됩니다. 재 크롤링을 허용 할 충분한 시간입니다.

이러한 것이 제한적인 경우 URL로 입력 된 간단한 사전 또는 해시 맵을 제안합니다. 이 값에는 마지막 크롤링 날짜 및 유지해야하는 다른 정보가 포함되어야합니다. 해당 데이터 구조를 1 천만 개의 URL로 제한하십시오. 아마 2GB의 공간에 가깝게 먹을 것입니다.

주기적으로 정리해야합니다. 제 제안은 하루에 한 번 실행되는 타이머를 사용하고 X 일 전에 크롤링 한 모든 URL을 정리하는 것입니다. 이 경우 X를 100으로 설정하면 하루에 100,000 개의 URL을 100 일 동안 보낼 수 있습니다.

하루에 수백만 개의 URL을 처리하는 고용량 크롤러에 대해 이야기하기 시작하면 훨씬 복잡한 데이터 구조와 창의적인 방법으로 복잡성을 관리 할 수 ​​있습니다. 하지만 귀하의 질문의 톤에서, 당신이 관심이 아니에요.

Answer 2

나는 이진 검색 목록에 넣기 전에 값을 해싱한다고 생각합니다. 이것은 문자열 비교의 병목 현상을 제거하고 int로 스왑합니다. 평등 검사. 또한 O (log2 (n)) 바이너리 검색 시간을 유지합니다. 실행 사이에 파이썬의 내장 된 hash()을 사용하면 일관된 결과를 얻지 못할 수도 있지만 구현에 따라 다릅니다. 실행 내에서 일관성있게 유지됩니다. 세션간에 일관성이있을 수있는 자체 해시를 구현하는 옵션이 항상 있습니다.