Diseño de un crawler web: frontera de URL, cortesía y deduplicación

Un crawler parece sencillo: descarga una página, extrae sus enlaces, descarga esos, repite. Escrito como un bucle, funciona para mil páginas. Con mil millones de páginas se viene abajo de formas instructivas: machaca sitios pequeños con cientos de peticiones en paralelo, descarga la misma página bajo cincuenta URL, se pierde en un calendario infinito y pasa la mayor parte del tiempo esperando al DNS.

Este artículo diseña un crawler que escala y sigue siendo cortés: cifras de capacidad, la frontera de URL con colas de prioridad y por host, robots.txt tal como lo estandarizó la RFC 9309, la deduplicación de URL y de contenido, las trampas para crawlers y los componentes que los rodean, con un diagrama de todo el bucle.

Requisitos y cifras

El objetivo: rastrear unos mil millones de páginas al mes para un índice de búsqueda o de analítica, refrescar más a menudo las páginas importantes y no sobrecargar nunca un sitio web.

La última fila es la que más importa. El descubrimiento supera con creces a la descarga, así que el crawler siempre está eligiendo qué no descargar. La priorización es una función central, no una optimización.

El bucle de rastreo

1. Toma la siguiente URL de la frontera.
2. Comprueba el robots.txt de su host, desde la caché.
3. Resuelve el nombre del host, desde una caché DNS local.
4. Descarga la página respetando el retardo de cortesía del host.
5. Guarda la respuesta en bruto.
6. Analízala, extrae los enlaces y normalízalos.
7. Descarta los enlaces ya vistos; añade el resto a la frontera con una prioridad.
8. Calcula la huella del contenido y omite los casi duplicados en el procesamiento posterior.

Cada paso después del primero es un punto en el que un crawler ingenuo malgasta esfuerzo o causa daño.

La frontera de URL

La frontera es el corazón de un crawler: una cola que tiene que responder a la vez a dos preguntas distintas. ¿Qué URL importa más? ¿Y a qué host podemos contactar ahora mismo?

La respuesta clásica es el diseño de Mercator, descrito en el capítulo sobre la frontera de URL de Introduction to Information Retrieval:

• Las colas frontales gestionan la prioridad. Un priorizador asigna cada URL nueva a una de F colas según señales como la frecuencia con la que cambia la página, su popularidad en enlaces o la importancia de su sitio.
• Las colas traseras gestionan la cortesía. Cada cola trasera contiene URL de un único host. Un heap registra, por host, el momento más temprano en que se le puede volver a contactar.
• Un hilo de fetcher toma el host de la cima del heap, descarga una URL de la cola trasera de ese host y vuelve a insertar el host con un nuevo momento más temprano. Cuando una cola trasera se vacía, se rellena desde las colas frontales, favoreciendo las prioridades altas.

Los diseñadores de Mercator recomendaban unas tres veces más colas traseras que hilos de fetcher, para que los hilos rara vez esperen a un host al que hay que tratar con cortesía.

A escala, particiona la frontera por host: aplica un hash al nombre del host para elegir un shard de la frontera, de modo que todas las URL de un host vivan en un mismo sitio y la cortesía pueda aplicarse localmente, sin coordinación.

Cortesía y robots.txt

Un crawler cortés envía una sola petición a la vez por host y espera entre peticiones. Una heurística habitual del mismo capítulo: esperar unas diez veces lo que tardó la última descarga de ese host, para que los servidores lentos tengan automáticamente más margen. Retrocede aún más ante respuestas 429 y 503, y respeta cualquier cabecera Retry-After.

robots.txt se convirtió en estándar en 2022 con la RFC 9309. Las reglas que un crawler tiene que cumplir bien:

La asimetría entre 4xx y 5xx sorprende: un archivo que falta significa «adelante», pero un error del servidor significa «no entres», porque el crawler no puede saber qué habrían dicho las reglas. Crawl-delay no forma parte de la RFC 9309, y los crawlers difieren en si lo respetan. Identifica tu crawler con un user agent descriptivo que incluya una URL con datos de contacto.

Deduplicar URL

La misma página se esconde tras muchas URL: HTTP://Example.com:80/a/./b?utm_source=x#top y http://example.com/a/b son una sola página. Normaliza antes de comprobar si una URL ya se vio:

• Pasa a minúsculas el esquema y el host, quita los puertos por defecto, resuelve los segmentos . y .. y normaliza la codificación por porcentaje, siguiendo la sección 6 de la RFC 3986.
• Quita el fragmento, que nunca llega al servidor.
• Elimina con cuidado los parámetros de seguimiento conocidos, como utm_*; otros parámetros pueden cambiar el contenido.
• Respeta las indicaciones rel="canonical" tras la descarga.

Después, comprueba un conjunto de URL vistas. Con miles de millones de URL, un filtro de Bloom es la opción habitual. Dimensionado para mil millones de URL con un 1 % de falsos positivos, necesita unos 9,6 bits por URL, alrededor de 1,2 GB en total, con siete funciones hash. Un falso positivo significa saltarse una URL que en realidad no has visto, un coste aceptable al 1 % para la mayoría de los rastreos; mantén un almacén exacto para las URL que no te puedes perder, como las entradas de los sitemaps.

Deduplicar contenido

Los espejos, las versiones para imprimir y los parámetros de sesión producen páginas idénticas, o casi, bajo URL distintas. Los duplicados exactos son fáciles: aplica un hash al contenido normalizado y compara. Los casi duplicados necesitan una huella que cambie poco cuando la página cambia poco. Simhash es la técnica estándar: una huella de 64 bits en la que documentos parecidos difieren en pocos bits. Investigadores de Google informaron en 2007 de que, para un repositorio de ocho mil millones de páginas, las huellas simhash de 64 bits con un umbral de tres bits distintos eran un ajuste práctico para detectar casi duplicados.

