Cuando una caché hace más que solo caché

La mayoría de la gente piensa en una caché como un simple acelerador de rendimiento: almacena un resultado, lo reutiliza más tarde y listo.

Pero en sistemas con alta concurrencia, una caché puede desempeñar un papel más importante. Puede convertirse en un mecanismo de coordinación que protege al resto del sistema de duplicar trabajo innecesario.

Esa es la idea detrás de cpp-cache, construida por el equipo de ingeniería de SIMYL y basada en un diseño que ha funcionado en producción durante más de seis años.

El problema: demasiados hilos, el mismo fallo (miss) Link to heading

Imagina que se solicita una clave popular en el momento exacto en que aún no está en la caché.

Si diez, cincuenta o cien hilos se encuentran con ese mismo fallo aproximadamente al mismo tiempo, una implementación ingenua dispara el mismo cálculo costoso una y otra vez. En lugar de reducir la carga, la caché la amplifica. Se consume más CPU, se genera más presión en el backend y la latencia se vuelve más difícil de controlar.

Este es el clásico problema del thundering herd (manada atronadora).

flowchart LR
    subgraph sin["Sin coordinación"]
        direction TB
        T1a[Hilo 1] -->|MISS| B1[Backend]
        T2a[Hilo 2] -->|MISS| B2[Backend]
        T3a[Hilo 3] -->|MISS| B3[Backend]
        TNa[Hilo N] -->|MISS| BN[Backend]
    end
    subgraph con["Con single-flight"]
        direction TB
        T1b[Hilo 1] -->|calcula| C[Caché]
        T2b[Hilo 2] -.->|espera| C
        T3b[Hilo 3] -.->|espera| C
        TNb[Hilo N] -.->|espera| C
        C -->|1 llamada| Backend
    end

    style sin fill:#fee,stroke:#c00
    style con fill:#efe,stroke:#0a0

A la izquierda, cada hilo golpea el backend de forma independiente. A la derecha, un hilo calcula mientras el resto espera — el backend ve una sola llamada.

Aquí está la diferencia en la práctica:

// Sin coordinación: cada hilo calcula de forma independiente
auto val = expensive_backend_call(key);  // x100 hilos = x100 llamadas

// Con cpp-cache: un hilo calcula, el resto espera y comparte
auto result = cache.get_or_compute(key);
// Solo una llamada al backend. Los 100 hilos obtienen el mismo resultado.

if (result.is_positive())
    use(*result.value());

Una buena caché concurrente no debería limitarse a recordar valores. También debería evitar que el sistema se colapse cuando falta el valor.

La solución: un cálculo por clave Link to heading

La propiedad más importante del diseño es sencilla:

Si varios hilos solicitan la misma clave que falta, solo uno de ellos realiza el cálculo. Los demás esperan y reutilizan el resultado.

Esto se conoce como comportamiento single-flight.

sequenceDiagram
    participant T1 as Hilo 1
    participant C as Caché
    participant T2 as Hilo 2
    participant T3 as Hilo 3
    participant B as Backend

    T1->>C: get_or_compute("clave")
    Note over C: Miss → Estado = COMPUTING
    T2->>C: get_or_compute("clave")
    Note over C: El estado es COMPUTING
    T2-->>C: Espera en variable de condición
    T3->>C: get_or_compute("clave")
    T3-->>C: Espera en variable de condición

    C->>B: Cálculo costoso
    B-->>C: Resultado

    Note over C: Estado = READY
    C-->>T1: Devuelve ComputedPositive
    C-->>T2: Notifica → Devuelve HitPositive
    C-->>T3: Notifica → Devuelve HitPositive

Lo mejor de este enfoque es que no sacrifica la concurrencia general. Los hilos que solicitan claves diferentes pueden seguir avanzando de forma independiente. La coordinación ocurre donde debe: en la clave en disputa, no en toda la caché.

El bloqueo global que protege la tabla hash y la lista LRU se mantiene solo para operaciones estructurales de nivel de microsegundos: búsqueda, inserción, reordenación. Nunca se mantiene mientras el “solver” (el calculador) se ejecuta. Eso significa que el trabajo costoso ocurre sin bloqueos, y diferentes claves se pueden calcular realmente en paralelo.

block-beta
    columns 4
    A["Fase 1\nMutex global\nbúsqueda/inserción"]:1
    B["Fase 2\nSIN BLOQUEOS\nEjecución del Solver"]:1
    C["Fase 3\nMutex de entrada\nestablecer estado + notificar"]:1
    D["Fase 4\nMutex global\nreordenación LRU"]:1

    style A fill:#fcc,stroke:#900
    style B fill:#cfc,stroke:#090
    style C fill:#ccf,stroke:#009
    style D fill:#fcc,stroke:#900

