Diseño de Sistemas: Autocompletado de Búsqueda - Tutorial de Diseño de Sistemas | TechLead

Enunciado del Problema

Diseña un sistema de autocompletado de búsqueda (sugerencias typeahead) como las sugerencias de Google Search. A medida que el usuario escribe cada carácter, el sistema retorna las sugerencias más relevantes en tiempo real. Este problema prueba tu comprensión de estructuras de datos (tries), algoritmos de ranking, caché y diseño de sistemas de baja latencia.

Paso 1: Requisitos

Requisitos Funcionales

Retornar las 5-10 mejores sugerencias mientras el usuario escribe
Sugerencias rankeadas por popularidad (frecuencia de búsqueda)
Soporte para sugerencias personalizadas basadas en historial del usuario
Manejar errores de escritura y coincidencia difusa
Soporte multi-idioma
Filtrar sugerencias inapropiadas/ofensivas

Requisitos No Funcionales

Tiempo de respuesta menor a 100ms (los usuarios esperan sugerencias instantáneas)
Alta disponibilidad (la falla del autocompletado degrada significativamente la UX de búsqueda)
Escalar a 10 mil millones de consultas de búsqueda por día
Las sugerencias deben reflejar temas en tendencia en minutos

Estimaciones de Escala

Métrica	Estimación
Consultas de búsqueda por día	10 mil millones
Términos de búsqueda únicos	~5 mil millones
Solicitudes de autocompletado por búsqueda	~6 (longitud promedio de consulta 6 caracteres)
QPS de autocompletado	~700,000
Latencia objetivo	<100ms p99

Paso 2: Estructura de Datos Trie

Un Trie (árbol de prefijos) es la estructura de datos fundamental para el autocompletado. Cada nodo representa un carácter, y los caminos de la raíz a las hojas representan términos de búsqueda completos. El trie permite búsquedas eficientes de prefijos en tiempo O(p) donde p es la longitud del prefijo.

// Implementación básica de Trie para autocompletado
interface TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;
  frequency: number;        // Cuántas veces se buscó este término
  topSuggestions: string[];  // Top K sugerencias pre-computadas para este prefijo
}

class AutocompleteTrie {
  private root: TrieNode;

  constructor() {
    this.root = this.createNode();
  }

  private createNode(): TrieNode {
    return {
      children: new Map(),
      isEndOfWord: false,
      frequency: 0,
      topSuggestions: [],
    };
  }

  // Insertar un término de búsqueda con su frecuencia
  insert(term: string, frequency: number): void {
    let node = this.root;
    for (const char of term.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, this.createNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
    node.frequency = frequency;
  }

  // Obtener sugerencias para un prefijo
  getSuggestions(prefix: string, limit = 10): string[] {
    let node = this.root;

    // Navegar al nodo del prefijo
    for (const char of prefix.toLowerCase()) {
      if (!node.children.has(char)) {
        return []; // Sin coincidencias
      }
      node = node.children.get(char)!;
    }

    // Si existen sugerencias pre-computadas, retornarlas
    if (node.topSuggestions.length > 0) {
      return node.topSuggestions.slice(0, limit);
    }

    // De lo contrario, recolectar todas las palabras bajo este prefijo
    const results: Array<{ term: string; frequency: number }> = [];
    this.collectWords(node, prefix, results);

    return results
      .sort((a, b) => b.frequency - a.frequency)
      .slice(0, limit)
      .map((r) => r.term);
  }

  private collectWords(
    node: TrieNode,
    prefix: string,
    results: Array<{ term: string; frequency: number }>
  ): void {
    if (node.isEndOfWord) {
      results.push({ term: prefix, frequency: node.frequency });
    }
    for (const [char, childNode] of node.children) {
      this.collectWords(childNode, prefix + char, results);
    }
  }
}

Optimización: Pre-computar Top Sugerencias

Recorrer el trie en tiempo de consulta para encontrar todos los términos coincidentes es demasiado lento para producción. En su lugar, pre-computa las top K sugerencias en cada nodo durante la fase de construcción. De esta forma, una búsqueda de prefijo es O(p) donde p es la longitud del prefijo, independientemente de cuántos términos coincidan.

// Optimizado: Pre-computar top sugerencias en cada nodo
class OptimizedTrie {
  private K = 10; // Número de sugerencias a pre-computar

  // Después de insertar todos los términos, pre-computar top K en cada nodo
  precomputeTopSuggestions(node: TrieNode = this.root, prefix = ""): Array<{ term: string; freq: number }> {
    const allTerms: Array<{ term: string; freq: number }> = [];

    // Si este nodo es fin de palabra, incluirlo
    if (node.isEndOfWord) {
      allTerms.push({ term: prefix, freq: node.frequency });
    }

    // Recolectar de todos los hijos
    for (const [char, child] of node.children) {
      const childTerms = this.precomputeTopSuggestions(child, prefix + char);
      allTerms.push(...childTerms);
    }

    // Almacenar top K en este nodo
    allTerms.sort((a, b) => b.freq - a.freq);
    node.topSuggestions = allTerms.slice(0, this.K).map((t) => t.term);

    return allTerms;
  }

