Caché LRU

Qué cubre este capítulo

Un caché guarda una cantidad limitada de elementos y, cuando se llena, tiene que decidir cuál tirar. La política least-recently-used (LRU) toma la decisión natural: desalojar lo que lleva más tiempo sin tocarse, apostando a que los datos usados recientemente se volverán a usar pronto. Es la política de desalojo detrás de los cachés de CPU, los page caches, los cachés web y de CDN, los buffer pools de bases de datos y los cachés de aplicación en todos lados. Este capítulo trata de cómo construir uno de forma eficiente, porque es una lección hermosa de composición: un caché necesita búsqueda O(1) y seguimiento O(1) del orden de acceso, y ninguna estructura por sí sola te da ambas — pero un hash map (búsqueda rápida, sin orden) más una lista doblemente ligada (reordenamiento rápido, sin búsqueda rápida) se combinan para dar exactamente la interfaz que un caché necesita. Este capítulo construye esa composición, observa cómo la lista de recencia se reordena en cada acceso y desaloja por atrás, y muestra por qué LRU le gana a políticas más simples en patrones de acceso realistas.

Un poco de historia

El caching y la idea del LRU son tan viejos como las jerarquías de memoria. La observación que hace que LRU funcione — la localidad temporal, la tendencia de los programas a reutilizar datos y código accedidos recientemente — se formalizó en los años 60 junto con el desarrollo de la memoria virtual y la paginación. El artículo de Les Belady de 1966 estudió algoritmos de reemplazo de páginas y demostró que la política óptima (desalojar el elemento que no se va a necesitar por más tiempo en el futuro) es inalcanzable en la práctica porque requiere conocer el futuro — así que los sistemas reales la aproximan, y LRU, que usa el pasado reciente como predictor del futuro cercano, se volvió la aproximación estándar. Belady también descubrió la contraintuitiva "anomalía de Belady", donde el reemplazo FIFO puede empeorar con más caché — un bug que LRU no tiene (LRU es un "algoritmo de pila", demostrablemente monótono respecto al tamaño del caché). La implementación eficiente de hash map más lista ligada se volvió un clásico de la programación, y hoy es tan común que Python la trae de fábrica como el decorador functools.lru_cache y collections.OrderedDict, y "implementa un caché LRU" es una de las preguntas más frecuentes en entrevistas de código — precisamente porque prueba si sabes componer dos estructuras para cumplir un requisito de dos partes.

La intuición

El requisito tiene dos mitades que jalan en direcciones distintas. En cada acceso tienes que (1) encontrar el elemento por su key, rápido, y (2) marcarlo como el más reciente, rápido; y cuando el caché se desborda tienes que (3) encontrar y quitar el elemento menos usado recientemente, rápido. Un hash map clava el (1) — búsqueda O(1) por key — pero no tiene noción de orden, así que no puede responder al (2) ni al (3). Una lista doblemente ligada clava el (2) y el (3) — puedes mover un nodo al frente o quitar el nodo de atrás en O(1) si tienes un puntero a él — pero encontrar un nodo por key implica recorrer la lista, O(n). Ninguna funciona sola. El truco es usar las dos, apuntando a los mismos nodos: el hash map mapea cada key a su nodo en la lista ligada, y la lista ligada mantiene los nodos ordenados por recencia.

Ahora las tres operaciones son O(1). Para hacer get de una key: la buscas en el hash map (O(1)) para obtener su nodo, luego desenlazas ese nodo de donde esté y lo insertas al frente de la lista (O(1), porque una lista doblemente ligada te deja quitar un nodo teniendo solo un puntero a él). Así, el frente de la lista siempre es el elemento más recientemente usado, y el fondo es el menos reciente. Para hacer put de una key nueva cuando el caché está lleno: la víctima del desalojo es simplemente el nodo justo antes de la cola — el fondo de la lista — así que lo quitas de la lista y del hash map (O(1)), y luego agregas el nodo nuevo al frente. Esa es toda la estructura: el hash map da acceso aleatorio, la lista doblemente ligada da el orden por recencia, y comparten nodos para que tocar un elemento actualice ambas vistas de una vez. Dos estructuras simples, cada una O(1) en lo suyo, compuestas en una que es O(1) en todo lo que el caché necesita.

