Diseño de Sistemas: Caché Distribuido - Tutorial de Diseño de Sistemas | TechLead

Enunciado del Problema

Diseña un sistema de caché distribuido similar a Memcached o Redis Cluster. El caché debe almacenar pares clave-valor a través de múltiples nodos, manejar fallos de nodos elegantemente y proporcionar latencia de lectura sub-milisegundo. El caché es una de las optimizaciones de rendimiento más impactantes en diseño de sistemas, y entender cómo funcionan los cachés distribuidos es esencial para diseñar sistemas escalables.

Paso 1: Requisitos y Objetivos

Requisitos Funcionales

Almacenar pares clave-valor con TTL (tiempo de vida) configurable
Soportar operaciones GET, SET, DELETE
Distribuir datos entre múltiples nodos de caché
Manejar adiciones y eliminaciones de nodos con mínima redistribución de datos
Soportar desalojo de caché cuando la memoria está llena
Proporcionar operaciones atómicas (incremento, compare-and-swap)

Requisitos No Funcionales

Latencia sub-milisegundo para lecturas (<1ms p99)
Alto rendimiento: 1 millón de operaciones por segundo por nodo
Alta disponibilidad: sobrevivir fallos de nodos individuales
Escalabilidad lineal: agregar nodos aumenta la capacidad proporcionalmente
Consistencia: configurable (fuerte o eventual)

Paso 2: Tipos de Arquitectura de Caché

Antes de diseñar un caché distribuido, entiende dónde encaja el caché en la arquitectura del sistema.

Opciones de Ubicación del Caché

Tipo	Dónde	Pros	Contras
Del lado del cliente	Navegador, app móvil	Más rápido, sin salto de red	Tamaño limitado, difícil de invalidar
Caché CDN	Ubicaciones edge	Baja latencia globalmente	Solo contenido estático, demora en invalidación
Caché de Aplicación	Memoria del servidor de app	Sin salto de red, rápido	No compartido, se pierde al reiniciar
Caché Distribuido	Clúster de caché dedicado	Compartido, escalable, durable	Salto de red, complejidad
Caché de Base de Datos	Caché de consultas de BD	Automático, sin cambios de código	Control limitado, memoria de BD

Cache-aside (Carga Perezosa) vs Write-through

// Cache-aside (most common pattern)
// Application manages cache population
class CacheAside {
  private cache: CacheClient;
  private db: Database;

  async get(key: string): Promise<any> {
    // 1. Check cache first
    const cached = await this.cache.get(key);
    if (cached !== null) {
      return cached; // Cache HIT
    }

    // 2. Cache MISS - fetch from database
    const data = await this.db.findByKey(key);
    if (data === null) return null;

    // 3. Populate cache for next time
    await this.cache.set(key, data, { ttl: 3600 });
    return data;
  }

  async update(key: string, data: any): Promise<void> {
    // 1. Update database
    await this.db.update(key, data);
    // 2. Invalidate cache (don't update - avoids race conditions)
    await this.cache.delete(key);
  }
}

// Write-through
// Cache is always updated alongside the database
class WriteThrough {
  private cache: CacheClient;
  private db: Database;

  async get(key: string): Promise<any> {
    // Always read from cache (it's always up-to-date)
    const cached = await this.cache.get(key);
    if (cached !== null) return cached;

    // Cold start: populate from DB
    const data = await this.db.findByKey(key);
    if (data) await this.cache.set(key, data);
    return data;
  }

  async update(key: string, data: any): Promise<void> {
    // Write to both cache and database
    await this.db.update(key, data);
    await this.cache.set(key, data);
    // Risk: if cache write fails after DB write, they're inconsistent
  }
}

// Write-behind (Write-back)
// Write to cache immediately, persist to DB asynchronously
class WriteBehind {
  private cache: CacheClient;
  private writeQueue: Queue;

  async update(key: string, data: any): Promise<void> {
    // Write to cache immediately (fast)
    await this.cache.set(key, data);
    // Queue DB write for async processing
    await this.writeQueue.enqueue({ key, data, timestamp: Date.now() });
    // Risk: data loss if cache fails before DB write
  }
}

Paso 3: Hashing Consistente para Distribución de Datos

