4. Políticas de evicción y LRU

Descripción

El patrón cache-aside de la lección anterior tiene una consecuencia que hay que enfrentar de cara: la caché se llena sin parar. Cada link nuevo que alguien visita entra a la caché en su primer miss, y nadie lo saca. Pero la RAM es finita —un servidor de Redis tiene, digamos, 8 o 16 GB, no infinitos—, así que tarde o temprano la caché se topa con su límite. En ese momento, para meter un dato nuevo, hay que sacar uno viejo. Esa expulsión se llama evicción (del inglés eviction, desalojo), y la regla que decide a quién se desaloja es la política de evicción. Elegirla bien es lo que separa una caché con hit ratio del 90% de una con hit ratio del 40%, usando exactamente la misma RAM.

Esta lección recorre las políticas —LRU, LFU, FIFO, random— y explica por qué LRU (Least Recently Used, "el menos usado recientemente") es el default sensato para la enorme mayoría de los sistemas, incluido Enlace. Vas a ver LRU no como una definición, sino en acción: una simulación pequeña, corrida en Python, que te muestra paso a paso qué entra, qué se desaloja, y —lo más importante— cuántas lecturas a la base de datos evita comparado con no tener nada. Al final vas a saber qué significan las maxmemory-policy de Redis (allkeys-lru, volatile-lru…) y cuál le toca a Enlace.

Conexión con el módulo: la lección 3 llenó la caché; esta decide qué tirar cuando se desborda. La lección 5 medirá cómo la política de evicción se traduce en hit ratio, y de ahí en latencia. La lección 6 calculará cuánta RAM hace falta para que la evicción casi nunca tenga que actuar (si el working set cabe entero, no desalojas nada caliente). Evicción y tamaño son las dos caras de la misma moneda: o tienes RAM de sobra, o tienes que elegir bien a quién sacrificas.

El clóset de temporada

Piénsalo así. Tienes un clóset de tamaño fijo y más ropa de la que cabe. No puedes agrandar el clóset (la RAM es finita), así que cada vez que compras una prenda nueva y ya está lleno, tienes que sacar una para hacer espacio. La pregunta es: ¿cuál sacas? De esa decisión depende si tu clóset termina lleno de la ropa que te pones o lleno de la que nunca usas.

Hay varias estrategias. Podrías sacar la que no te has puesto en más tiempo —si no la usaste en meses, probablemente no la vas a extrañar—: esa es LRU. Podrías sacar la que te pones con menos frecuencia total —llevas la cuenta de cuántas veces usaste cada prenda y sacas la de menor cuenta—: esa es LFU. Podrías sacar la que compraste primero, sin importar si la usas o no —la más vieja en entrar—: esa es FIFO. O podrías cerrar los ojos y sacar una al azar: esa es random. Las cuatro hacen espacio; solo algunas hacen espacio inteligente, sacando lo que de verdad no vas a necesitar.

LRU —"saca lo que no has usado en más tiempo"— es la que mejor funciona para la ropa y para casi todo lo demás, y la razón tiene nombre: localidad temporal. Lo que usaste hace poco tiendes a volver a usarlo pronto (la sudadera de esta semana), y lo que no tocas hace rato probablemente ya no lo necesitas (el abrigo de hace tres estaciones). En Enlace pasa exactamente lo mismo: un link que alguien visitó hace un segundo probablemente reciba más visitas en los próximos segundos (está circulando ahora), mientras que uno que nadie toca hace horas seguramente ya se enfrió. LRU apuesta a esa regularidad, y por eso acierta tanto.

Cuando la caché se llena, hay que desalojar algo para meter lo nuevo. La política de evicción decide a quién. LRU —desalojar lo menos usado recientemente— gana en la mayoría de los casos porque explota la localidad temporal: lo recién usado se vuelve a usar pronto, lo frío ya no.

Las políticas, una por una

Antes de simular, tengamos claras las cuatro candidatas, qué llevan de cuenta y cuál es su debilidad:

Política	Qué desaloja	Qué necesita recordar	Debilidad
LRU (Least Recently Used)	La entrada usada hace más tiempo	El orden de último acceso	Un barrido de datos fríos (un bot recorriendo links raros) puede empujar afuera a los calientes
LFU (Least Frequently Used)	La entrada con menos accesos totales	Un contador por entrada	Un dato viejo con muchos accesos acumulados se queda aunque ya nadie lo pida ("caché contaminada")
FIFO (First In, First Out)	La que entró primero, sin mirar el uso	El orden de inserción	Ignora si un dato viejo sigue siendo popular; puede tirar algo caliente solo por ser antiguo
Random	Una al azar	Nada	No usa ninguna información; simple y barata, pero desperdicia hits evitables

Fíjate en el tradeoff entre LRU y LFU, que es el debate clásico. LRU solo recuerda cuándo se usó por última vez cada dato; es barato y reacciona rápido a los cambios de moda (si un link deja de circular, cae al fondo y se desaloja pronto). Su punto débil es el barrido: si un proceso recorre de golpe un montón de links fríos (por ejemplo, un bot escaneando códigos), cada uno entra como "recién usado" y empuja a los calientes hacia la salida, aunque los fríos no se vuelvan a pedir jamás. LFU recuerda cuántas veces se usó cada dato, así que resiste el barrido (un link frío con un solo acceso no desaloja a uno caliente con miles). Pero LFU tiene su propia trampa: un dato que fue popularísimo el mes pasado acumuló tantos accesos que se queda pegado aunque ya nadie lo pida —la caché se "contamina" de viejas glorias—. Por eso Redis ofrece variantes de LFU con decaimiento, pero eso ya es afinación fina. Para Enlace, cuyo tráfico sigue modas que cambian (un link es viral esta semana y se olvida la próxima), LRU es la elección natural: reacciona rápido a lo que está caliente ahora.

Simulando una LRU

La mejor forma de entender LRU es verla funcionar. Vamos a construir una caché LRU minúscula —capacidad 3, para que la evicción ocurra seguido y se vea— y a alimentarla con una secuencia de short_code donde uno, aX9, es viral y se repite. En Python, una LRU se implementa limpiamente con un OrderedDict, que recuerda el orden de inserción y permite mover una clave al final cuando se usa:

# lru_sim.py — una caché LRU de capacidad 3, paso a paso
from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = OrderedDict()          # orden: viejo (izq) -> nuevo (der)
        self.hits = 0
        self.misses = 0
        self.evictions = []

    def get(self, key):
        if key in self.store:
            self.store.move_to_end(key)     # usarlo lo vuelve "reciente"
            self.hits += 1
            return self.store[key]
        self.misses += 1
        return None

    def put(self, key, value):
        if key in self.store:
            self.store.move_to_end(key)
        self.store[key] = value
        if len(self.store) > self.capacity:
            evicted, _ = self.store.popitem(last=False)   # saca el mas viejo
            self.evictions.append(evicted)


# aX9 es viral: se repite. Cache-aside: en cada miss, se puebla desde la BD.
sequence = ["aX9", "bK2", "cP7", "aX9", "dR4", "aX9", "bK2", "eT1", "aX9"]
cache = LRUCache(3)
db_reads = 0

for i, code in enumerate(sequence, 1):
    val = cache.get(code)
    if val is None:                          # MISS -> leer BD y poblar
        db_reads += 1
        cache.put(code, f"url_of_{code}")
        action = "MISS -> lee BD + puebla"
    else:                                    # HIT -> se evita la BD
        action = "HIT  -> evita la BD"
    contents = " ".join(cache.store.keys())
    print(f"{i} | {code} | {action:24} | cache: {contents}")

n = len(sequence)
print(f"\npeticiones = {n} | hits = {cache.hits} | misses = {cache.misses}")
print(f"hit ratio  = {cache.hits/n:.1%}")
print(f"evictions  = {cache.evictions}")
print(f"lecturas a la BD: SIN cache = {n}, CON cache = {db_reads} "
      f"({n - db_reads} evitadas)")