La clave fundamental: la Fase 2 (donde ocurre el trabajo real) mantiene cero bloqueos. Por eso se pueden resolver múltiples claves de forma concurrente aunque haya un único mutex global.

Diseñado también para fallos del mundo real Link to heading

Otro aspecto notable de la caché es que trata los fallos como resultados significativos.

Tanto los resultados exitosos como los fallidos pueden almacenarse en la caché, cada uno con su propio TTL.

¿Por qué es importante? Considera un escenario concreto: tu backend devuelve un 404 para un recurso que no existe. Sin caché negativa, cada una de las peticiones para ese recurso vuelve a intentar consultar el backend. Bajo un tráfico alto, una clave inexistente puede generar tanta carga como una popular — quizás más, porque nunca hay un resultado en caché que absorba las peticiones.

Con la caché negativa, el primer fallo llama al “solver”, obtiene un error y almacena ese error durante 30 segundos (o el TTL negativo que se haya definido). Durante los siguientes 30 segundos, todas las peticiones posteriores ven el fallo almacenado inmediatamente. El backend queda protegido.

Es una característica pequeña con una recompensa muy práctica, especialmente en sistemas donde el conjunto de claves “ausentes conocidas” es grande o donde un fallo del backend es temporal y reintentarlo cientos de veces por segundo no sirve de nada.

sequenceDiagram
    participant T1 as Hilo 1
    participant C as Caché
    participant T2 as Hilo 2
    participant B as Backend

    T1->>C: get_or_compute("clave-inexistente")
    C->>B: Llamada al Solver
    B-->>C: 404 / nullptr
    Note over C: Estado = FAILED (TTL=30s)
    C-->>T1: ComputedNegative

    T2->>C: get_or_compute("clave-inexistente")
    Note over C: FAILED, dentro del TTL
    C-->>T2: HitNegative (instantáneo, sin llamada al backend)

Se llama al backend una vez. Durante los siguientes 30 segundos, cada petición para esa clave obtiene un fallo inmediato en caché — sin llamadas redundantes.

Tiempos de vida más seguros bajo concurrencia Link to heading

El diseño separa la validez lógica de la vida útil física.

Los valores almacenados en caché se exponen a través de shared_ptr, lo que significa que un valor puede ser expulsado o invalidado por la caché sin volverse inseguro inmediatamente para el código que todavía lo está utilizando.

¿Por qué es importante concretamente? Sin esta separación, un hilo que lee un valor en caché podría colapsar si otro hilo lo expulsa en el momento equivocado. Ese es un error de “uso después de liberación” (use-after-free), una de las clases más peligrosas de errores de memoria en C++, y que solo se manifestaría bajo condiciones de temporización específicas en producción.

La caché también mantiene un recuento de referencias atómico interno en cada entrada. Una entrada no puede ser expulsada si algún hilo está trabajando activamente con ella. Este invariante es impuesto por el modelo formal (más sobre esto abajo) y fue el origen de la corrección de un error real.

sequenceDiagram
    participant A as Hilo A
    participant C as Caché
    participant E as Expulsor

    A->>C: get_or_compute(clave)
    Note over C: acquire() → refcount = 2
    A->>A: Usando el valor (seguro)
    E->>C: Necesito expulsar esta entrada
    Note over C: refcount = 2 > 1 → ¡saltar!
    E->>C: Expulsa una entrada diferente en su lugar
    A->>C: Hecho → release() → refcount = 1
    Note over C: Entrada segura para futura expulsión

El recuento de referencias actúa como un escudo: mientras cualquier hilo esté usando activamente una entrada, el expulsor la ignora. No es posible que ocurra un “use-after-free”.

Una caché con estados explícitos Link to heading

Internamente, las entradas pasan por estados explícitos: calculando, listo, fallido e invalidado.

stateDiagram-v2
    [*] --> EMPTY
    EMPTY --> COMPUTING: Fallo de caché
    COMPUTING --> READY: Éxito
    COMPUTING --> FAILED: Fallo
    READY --> READY: Acierto (refrescar TTL)
    FAILED --> FAILED: Acierto (refrescar TTL)
    READY --> INVALIDATED: invalidate()
    FAILED --> INVALIDATED: TTL Expirado
    INVALIDATED --> EMPTY: Expulsión LRU
    READY --> EMPTY: TTL Expirado + Expulsión

Observa los bucles sobre Ready y Failed: cada acierto de caché refresca el TTL, implementando una ventana deslizante que mantiene vivas las entradas accedidas con frecuencia. Esa claridad importa.