El desafío clave en un caché distribuido es decidir qué nodo almacena qué clave. El hashing modular simple (hash(key) % N) falla cuando se agregan o eliminan nodos porque casi todas las claves se redistribuyen. El hashing consistente resuelve esto minimizando la redistribución de claves.

import { createHash } from "crypto";

class ConsistentHashRing {
  private ring = new Map<number, string>(); // position -> nodeId
  private sortedPositions: number[] = [];
  private virtualNodesPerNode: number;

  constructor(virtualNodesPerNode = 150) {
    this.virtualNodesPerNode = virtualNodesPerNode;
  }

  // Add a node to the ring
  addNode(nodeId: string): void {
    for (let i = 0; i < this.virtualNodesPerNode; i++) {
      const virtualKey = `${nodeId}:vn${i}`;
      const position = this.hash(virtualKey);
      this.ring.set(position, nodeId);
      this.sortedPositions.push(position);
    }
    this.sortedPositions.sort((a, b) => a - b);
  }

  // Remove a node from the ring
  removeNode(nodeId: string): void {
    for (let i = 0; i < this.virtualNodesPerNode; i++) {
      const virtualKey = `${nodeId}:vn${i}`;
      const position = this.hash(virtualKey);
      this.ring.delete(position);
    }
    this.sortedPositions = this.sortedPositions.filter(
      (pos) => this.ring.has(pos)
    );
  }

  // Find which node should store a given key
  getNode(key: string): string {
    if (this.ring.size === 0) throw new Error("No nodes in ring");
    const keyPosition = this.hash(key);
    const idx = this.findNextPosition(keyPosition);
    return this.ring.get(this.sortedPositions[idx])!;
  }

  // Get N nodes for replication
  getNodes(key: string, replicaCount: number): string[] {
    const nodes = new Set<string>();
    const keyPosition = this.hash(key);
    let idx = this.findNextPosition(keyPosition);

    while (nodes.size < replicaCount && nodes.size < this.getUniqueNodeCount()) {
      const nodeId = this.ring.get(this.sortedPositions[idx])!;
      nodes.add(nodeId);
      idx = (idx + 1) % this.sortedPositions.length;
    }

    return Array.from(nodes);
  }

  private hash(key: string): number {
    const hash = createHash("md5").update(key).digest();
    return hash.readUInt32BE(0);
  }

  private findNextPosition(target: number): number {
    let lo = 0, hi = this.sortedPositions.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.sortedPositions[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return lo < this.sortedPositions.length ? lo : 0;
  }

  private getUniqueNodeCount(): number {
    return new Set(this.ring.values()).size;
  }
}

¿Por Qué Nodos Virtuales?

Sin nodos virtuales, la distribución de datos puede ser muy desigual porque los nodos se colocan en puntos arbitrarios del anillo hash. Con 100-200 nodos virtuales por nodo físico, cada nodo físico es responsable de muchos rangos pequeños en el anillo, resultando en una distribución mucho más uniforme.

Cuando se agrega un nodo, solo toma una fracción de claves de sus vecinos. Cuando se elimina un nodo, sus claves se distribuyen uniformemente entre los nodos restantes. Esto significa que solo K/N claves necesitan moverse (K = claves totales, N = nodos totales), comparado con casi todas las claves con hashing modular.

Paso 4: Estrategias de Replicación

Para sobrevivir fallos de nodos, cada par clave-valor debe almacenarse en múltiples nodos. El factor de replicación (típicamente 2-3) determina cuántas copias existen.

class ReplicatedCache {
  private hashRing: ConsistentHashRing;
  private nodes: Map<string, CacheNode>;
  private replicaCount = 3;

  async set(key: string, value: any, ttl?: number): Promise<void> {
    const targetNodes = this.hashRing.getNodes(key, this.replicaCount);

    const writePromises = targetNodes.map((nodeId) =>
      this.nodes.get(nodeId)!.set(key, value, ttl)
    );

    // Wait for quorum (majority) to acknowledge
    const quorum = Math.floor(this.replicaCount / 2) + 1;
    await this.waitForQuorum(writePromises, quorum);
  }

  async get(key: string): Promise<any> {
    const targetNodes = this.hashRing.getNodes(key, this.replicaCount);

    for (const nodeId of targetNodes) {
      try {
        const value = await this.nodes.get(nodeId)!.get(key);
        if (value !== null) return value;
      } catch (error) {
        continue; // Node is down, try next replica
      }
    }

    return null;
  }

