[2009 WSDM] Desafíos en la construcción de sistemas de recuperación de información a gran escala

Dimensiones principales y trade-offs de un sistema de recuperación de información

• Al diseñar un sistema, es necesario considerar de forma equilibrada los trade-offs de ingeniería entre factores como los siguientes.
  • Cantidad de documentos indexados
  • Cantidad de consultas procesadas por segundo (QPS)
  • Frescura del índice / velocidad de actualización
  • Latencia de consulta
  • Cantidad de información almacenada por documento
  • Complejidad/costo del cálculo de puntaje y de los algoritmos de búsqueda
• La dificultad de ingeniería tiende a ser proporcional al producto de estos parámetros.
• Todos estos factores afectan tanto el rendimiento total como la relación rendimiento/costo (rendimiento por dólar).

Cambios en la escala del sistema (1999 vs 2009)

• Durante los últimos 10 años, la escala del sistema y los requisitos de rendimiento cambiaron de forma drástica.
  • # documentos: ~70 millones → varios miles de millones (~100 veces más)
  • consultas procesadas por día: (~1000 veces más)
  • información indexada por documento: (~3 veces más)
  • latencia de actualización: de varios meses → varios minutos (~10000 veces menos)
  • latencia promedio de consulta: <1 segundo → <0.2 segundos (~5 veces menos)
  • recursos del sistema: más máquinas * máquinas más rápidas (~1000 veces más)
• Como estos parámetros cambian constantemente, a veces por varios órdenes de magnitud, el diseño del sistema debe evolucionar sin pausa.
  • Un diseño adecuado para un momento específico (X) puede ser una muy mala decisión a una escala 10 o 100 veces mayor. (Por eso conviene diseñar pensando en un crecimiento de alrededor de 10 veces, pero planear una reescritura antes de llegar a 100 veces)
  • Hubo 7 renovaciones importantes en los últimos 10 años.

Arquitectura inicial del sistema (1997-1999)

• Etapa de proyecto de investigación (1997):
  • El servidor web frontend recibía consultas y distribuía solicitudes de procesamiento a servidores de índice y servidores de documentos
  • Servidores de índice: sharding basado en ID de documento (docid)
  • Servidores de documentos: sharding basado en ID de documento (docid)