Hace que la implementación sea más disciplinada, las reglas de concurrencia más fáciles de razonar y el comportamiento previsto más fácil de verificar.

Cuando la verificación formal detecta un error real Link to heading

Lo que hace que este proyecto sea especialmente interesante para mí es que no se detiene en las pruebas.

El repositorio incluye un modelo formal Promela/SPIN que explora exhaustivamente unos 3,5 millones de estados del protocolo de concurrencia. Ese modelo verificó 23 aserciones de seguridad y 10 propiedades de vitalidad (liveness), incluyendo la terminación, la ausencia de inanición y la garantía de que cada clave solicitada se calcula eventualmente.

Pero la mejor parte de la historia no son los checks en verde. El modelo realmente encontró un error real.

El código C++ original tenía una función de expulsión que comprobaba si una entrada estaba en estado Computing antes de expulsarla — pero no comprobaba el recuento de referencias. Eso significaba que una entrada podía ser expulsada mientras otro hilo la estaba usando activamente, lo que llevaba a un potencial “use-after-free”. El modelo Promela ya tenía la protección correcta (refcount <= 1 antes de la expulsión), y cuando SPIN exploró todos los entrelazados, expuso la falta de esa comprobación en la implementación C++.

Este es exactamente el tipo de error de concurrencia que sobrevive a las revisiones de código y a las pruebas convencionales — requiere un entrelazado específico de expulsión y referencia activa para dispararse. El modelo formal lo detectó antes de que llegara a producción.

Ese único descubrimiento justifica el esfuerzo de construir el modelo.

Una mirada honesta a los compromisos (tradeoffs) Link to heading

Ningún diseño está exento de compromisos, y reconocerlos es importante.

• Mutex global: El bloqueo único que protege la estructura funciona bien cuando el calculador es el verdadero cuello de botella (que suele serlo), pero podría convertirse en un punto de contención bajo miles de hilos con tasas de fallos muy altas. Se planea la fragmentación (sharding) en N sub-caches.
• Dependencia de Aleph-w: La caché utiliza las estructuras de datos intrusivas de Aleph-w para mejorar el rendimiento, pero esto hace que la integración sea más difícil que la de una librería “header-only”. Se está considerando un modo autónomo.
• Sin benchmarks todavía: A pesar de la validación en producción a 100K peticiones/segundo, el repositorio carece de micro-benchmarks. Esta es la próxima adición planeada.

Estas son limitaciones reales. No socavan el diseño central, pero condicionan su adopción hoy en día.

Por qué vale la pena preocuparse por esto Link to heading

La infraestructura como esta rara vez atrae la misma atención que las funciones orientadas al cliente, pero tiene un apalancamiento enorme.

Una mejor caché concurrente puede significar:

• menos llamadas duplicadas al backend,
• menos desperdicio bajo tráfico por ráfagas,
• latencia más predecible,
• comportamiento de memoria más seguro,
• y mayor confianza en la corrección — no solo por las pruebas, sino por la verificación formal exhaustiva.

Ese es el tipo de mejora de ingeniería que ayuda silenciosamente a todo lo que hay encima.

Qué sigue Link to heading

El proyecto está disponible de forma abierta en lrleon/cpp-cache. Si quieres probarlo, las instrucciones de construcción muestran cómo compilar y ejecutar las pruebas en menos de cinco minutos.

Los próximos pasos planeados incluyen:

• Benchmarks con recuento de hilos, espacio de claves y tasa de fallos configurables.
• Fragmentación (Sharding) para escalabilidad lineal con los núcleos.
• Una variante try_find() que devuelva inmediatamente si se está calculando una entrada.
• Opción de compilación autónoma sin Aleph-w.

Las contribuciones, el feedback y las críticas constructivas son bienvenidos.

Reflexión final Link to heading

Lo que más me gusta de esta versión de cpp-cache es que refleja una idea madura de la ingeniería de rendimiento.

No se trata solo de almacenar resultados más rápido. Se trata de controlar la contención de forma inteligente, proteger al sistema del comportamiento de manada y tratar la corrección como parte del trabajo de rendimiento, no como algo secundario.

El hecho de que la verificación formal haya detectado un error real en la ruta de expulsión es el tipo de historia que hace que la inversión en rigor valga la pena. No todos los proyectos necesitan un modelo Promela — pero cuando estás construyendo infraestructura concurrente de la que dependen otros sistemas, el coste de un error sutil en producción supera con creces el coste de construir un modelo.

Ese es exactamente el tipo de inversión en infraestructura que da sus frutos con el tiempo.