La LRUCache mantiene sus claves ordenadas de más vieja (izquierda) a más reciente (derecha). Cada get que acierta mueve la clave al extremo reciente (move_to_end), así que "recién usado" siempre está a la derecha y "hace más tiempo que no se usa" siempre a la izquierda. Cuando un put desborda la capacidad, popitem(last=False) saca la de la izquierda —la menos usada recientemente—. La secuencia mete a aX9 como el link viral que se repite, y capacidad 3 fuerza evicciones para que veas a LRU decidir.

Qué esperar. Con python lru_sim.py:

1 | aX9 | MISS -> lee BD + puebla   | cache: aX9
2 | bK2 | MISS -> lee BD + puebla   | cache: aX9 bK2
3 | cP7 | MISS -> lee BD + puebla   | cache: aX9 bK2 cP7
4 | aX9 | HIT  -> evita la BD       | cache: bK2 cP7 aX9
5 | dR4 | MISS -> lee BD + puebla   | cache: cP7 aX9 dR4
6 | aX9 | HIT  -> evita la BD       | cache: cP7 dR4 aX9
7 | bK2 | MISS -> lee BD + puebla   | cache: dR4 aX9 bK2
8 | eT1 | MISS -> lee BD + puebla   | cache: aX9 bK2 eT1
9 | aX9 | HIT  -> evita la BD       | cache: bK2 eT1 aX9

peticiones = 9 | hits = 3 | misses = 6
hit ratio  = 33.3%
evictions  = ['bK2', 'cP7', 'dR4']

Léelo con calma, porque cada línea cuenta una historia. Mira el paso 4: se pide aX9, es un hit, y observa cómo aX9 salta al final de la caché (bK2 cP7 aX9) —usarlo lo volvió el más reciente, así que ahora es el último candidato a ser desalojado—. Esa es la mecánica de LRU protegiendo lo caliente. Mira ahora el paso 5: entra dR4, la caché estaba llena, y ¿a quién desaloja? A bK2, que era el que llevaba más tiempo sin usarse —no a aX9, que acababa de recibir un hit—. LRU sacrificó al frío y protegió al viral. Fíjate también en el paso 3→5: aX9 sobrevivió a dos evicciones (las de bK2 y cP7) precisamente porque sus hits lo mantuvieron fresco. Y al final: de 9 peticiones, se evitaron 3 lecturas a la base de datos (los tres hits). Con una caché de solo 3 ranuras y un dato viral, un tercio de las lecturas ya no molestan a la base de datos.

Por qué el hit ratio de la simulación es "solo" 33%

No te asustes con el 33.3%: es un artefacto de haber hecho la caché deliberadamente diminuta (capacidad 3) para que la evicción se viera. Con una caché tan chica, solo cabe el viral y dos vecinos, así que la mayoría de los links distintos entran fríos y pagan su miss. En Enlace la caché no es de 3 ranuras: es de cientos de miles de entradas (la lección 6 calcula ~666,667), suficiente para que todo el working set caliente quepa. Cuando el working set cabe entero, la evicción casi no actúa sobre datos calientes —solo desaloja los que ya se enfriaron—, y el hit ratio sube al 90% o más. La simulación no dice "LRU da 33%"; dice "LRU protege lo caliente incluso con casi nada de espacio, y evita lecturas reales". Con espacio de verdad, esa misma lógica da un hit ratio excelente. Esa relación entre tamaño y hit ratio es justo lo que dimensionas en la lección 6.

Evicción en Redis: las maxmemory-policy

En el mundo real no implementas la LRU a mano: Redis (nuestro cache) la trae de fábrica. Le pones un límite de memoria con maxmemory (por ejemplo, maxmemory 4gb) y le dices con maxmemory-policy qué hacer cuando lo alcanza. Las opciones que importan:

maxmemory-policy	Qué hace
noeviction	No desaloja nada: cuando se llena, rechaza las escrituras nuevas con error. La fuente de verdad no está en riesgo, pero la caché deja de aceptar datos nuevos.
allkeys-lru	Desaloja con LRU entre todas las claves. La elección típica para una caché pura como la de Enlace.
allkeys-lfu	Desaloja con LFU (menos frecuente) entre todas las claves. Útil si el tráfico es muy estable.
volatile-lru	Desaloja con LRU solo entre las claves que tienen TTL (las marcadas para expirar). Las claves sin TTL se quedan.
allkeys-random	Desaloja al azar. Barato, pero desperdicia hits evitables.

Para Enlace, donde el cache es una caché pura (todo su contenido es reconstruible desde la base de datos y todo es candidato legítimo a desalojo), la elección natural es allkeys-lru: aplica LRU sobre todas las claves, que es exactamente la política del clóset de temporada. volatile-lru tiene sentido cuando mezclas en el mismo Redis datos "cacheables" (con TTL) y datos que no quieres perder (sin TTL) —pero en una caché pura no deberías tener datos que no puedas reconstruir, así que allkeys-lru es más simple y más seguro—. Y noeviction es lo que no quieres en una caché: convierte un problema de rendimiento (caché llena) en un error (escrituras rechazadas). Una nota honesta: la LRU de Redis es aproximada —muestrea unas pocas claves y desaloja la más vieja de la muestra, en vez de rastrear el orden global exacto— porque la LRU perfecta costaría memoria y CPU; el resultado es casi idéntico al de la LRU exacta que simulaste, a una fracción del costo.

Errores comunes

Dejar la caché en noeviction sin darse cuenta. Qué pasa: alguien monta Redis con la configuración por defecto (que en algunas versiones es noeviction), la caché se llena, y de pronto las escrituras a la caché empiezan a fallar con "OOM command not allowed". El sistema no se cae —la base de datos sigue siendo la verdad—, pero la caché deja de poblarse y el hit ratio se estanca. Por qué pasa: noeviction suena seguro ("no borra nada") pero para una caché es justo lo contrario de lo que quieres. Cómo detectarlo: si ves errores de OOM en Redis o el hit ratio deja de subir al llenarse, revisa la política. Cómo corregirlo: para una caché pura, pon allkeys-lru (o allkeys-lfu). Una caché debe poder tirar lo viejo para meter lo nuevo; esa es su naturaleza.

Elegir LFU creyendo que "más frecuente" siempre gana. Qué pasa: alguien razona "quiero quedarme con lo más pedido, así que LFU" y configura allkeys-lfu. Meses después, la caché está llena de links que fueron virales hace tiempo y acumularon millones de accesos, pero que ya nadie visita —desalojan a los links calientes de hoy, que apenas empiezan a acumular cuenta—. El hit ratio baja. Por qué pasa: LFU premia la frecuencia histórica, y sin decaimiento, las viejas glorias nunca sueltan su lugar. Cómo detectarlo: si tu tráfico sigue modas que cambian (como Enlace) y el hit ratio empeora con LFU, es la contaminación de la caché. Cómo corregirlo: para tráfico con modas cambiantes, LRU reacciona mejor —lo que dejó de circular cae al fondo y se desaloja pronto—. LFU brilla en tráfico muy estable; LRU, en tráfico que cambia. Enlace es lo segundo.

Confundir "la caché se llenó" con "la caché falló". Qué pasa: alguien ve que la caché está al 100% de su memoria y entra en pánico, creyendo que algo se rompió. Pero una caché debe estar llena: ese es su estado normal de trabajo. Una caché medio vacía es una caché desperdiciada (RAM pagada y sin usar). Por qué pasa: se asocia "lleno" con "problema", como con un disco. Cómo detectarlo: mira el hit ratio y la tasa de evicción, no el porcentaje de memoria. Una caché llena con hit ratio alto y evicción moderada está sana. Cómo corregirlo: cambia la métrica que miras. "Llena" es normal; lo que importa es qué está tirando la evicción. Si tira datos calientes (evicción alta y hit ratio bajando), es que la caché es demasiado chica para el working set —y eso se arregla con más RAM, que es lo que dimensionas en la lección 6—, no cambiando la política.