Complejidad: cómo escala

Toda operación — get, put y desalojo — es O(1), independiente del tamaño del caché, usando espacio O(capacidad). No hay ciclos: una búsqueda en hash map y un número constante de reajustes de punteros. Esa eficiencia es el cómo; el porqué — por qué LRU y no una política más simple — tiene que ver con el hit rate en cargas reales, que es lo que mide el enfrentamiento. Los patrones de acceso reales están sesgados: unos pocos elementos son calientes, la mayoría son fríos (una distribución Zipf/ley de potencias, como se ve en el tráfico web, los renglones de una base de datos y el acceso a archivos). El enfrentamiento corre esa carga a través de tres políticas de desalojo — LRU, FIFO (desaloja el insertado más antiguo) y aleatoria — y mide el hit rate del caché:

LRU gana en todas las capacidades. Con una capacidad de 50 (de 500 keys), LRU logró un hit rate de 71% contra el 65% de FIFO y de la aleatoria — una ventaja de 6 puntos, que en términos de caching es grande: significa notablemente menos viajes al almacén lento de respaldo. La razón es que LRU mantiene residentes los elementos calientes: cada acceso a una key popular la regresa al frente, así que sobrevive al desalojo, mientras que FIFO la desaloja en un calendario fijo sin importar qué tan seguido se use, y la aleatoria la desaloja por suerte. El margen depende de la carga — con localidad temporal más fuerte (elementos usados recientemente que se reutilizan pronto, como en los programas reales) la ventaja de LRU crece; con acceso aleatorio uniforme (sin localidad) todas las políticas convergen, porque no hay nada que predecir. En los patrones sesgados y ricos en localidad que los cachés reales de verdad ven, la predicción basada en recencia de LRU paga consistentemente el pequeño costo de mantenimiento de la lista.

En qué es bueno y en qué no

El caché LRU — y su composición eficiente — es la herramienta correcta para cualquier caché acotado sobre una carga con localidad temporal, que son casi todas. La memoización (cachear resultados de funciones — functools.lru_cache es exactamente esto), los cachés de CPU y memoria, los page caches del SO, los buffer pools y cachés de consultas de bases de datos, los cachés de navegadores y CDN, los cachés de DNS y los cachés de objetos a nivel de aplicación usan LRU o una variante cercana. También es la respuesta estándar cuando necesitas un almacén key-value con acceso O(1) que además rastree el orden de uso por la razón que sea. La técnica de composición se generaliza más allá del caching: cada vez que necesitas dos operaciones O(1) que ninguna estructura sola te da, combinar estructuras que comparten nodos es la jugada (LRU es el ejemplo canónico, pero el patrón se repite).

Donde el LRU puro batalla es en cargas pesadas en scans (una pasada secuencial grande contamina el caché con cosas que nunca se reutilizan, desalojando datos calientes), cargas que se predicen mejor por frecuencia que por recencia (donde gana LFU) y patrones de acceso adversarios diseñados para derrotarlo. También usa más memoria por entrada que un hash map pelón (los dos punteros de lista ligada por nodo) y más que una política más simple como FIFO o aleatoria — por eso, cuando la ganancia en hit rate no justifica el mantenimiento (acceso uniforme, cachés diminutos), una política más simple basta. Los cachés distribuidos agregan más complicaciones (consistencia, sharding) más allá de la estructura de una sola máquina. Para el caso común — un caché local acotado sobre accesos ricos en localidad — las operaciones O(1) de LRU y su buen hit rate lo vuelven la opción por defecto, pero los sistemas de producción a menudo recurren a variantes resistentes a scans (ARC, 2Q, LRU-K) cuando la carga lo exige.

Los datos, o las entradas

