Crawler (Buscadores). La araña de internet

Este proyecto nos intenta explicar el concepto de Crawler, los problemas que resuelve y qué impedimentos existen tomando como referencia los artículos The Anatomy of a Large-Scale Hypertextual Web Search Engine (enlace), Efficient Crawling Through URL Ordering (Enlace), Mercator: A Scalable, Extensible Web Crawler (Enlace) y High-Performance Web Crawling(Enlace).

En este enlace a YouTube teneis una explicación en video sobre el proyecto.

1. Introducción: Qué es un crawler

Un crawler (rastreador) es un software destinado para la recuperación de Documentos Web, normalmente usados por los motores de búsqueda.

Este término adquiere especial relevancia cuando la WWW (World Wide Web) aumenta considerablemente de tamaño y, por lo tanto, utilizan estos software para responder los siguientes problemas a resolver:

Cantidad elevada de Documentos Web
Dinamismo de los Documentos
Continua expansión

Con la idea de evitar estos problemas, los buscadores han optimizado sus Rastreadores para proporcionar la información más correcta y adecuada. Para conseguirlo, cada motor ha realizado sus propios estudios y han aplicado algoritmos diversos con diferentes resultados.

En otro punto, el constante aumento de páginas y su dinamismo exigen utilizar rastreos más veloces, que devuelvan la información lo más comprimida posible y utilizando estructuras de datos eficientes.

El funcionamiento de un rastreador normalmente se basa en los siguientes procesos:

Obtener el conjunto inicial de URLs (Uniform Resource Locutor, Localizador Uniforme de Recursos)
Recolección de URLs . El rastreador se descarga este conjunto de documento web asociado (llamado "semilla") y busca dentro de esta otras URLs.
Cada nueva URL encontrada se añade a la lista de URLs que la araña Web debe visitar

Algunos ejemplos de Rastreados son:

Matthew Gray's Wanderer : Rastreador de páginas NCSA Mosaix( Navegador Gráfico de páginas web para Windows) creado en la primavera de 1993.
Google: es un motor de búsqueda en la web propiedad de Alphabet Inc. Sus principales características son:

Utilización de un índice eficiente.
Utilización de estructuras optimizadas.
Alto grado de escalabilidad

URLServer: proporciona las semillas de las URLs para ser extraídas por el software.
StoreServer: recibe las URLs,realiza unos cálculos de compresión y los almacena en un repositorio. Para analizar.
Indexador: Es la parte más importante del proceso. Se encarga de ejecutar una serie de algoritmos para leer la información del StoreServe, descomprimirla y analizarla. Los documentos son convertidos a conjuntos de palabras (llamados hits), estos, a su vez son subdivididos en otros conjuntos conocidos como barriles, y por último , estos barriles forman una estructura forward index parcialmente ordenada. Aparte de eso también se genera a partir de cada documento un fichero de anclaje, es decir, un documento donde está almacenado todos los enlaces que existen en la web y que texto enlazan.
URLresolver: Se encarga de analizar toda la información almacenada en los ficheros de anclaje. Una vez aplicado este proceso se puede obtener una estimación de relevancia aplicando el método PageRank.
Sprter se encarga de ordenar los barriles.

The Internet Archive: Sistema que distribuye las consultas entre diversas máquinas. Cada proceso de rastreo puede recibir hasta 64 peticiones y no puede enviar una petición a dos maquinas diferentes.
Mercator Crawler: Esté buscador es escalable, extensible y modular construido en JAVA. Con respecto al resto de los buscadores analizados, sus beneficios son la:

Eficiencia
Velocidad
Alta probabilidad de acierto
Modularidad

Web Fountain : Rastreador distribuido y modular desarrollado en el lenguaje C ++. Tiene una filosofía muy parecida al rastreador anterior pero, en esta ocasión, la estructura física es diversa. Siguen un patrón Maestro-Esclavo donde un servidor principal se encarga de coordinar una serie de máquinas. Sus algoritmos de indexación se basan en resoluciones de ecuaciones con programación no lineal.
Poly Bot: Rastreador que fusiona la eficiencia del C++ con la facilidad de modificación del Python. Este sistema se divide por tres tipos de servidores:

Responsable de Crawling
Descargadores de URLs.
Resolvedores de DNS.