• Principios básicos:
  • A los documentos se les asignaban IDs enteros (docids) (los documentos importantes o de alta calidad recibían IDs pequeños)
  • Servidor de índice: (consulta) → devuelve una lista ordenada de (puntaje, docid, ...). Sharding por docid, con replicación para asegurar capacidad. Costo O(#consultas * #documentos en el índice).
  • Servidor de documentos: (docid, consulta) → genera (título, snippet). Mapea docid → texto completo del documento en disco. Sharding por docid. Costo O(#consultas).
• Sistema de serving (1999):
  • A la estructura del proyecto de investigación se le agregaron servidores de caché e integración con el sistema de anuncios
  • Operación con réplicas de shards de servidores de índice/documentos
  • Caché: se almacenaban en caché tanto los resultados del índice como los snippets de documentos. Tasa de aciertos de caché de 30-60%. Gran contribución a la mejora del rendimiento y a la reducción de la latencia de consulta. (Sin embargo, había que tener cuidado con grandes picos de latencia al actualizar el índice o vaciar la caché)

Estrategias de particionamiento del índice

• Por documento (By doc): cada shard tiene el índice de una parte de los documentos (opción elegida por Google)
  • Ventajas: procesamiento de consultas independiente por shard, fácil mantenimiento de información adicional por documento, poco tráfico de red (solicitudes/respuestas)
  • Desventajas: todos los shards deben procesar la consulta, y para una consulta de K palabras se requieren búsquedas en disco O(K*N) en N shards
• Por palabra (By word): cada shard tiene el índice de una parte de las palabras para el conjunto completo de documentos
  • Ventajas: una consulta de K palabras es procesada por como máximo K shards, con O(K) búsquedas en disco
  • Desventajas: requiere mucho más ancho de banda de red (hay que reunir en un solo lugar la información por palabra de los documentos coincidentes), y es difícil mantener información por documento

Crawling e indexación iniciales (1998-1999)

• Crawling:
  • Sistema simple de crawling por lotes: lista inicial de URL → crawling de páginas → extracción de enlaces y agregación a la cola → detenerse al recolectar suficientes páginas
  • Consideraciones: evitar sobrecargar sitios específicos, decidir la prioridad de páginas no rastreadas (por ejemplo, PageRank), administrar de forma eficiente la cola de URL no rastreadas, manejar fallas de máquinas
• Indexación:
  • Sistema simple de indexación por lotes, basado en herramientas Unix sencillas
  • Problemas: ausencia de checkpointing, lo que hacía muy dolorosas las fallas de máquinas; ausencia de checksums de los datos fuente, lo que causaba problemas por errores de bits de hardware (agravados por las primeras máquinas sin ECC/paridad, problema de “mayormente ordenado”); experiencia de “memoria y programación hostiles”
  • Solución: desarrollo de una abstracción de archivos capaz de almacenar checksums de registros pequeños y omitir/re-sincronizar registros dañados

Método de actualización del índice (1998-1999)

• Frecuencia: aproximadamente una vez al mes
• Proceso:
  1. Esperar hasta una franja horaria de poco tráfico
  2. Poner algunas réplicas fuera de línea
  3. Copiar el nuevo índice a las réplicas fuera de línea
  4. Iniciar un nuevo frontend que apunte al índice actualizado y dirigirle parte del tráfico
• Estrategia de uso del disco en los servidores de índice:
  • La parte exterior del disco ofrece mayor ancho de banda
  1. (Mientras el índice existente sigue en servicio) copiar el nuevo índice a la mitad interior del disco
  2. Reiniciar para usar el nuevo índice
  3. Eliminar el índice anterior
  4. Volver a copiar el nuevo índice a la mitad exterior, más rápida
  5. Eliminar la primera copia del nuevo índice que estaba en la parte interior
  6. Usar el espacio interior liberado para estructuras de datos orientadas a mejorar el rendimiento (por ejemplo, Pair cache: precomputar el resultado de la intersección de posting lists para pares de términos de consulta que aparecen con frecuencia juntos)

Respuesta al crecimiento y escalado (1999-2001)

• En '99, '00 y '01 crecieron bruscamente el tamaño del índice y el tráfico (~50 millones → más de 1,000 millones de páginas, crecimiento de tráfico mensual del 20% + duplicación del tráfico de un día para otro por la alianza con Yahoo, etc.)
• El rendimiento de los servidores de índice se volvió crítico: fue necesario seguir agregando máquinas y mejorar el rendimiento por software entre 10% y 30% cada mes
• Forma de escalado: agregar más shards y más réplicas
• Implicaciones:
  • El tiempo de respuesta de los shards depende de la cantidad de búsquedas en disco y del volumen de datos que hay que leer
  • Áreas para mejorar el rendimiento: mejor scheduling de disco, mejor codificación del índice

Evolución de las técnicas de codificación del índice

• Codificación inicial ('97): formato muy simple alineado por bytes (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). Un hit es posición + atributos (tamaño de fuente, título, etc.). Se agregaron skip tables para posting lists grandes. La decodificación era barata, pero la compresión era baja y requería mucho ancho de banda de disco.
• Diversas técnicas de codificación:
  • A nivel de bits: Unary, Gamma, Rice_k (caso especial del código Golomb), Huffman-Int
  • Alineadas por bytes: varint (7 bits por byte + bit de continuación)
• Formato de índice basado en bloques: reduce tanto espacio como uso de CPU (~30% menos tamaño), y mejora la velocidad de decodificación. Usa bloques de longitud variable. Encabezado (delta, longitud, etc.) + deltas de ID de documento (Rice_k) + cantidad de hits (Gamma) + atributos de hit (run-length Huffman) + posiciones de hit (Huffman-Int).
• Nuevo formato de índice (desde 2004): usa un único espacio plano de posiciones. Estructuras auxiliares rastrean los límites de documento. Las posting lists son listas de posiciones codificadas por delta. Son importantes tanto la compacidad como la altísima velocidad de decodificación.

Sistema de índice en memoria (principios de 2001)

• Contexto: al aumentar el sharding y las réplicas, ya era posible contar con suficiente memoria total para mantener una copia completa del índice en memoria
• Arquitectura: frontend → balanceador de carga (bal) → shard (varias réplicas de servidores de índice en memoria por shard)
• Ventajas: gran aumento del throughput y fuerte reducción de la latencia (en especial para consultas complejas que antes requerían I/O en disco de gigabytes; por ejemplo, “circle of life”)
• Problemas:
  • Varianza (Variance): se pasó de usar decenas a miles de máquinas, lo que hizo más difícil la previsibilidad (por ejemplo, tareas cron aleatorias que causaban problemas)
  • Disponibilidad (Availability): cada dato de índice de documento tenía una o pocas réplicas, lo que podía provocar “consultas de la muerte” (caída simultánea de todos los backends) y problemas de disponibilidad del índice cuando fallaban máquinas (especialmente para documentos importantes, que debían replicarse)

Diseño y tecnologías del sistema posterior (desde 2004)

• Hardware: centros de datos de mayor escala, racks de diseño propio, motherboards de clase PC, hardware económico de almacenamiento y red, Linux + software desarrollado internamente
• Diseño de serving (edición 2004): estructura jerárquica
  • Servidor Root → servidores Parent → servidores Leaf (los Repository Shards se cargan desde GFS mediante File Loader)
  • Integración con servidores de caché

Codificación Group Varint

• Idea: resolver la ineficiencia de la decodificación de Varint (muchas operaciones de branch/shift/mask). Codifica grupos de 4 valores enteros en 5 a 17 bytes.
• Método:
  • Se toman 4 etiquetas de 2 bits que indican la longitud en bytes de cada valor (1 a 4 bytes) y se combinan en un byte de prefijo
  • Después del byte de prefijo se almacenan los bytes reales de los datos
• Decodificación: se lee el byte de prefijo y se usa como índice para consultar una tabla precalculada de 256 entradas → se obtienen offsets e información de máscaras para decodificar los 4 valores de una sola vez
• Rendimiento: mucho más rápido que el método anterior (Group Varint: ~400M/seg, 7-bit Varint: ~180M/seg, 30-bit Varint w/ 2-bit len: ~240M/seg)

Búsqueda universal (2007)

• Sistema que no solo muestra resultados de búsqueda web, sino que integra y presenta distintos tipos de información (imágenes, información local, noticias, video, blogs, libros, etc.).
• Un nodo Super root envía consultas a varios sistemas de búsqueda especializados (motores de búsqueda verticales) y agrega los resultados.

Desafíos del crawling y la indexación de baja latencia

• Reflejar actualizaciones en cuestión de minutos es un desafío muy difícil.
• Heurísticas de crawling: ¿qué páginas conviene rastrear?
• Sistema de crawling: hay que rastrear páginas rápidamente
• Sistema de indexación: depende de datos globales como PageRank y anchor text → se requieren aproximaciones online en tiempo real
• Sistema de serving: debe estar preparado para aceptar actualizaciones mientras procesa consultas (lo que exige estructuras de datos muy distintas de las de un sistema de actualización por lotes)

Importancia de la experimentación y de la infraestructura

• Facilidad para experimentar: muy importante (ciclos rápidos de experimentación → más experimentos → más mejoras)
• Tipos de experimentos:
  • Experimentos fáciles: ajustar pesos de datos existentes, etc.
  • Experimentos difíciles: requieren nuevos datos que no están en el índice de producción. (Debe ser fácil generar/integrar esos datos y usarlos en experimentos)
• Infraestructura clave:
  • GFS: sistema de archivos distribuido a gran escala
  • MapReduce: permite escribir/ejecutar fácilmente tareas de procesamiento de datos a gran escala. (Acelera la generación de datos del índice de producción y permite experimentos temporales rápidos)
  • BigTable: sistema de almacenamiento semi-estructurado. (Permite acceso online y eficiente a información por documento, y que varios procesos actualicen de forma asíncrona información de documentos, algo clave para pasar de actualizaciones por horas a actualizaciones por minutos)

Ciclo de experimentación y lanzamiento

1. Diseño de ideas y experimentos offline:
   • Generación de datos con MapReduce, BigTable, etc.
   • Ejecución de experimentos offline y validación del efecto (conjuntos de consultas evaluados por humanos, conjuntos aleatorios de consultas, etc.)
   • En esta etapa no importan la latencia ni el throughput del prototipo.
   • Mejora iterativa basada en los resultados experimentales.
2. Experimentos en vivo:
   • Si los resultados offline son buenos, se hacen experimentos en vivo sobre una pequeña fracción del tráfico real de usuarios (tiny sliver) (por lo general una muestra aleatoria y, a veces, una clase específica de consultas).
   • En esta etapa la latencia importa más que el throughput. El framework de experimentación debe comportarse de forma cercana a la latencia del entorno de producción.
3. Ajuste de rendimiento y lanzamiento:
   • Si los experimentos en vivo dan buenos resultados, se ajusta el rendimiento o se reimplementa para que pueda ejecutarse con la carga completa (por ejemplo, precalcular datos en lugar de calcularlos en tiempo de ejecución, usar aproximaciones más baratas si son “suficientemente buenas”)
   • Importancia del proceso de lanzamiento (Rollout): considerar continuamente el trade-off entre calidad y costo, y equilibrar lanzamientos rápidos con baja latencia/estabilidad del sitio (se necesita buena colaboración entre el equipo de calidad de búsqueda y el equipo responsable de rendimiento/estabilidad)

Dirección futura y desafíos

• Recuperación de información multilingüe (Cross-Language IR): traducir todos los documentos del mundo a todos los idiomas → crecimiento enorme del índice y alto costo computacional. (Se requiere seguir mejorando la calidad de traducción y construir sistemas a gran escala para manejar modelos de lenguaje más grandes y complejos)
• Listas de control de acceso (ACLs) dentro de sistemas de recuperación de información: entornos mixtos con documentos privados, semiprivados, ampliamente compartidos y públicos. (Se necesita un sistema que procese eficientemente ACL de tamaños muy variados; la solución óptima para documentos compartidos con 10 personas no es la misma que para documentos compartidos con todo el mundo, y los patrones de compartición pueden cambiar con el tiempo)
• Construcción automática de sistemas IR eficientes: actualmente se usan varios sistemas para distintos objetivos (actualizaciones ultrarrápidas, documentos a escala masiva, etc.). (¿Será posible desarrollar un sistema único capaz de construir automáticamente un sistema de búsqueda eficiente según los requisitos dados como parámetros?)
• Extracción de información a partir de datos semi-estructurados: hay muy pocos datos con etiquetas semánticas claras. En cambio, abundan las tablas, formularios y otros datos semi-estructurados. (Se necesitan mejores algoritmos y técnicas para extraer información estructurada desde fuentes no estructuradas/semi-estructuradas, aprovechando su ruido pero también su redundancia, y la capacidad de relacionar/combinar/agregar información de múltiples fuentes)

Conclusión

• Diseñar y construir sistemas de recuperación de información a gran escala es un trabajo desafiante y fascinante.
• Las nuevas tecnologías de búsqueda a menudo requieren nuevos diseños de sistema.