El enfrentamiento corre una carga de accesos con distribución Zipf (ley de potencias) — unas pocas keys calientes, muchas frías, como el tráfico real de un caché — a través de las políticas de desalojo LRU, FIFO y aleatoria en varias capacidades, midiendo el hit rate de cada una. La correctitud se verifica corriendo cientos de secuencias aleatorias de get/put por el caché hecho a mano de hash map más lista ligada, en paralelo con una referencia de collections.OrderedDict, afirmando valores de retorno idénticos y, sobre todo, un orden de recencia idéntico después de cada operación. La animación corre un caché de capacidad 4 por una secuencia de gets y puts, dibujando la lista de recencia del más al menos reciente y mostrando cómo un get promueve una key al frente y un put con el caché lleno desaloja por atrás.

Constrúyelo, una función a la vez

El caché LRU — un hash map y una lista doblemente ligada compartiendo nodos, todas las operaciones en O(1):

class LRUCache:
    """Capacity-bounded LRU cache. `store` maps key → node for O(1) lookup; a doubly-linked list
    with head/tail sentinels keeps nodes in recency order — front (head.next) is most-recently-used,
    back (tail.prev) is least-recently-used and the eviction victim."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = _Node()                       # sentinel: MRU side
        self.tail = _Node()                       # sentinel: LRU side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _push_front(self, node):
        node.next = self.head.next                # splice just after the head sentinel (MRU)
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        """Return the value and mark the key most-recently-used (move its node to the front). Returns
        None on a miss. O(1): a dict lookup plus two pointer splices."""
        node = self.store.get(key)
        if node is None:
            return None                           # miss
        self._unlink(node)
        self._push_front(node)                    # touch → becomes most recently used
        return node.val

    def put(self, key, val):
        """Insert or update a key as most-recently-used. If the cache is full and the key is new,
        evict the least-recently-used node (the one just before the tail sentinel) first. O(1)."""
        node = self.store.get(key)
        if node is not None:
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.store) >= self.capacity:
            lru = self.tail.prev                  # the least-recently-used node
            self._unlink(lru)
            del self.store[lru.key]               # evict it
        node = _Node(key, val)
        self.store[key] = node
        self._push_front(node)

    def order(self):
        """The keys from most- to least-recently-used — for inspection and the animation."""
        out, cur = [], self.head.next
        while cur is not self.tail:
            out.append(cur.key)
            cur = cur.next
        return out

Míralo funcionar

Aquí tienes un caché LRU de capacidad 4. Las celdas muestran la lista de recencia, el más recientemente usado a la izquierda (MRU) y el menos a la derecha (LRU). Fíjate en los dos tipos de operación. Un put de una key nueva la inserta al frente y, si el caché está lleno, primero desaloja la key de atrás — la menos usada recientemente — para hacer espacio; observa cómo llega E y desaloja a B, el elemento que lleva más tiempo sin tocarse. El get es el más sutil: get A encuentra a A y lo mueve al frente (verde), marcándolo como el más reciente, lo que cambia a quién le toca el desalojo — porque A acaba de tocarse, ahora está a salvo, y alguien más se vuelve la víctima. Sigue el reordenamiento de la lista en cada acceso: el frente se llena con lo que estás usando, el fondo acumula lo que has descuidado, y el desalojo siempre toma del extremo descuidado. Ese barajeo constante es lo que mantiene residentes los datos calientes:

El código completo

La pestaña "desde cero" es el caché LRU construido con un hash map y una lista doblemente ligada; la pestaña de librería es la versión con collections.OrderedDict (la forma de la librería estándar y la referencia de correctitud) más las políticas FIFO y aleatoria del enfrentamiento de hit rate, con una nota sobre functools.lru_cache. Cambia entre ellas — la versión con OrderedDict es más corta porque esconde la lista ligada dentro de una estructura con pilas incluidas, pero es el mismo algoritmo, que es exactamente lo que revela construirlo a mano.

"""LRU cache — a fixed-capacity key-value store that, when full, evicts the LEAST RECENTLY USED
item to make room. It's the eviction policy behind CPU caches, page caches, web and CDN caches,
database buffer pools, and application caches everywhere, because it captures a simple truth about
access patterns: recently-used data tends to be used again soon (temporal locality), so the thing
untouched the longest is the safest to discard.