WebRace: Es un módulo para el Crawler eRace implementado en Java. Su funcionamiento es un poco especial, ya que recibe peticiones de los usuarios para descargar páginas web, actuando el rastreador como un servidor inteligente. Es decir, no empezamos siempre con la misma semilla sino es cambiante dependiendo de la consulta de los usuarios. Una vez analizada, el software puede generar una estructura conocida como "suscripción", que solamente se actualizará cuando se produzca alguna modificación en la página.
Ubicrawler: Rastreador distribuido y tolerante a fallos creado en Java. La diferencia respecto al resto de ejemplos analizados es que , este rastreador se compone de un número de agentes idénticos que pueden realizar las mismas funciones. Para tratar una consulta, este rastreador procesa la petición y le aplica una función hash. El resultado obtenido le indica que agente debe procesar la consulta.Los beneficios que tiene utilizar una función hash es evitar que dos agentes traten una petición idéntica. Además si alguno de los agentes es detenido o tiene un problema el resto de ellos tienen la capacidad de redistribuirse su carga de trabajo.

2. Problemas que intenta resolver un crawler.

La finalidad que tiene un rastreador es buscar las URLs que poseen la información más exacta sobre una consulta realizada por un usuario.Por lo tanto, el principal problema que nos encontramos es seleccionar las páginas más relevantes y ordenarlas en función de la información que contienen. Para todo proceso de ordenación tendremos que empezar conociendo que métrica vamos utilizar para medir la relevancia de la página y , en el caso de los rastreadores, no existe un único método, sino se han desarrollado diferentes soluciones como:

Similitud a la consulta Q : Siendo P una web y Q una consulta, se convierten en vectores y se comparan su similitud en las palabras que contienen cada una.
Backlink Count: Analiza el número de enlaces que existen a la web P. A mayor número de enlaces, mejor posición.
PageRank: Algoritmo que calcula el ranking de una web utilizando diferentes parámetros como:

El número de enlaces que hay hacia la web
Número de enlaces q salientes que hay
Información que contiene la web

Forward Link Count: Número de enlaces que emanan de P
Location Metric: Mide la distancia al origen de la consulta. Para alguien que se encuentra en Chile, le interesará Webs que estén en América antes que estén en Europa por ejemplo.

Una vez hemos conocido qué métricas vamos aplicar en el rastreados, tendremos que analizar diferentes métodos de rastreo. El problema en este apartado no es el método elegido sino la gran cantidad de URLs que tendremos que analizar a diario y de forma eficiente. Las soluciones a este problema es utilizar métodos aproximados que se acerquen a un valor. Entre los métodos más actuales destacamos los siguientes tres:

Crawl & Stop: El rastreador C comienza por una página $P_{0}$ . Una vez procesada pasa a la siguiente hasta llegar a la última página almacenada. En este punto, un rastreador perfecto que tiene K paginas almacenadas debería visitar las páginas desde la primera $P_{0}$ a la $P_{k}$ para redistribuirlas de la siguiente forma $R_{1}$ a $R_{k}$ donde $R_{1}$ seria la pagina con la información más importante, $R_{2}$ la siguiente, y así sucesivamente.
Crawl & Stop with Threshold: Al igual que en el anterior método, visitamos una cantidad de K páginas. Sin embargo, ahora tendremos un punto importante G que utilizaremos para aplicar un algoritmo de la siguiente forma: Si consideramos I el algoritmo para medir la relevancia y P la página analizada entonces $I(P)^{3} \geq G$ es considerada como hot (relevante). Toda la páginas relevantes (hot) las denominaremos H (páginas que contienen información relevante para la búsqueda).
Aplicando toda esta información y considerando que el rastreador no tiene un tiempo ilimitado para realizar la tarea podemos definir que $P_{ST}(C)$ es el porcentaje de páginas H que han sido encontradas cuando el rastreador se para. Si K < H, entonces el rastreador ideal tendrá un rendimiento de (K*100)/H . En cambio, si K $g sergeq$ H, entonces será ideal y tendrá un rendimiento del cien por ciento.
Limited Buffer Crawl: En este modelo tenemos una consideración nueva, la capacidad de almacenamiento para el proceso es limitado. Asumimos que el rastreador solo puede guardar B páginas en su buffer. Por ello, cuando el rastreador se llene tendremos que aportar una solución entre las cuales estará:

Eliminar del buffer una pagina aleatoriamente (más rápido pero que puede bajar mucho la calidad de los resultados)
Eliminar las páginas más relevantes.

3. Problemas que se encuentra un crawler

