Como funciona Google

Siendo largamente tanto en tamaño como en calidad de resultados el mejor buscador de la red es hora de analizar como funciona Google. En esta nota analizamos el funcionamiento del motor, algoritmos y estructuras de datos utilizadas.

Como funciona Google
Richie Adler
Corregido por Ricardo Galli

Anatomia del sistema

En la siguiente figura se muestra un esquema general de la arquitectura del sistema:

Descripcion general

El motor de indexación de Google esta implementado en C/C++ por razones de eficiencia y puede correr tanto sobre Solaris como sobre Linux. En Google, el proceso de exploración (descargar las páginas a indexar) es realizado por varios exploradores distribuidos. Existe un proceso URLserver que envía listas de URLs a ser descargados a los exploradores. Las páginas que son descargadas son enviadas luego al storeserver. El storeserver comprime y guarda las páginas en un repositorio. Toda página tiene asociado un ID denominado docID que es asignado cada vez que un nuevo URL es interpretado desde una página. La función de indexación es llevada a cabo por un proceso indexador y un clasificador. El indexador lleva a cabo varias funciones: Lee el repositorio, descomprime los documentos y los interpreta, cada documento es convertido en un conjunto de ocurrencias de palabras llamadas hits o aciertos. Cada acierto registra la palabra, posición en el documento y una aproximación del tamaño de la fuente y si está o no en mayúsculas. El indexador distribuye estos aciertos en una serie de “barriles” (barrels) creando un índice. Además, el indexador interpreta todos los enlaces en cada página y guarda información importante sobre los mismos en un archivo llamado anchors, este archivo contiene información suficiente sobre origen y el destino del enlace, y cual es el texto del mismo.

