Google: Cómo funciona por dentro
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: Sus funciones son leer el repositorio, descomprimir los documentos e interpretarlos
- Pasos:
- 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
almacenes (barrels) creando un índice.
- También interpreta todos los enlaces en cada página y guarda información importante sobre los mismos en un archivo llamado anchors, que 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, y éstos a su vez en docIDs.
- Pasa el texto del enlace al índice y los asocia con el docID apuntado por el enlace.
- 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.
- Pasos:
- El clasificador
- Pasos:
- 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.
- 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
- Pasos:
Estructuras de datos
Las estructuras de datos están optimizadas para poder realizar las búsquedas y recuperar documentos rápidamente.
- El repositorio: Contiene el HTML completo de cada página comprimido con zlib. Previo al contenido se almacena también el docId, la longitud y la URL. Todas las páginas están alamacenadas de manera secuencial, permitiendo generar todos los índices (si hiciera falta) a partir del repositorio. El de Google ocupa más o menos 54 Gb. comprimido (ahora un 66% de espacio).
- El índice de documentos: Contiene información sobre cada página. Es un archivo secuencial ordenado por docId. Almacena el estado del documento y una serie de estadísticas sobre él.
- El léxico: Lista de palabras que se manejan (aproximadamente 14 millones). Se emplea una lista secuencial y una tabla hash de apoyo.
- Listas de hits: 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.
- Índice sin invertir: Está en realidad parcialmente ordenado y distribuido en barrels (se usan 64 barrels). Cada barrel guarda un rango de wordIDs.
- Í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.
![[Recuperacion Organizacion Informacion. Valid RSS1.0]](img/valid-rss1.png "Recuperacion Organizacion Informacion Validate my RSS feed")
![[Recuperacion Organizacion Informacion.Valid RSS2.0]](./img/valid-rss2.png "Recuperacion Organizacion Informacion Validate my RSS feed")