  // Ahora getSuggestions es O(longitud_prefijo) - solo caminar al nodo
  getSuggestions(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    return node.topSuggestions;
  }
}

Paso 3: Ranking y Personalización

El ranking puro basado en frecuencia es un punto de partida, pero los sistemas modernos de autocompletado usan múltiples señales para rankear sugerencias.

interface SuggestionCandidate {
  term: string;
  globalFrequency: number;
  recentFrequency: number;   // Frecuencia en las últimas 24 horas (tendencia)
  userFrequency: number;     // Cuántas veces ESTE usuario buscó esto
  score: number;
}

class SuggestionRanker {
  rank(
    candidates: SuggestionCandidate[],
    context: SearchContext
  ): SuggestionCandidate[] {
    return candidates
      .map((c) => ({
        ...c,
        score: this.calculateScore(c, context),
      }))
      .sort((a, b) => b.score - a.score);
  }

  private calculateScore(
    candidate: SuggestionCandidate,
    context: SearchContext
  ): number {
    let score = 0;

    // Popularidad global (escala logarítmica para prevenir dominación)
    score += Math.log10(candidate.globalFrequency + 1) * 30;

    // Impulso de tendencia (frecuencia reciente vs histórica)
    const trendingRatio = candidate.recentFrequency / (candidate.globalFrequency / 365 + 1);
    if (trendingRatio > 2) {
      score += Math.min(trendingRatio * 10, 50); // Limitar bonus de tendencia
    }

    // Personalización: historial de búsqueda propio del usuario
    score += Math.log10(candidate.userFrequency + 1) * 40;

    // Frescura: preferir términos creados recientemente
    // (para eventos de noticias, nuevos productos, etc.)

    // Relevancia de ubicación
    if (context.location && candidate.term.includes(context.location)) {
      score += 15;
    }

    return score;
  }
}

Paso 4: Recolección y Procesamiento de Datos

El sistema de autocompletado necesita un pipeline continuo para recolectar consultas de búsqueda, agregar frecuencias y actualizar el trie.

Arquitectura del Pipeline de Datos

Logging de Consultas: Cada consulta de búsqueda se registra en Kafka con timestamp, ID de usuario y ubicación
Agregación (Batch): Un trabajo MapReduce/Spark ejecuta periódicamente para agregar frecuencias de consultas
Agregación (Tiempo Real): Un procesador de flujo (Flink/Spark Streaming) actualiza consultas tendencia en casi tiempo real
Constructor de Trie: Reconstruye periódicamente el trie desde datos agregados y lo despliega a nodos de servicio
Filtrado: Elimina sugerencias ofensivas, peligrosas o inapropiadas antes de construir el trie

// Pipeline de datos para construir el trie de autocompletado

class AutocompleteDataPipeline {
  // Paso 1: Agregar consultas de búsqueda (batch - ejecuta cada hora)
  async aggregateQueries(): Promise<Map<string, number>> {
    const frequencies = new Map<string, number>();

    // Procesar logs de consultas de la última ventana de tiempo
    const queryLogs = await this.kafka.consume("search-queries");

    for (const log of queryLogs) {
      const normalized = this.normalizeQuery(log.query);
      if (this.isValidSuggestion(normalized)) {
        frequencies.set(normalized, (frequencies.get(normalized) || 0) + 1);
      }
    }

    return frequencies;
  }

  // Paso 2: Construir trie desde datos agregados
  async buildTrie(frequencies: Map<string, number>): Promise<AutocompleteTrie> {
    const trie = new AutocompleteTrie();

    for (const [term, freq] of frequencies) {
      trie.insert(term, freq);
    }

    trie.precomputeTopSuggestions();
    return trie;
  }

  // Paso 3: Desplegar a nodos de servicio
  async deployTrie(trie: AutocompleteTrie): Promise<void> {
    // Serializar trie a un formato binario compacto
    const serialized = this.serializeTrie(trie);

    // Subir a almacenamiento compartido
    await this.s3.upload("autocomplete-tries", `trie-${Date.now()}.bin`, serialized);

    // Notificar a nodos de servicio para cargar nuevo trie
    await this.broadcast("trie-update", { version: Date.now() });
  }

  private normalizeQuery(query: string): string {
    return query
      .toLowerCase()
      .trim()
      .replace(/\s+/g, " "); // Colapsar espacios en blanco
  }