The interesting part is the engineering. A cache needs two O(1) operations at once: look up a key
instantly, AND update its recency instantly (mark it most-recently-used on every access, and find
the least-recently-used to evict). No single structure gives both — a hash map has O(1) lookup but
no order, a linked list has O(1) reordering but no fast lookup. The classic answer COMBINES them: a
hash map from key to a node, plus a doubly-linked list that keeps the nodes in recency order
(most-recent at the front, least-recent at the back). The hash map finds any node in O(1); the
doubly-linked list moves a node to the front or drops the back node in O(1). Together they are
exactly the interface a cache needs — two simple structures composing into one that neither could
be alone.
"""


class _Node:
    __slots__ = ("key", "val", "prev", "next")

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


# region: lru
class LRUCache:
    """Capacity-bounded LRU cache. `store` maps key → node for O(1) lookup; a doubly-linked list
    with head/tail sentinels keeps nodes in recency order — front (head.next) is most-recently-used,
    back (tail.prev) is least-recently-used and the eviction victim."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.head = _Node()                       # sentinel: MRU side
        self.tail = _Node()                       # sentinel: LRU side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _push_front(self, node):
        node.next = self.head.next                # splice just after the head sentinel (MRU)
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        """Return the value and mark the key most-recently-used (move its node to the front). Returns
        None on a miss. O(1): a dict lookup plus two pointer splices."""
        node = self.store.get(key)
        if node is None:
            return None                           # miss
        self._unlink(node)
        self._push_front(node)                    # touch → becomes most recently used
        return node.val

    def put(self, key, val):
        """Insert or update a key as most-recently-used. If the cache is full and the key is new,
        evict the least-recently-used node (the one just before the tail sentinel) first. O(1)."""
        node = self.store.get(key)
        if node is not None:
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.store) >= self.capacity:
            lru = self.tail.prev                  # the least-recently-used node
            self._unlink(lru)
            del self.store[lru.key]               # evict it
        node = _Node(key, val)
        self.store[key] = node
        self._push_front(node)

    def order(self):
        """The keys from most- to least-recently-used — for inspection and the animation."""
        out, cur = [], self.head.next
        while cur is not self.tail:
            out.append(cur.key)
            cur = cur.next
        return out
# endregion

"""The library way and the policy contrasts. Three things:

- `OrderedDictLRU` is the standard-library way to write an LRU cache — `collections.OrderedDict`
  keeps insertion order and `move_to_end` / `popitem` give O(1) recency updates and eviction, so
  it's the same algorithm as impl.py's hash-map-plus-linked-list, just using a battery-included
  structure. It's the correctness reference. (Python's `functools.lru_cache` decorator memoizes
  function calls with exactly this policy.)
- `FIFOCache` and `RandomCache` are the OTHER eviction policies, for the hit-rate face-off: FIFO
  evicts the oldest-inserted item regardless of use, and Random evicts an arbitrary one. Comparing
  their hit rates against LRU shows WHY recency-based eviction is worth the extra bookkeeping.
"""
import random
from collections import OrderedDict


# region: ordereddict
class OrderedDictLRU:
    """An LRU cache in a few lines using collections.OrderedDict — the standard-library approach, and
    the correctness reference for the hand-built hash-map + doubly-linked-list version."""

    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 most-recently-used
        return self.data[key]

    def put(self, key, val):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = val
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)         # evict least-recently-used (front)
# endregion


# region: policies
class FIFOCache:
    """Evicts the OLDEST-INSERTED item, ignoring how recently it was used — no recency tracking."""

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

    def get(self, key):
        return self.data.get(key)                 # a hit does NOT change eviction order

    def put(self, key, val):
        if key not in self.data and len(self.data) >= self.capacity:
            self.data.popitem(last=False)         # evict the oldest inserted
        self.data[key] = val