Ejercicios

Ejercicio 1 — Traza la LRU a mano. Con una caché LRU de capacidad 2 (más chica todavía) y arrancando vacía, traza esta secuencia de accesos: A, B, A, C, B. Para cada uno di si es hit o miss, qué queda en la caché (de más viejo a más reciente) y, cuando haya evicción, a quién se desaloja.

Ver solución

Capacidad 2, arrancando vacía:

#	acceso	resultado	evicción	caché (viejo→nuevo)
1	A	MISS	—	A
2	B	MISS	—	A B
3	A	HIT	—	B A (A salta a reciente)
4	C	MISS	B	A C (B era el más viejo)
5	B	MISS	A	C B (A era el más viejo)

Hits: 1. Misses: 4. Hit ratio = 1/5 = 20%.

El momento clave es el paso 4. La caché estaba llena con A y B, pero en el paso 3 se usó A, lo que lo volvió el más reciente y empujó a B al fondo. Así que cuando entra C y hay que desalojar, cae B —el menos usado recientemente— y no A. LRU protegió a A porque se había usado hace poco. Si la política hubiera sido FIFO (desalojar el que entró primero, sin mirar el uso), habría caído A en el paso 4, aunque se acababa de usar —y eso habría sido peor—. Esta es, en miniatura, la ventaja de LRU sobre FIFO: usar un dato lo protege.

Ejercicio 2 — El barrido que envenena LRU. LRU tiene un punto débil: un "barrido" de datos fríos. Imagina una caché LRU de capacidad 3 que tiene cacheados tres links calientes (H1, H2, H3, que se piden a cada rato). De pronto, un bot pide cinco links fríos distintos (F1, F2, F3, F4, F5) que nunca se volverán a pedir. Después de eso, ¿qué queda en la caché, y qué pasó con los links calientes? ¿Qué política habría resistido mejor?

Ver solución

La caché tenía H1 H2 H3. El bot pide cinco fríos, cada uno un miss que puebla y desaloja:

• F1 entra → desaloja H1 → H2 H3 F1
• F2 entra → desaloja H2 → H3 F1 F2
• F3 entra → desaloja H3 → F1 F2 F3
• F4 entra → desaloja F1 → F2 F3 F4
• F5 entra → desaloja F2 → F3 F4 F5

Al final la caché contiene F3 F4 F5 —tres links fríos que nunca se volverán a pedir— y los tres calientes H1, H2, H3 fueron desalojados. La próxima vez que alguien pida H1, será un miss, aunque H1 sea popularísimo. El barrido "envenenó" la caché: LRU trató a cada link frío como "recién usado" y dejó que empujaran a los calientes.

LFU habría resistido mejor: H1, H2, H3 tienen muchos accesos acumulados, y cada frío tiene solo uno, así que LFU no habría desalojado a los calientes por culpa de fríos de un solo uso. Este es exactamente el caso donde LFU gana. En la práctica, Redis mitiga esto con variantes y muestreo, pero el ejercicio muestra por qué la elección de política depende del patrón de acceso: no hay una política que gane siempre. Para Enlace, donde los barridos de bots existen pero el working set caliente es grande y cabe en RAM, LRU con suficiente memoria aguanta bien —el barrido tendría que ser enorme para desalojar todo el working set—.

Ejercicio 3 — Elige la maxmemory-policy. Para cada escenario de Redis, di qué política de maxmemory-policy conviene y por qué en una frase. (a) La caché pura de Enlace: todo su contenido se puede reconstruir desde la base de datos. (b) Un Redis que mezcla datos cacheables (con TTL) y una lista de "sesiones activas" que NO quieres perder (sin TTL). (c) Un sistema donde prefieres que la caché rechace datos nuevos antes que borrar algo que ya tiene.