  private isValidSuggestion(query: string): boolean {
    if (query.length < 2 || query.length > 100) return false;
    if (this.offensiveFilter.isOffensive(query)) return false;
    return true;
  }
}

Paso 5: Estrategias de Caché

Con 700K QPS, servir cada solicitud desde el trie es impracticable incluso con sugerencias pre-computadas. El caché multi-nivel es esencial.

Capas de Caché

Caché del Navegador: Cachear sugerencias en el cliente. Si el usuario escribe "como h" luego borra "h", re-escribir "h" no debe consultar al servidor.
Caché CDN/Edge: Prefijos populares ("como hacer", "qué es") pueden cachearse en el edge del CDN. El 20% de los prefijos representan el 80% de las solicitudes.
Caché de Aplicación (Redis): Mapeo prefijo -> sugerencias cacheado en Redis. TTL de 1-5 minutos para balance entre frescura y rendimiento.
Trie En Memoria: El trie cargado completamente en la memoria de cada nodo de servicio para búsquedas sub-milisegundo.

class AutocompleteServer {
  private trie: AutocompleteTrie;
  private cache: RedisClient;

  async getSuggestions(prefix: string, userId?: string): Promise<string[]> {
    const normalizedPrefix = prefix.toLowerCase().trim();

    // Capa 1: Verificar caché Redis
    const cacheKey = `ac:${normalizedPrefix}`;
    const cached = await this.cache.get(cacheKey);
    if (cached) {
      const suggestions = JSON.parse(cached);
      // Opcionalmente fusionar con resultados personalizados
      if (userId) {
        return this.mergePersonalized(suggestions, userId, normalizedPrefix);
      }
      return suggestions;
    }

    // Capa 2: Consultar el trie en memoria
    const suggestions = this.trie.getSuggestions(normalizedPrefix);

    // Cachear por 2 minutos
    await this.cache.setex(cacheKey, 120, JSON.stringify(suggestions));

    if (userId) {
      return this.mergePersonalized(suggestions, userId, normalizedPrefix);
    }

    return suggestions;
  }

  // Optimización del lado del cliente: debounce y agrupar solicitudes
  // No enviar una solicitud en cada tecla
  // Esperar 100-200ms después de la última tecla antes de solicitar
}

// Implementación del lado del cliente
class AutocompleteClient {
  private debounceTimer: NodeJS.Timeout | null = null;
  private cache = new Map<string, string[]>();

  onInput(prefix: string): void {
    // Verificar caché del lado del cliente primero
    if (this.cache.has(prefix)) {
      this.renderSuggestions(this.cache.get(prefix)!);
      return;
    }

    // Debounce: esperar 150ms después de la última tecla
    if (this.debounceTimer) clearTimeout(this.debounceTimer);
    this.debounceTimer = setTimeout(() => {
      this.fetchSuggestions(prefix);
    }, 150);
  }

  private async fetchSuggestions(prefix: string): Promise<void> {
    const response = await fetch(`/api/autocomplete?q=${encodeURIComponent(prefix)}`);
    const suggestions = await response.json();

    // Cachear en el cliente
    this.cache.set(prefix, suggestions);
    this.renderSuggestions(suggestions);
  }
}

Paso 6: Soporte Multi-Idioma

Soportar múltiples idiomas introduce desafíos alrededor de conjuntos de caracteres, tokenización y ranking culturalmente apropiado.

Tries separados por idioma: Construir y servir diferentes tries basados en el locale del usuario
Normalización Unicode: Normalizar caracteres para manejar acentos y diacríticos (ej., "cafe" debe coincidir con "café")
Idiomas CJK: Chino, japonés y coreano no usan espacios entre palabras, requiriendo diferentes estrategias de tokenización
Idiomas RTL: Árabe y hebreo necesitan manejo especial para la dirección de coincidencia de prefijos
Transliteración: Permitir buscar en un script y sugerir en otro (ej., escribir en japonés romanizado para obtener sugerencias en Kanji)

Resumen de Arquitectura del Sistema

Resumen de Componentes

Componente	Tecnología	Propósito
Capa de Servicio	Trie en memoria en servidores de app	Búsquedas de prefijo sub-ms
Caché	Redis + caché edge CDN	Reducir búsquedas en trie para prefijos populares
Procesamiento Batch	Spark / MapReduce	Agregar frecuencias de consultas cada hora
Procesamiento de Flujo	Flink / Kafka Streams	Detectar consultas en tendencia en tiempo real
Almacenamiento	S3 (snapshots de trie), Cassandra (logs de consultas)	Persistir construcciones de trie y datos crudos
Personalización	Redis historial por usuario	Mezclar historial personal en sugerencias

Consejos de Entrevista

Comienza con el trie: Explica la estructura de datos primero, luego optimiza con top-K pre-computado
Enfatiza la latencia: Cada optimización debe enfocarse en tiempos de respuesta sub-100ms
Discute el pipeline de datos: Cómo se actualizan las sugerencias es tan importante como cómo se sirven
Menciona optimizaciones del lado del cliente: Debouncing y caché del cliente reducen la carga del servidor en 50%+
Aborda el filtrado: Siempre menciona la moderación de contenido para sugerencias de autocompletado