Caché LRU explicada: cómo funciona, código y complejidad

Qué problema resuelve una caché LRU

Una caché guarda los resultados de operaciones lentas, como consultas a bases de datos, peticiones web o cálculos costosos, para responder rápido a las peticiones repetidas. La memoria es limitada, así que la caché debe decidir qué descartar cuando se llena. LRU apuesta a que los datos usados hace poco se volverán a usar pronto, y los que llevan mucho sin tocarse probablemente no. Esta apuesta funciona bien en muchas cargas reales, por eso LRU y sus aproximaciones aparecen en cachés de CPU, cachés de páginas de sistemas operativos, bases de datos, servidores web y CDN.

La idea: dos estructuras que trabajan juntas

Necesitamos que dos cosas sean rápidas: encontrar una clave y saber cuál es la menos usada recientemente. Un mapa hash por sí solo no tiene orden. Una lista por sí sola es lenta para buscar. Juntos hacen ambas cosas:

En get(key), busca el nodo en el mapa, muévelo al frente y devuelve su valor. En put(key, value), actualiza o crea el nodo al frente; si la caché supera ahora la capacidad, quita el nodo del final y borra su clave del mapa.

Ejemplo resuelto con capacidad 2

Implementación desde cero en Python

Los nodos centinela de cabeza y cola eliminan los casos especiales de la lista vacía: todo nodo real tiene siempre un nodo antes y otro después.

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

La versión corta con OrderedDict

collections.OrderedDict es en sí mismo un mapa hash combinado con una lista doblemente enlazada, y move_to_end y popitem(last=False) son O(1). Eso lo convierte en la opción idiomática en Python cuando necesitas una caché LRU como objeto.

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

Cachear resultados de funciones con functools.lru_cache

Para cachear los valores de retorno de una función, usa el decorador functools.lru_cache. Los argumentos deben ser hashables, porque se convierten en claves de diccionario. cache_info() muestra aciertos, fallos y el tamaño actual.

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=None da una caché sin límite, que es lo que hace functools.cache (Python 3.9 y posteriores). Llama a fib.cache_clear() para vaciarla.

Complejidad temporal y espacial

Variantes, errores y cuándo usar LRU

• LFU (least frequently used) expulsa el elemento con menos accesos; protege a los elementos populares de los recorridos puntuales, pero es más complejo.
• LRU aproximado: sistemas como Redis muestrean unas pocas claves y expulsan la más antigua entre ellas en lugar de mantener una lista exacta, lo que ahorra memoria.
• Las cachés TTL hacen que las entradas expiren tras un tiempo fijo, a menudo combinado con un límite de tamaño.
• Olvidar mover una entrada al frente en get, o en put de una clave existente, convierte LRU en FIFO.
• Olvidar borrar la clave expulsada del mapa hash deja entradas colgantes y provoca fugas de memoria.
• Compartir una caché LRU entre hilos requiere un bloqueo (lock) alrededor de cada operación; functools.lru_cache es seguro de llamar desde varios hilos.

LRU es una buena opción por defecto cuando el uso reciente predice el uso futuro. Rinde mal cuando un recorrido grande y puntual expulsa datos muy usados; cargas así se benefician de LFU o de políticas resistentes a recorridos. Diseñar una caché LRU con operaciones O(1) es además una de las preguntas de entrevista de programación más comunes, porque evalúa mapas hash y listas enlazadas a la vez.