  private async waitForQuorum(
    promises: Promise<void>[],
    quorum: number
  ): Promise<void> {
    let successes = 0;
    let failures = 0;
    const total = promises.length;

    return new Promise((resolve, reject) => {
      for (const p of promises) {
        p.then(() => {
          successes++;
          if (successes >= quorum) resolve();
        }).catch(() => {
          failures++;
          if (failures > total - quorum) {
            reject(new Error("Failed to achieve write quorum"));
          }
        });
      }
    });
  }
}

Paso 5: Políticas de Desalojo

Cuando la memoria del caché está llena, las entradas antiguas deben eliminarse para hacer espacio a las nuevas. La política de desalojo determina qué entradas eliminar.

Comparación de Políticas de Desalojo

Política	Descripción	Mejor Para	Costo
LRU	Desalojar el menos recientemente usado	Uso general	Medio (lista doblemente enlazada)
LFU	Desalojar el menos frecuentemente usado	Cargas sesgadas por frecuencia	Mayor (contadores de frecuencia)
FIFO	Desalojar la entrada más antigua	Casos de uso simples	Bajo (cola)
Aleatorio	Desalojar una entrada aleatoria	Cuando los patrones de acceso son uniformes	Muy bajo
Basado en TTL	Desalojar entradas expiradas primero	Datos sensibles al tiempo	Bajo (heap de expiración)

// LRU Cache implementation using a doubly linked list + hash map
class LRUCache<K, V> {
  private capacity: number;
  private cache = new Map<K, { value: V; node: DLLNode<K> }>();
  private dll: DoublyLinkedList<K>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.dll = new DoublyLinkedList();
  }

  get(key: K): V | null {
    const entry = this.cache.get(key);
    if (!entry) return null;

    this.dll.moveToFront(entry.node);
    return entry.value;
  }

  set(key: K, value: V): void {
    if (this.cache.has(key)) {
      const entry = this.cache.get(key)!;
      entry.value = value;
      this.dll.moveToFront(entry.node);
      return;
    }

    if (this.cache.size >= this.capacity) {
      const evicted = this.dll.removeTail();
      if (evicted) {
        this.cache.delete(evicted.key);
      }
    }

    const node = this.dll.addToFront(key);
    this.cache.set(key, { value, node });
  }

  delete(key: K): boolean {
    const entry = this.cache.get(key);
    if (!entry) return false;
    this.dll.remove(entry.node);
    this.cache.delete(key);
    return true;
  }
}

Paso 6: Prevención de Estampida de Caché

Una estampida de caché (también llamada manada atronadora) ocurre cuando una clave de caché popular expira y cientos de solicitudes concurrentes fallan en el caché simultáneamente, sobrecargando la base de datos con consultas idénticas.

Escenarios de Estampida

Expiración de clave: El TTL de una clave popular expira y miles de solicitudes golpean la base de datos
Reinicio de caché: Un nodo de caché se reinicia con un caché vacío (arranque en frío)
Despliegue: Nuevo código que cachea claves diferentes causa una ola de fallos de caché

class StampedeProtectedCache {
  private cache: CacheClient;
  private db: Database;
  private locks: RedisClient;

  // Strategy 1: Distributed Locking
  async getWithLock(key: string): Promise<any> {
    const cached = await this.cache.get(key);
    if (cached) return cached;

    const lockKey = `lock:${key}`;
    const acquired = await this.locks.set(lockKey, "1", "EX", 10, "NX");

    if (acquired) {
      try {
        const data = await this.db.findByKey(key);
        await this.cache.set(key, data, { ttl: 3600 });
        return data;
      } finally {
        await this.locks.del(lockKey);
      }
    } else {
      await this.sleep(50);
      return this.getWithLock(key);
    }
  }

  // Strategy 2: Stale-While-Revalidate
  async getWithStaleRefresh(key: string): Promise<any> {
    const entry = await this.cache.getWithMeta(key);

    if (entry && !entry.isExpired) {
      return entry.value;
    }

    if (entry && entry.isExpired) {
      this.refreshInBackground(key);
      return entry.value; // Return stale data
    }

    return this.fetchAndCache(key);
  }