class RandomCache:
    """Evicts a RANDOM item when full — the simplest policy, no order at all."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}

    def get(self, key):
        return self.data.get(key)

    def put(self, key, val):
        if key not in self.data and len(self.data) >= self.capacity:
            del self.data[random.choice(list(self.data))]
        self.data[key] = val
# endregion

Desde cero vs librería

El caché LRU es la lección más limpia de composición del libro: un requisito que ninguna estructura sola satisface, resuelto combinando dos que satisfacen la mitad cada una, compartiendo nodos para que una actualización toque ambas vistas al mismo tiempo. Ese patrón — hash map para acceso aleatorio, estructura ligada para el orden — vale la pena reconocerlo porque se repite cada vez que necesitas dos operaciones rápidas que jalan en direcciones distintas. También muestra que la versión "con pilas incluidas" (OrderedDict, functools.lru_cache) no es magia: OrderedDict es un hash map más una lista doblemente ligada por dentro, y por eso construir el caché a mano desmitifica la librería. Y el enfrentamiento saca a la luz el porqué detrás de esta política omnipresente — LRU le gana a FIFO y a la aleatoria en cargas ricas en localidad porque la recencia predice la reutilización, que es la misma suposición de localidad temporal que justifica que los cachés existan. En producción usarías functools.lru_cache para memoización o el buffer manager de una base de datos para almacenamiento; construir la estructura tú mismo es lo que convierte "hash map más lista doblemente ligada igual a caché O(1)" en una composición que armaste en lugar de una receta que memorizaste.

Dónde te lo vas a encontrar de verdad

Los cachés LRU están por todos lados en la jerarquía de memoria y más allá. Los cachés de CPU (L1/L2/L3) usan aproximaciones de LRU en hardware para decidir qué líneas de caché desalojar. Los sistemas operativos usan políticas de la familia LRU para el reemplazo de páginas en memoria virtual y para el page cache del sistema de archivos. Las bases de datos lo usan (y variantes resistentes a scans como ARC en los descendientes de PostgreSQL y 2Q) para los buffer pools que cachean páginas de disco, una de las palancas de rendimiento más grandes en un DBMS. Los navegadores web, las CDN (Cloudflare, Akamai) y los reverse proxies (Varnish, nginx) cachean contenido con variantes de LRU. Los cachés de aplicación (Redis con allkeys-lru, Memcached, Guava, Caffeine) ofrecen desalojo LRU. Los decoradores de memoización (functools.lru_cache) cachean resultados de funciones con él. Los resolvers de DNS, los cachés de consultas de ORM y los cachés de imágenes/miniaturas lo usan. Y es una pregunta perenne de entrevista porque implementarlo bien pone a prueba la intuición de composición. Donde sea que un caché acotado tenga que decidir qué conservar, es muy probable que la política sea un LRU o alguna de sus variantes.

Puntos clave

Un caché LRU desaloja el elemento menos usado recientemente cuando se llena, y su implementación eficiente compone un hash map (búsqueda O(1) por key) con una lista doblemente ligada (orden O(1) por recencia, frente = más reciente, atrás = menos), compartiendo nodos para que get, put y desalojo sean todos O(1). La lista doblemente ligada es esencial — es lo que permite quitar un nodo de en medio en O(1). LRU le gana a FIFO y a la aleatoria en cargas ricas en localidad (una ventaja de 6 puntos de hit rate aquí, más grande con localidad más fuerte) porque la recencia predice la reutilización, aunque es vulnerable a la contaminación por scans, contra la que se defienden las variantes de producción (ARC, 2Q, LRU-K). Es el ejemplo canónico de componer dos estructuras para cumplir un requisito de dos partes.

El siguiente capítulo pasa de las keys de una dimensión al espacio. Un árbol k-d organiza puntos en múltiples dimensiones para que "¿cuál punto almacenado está más cerca de esta consulta?" y "¿qué puntos caen en esta región?" se puedan responder mucho más rápido que revisando todos los puntos — la estructura detrás de la búsqueda de vecinos más cercanos, las bases de datos espaciales y la geometría que sostiene buena parte del machine learning. Es un árbol binario de búsqueda generalizado a k dimensiones, partiendo el espacio un eje a la vez, y muestra tanto el poder como los límites eventuales del particionamiento espacial conforme crecen las dimensiones.