Trampas para crawlers

Algunos sitios generan espacios de URL infinitos, a menudo sin querer: calendarios con un enlace «mes siguiente» sin fin, IDs de sesión en cada URL, búsquedas facetadas con todas las combinaciones de filtros y enlaces relativos que alargan una ruta sin parar. Defensas:

• Limita la longitud de las URL y la profundidad de las rutas.
• Limita las páginas por host y ciclo de rastreo, en proporción a la importancia del host.
• Detecta segmentos de ruta repetidos como /a/b/a/b/a/b.
• Baja la prioridad de las URL cuyas huellas de contenido siguen coincidiendo con páginas que ya tienes.

Los sitemaps ayudan en sentido contrario: enumeran las URL que un sitio quiere que se rastreen, hasta 50 000 URL o 50 MB sin comprimir por archivo de sitemap, con archivos de índice de sitemaps para más.

Alrededor del bucle: DNS, almacenamiento y re-rastreo

• El DNS es un cuello de botella oculto. Con cientos de descargas por segundo, un resolvedor con caché compartido cerca de los fetchers evita enviar cada consulta aguas arriba.
• Almacenamiento. Escribe las respuestas en bruto en el almacenamiento de objetos en grandes archivos por lotes, y envía el texto analizado y los enlaces hacia la indexación a través de un stream.
• Re-rastreo. Las páginas cambian a ritmos distintos. Registra con qué frecuencia cambió cada página en visitas anteriores y programa su siguiente descarga en consecuencia; las peticiones condicionales con If-Modified-Since o ETag ahorran ancho de banda cuando nada ha cambiado.
• Las páginas con mucho JavaScript necesitan un navegador headless, mucho más caro por página. Renderiza solo los hosts que lo necesitan.

El diagrama del crawler web

Cómo leerlo:

• El marco es la frontera de URL: las colas de prioridad alimentan las colas por host, que aplican la cortesía.
• Los fetchers toman una URL por host cada vez, consultan la caché de robots.txt y la caché DNS, y descargan de Internet.
• Las páginas en bruto van al almacén de objetos. El parser extrae enlaces y texto.
• Los enlaces nuevos pasan por el filtro de URL vistas antes de volver a la frontera, lo que cierra el bucle. Las huellas de contenido señalan los casi duplicados.
• Las páginas analizadas siguen hacia la indexación a través del stream de la derecha.
• El bloque Markdown enumera las cifras de capacidad y las reglas de cortesía.

Dibujar pipelines con bucles

• Haz visible el bucle. Un crawler es un ciclo; dibujarlo como un pipeline recto oculta la realimentación que causa los problemas de trampas y duplicados.
• Muestra dónde se aplica la cortesía. Pon las colas por host en el dibujo, no en una nota al pie.
• Marca las cachés como cachés. Las cachés de robots.txt y DNS cambian la carga sobre el mundo exterior; indica su caducidad.
• Pon cifras en las aristas: páginas por segundo que entran, enlaces por página que salen.

Para el método general, consulta el ejemplo de diagrama de diseño de sistemas. El control de tasa hacia cada host usa las mismas ideas que el diseño de un rate limiter, y el procesamiento posterior al rastreo se parece al diagrama de arquitectura de pipelines de datos.

Constrúyelo en Archboard

1. Inicia sesión con Google o GitHub y crea un diagrama.
2. Añade un Marco del pack Básico llamado URL frontier y coloca dentro dos nodos Cola del pack Datos: las colas de prioridad y las colas por host.
3. Añade un nodo Instancia de cómputo del pack Nube para los fetchers, un nodo DNS y un nodo Internet del pack Red, y un nodo Redis del pack Datos para la caché de robots.txt.
4. Añade un Almacén de objetos del pack Datos para las páginas en bruto y otro nodo Instancia de cómputo para el parser.
5. Añade un segundo nodo Redis para el filtro de URL vistas, una Base de datos administrada del pack Nube para las huellas de contenido y un nodo Kafka del pack Datos para las páginas que van a la indexación.
6. Dibuja el bucle con aristas etiquetadas y añade un bloque Markdown del pack Básico con las cifras.

El ejemplo usa 13 nodos de diagrama, dentro del plan Free.

Preguntas frecuentes

¿Qué es una frontera de URL? La estructura de datos que decide qué descarga un crawler a continuación. Combina colas de prioridad, que ordenan las URL por importancia, con colas por host y un calendario que impiden que el crawler contacte a un host con demasiada frecuencia.

¿Cómo se mantienen corteses los crawlers? Una conexión por host a la vez, un retardo entre peticiones que crece con el tiempo de respuesta del servidor, retroceder ante respuestas 429 y 503 y seguir robots.txt.

¿Qué pasa si robots.txt devuelve un error? Según la RFC 9309, un estado 4xx significa que el crawler puede rastrear el sitio, mientras que un estado 5xx o un error de red significa que debe suponer que todo está prohibido hasta que pueda leer el archivo.

¿Cómo evitan los crawlers descargar dos veces la misma página? Normalizan las URL y las comprueban contra un conjunto de URL vistas, a menudo un filtro de Bloom, y calculan huellas del contenido con hashes exactos y simhash para detectar la misma página bajo URL distintas.

¿Qué tamaño necesita un filtro de Bloom para mil millones de URL? Unos 1,2 GB para una tasa de falsos positivos del 1 %, usando alrededor de 9,6 bits por URL y siete funciones hash. Tasas de error más bajas cuestan más bits por entrada.

Empieza gratis — un puesto, sin tarjeta de crédito.