  // Strategy 3: Probabilistic Early Expiration
  async getWithEarlyExpiration(key: string, baseTTL: number): Promise<any> {
    const entry = await this.cache.getWithTTL(key);

    if (entry) {
      const remainingTTL = entry.ttl;
      const shouldRefreshEarly = Math.random() < Math.exp(-remainingTTL / (baseTTL * 0.1));

      if (shouldRefreshEarly) {
        this.refreshInBackground(key);
      }
      return entry.value;
    }

    return this.fetchAndCache(key);
  }

  private async refreshInBackground(key: string): Promise<void> {
    this.fetchAndCache(key).catch(console.error);
  }

  private sleep(ms: number): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, ms));
  }
}

Paso 7: Monitoreo y Métricas

Un caché distribuido requiere monitoreo cuidadoso para asegurar que funciona óptimamente y detectar problemas antes de que impacten a los usuarios.

Métricas Clave a Monitorear

Tasa de Aciertos de Caché: Porcentaje de solicitudes servidas desde el caché. Objetivo: >95% para la mayoría de cargas de trabajo. Una tasa baja indica TTL incorrecto, memoria insuficiente o mal diseño de claves.
Latencia (p50, p99, p999): Debe ser sub-milisegundo. Los picos indican problemas de red o puntos calientes.
Uso de Memoria: Rastrear el uso de memoria por nodo. Alertar cuando se acerca a la capacidad para prevenir desalojos excesivos.
Tasa de Desalojo: Una tasa alta de desalojo significa que el caché es muy pequeño o los TTLs están mal configurados.
Conteo de Conexiones: Número de conexiones de clientes por nodo. Distribución desigual indica problemas de enrutamiento.
Distribución de Claves: Asegurar que las claves están distribuidas uniformemente entre nodos (sin puntos calientes).
Retraso de Replicación: Tiempo para que una escritura se propague a las réplicas. Un retraso alto arriesga servir datos obsoletos.

class CacheMetrics {
  private hits = 0;
  private misses = 0;
  private latencies: number[] = [];

  recordHit(latencyMs: number): void {
    this.hits++;
    this.latencies.push(latencyMs);
  }

  recordMiss(latencyMs: number): void {
    this.misses++;
    this.latencies.push(latencyMs);
  }

  getStats(): CacheStats {
    const total = this.hits + this.misses;
    const sorted = [...this.latencies].sort((a, b) => a - b);

    return {
      hitRatio: total > 0 ? this.hits / total : 0,
      totalRequests: total,
      p50Latency: sorted[Math.floor(sorted.length * 0.5)] || 0,
      p99Latency: sorted[Math.floor(sorted.length * 0.99)] || 0,
      p999Latency: sorted[Math.floor(sorted.length * 0.999)] || 0,
    };
  }

  shouldAlert(stats: CacheStats): string[] {
    const alerts: string[] = [];
    if (stats.hitRatio < 0.90) {
      alerts.push(`Low cache hit ratio: ${(stats.hitRatio * 100).toFixed(1)}%`);
    }
    if (stats.p99Latency > 5) {
      alerts.push(`High p99 latency: ${stats.p99Latency}ms`);
    }
    return alerts;
  }
}

Resumen de Arquitectura

Componente	Decisión de Diseño
Distribución de Datos	Hashing consistente con 150 nodos virtuales por nodo físico
Replicación	3 réplicas, escrituras por quórum (2/3), lectura del más cercano
Política de Desalojo	LRU con expiración basada en TTL (por defecto en Redis: allkeys-lru)
Prevención de Estampida	Bloqueo distribuido para claves frías, stale-while-revalidate para claves calientes
Patrón de Caché	Cache-aside para lecturas, invalidación en escrituras
Serialización	MessagePack o Protocol Buffers (más rápido que JSON)
Monitoreo	Tasa de aciertos, percentiles de latencia, tasa de desalojo, uso de memoria por nodo

Consejos para Entrevistas

Comienza con hashing consistente: Este es el concepto central que los entrevistadores quieren escuchar
Explica los nodos virtuales: Demuestra que entiendes por qué el hashing consistente sin nodos virtuales lleva a distribución desigual
Discute estrategias de invalidación de caché: Cache-aside con invalidación en escrituras es el predeterminado más seguro
Siempre menciona la estampida de caché: Esto demuestra experiencia en producción y profundidad de entendimiento
Compara Redis vs Memcached: Redis tiene estructuras de datos, persistencia y replicación; Memcached es más simple y multi-hilo