Estrategias de caché y sus trampas

Por qué usar una caché y qué cuesta

Una caché guarda una copia de los datos en algún lugar más rápido o más cercano que su ubicación original, para que las solicitudes repetidas no paguen el precio completo cada vez. La Sección 0.2 presentó la idea como un intercambio de espacio por tiempo. A escala de arquitectura, el intercambio es más interesante, porque una caché cambia tres cualidades a la vez. Reduce la latencia (una búsqueda en Redis en el mismo centro de datos suele tardar mucho menos de un milisegundo; una consulta a la base de datos que une cinco tablas puede tardar decenas de milisegundos). Aumenta el rendimiento (throughput) y protege la base de datos, porque cada acierto (hit) es una consulta que la base de datos nunca ve. Y puede mejorar la disponibilidad, porque una caché capaz de servir datos algo antiguos sigue funcionando mientras la fuente está lenta o caída.

El precio se paga en corrección y en complejidad. Una caché es una segunda copia de los datos, y dos copias pueden no coincidir. Por tanto, toda caché encarna una decisión sobre cuán desactualizada puede estar una respuesta, y para quién. Una carta de restaurante con cinco minutos de antigüedad es aceptable; un saldo bancario con cinco minutos de antigüedad, mostrado a un cliente que decide si puede permitirse un pago, no lo es. Las cachés también añaden un componente que puede fallar, consumen memoria que cuesta dinero y crean nuevos modos de fallo, como las estampidas y los arranques en frío, que no existen sin ellas. Por eso la primera pregunta no es ¿qué caché?, sino ¿qué puede estar desactualizado, cuánto y qué pasa si lo está?

La eficacia de una caché se mide por su tasa de aciertos: los aciertos divididos entre todas las búsquedas. La tasa de aciertos depende de lo sesgado que sea el patrón de acceso. El tráfico de lectura de la mayoría de los sistemas de consumo está muy sesgado (una pequeña fracción de los restaurantes, productos o cuentas recibe la mayoría de las lecturas), así que una caché que contiene un pequeño porcentaje de los datos a menudo puede responder a la mayoría de las lecturas. El acceso uniformemente aleatorio, en cambio, se aprovecha mal de la caché hagas lo que hagas.

Los cinco patrones clásicos

Los patrones de caché se diferencian en quién carga la caché, en cuándo llegan las escrituras a la fuente y, por tanto, en cuán desactualizados y cuán duraderos pueden ser los datos. La tabla los compara; los párrafos que la siguen explican dónde encaja cada uno.

Cache-aside es la opción por defecto por una buena razón: es fácil razonar sobre él y falla de forma segura, porque si la caché desaparece la aplicación simplemente lee la base de datos (más despacio). Read-through traslada la misma lógica a una biblioteca o un producto de caché, lo que resulta ordenado, pero no cambia el comportamiento. Write-through conviene para los datos que se leen poco después de escribirse, como la sesión de un usuario o su carrito de la compra. Write-behind es el arriesgado: convierte la caché en el sistema de registro temporal, así que solo es apropiado cuando perder los últimos segundos de escrituras es aceptable (contadores de visitas, eventos de analítica, puntuaciones de juegos) o cuando la propia caché está replicada y es duradera. Nunca uses write-behind para el dinero. Refresh-ahead es una optimización para un pequeño conjunto de claves muy solicitadas, como la lista de restaurantes de la página de inicio en una ciudad con mucha actividad.

import json, random

TTL = 300  # seconds