Los crawlers tienen distintas necesidad para realizar el rastreo de las páginas web. Solucionar estos problemas es un verdadero dilema ya que entre una serie de problemas de distintos tipos, como por ejemplo la capacidad de almacenaje que poseen, el ancho de banda (tanto suyo, como de la web rastreada) relacionados con aspectos más hardware nos encontramos con otros problemas de software como son:

Alias de URL: Las URLs pueden transformarse para poseer seudo nombre que las hagan más amigables. Esta técnica también puede provocar serios problemas en nuestro navegador ya que pueden existir dos o más alias diferentes que apunten a la misma página. Existen cuatro casos que debemos analizar:

Alias en el dominio o nombre del servidor: Es muy frecuente que tengamos un servidor con una IP, en el cual tengamos alojadas distintas páginas Web con diferentes alias cada una de ellas. Cada una de estas Web utilizará la misma IP y , por lo tanto, el servidor como el rastreador se tendrán que comunicar de forma eficiente para no procesar varias veces una misma IP.
Omisión de número de puerto: Los protocolos normales de comunicación entre un cliente y el servidor web es de 80 para una conexión HTTP y 21 para una FTP. Dependiendo de nuestro rastreador y que tipo de conexiones va a realizar tendremos que configurarlo para realizar las consultas por el puerto adecuado.
Rutas alternativas en el mismo servidor: Hay casos que dos rutas diferentes accedan a un mismo espacio Web.Para esos casos nuestro rastreador solamente debería procesar la web una vez ignorando futuras peticiones procedentes de otras URL diferentes.
Réplicas en diferentes servidores: Los documentos Web más demandados seguramente serán replicados en diferentes servidores. En este caso, al igual que el anterior, deberemos comprobar que no analizamos dos veces el mismo documento.

IDs de sesión en las URLs: En muchas ocasiones, es necesaria la creación de sesiones para poder acceder a páginas dinámicas. Esto provoca que diferentes sesiones accedan a los mismos recursos y por lo tanto nuestros rastreador imite estos usuarios y analice documentos repetidos. La solución para este problema es implementar soluciones para detectar ficheros repetidos como el fingerprint de Mercator.
Crawler Traps: Una URL o conjunto de URLs que causan que el rastreador esté rastreando indefinidamente. Algunos crawler traps se dividen como:

Involuntarios: Un enlace simbólico en un sistema de ficheros que crea un ciclo.
Voluntarios Spammers que muestran publicidad de forma cíclica.

4. Etapas del crawling

Para responder la consulta que realice un usuario es necesario pasar por diferentes etapas con sus respectivas funciones. El orden y los métodos no siempre serán las mismas, dependiendo de la implementación y el hardware utilizado el rastreador puede tener pequeñas modificaciones para mejorar su eficiencia.

4.1 Google

Si nos centramos en los rastreadores más grandes como Google nos enfrentamos a software que interactúan con una cantidad gigante de páginas y han optado por un sistema distribuido. Su funcionamiento es el siguiente; poseen un único servidor URLServer que sirve las URLs a un número de rastreadores. Aparte cada uno de ellos, mantiene su propia caché para evitar hacer una búsqueda de DNS antes de rastrear cada documento.Un crawler puede recibir hasta 300 conexiones abiertas al mismo tiempo, es decir,Google puede obtener aproximadamente 100 páginas cada segundo usando 4 rastreadores, es decir, una media de 600 Kbits/s. Respecto a las conexiones, no tienen que estar todas en el mismo estado. Siempre habrán conexiones conectando a un servidor, enviado una solicitud, recibiendo una respuesta y resolviendo el alias.Todas estas características hacen que el rastreador un componente muy complejo, con un sistema de I/O (Entrada/Salida) asíncrono para gestionar eventos y un número de colas para mover páginas de un estado a otro.

4.2 WebBase

Otro tipo de rastreador diferente es WebBase. Este software se basa en ejecutar muchos procesos al mismo tiempo para realizar un rastreo. Cada proceso recibe una lista de URLs para ser descargadas y simplemente devuelven el contenido completo de HTML o un error si no lo consiguen. Para ejecutar este sistema se abre cientos de conexiones al mismo tiempo, a una velocidad de unas 25 páginas por segundo por cada proceso.También está adaptado para rastreos en servidores que tienen una velocidad bastante lenta y permiten descargar poca información rápidamente. En esos casos primero, se dividen todas las URLs que van a ser rastreadas en 500 colas basadas en un hash del servidor donde está alojada. Con esto se consigue que todas las URLs que pertenecen a un mismo servidor se encuentren en una misma cola y , por lo tanto, un servidor con retardo solamente disminuirá la eficiencia en una de las conexiones. Aparte de este método, el sistema permite al webmaster la capacidad de restringir el acceso de este rastreador.

