Web crawler que almacena urls visitadas en archivo - java, algoritmo, estructuras de datos, web-crawler

Estoy teniendo problemas para averiguar cómo puedoalmacene y escanee grandes cantidades de URLS visitados desde un rastreador web. La idea es que la cantidad de URL visitadas sea eventualmente demasiado para almacenar en la memoria y debería almacenarlas en un archivo, pero me preguntaba si esto no es muy ineficiente. Si después de obtener un lote de URL "s y quiero comprobar si la URL ya se visitó, tengo que verificar la línea de archivos visitados y ver si hay una coincidencia.

Pensé en usar un caché pero el problemaaún permanece cuando la URL no se encuentra en el caché y todavía tendría que revisar el archivo. ¿Tengo que revisar el archivo línea por línea para cada URL y hay una manera mejor / más eficiente de hacer esto?

Respuestas

Una estructura de datos clave aquí podría ser una Filtro de floracióny Guayaba Proporciona una implementación. El filtro Bloom le diría (quizás haya visitado la URL) o no lo ha hecho con seguridad. Si el resultado es tal vez puede ir y revisar el archivo si ya se visitó, de lo contrario, visite la URL y la tienda. Se encuentra en el archivo, así como en el filtro Bloom. Ahora, para optimizar las búsquedas de archivos, puede codificar la URL para obtener un tamaño fijo byte[] en lugar de longitud de cadena no fijada (por ejemplo: md5).

byte[] hash = md5(url);
if(bloomFilter.maybe(hash)){
checkTheFile(hash);
}else{
visitUrl(url);
addToFile(hash);
addToBloomFilter(hash);
}

Puede utilizar una base de datos y el hash es la clave principal para obtener una O(1) hora de acceso cuando verifica si existe una clave, o puede implementar un índice tú mismo.

¿Qué pasa con tener un archivo por URL? Si el archivo existe, se ha rastreado la URL.

A continuación, puede obtener más sofisticado y tener estoEl archivo contiene datos que indican los resultados del último rastreo, cuánto tiempo desea esperar antes del siguiente rastreo, etc. (Es útil poder detectar 404, por ejemplo, y decidir si intentarlo de nuevo o abandonar esa URL). .)

Con este enfoque, vale la pena normalizar las URL para que pequeñas diferencias en la URL no den lugar a archivos diferentes.

He usado esta técnica en mi rastreador de nodos (https://www.npmjs.com/package/node-nutch) y me permite almacenar el estado en el sistema de archivos (para rastreos simples) o en S3 (para rastreos que involucran más de un servidor).