def get_menu(restaurant_id):
    key = f"menu:{restaurant_id}:v3"            # version the key with the data shape
    cached = cache.get(key)
    if cached is not None:
        return json.loads(cached)                # hit
    with cache.lock(f"lock:{key}", timeout=5):  # coalesce: one loader per key
        cached = cache.get(key)                  # someone may have filled it meanwhile
        if cached is not None:
            return json.loads(cached)
        menu = db.load_menu(restaurant_id)       # miss: go to the system of record
        jitter = random.randint(0, TTL // 10)    # spread expiry times out
        cache.set(key, json.dumps(menu), ex=TTL + jitter)
        return menu

def update_price(restaurant_id, item_id, price):
    db.update_price(item_id, price)              # 1. change the system of record
    cache.delete(f"menu:{restaurant_id}:v3")     # 2. invalidate, do not overwrite

Tiempo de vida e invalidación

Hay dos formas de impedir que una caché sirva datos que han cambiado. La primera es un tiempo de vida (TTL): cada entrada caduca tras un periodo fijo, lo que acota la desactualización sin ninguna coordinación. Un TTL de cinco minutos en las cartas significa que un cambio de precio es visible en todas partes en un plazo de cinco minutos. La segunda es la invalidación explícita: cuando la fuente cambia, algo borra o actualiza la copia en caché. La invalidación da datos más frescos, pero exige que cada ruta del código que modifica los datos conozca todas las cachés que los contienen, que es justo lo que falla a medida que los sistemas crecen. En los sistemas distribuidos, la invalidación suele estar dirigida por eventos: el servicio de carta publica MenuChanged y cada servicio que tiene una copia borra su entrada. La mayoría de los diseños profesionales combinan ambas: invalidan al producirse un cambio para tener datos frescos y mantienen un TTL como red de seguridad para la invalidación que se haya escapado.

La dificultad queda recogida en una frase ingeniosa atribuida a Phil Karlton, de Netscape: Solo hay dos cosas difíciles en informática: la invalidación de caché y ponerles nombre a las cosas. Es difícil porque la invalidación es un problema de sistemas distribuidos disfrazado. La escritura en la base de datos y el borrado en la caché son dos operaciones en dos sistemas sin una transacción compartida, así que una puede tener éxito mientras la otra falla, y las operaciones de distintas solicitudes pueden intercalarse.

Dos reglas evitan la mayoría de los problemas. Primera: en una escritura, actualiza la base de datos y luego borra la entrada de la caché; no escribas el nuevo valor en la caché. Dos escritores concurrentes que actualizan cada uno la caché pueden terminar en el orden inverso al de sus commits en la base de datos y dejar el valor más antiguo en caché indefinidamente, mientras que un borrado solo puede causar un fallo adicional. Segunda: acepta que incluso borrar al escribir deja una pequeña condición de carrera, que se muestra a continuación, y acótala con un TTL. El artículo de Facebook de 2013 sobre el escalado de memcache describe los leases (concesiones) para este caso: la caché da un token al cliente que tuvo el fallo y rechaza la escritura posterior de ese cliente si la clave se borró entretanto.

Estampidas y el thundering herd

Una cache stampede (estampida de caché) se produce cuando una entrada popular caduca, o un nodo de caché se reinicia vacío, y cientos de solicitudes concurrentes fallan en el mismo instante. Cada una va a la base de datos a calcular el mismo valor, y la base de datos, dimensionada para la tasa de fallos normal de la caché, se ve desbordada. Las respuestas más lentas hacen que se acumulen más solicitudes, y la sobrecarga puede propagarse en cascada. El fenómeno relacionado del thundering herd (manada en estampida) describe a muchos clientes en espera que se despiertan a la vez para competir por un único recurso. Facebook informó de que, para un conjunto de claves especialmente propensas a esto, los leases redujeron la tasa máxima de consultas a la base de datos de 17 000 a 1300 por segundo.

Las defensas se combinan bien. La agrupación de solicitudes (request coalescing), también llamada single flight, permite que solo una solicitud por clave vaya a buscar el dato a la fuente mientras las demás esperan su resultado; dentro de un proceso es un mapa de futuros en curso, y entre procesos, un bloqueo breve en la caché, como en el código anterior. La caducidad con jitter añade una cantidad aleatoria a cada TTL para que las entradas escritas a la vez (tras un despliegue o un vaciado de la caché) no caduquen a la vez. Stale-while-revalidate sirve el valor caducado a todos mientras una solicitud en segundo plano obtiene uno nuevo, lo que elimina por completo el pico de latencia cuando una ligera desactualización es aceptable. La caducidad anticipada probabilística (Vattani, Chierichetti y Lowenstein, VLDB 2015) hace que cada lector decida al azar, con una probabilidad que aumenta a medida que se acerca la caducidad, si actualiza antes de tiempo, de modo que normalmente una solicitud actualiza la entrada antes de que caduque de verdad. Por último, el precalentamiento de una caché nueva a partir de una lista de claves muy solicitadas antes de que reciba tráfico evita la estampida del arranque en frío tras un reinicio.

Niveles de caché

Hay cachés en todos los niveles entre el usuario y el disco, y una solicitud la responde el primer nivel que tiene una copia utilizable. El navegador mantiene una caché privada controlada por cabeceras HTTP. Una red de distribución de contenidos (CDN) mantiene copias compartidas en ubicaciones del borde (edge) cercanas a los usuarios, ideal para imágenes, scripts y respuestas de API públicas como las cartas. Un proxy inverso en el origen (Nginx, Varnish) puede almacenar en caché respuestas completas durante unos segundos, lo que se llama microcaching y puede absorber un pico repentino. La aplicación almacena en caché objetos calculados, ya sea en el propio proceso (lo más rápido, pero cada instancia tiene su propia copia y no coinciden entre sí) o en una caché compartida como Redis o Memcached. La base de datos almacena en caché páginas en memoria (los shared buffers de PostgreSQL, el buffer pool de InnoDB) y puede precalcular resultados costosos en vistas materializadas.

Cuanto más lejos de los datos, mayor es el ahorro por acierto y más difícil la invalidación. Puedes borrar una clave de Redis en un milisegundo; puedes purgar una CDN, más despacio; no puedes llegar en absoluto al navegador de un cliente, así que el max-age que envíes es una promesa con la que tendrás que vivir. Por eso las duraciones largas en el navegador se usan para archivos cuya URL cambia cuando cambia su contenido (app.3f9a1c.js), y las cortas, o la revalidación, para todo lo demás.

Cabeceras de caché HTTP

HTTP tiene un modelo de caché completo, definido en el RFC 9111 (junio de 2022), y usarlo bien puede eliminar carga antes de que llegue a tus servidores. Cache-Control: max-age=60 permite que cualquier caché reutilice una respuesta durante 60 segundos; s-maxage lo sustituye para las cachés compartidas, como las CDN; private prohíbe que las cachés compartidas la almacenen (úsalo para todo lo personal); no-cache, de forma confusa, significa almacénala, pero consulta con el servidor antes de cada reutilización; y no-store significa no guardes nunca una copia, el ajuste correcto para los saldos y los extractos bancarios. Las extensiones stale-while-revalidate y stale-if-error (RFC 5861, 2010) aplican a nivel HTTP las ideas sobre estampidas y disponibilidad vistas antes.

Cuando una copia en caché está desactualizada, el cliente no necesita descargarla de nuevo. Un validador le permite preguntar si ha cambiado algo: el servidor envía con la respuesta un ETag (un identificador de versión opaco) o una fecha Last-Modified, y más tarde el cliente envía If-None-Match o If-Modified-Since. Si nada ha cambiado, el servidor responde 304 Not Modified sin cuerpo, lo que ahorra ancho de banda y, a menudo, la mayor parte del trabajo del servidor. Estas solicitudes condicionales se definen en el RFC 9110. La cabecera Vary indica a las cachés qué cabeceras de la solicitud (como Accept-Language) producen respuestas distintas, para que nunca se sirva una carta en francés a una solicitud en inglés.

GET /restaurants/17/menu HTTP/1.1
Host: api.example-food.test

HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: public, max-age=60, s-maxage=300, stale-while-revalidate=30
ETag: "menu-17-v42"

... 18 KB of menu JSON ...

# 100 seconds later the copy is past max-age plus the stale-while-revalidate
# window, so the browser must revalidate before using it:
GET /restaurants/17/menu HTTP/1.1
If-None-Match: "menu-17-v42"

HTTP/1.1 304 Not Modified
Cache-Control: public, max-age=60, s-maxage=300, stale-while-revalidate=30
ETag: "menu-17-v42"

# A bank balance, by contrast, must never sit in any cache:
Cache-Control: no-store

Desalojo, dimensionamiento y riesgos de consistencia

Una caché es más pequeña que los datos que tiene detrás, así que, cuando se llena, debe desalojar algo. Menos recientemente usado (LRU) desaloja la entrada que lleva más tiempo sin tocarse y funciona bien cuando el uso reciente predice el uso futuro. Menos frecuentemente usado (LFU) desaloja la entrada que se usa con menos frecuencia y resiste los recorridos puntuales (un informe nocturno que toca una vez cada restaurante vaciaría una caché LRU de sus entradas realmente muy solicitadas). Las cachés de producción se aproximan a ambas: Redis, por ejemplo, toma una muestra de unas pocas claves y desaloja la mejor candidata entre ellas, y ofrece políticas como allkeys-lru, allkeys-lfu y volatile-ttl. Su política por defecto, noeviction, rechaza las escrituras cuando la memoria está llena, lo que conviene a Redis usado como almacén, pero no como caché, así que configura la política de forma deliberada.

Más allá de la desactualización, las cachés introducen riesgos de consistencia más sutiles. Un usuario que cambia su dirección de entrega y luego ve la antigua, porque la lectura vino de una caché que otra instancia aún no había invalidado, sufre la ruptura de la garantía de leer sus propias escrituras (Sección 7.4); una solución habitual es saltarse la caché para las escrituras recientes del propio usuario. Las cachés en proceso de muchas instancias no coinciden entre sí, así que solicitudes consecutivas enviadas a instancias distintas pueden mostrar un valor que retrocede. Almacenar en caché un error o un resultado vacío sin un TTL corto convierte una interrupción breve en una larga. Almacenar en caché datos que mezclan usuarios (una página con el nombre del cliente, guardada en caché solo bajo la URL) filtra datos personales al siguiente visitante, una clase de incidente de seguridad bien conocida. Y las claves de caché deben incluir todo lo que cambia la respuesta: el inquilino (tenant), el idioma, la moneda, los permisos y la versión del formato de los datos.