4.3 Mercator

Otro ejemplo de rastreador es Mercator. Este software tiene múltiples hilos de trabajo cuando se produce un rastreo. Cada hilo se repite tantas veces necesite para poder realizar el trabajo.

El primer paso de un rastreador Mercator es obtener una URL absoluta del URLFrontier. Para realizar esta tarea primero de todo tiene que identificar el protocolo de red que debe ser utilizado para descargarla. En un principio el software solamente incluye la configuración por defecto para los protocolos HTTP, FTP y Gopher (servicio de Internet consistente en el acceso a la información a través de menús) y, si tenemos la necesidad de rastrear nuevos protocolos se introducen en un fichero de configuración y son dinámicamente cargados al comenzar con el rastreo
Después del paso 1 y tener seleccionado el protocolo correcto para la descarga, el siguiente paso es ejecutar el módulo de ejecución para descargar el documento de internet en un hilo RewindInputStream (RIS, método E/S que dada una entrada de flujo permite obtener y almacenar el contenido referenciado por la entrada para ser leído posteriormente tantas veces como sea necesario).
Una vez que el documento ha sido escrito en el RIS, el hilo que trabaja, ejecuta el test de contenido-visto para determinar si este documento ha sido visto anteriormente.
Si es así , el documento no es procesado otra vez y el hilo borra la URL del URLFrontlier. Todos los documentos descargados, tienen asociados un MIME TYPE (Multipurpose Internet Mail Extensions, son una serie de convenciones o especificaciones dirigidas al intercambio a través de Internet de todo tipo de archivos (texto, audio, vídeo, etc.) de forma transparente para el usuario). Este proceso de asociar al documento un MIME se basa en el fichero de configuración de Mercator y puede ser modificado para asociar uno o otro tipo de estructura MIME.
Después de descargar el fichero y asociar el MIME, se selecciona el módulo que debe procesarlo. Un ejemplo sería el Extractor de Enlaces y el contador de Etiquetas que son utilizados para documentos de tipo text/html.
Cada enlace es convertido en una URL Absoluta y pasada por un filtro URLFilter para determinar si debe ser descargada.
Si la URL es aceptada, pasa por el módulo de prueba de contenido-visto, que comprueba si la URL ha sido descargada anteriormente.

4.4 WebEater

Un rastreador WebEater mide la relevancia de cada página con respecto a un tema o búsqueda que el usuario realice. Por supuesto, se considera relevante toda la página que contiene la palabra buscada en el título y se añade a una ColaClave. Los resultados positivos que no esta en el título se almacena en ColaURL. Por supuesto, se analizará primero aquellas añadidas en las ColaClave.

5. Qué otras áreas de investigación están relacionadas con el Crawling

El área de investigación más ligada a los Crawling es los motores de búsqueda aunque también está muy relacionado con la Minería de Datos y la Recuperación de Información.

No obstante, basándonos en la bibliografía consultada sobre los crawlers, teniendo en cuenta las distintas tareas que se deben realizar, también lo podemos relacionar de forma secundaria con:

Servidores de nombres DNS: Las mejoras que aportemos en estas tecnologías afectarían directamente a los Crawlers ya que son un paso importante en sus tareas.
Indexación web. Un aumento en la eficiencia de los índices puede suponer una disminución en los tiempos de ejecución de las diversas consultas.
Extractores de enlaces de documentos WEB

6. Qué otras áreas de investigación están relacionadas con el Crawling

El área de investigación más ligada a los Crawling es los motores de búsqueda aunque también está muy relacionado con la Minería de Datos y la Recuperación de Información.

No obstante, basándonos en la bibliografía consultada sobre los crawlers, teniendo en cuenta las distintas tareas que se deben realizar, también lo podemos relacionar de forma secundaria con:

Servidores de nombres DNS: Las mejoras que aportemos en estas tecnologías afectarían directamente a los Crawlers ya que son un paso importante en sus tareas.
Indexación web. Un aumento en la eficiencia de los índices puede suponer una disminución en los tiempos de ejecución de las diversas consultas.
Extractores de enlaces de documentos WEB