Ver solución

• (a) Enlace: allkeys-lru. Todo el contenido es reconstruible y todo es candidato legítimo a desalojo, así que aplicar LRU sobre todas las claves es lo correcto y lo más simple. Es la elección por defecto para una caché pura.
• (b) Mezcla con datos que no quieres perder: volatile-lru. Esta política solo desaloja entre las claves con TTL (las cacheables), y deja intactas las que no tienen TTL (las sesiones activas). Así proteges los datos no reconstruibles mientras dejas que los cacheables se turnen. (Aunque, idealmente, los datos que no puedes perder no deberían vivir en una caché volátil, sino en la base de datos.)
• (c) Rechazar antes que borrar: noeviction. Esta política no desaloja nada; cuando se llena, rechaza las escrituras nuevas con error. Rara vez es lo que quieres en una caché, pero existe para casos donde borrar un dato ya presente sería peor que no aceptar uno nuevo. Para una caché de rendimiento como la de Enlace, es justo lo que no eliges.

La regla mecánica: caché pura → allkeys-lru; caché mezclada con datos preciosos → volatile-lru (o, mejor, no mezcles); nunca borrar → noeviction (casi nunca deseable en una caché). Enlace vive en el primer caso, el más limpio.

Resumen y siguiente paso

En esta lección enfrentaste la consecuencia de que la RAM es finita: cuando la caché se llena, hay que desalojar algo para meter lo nuevo, y la política de evicción decide a quién. Recorriste las candidatas —LRU, LFU, FIFO, random— y viste por qué LRU es el default sensato: explota la localidad temporal (lo recién usado se vuelve a usar pronto), reacciona rápido a los cambios de moda, y es barata de mantener. Lo viste funcionar en una simulación de capacidad 3: LRU protegió al link viral aX9 (sus hits lo mantuvieron fresco) y sacrificó a los fríos, evitando 3 de 9 lecturas a la base de datos incluso con casi nada de espacio.

Entendiste el tradeoff LRU vs LFU —LRU reacciona a lo caliente ahora, LFU premia la frecuencia histórica y se contamina de viejas glorias— y por qué Enlace, con sus modas cambiantes, prefiere LRU. Y aterrizaste en Redis: maxmemory para el límite y allkeys-lru como la maxmemory-policy correcta para una caché pura, con noeviction como lo que hay que evitar.

Antes de avanzar deberías poder: explicar qué es la evicción y por qué es inevitable; definir LRU y por qué gana en la mayoría de los casos; describir el punto débil de LRU (el barrido de datos fríos) y cuándo LFU lo resiste mejor; y elegir allkeys-lru para Enlace justificándolo.

Lo que sigue es el número que hemos estado rodeando toda la lección: el hit ratio, y cómo se traduce en la latencia que siente el usuario. En la lección 5 vas a ejecutar la fórmula central del módulo —L = h·L_cache + (1−h)·L_db— para hit ratios de 0.5, 0.8, 0.9 y 0.95, y vas a ver por qué el salto de 0.9 a 0.95 casi divide la latencia a la mitad, aunque solo suba cinco puntos.

Recursos

• Redis — Key eviction (maxmemory-policy) — la documentación oficial de todas las políticas de evicción de Redis (allkeys-lru, volatile-lru, allkeys-lfu, noeviction…) y de cómo funciona su LRU aproximada por muestreo. La referencia exacta para configurar el cache de Enlace.
• collections.OrderedDict — documentación de Python — la estructura con la que implementamos la LRU de la simulación. move_to_end y popitem(last=False) son las dos operaciones que hacen que un OrderedDict se comporte como una caché LRU exacta.
• Designing Data-Intensive Applications, Kleppmann — sobre localidad y patrones de acceso — el fundamento teórico de por qué la localidad temporal (lo recién usado se vuelve a usar) hace que LRU acierte tanto, y por qué el patrón de acceso decide qué política gana. El "por qué" detrás de la elección de esta lección.