El URLresolver lee registros del archivo de enlaces y convierte URLs relativos en URLs absolutos (por ejemplo si el enlace es desde http://foo.bar/index.htm hacia images/bar.gif el URL absoluto es http://foo.bar/images/bar.gif). Luego convierte los URLs absolutos en docIDs. Pasa el texto del enlace al índice y los asocia con el docID apuntado por el enlace. También genera una base de enlaces que son simplemente pares de docIDs de la forma “desde-hasta”. La base de enlaces es luego usada por el algoritmo de PageRanking para determinar la importancia de cada documento.

El proceso clasificador toma los barrels que están ordenados por docId y los reordena por wordID para generar un índice invertido. Esto es realizado en el mismo lugar para ahorrar espacio auxiliar. El clasificador produce también una lista de wordIDs y desplazamientos al índice invertido. Un programa denominado DumpLexicon toma la lista junto con el léxico producido por el indexador y genera un nuevo léxico para ser usado por el buscador. El buscador es invocado por el servidor web y usa el léxico construido por DumpLexicon junto con el índice invertido y los PageRanks para resolver las búsquedas.

Estructuras de datos

Las estructuras de datos de Google están optimizadas de forma tal que enormes colecciones de documentos puedan ser exploradas, indexadas y buscadas con poco o casi ningún costo.

BigFiles

Un BigFile es un archivo que puede ocupar varios sistemas de ficheros y que se puede direccionar por un desplazamiento de 64 bits, la distribución del archivo en múltiples sistemas de ficheros es manejada automáticamente por la biblioteca de Bigfiles. La biblioteca da al programador una interfaz abstracta que permite manejar los BigFiles como si fueran archivos comunes encargándose de todo el proceso interno necesario para almacenar archivos inmensos.

Repositorio

El repositorio contiene el HTML completo de cada página. Cada página es comprimida usando Zlib. En el repositorio, los documentos se almacenan comprimidos uno a continuación del otro en un archivo secuencial simple y esta prefijados por el docId, longitud y URL como puede verse en la figura 2. El repositorio no requiere otras estructuras para ser usado y accedido. Esto ayuda a darle consistencia al sistema ya que todo el motor de Google y toda la base pueden reconstruirse únicamente a partir del repositorio. Así mismo, el repositorio permite que toda página devuelta por el buscador luego de una consulta pueda ser mostrada al usuario aunque ya no esté disponible en línea. Esto se logra con la opción cached-page del buscador, sumamente útil para sitios antiguos que ya no están, o fueron actualizados, o incluso para los que están fuera de línea en el momento de hacer la consulta.

Document Index

El document index guarda información sobre cada documento. Es un archivo secuencial indexado ISAM ordenado por docID. La información almacenada en cada entrada incluye el estado del documento, una referencia al documento dentro del repositorio, un checksum y varias estadísticas. Si el documento que ha sido explorado contiene también un puntero a un archivo de tamaño variable llamado docinfo que contiene el URL y el título del documento. En el caso contrario, el puntero apunta al URLlist que contiene sólo el URL. Adicionalmente, existe un archivo que es usado para traducir URLs en docIDs, es una lista de URL checksums con sus correspondientes docIds y está ordenada por checksum. Para encontrar el docId de un URL especifico se calcula el checksum del URL y luego se hace una búsqueda binaria dentro de este archivo para encontrar el docID que corresponda al checksum. Los URLs puede ser convertidos en docIDs en lotes haciendo un refundido con este archivo. Esta técnica es usada por el URLresolver para convertir URLs en docIDs. Este modo lotes de actualización es crucial en cuanto a la eficiencia del sistema.

Lexico

El léxico tiene varios formatos diferentes. Un cambio importante es que el léxico puede manejarse en memoria a un precio razonable. El léxico consta de 14 millones de palabras y esta implementado en 2 partes. Una lista de palabras concatenadas entre sí y separadas por NULLs, Y una tabla de hash (dispersión) de punteros. Para varias funciones adicionales, la lista de palabras tiene alguna información auxiliar que esta mas allá del nivel de explicación de este informe.

Hit Lists

Las hit lists (lista de aciertos) es una lista con las ocurrencias de una determinada palabra en un documento en particular incluyendo la posición, fuente y si está o no en mayúsculas. Las hit lists ocupan la mayoría del espacio necesario para los índices, por tal razón deben almacenarse en forma eficiente. Los detalles de codificación de las hit lists se muestran en la siguiente figura:

Este formato de codificación usa dos bytes por cada hit. Hay dos tipos de hits, fancy-hits y plain-hits. Fancy-hits son aquellos que ocurren dentro de una URL, titulo, anchor o meta-tag. Plain-hits son todos los demás. Un plain-hit consiste en un bit que indica si la palabra esta en mayúsculas o minúsculas, tamaño de la fuente y 12 bits para la posición de la palabra en el documento. Todas las posiciones mayores a 4095 se rotulan 4096. El tamaño de la fuente se representa en forma relativa al resto del documento usando 3 bits. Solo 3 valores se usan porque 111 representa un fancy-hit. Un fancy-hit almacena el bit de mayúsculas/minúsculas, el tamaño de la fuente fijada en 111, 4 bits para indicar el tipo de fancy-hit y 8 bits para la posición del mismo. Para enlaces, los 8 bits de posición se separan en 4 bits de posición dentro del texto del anchor y 4 bits para un clave (hash) del docId del documento en el cual esta el enlace.

La longitud de cada hit-list es alamcenada antes de la lista misma.

El índice

El índice sin invertir está en realidad parcialmente ordenado. Está distribuido en barrels (se usan 64 barrels). Cada barrel guarda un rango de wordIDs. Si un documento contiene palabras que corresponden a un determinado barrel, los docIds son registrados en el barrel seguidos de una lista de wordIDs con hit-lists que corresponden a dichas palabras. Este esquema requiere un poco mas de espacio al duplicar los docIDs, pero la diferencia es muy chica por un numero razonable de buckets y salva mucho tiempo y complejidad de programación en la fase final de indexación.

El índice invertido

El índice invertido consiste en los mismos barrels que el índice pero ya procesado por el clasificador. Para cada wordId válido, el léxico contiene un puntero al barrel correspondiente a la palabra. El puntero apunta a una lista de docIDs junto con sus correspondientes hit-lists. Esta lista representa las ocurrencias de la palabra en todos los documentos indexados.

Procesos

Exploración (crawling)

Ejecutar los web exploradores es un proceso complejo. Hay asuntos altamente intrincados referidos al rendimiento y confiabilidad de los procesos y hasta existen problemas sociales involucrados. El proceso de exploración es sin dudas la más frágil de las aplicaciones ya que implica interactuar con cientos de miles de servidores web y servidores de nombre que están mas allá del campo de control del sistema. Para escalar a miles de millones de páginas, Google usa un sistema veloz de exploración distribuido. Un solo URLserver sirve listas de URLs a un numero de exploradores (típicamente 3). Tanto el URLserver como los exploradores están implementados en Python. Cada explorador abre unas 300 conexiones HTTP simultáneamente, esto es necesario para poder bajar páginas a un ritmo razonable. En momentos pico el sistema puede descargar 100 páginas por segundo usando 4 exploradores. Esto implica unos 600KBytes por segundo de datos. Un punto mayor de estrés es el DNS lookup, cada explorador mantiene su propio cache de DNS de forma tal de no tener que hacer un DNS lookup antes de explorar cada documento. Cada una de las cientos de conexiones puede estar en un determinado estado: looking up DNS, conectándose al servidor, enviando solicitud o recibiendo respuesta. Estos factores hacen del explorador un componente complejo en el sistema. Se usa IO asincrónica para manejar eventos y un numero de colas para mover las URLs solicitados de un estado a otro.

Los exploradores utilizados por Google respetan estrictamente el protocolo “robots.txt” para exclusión de robots en algunos sitios y, además, esperan 1 segundo entre conexión y conexión para un mismo servidor web de forma tal de no alterar significativamente el rendimiento de los mismos.

Indexación

Lo primero necesario para indexar páginas web es interpretarlas. El proceso de interpretación debe contemplar un gran, enorme, numero de posibles errores que varían desde errores en etiquetas HTML, miles de ceros en medio de un tag, caracteres no-ASCII, etiquetas mal anidadas y no cerradas, etiquetas anidados en forma casi infinita y gran variedad de otros errores. Para maximizar la velocidad Google usa flex para generar un analizador léxico que se alimenta con su propia pila. El desarrollo de este intérprete, que debe correr a una velocidad razonable y ser muy robusto, involucra gran cantidad de trabajo. Una vez interpretado cada documento es codificado en los barrels. Cada palabra es convertida en un Word-Id usando una tabla de hashing mantenida en memoria, o sea, el léxico. Nuevos agregados a la tabla de hashing del léxico son registrados en un archivo. Una vez que las palabras son convertidas en wordIDs sus ocurrencias en el documento son traducidas a hit-lists y son almacenadas en los barrels. La mayor dificultad con la paralelización de la fase de indexado es que el léxico debe compartirse. En lugar de compartir el léxico, Google escribe un registro de todas las palabras extras que no están en el léxico base que se fijó en 14 millones de palabras. De esta forma múltiples indexadores pueden ejecutarse en paralelo y luego el archivo de registro puede ser procesado por el último indexador.

Para generar el índice invertido, el indexador toma cada uno de los barrels ordenándolo por wordID para producir un barrel invertido. El proceso de ordenamiento también es paralelizado para usar tantas máquinas como se pueda simplemente corriendo múltiples ordenadores que pueden procesar diferentes buckets al mismo tiempo. Dado que los barrels no caben en memoria, el clasificador los subdivide en baskets ordenando cada basket en memoria y volcando el contenido combinado al barrel.

Búsqueda (Searching)

El objetivo del proceso de búsqueda es proveer una búsqueda de calidad y eficiente. Muchos de los grandes buscadores comerciales han hecho grandes progresos en cuanto a la eficiencia, por lo que Google se ha concentrado en proveer calidad en los resultados. El proceso de consultas de Google involucra 4 pasos: interpretar la consulta, convertir palabras en wordIDs, buscar el principio de la doclist en el barrel que corresponde a cada palabra. Buscar en los doclists hasta que se encuentre un documento que contiene todos los términos buscados y finalmente computar el orden (ranking) correspondiente de cada documento.

El sistema de ranking

Para ordenar documentos (decidir su importancia respecto de una consulta) Google utiliza un algoritmo propio denominado PageRank. El algoritmo de PageRank está basado en el grafo de enlaces de la web que como tal es un recurso sumamente importante y largamente ignorado en la mayoría de los buscadores. Google dispone de tablas con miles de millones de enlaces de la forma (docID desde-docID hasta), lo cual constituye una buena representación de la web como un grafo de enlaces.

El concepto básico del algoritmo PageRank es que una página es más importante en la medida en que mas páginas apuntan hacia ella. El algoritmo de PageRank extiende este concepto computando no solamente la cantidad de enlaces, sino también normalizando de acuerdo a la cantidad de enlaces en una página, y propagando infinitamente de forma tal que la importancia de una página depende de: cuantas páginas apuntan a ella, de la cantidad de enlaces en estas páginas, y de cuantas y que tan importantes son las páginas que apuntan a las que apuntan a la página. El algoritmo se resume así:

Asumimos que una página “A” tiene páginas T1..Tn que la apuntan. El parámetro d es un parámetro probabilístico que vale entre 0 y 1. Google usa d=0.85. Se define C(A) como la cantidad de enlaces que salen de la página (A). El PageRank de A se calcula como PR(A)=(1-d)+d(PR(T1)/C(T1)+ … + PR(Tn)/C(Tn))

Notar que los PageRanks forman una distribución probabilística sobre las páginas, la suma de los PageRanks de todas las páginas da 1. El PageRank de una página puede calcularse usando un simple algoritmo iterativo, el PageRank de 26 millones de páginas se puede calcular en pocas horas en una maquina modesta. Dadas n páginas se comienza con PR(Ai)=1/n y luego simplemente se corren x pasadas del algoritmo que calcula el PageRank de cada página hasta que los valores se estabilizan, esta es una técnica comúnmente usada en algoritmia para simplificar algoritmos recursivos.

Justificación intuitiva

El método de PageRank puede verse como un modelo del comportamiento del usuario. Supongamos que tenemos a un navegador aleatorio (random surfer) que dada una página aleatoria elige enlaces y clickea sin usar el botón back, pero eventualmente se aburre y comienza desde otra página aleatoria. ¡La probabilidad de que el visitante llegue a una página es su PageRank!. Y el valor d es la probabilidad de que en una página dada el visitante se aburra y empiece de nuevo desde otra página.

Conclusiones

Google esta diseñado para ser una herramienta de búsqueda escalable eficiente y con un sistema altamente avanzado de ranking de páginas. El uso del algoritmo de PageRank le da una gran calidad a los resultados de búsquedas “comunes”, la enorme cantidad de datos, de lejos la colección mas grande de páginas web del mundo, le permiten resolver eficazmente búsquedas “difíciles” mientras que el repositorio de páginas asegura que los resultados devueltos pueden ser accedidos y consultados por el usuario siendo a su vez de enorme valor como una colección histórica de los documentos en la web.