Diseño de un sistema typeahead: cómo funciona el autocompletado de búsqueda a escala

Escribe «how to» en un cuadro de búsqueda y las sugerencias aparecen antes de que termines la siguiente palabra. Esa función responde a una petición en casi cada pulsación, para cada usuario, y tiene que sentirse instantánea: la investigación sobre tiempos de respuesta, que se remonta a décadas atrás, sitúa el límite de «el sistema reacciona al instante» en unos 0,1 segundos. Nada del autocompletado es difícil por separado. El reto es hacer cosas simples dentro de un presupuesto de latencia ajustado y con una tasa de peticiones muy alta, manteniendo a la vez las sugerencias frescas y libres de todo lo que nunca quieres mostrar.

Este artículo diseña un servicio typeahead: requisitos y capacidad, el índice de prefijos top-k, el servicio y el sharding, el pipeline de construcción offline, las consultas en tendencia, la caché, la personalización y el filtrado, con un diagrama de las dos mitades.

Requisitos

Funcionales:

• Devolver las 5 a 10 mejores compleciones para un prefijo, ordenadas sobre todo por popularidad.
• Reflejar las nuevas tendencias en minutos, no en días.
• No mostrar nunca sugerencias que incumplan tus políticas.

No funcionales:

• Unos 100 ms de extremo a extremo, lo que deja al backend un presupuesto de decenas de milisegundos tras el tiempo de red.
• Alta disponibilidad: si las sugerencias fallan, la búsqueda sigue funcionando, así que degrada con elegancia.
• Barato: esto se ejecuta en cada pulsación.

Capacidad

Supón 50 millones de usuarios diarios que buscan 10 veces al día cada uno, con unas 6 peticiones de sugerencias por búsqueda una vez que el cliente deja de enviar una por carácter:

Dos observaciones dan forma al diseño. Los prefijos cortos son extremadamente repetitivos: todo el que escribe «w» hace la misma pregunta. Y la respuesta a un prefijo cambia despacio, así que se puede calcular de antemano.

El cliente hace la mitad del trabajo

• Debounce. Espera de 100 a 200 ms tras la última pulsación antes de enviar una petición, para que quien teclea rápido no dispare una petición por carácter.
• Cancela las peticiones obsoletas. Cuando sale un prefijo nuevo, aborta el anterior e ignora las respuestas tardías de un prefijo más antiguo.
• Guarda en caché local. Si «how t» devolvió diez resultados que empiezan todos por «how to», el cliente puede filtrarlos para «how to» sin hacer ninguna petición.
• Degrada en silencio. Si la llamada de sugerencias falla o va lenta, no muestres nada; la búsqueda tiene que seguir funcionando.

El índice de prefijos top-k

La estructura clásica es un trie, donde cada nodo es un prefijo y sus hijos lo amplían en un carácter. Recorrer el trie y buscar en todo el subárbol las consultas más populares en el momento de la petición es demasiado lento para los prefijos populares. En su lugar, precalcula la respuesta: guarda en cada nodo de prefijo las k mejores compleciones, ya ordenadas. Una búsqueda se convierte en una sola lectura.

Muchas implementaciones prescinden por completo del trie basado en punteros y guardan un mapa plano del prefijo a su lista top-k, limitado a una longitud máxima de prefijo, ya que los prefijos muy largos son raros y pueden recurrir a una ruta más lenta. Construir uno a partir de recuentos agregados es breve:

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

El resultado es de solo lectura y se carga en memoria en cada nodo de servicio. Si ya usas Elasticsearch, su completion suggester ofrece la misma idea como funcionalidad: la documentación describe estructuras de datos que permiten búsquedas rápidas pero son costosas de construir y se guardan en memoria, que es exactamente el compromiso que asume este diseño.

Servicio y sharding

El servicio de sugerencias normaliza el prefijo (minúsculas, recorte de espacios, normalización Unicode), lee la lista top-k del índice, mezcla los resultados en tendencia y personales, filtra y responde. Todo lo que lee está en memoria.

Cuando el índice ya no cabe en una máquina, divídelo en shards. Hacerlo por la primera letra parece natural, pero queda muy desequilibrado: muchas más consultas empiezan por «s» que por «x». Mejor aplica un hash al prefijo, o divide por rangos de tráfico medido, y replica cada shard para que la caída de un nodo solo reduzca la capacidad. Como el índice se reconstruye offline, las réplicas nunca tienen que ponerse de acuerdo sobre escrituras; cada una carga el mismo snapshot.

El pipeline de construcción offline

1. Recoger. Los frontends de búsqueda registran cada consulta completada en un stream como Kafka.
2. Agregar. Un trabajo batch cuenta las consultas en una ventana, por ejemplo los últimos 30 días, dando más peso a los días recientes, y descarta las consultas raras por debajo de un umbral para proteger la privacidad y eliminar ruido.
3. Filtrar. Aplica listas de bloqueo y clasificadores de políticas antes de que nada se convierta en sugerencia.
4. Construir. Calcula el índice de prefijos como antes y escríbelo como snapshot versionado en el almacenamiento de objetos.
5. Desplegar. Los nodos de servicio cargan el snapshot nuevo junto al anterior, cambian de forma atómica y conservan la versión previa para revertir rápido.

