Como funciona google

Como funciona Google
* Google
* Reviews
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. Esta es una edicion revisada del articulo corregida por Ricardo Galli a quien le agradecemos enormemente
Comofunciona Google
Richie Adler (Exclusivo de Maldita Internet)
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 esinterpretado 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óndel 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 delmismo.
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 deenlaces 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 clasificadorproduce 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 esmanejada 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...