Las reconstrucciones cada hora o cada día mantienen el índice principal lo bastante fresco para la mayoría de las consultas.

Consultas en tendencia

Una noticia de última hora genera una nueva consulta popular en minutos, mucho antes de la siguiente construcción batch. Añade una pequeña capa de tiempo real: un procesador de streams cuenta las consultas en ventanas deslizantes, detecta las que suben mucho más rápido que su línea base y las escribe en un almacén rápido como Redis, indexadas por prefijo. El servicio de sugerencias las mezcla con los resultados batch. Mantén esta capa pequeña y fíltrala a fondo; es ahí donde un ataque coordinado intentaría colar sugerencias.

Caché en cada capa

Los prefijos cortos son los más calientes y los más cacheables, porque son idénticos para todo el mundo. Los resultados personalizados no se pueden cachear en la CDN, una de las razones para mantener ligera la personalización.

Personalización, erratas y filtrado

• Historial personal. Mezclar las consultas recientes del propio usuario con las sugerencias globales ayuda mucho y es barato si esas consultas viven en el dispositivo o en un pequeño almacén por usuario.
• Erratas. La coincidencia aproximada a una edición del prefijo rescata «pyhton». Es más cara, así que muchos sistemas prueban primero los prefijos exactos y solo recurren a la coincidencia aproximada cuando hay pocos resultados.
• El filtrado se aplica dos veces: offline, antes de que una consulta entre en el índice, y online, contra una lista de bloqueo rápida que se puede actualizar en minutos sin reconstruir nada.

El diagrama del typeahead

Cómo leerlo:

• El marco online es la ruta de cada pulsación: navegador, caché de la CDN, puerta de enlace de API y servicio de sugerencias.
• El servicio de sugerencias lee dos shards de prefijos en memoria y el almacén de tendencias en Redis, y combina y filtra los resultados.
• El marco offline es la ruta de construcción: logs de consultas desde Kafka, el trabajo de agregación y snapshots versionados del índice en el almacenamiento de objetos.
• La arista discontinua del almacenamiento de objetos a los shards es la carga del snapshot, el único vínculo entre las dos mitades.
• El bloque Markdown muestra el presupuesto de latencia y las cifras de capacidad.

Dibujar sistemas de lectura intensiva con claridad

• Separa online y offline. Las dos mitades tienen presupuestos de latencia, modos de fallo y responsables distintos, y el diagrama debería mostrarlo de un vistazo.
• Muestra cada capa de caché, con su caducidad. En un sistema de lectura intensiva, las cachés son la mayor parte de la arquitectura.
• Dibuja el único vínculo entre las mitades: aquí, un snapshot versionado. Explica cómo llegan las actualizaciones a los usuarios y cómo funciona la reversión.
• Anota el presupuesto de latencia en la ruta online.

Para el enfoque general, consulta el ejemplo de diagrama de diseño de sistemas. El diagrama de estrategias de caché trata las capas de caché con más detalle, y la agregación de logs sigue los patrones del diagrama de arquitectura de pipelines de datos.

Constrúyelo en Archboard

1. Inicia sesión con Google o GitHub y crea un diagrama.
2. Añade dos nodos Marco del pack Básico: Online, per keystroke, y Offline, hourly build.
3. En el marco online, añade un nodo Dispositivo del pack Red para el navegador, una CDN y una Puerta de enlace de API del pack Nube, un nodo Instancia de cómputo para el servicio de sugerencias, dos nodos Redis del pack Datos para los shards de prefijos y otro nodo Redis para las consultas en tendencia.
4. En el marco offline, añade un nodo Kafka del pack Datos para los logs de consultas, un nodo Instancia de cómputo del pack Nube para el trabajo de agregación y un Almacén de objetos del pack Datos para los snapshots del índice.
5. Dibuja la ruta de las peticiones de izquierda a derecha, la ruta de construcción debajo y una arista discontinua de los snapshots a los shards.
6. Añade un bloque Markdown del pack Básico con el presupuesto de latencia y la capacidad.

El ejemplo usa 13 nodos de diagrama, dentro del plan Free.

Preguntas frecuentes

¿Qué estructura de datos se usa para el autocompletado? Un trie, o un mapa plano del prefijo a los resultados, con las k mejores compleciones precalculadas en cada prefijo. Precalcular convierte cada búsqueda en una sola lectura en memoria.

¿Qué tan rápido debe ser el autocompletado? Unos 100 ms desde la pulsación hasta las sugerencias se perciben como instantáneos. Tras el tiempo de red, al backend le quedan decenas de milisegundos, y por eso el índice vive en memoria.

¿Cómo se mantienen al día las sugerencias? Un pipeline batch reconstruye el índice a partir de los logs de consultas cada hora o cada día, y una capa de tiempo real añade en minutos las consultas que suben rápido.

¿Hay que enviar una petición de autocompletado en cada pulsación? No. Aplica un debounce de 100 a 200 ms en el cliente, cancela las peticiones obsoletas y reutiliza los resultados en caché para prefijos más largos. Así se reduce mucho el volumen de peticiones.

¿Cómo se evitan las sugerencias ofensivas? Filtra offline antes de que las consultas entren en el índice, aplica umbrales mínimos de popularidad y comprueba los resultados online contra una lista de bloqueo que puedas actualizar rápido.

Empieza gratis — un puesto, sin tarjeta de crédito.