LRU Cache — qué es, algoritmo de desalojo y cómo funciona

¿Qué es LRU Cache?

LRU Cache (Least Recently Used Cache) es una estructura de datos de tamaño fijo que almacena un número limitado de elementos y elimina automáticamente aquellos que se han accedido con menos frecuencia. Cuando una aplicación solicita un elemento, este se mueve a la parte “fresca” de la caché, mientras que los elementos no utilizados durante mucho tiempo se desplazan hacia el final y se eliminan cuando se alcanza el límite.

El nombre “Least Recently Used” describe la política de desalojo: se elimina el elemento que no se ha utilizado durante más tiempo entre todos los almacenados. Esto se basa en el supuesto de localidad de referencia (locality of reference): los datos solicitados recientemente tienen una alta probabilidad de volver a necesitarse. Por eso LRU se considera una de las estrategias de almacenamiento en caché más efectivas para la mayoría de las aplicaciones.

La implementación clásica de LRU Cache requiere dos estructuras de datos: una tabla hash para acceso O(1) a cualquier elemento por clave y una lista doblemente enlazada para rastrear el orden de uso. La tabla hash almacena referencias a los nodos de la lista, y la lista mantiene el orden desde el elemento más nuevo (cabeza) hasta el más antiguo (cola).

Operaciones básicas de LRU Cache

La operación get(key) verifica si la clave existe en la tabla hash. Si se encuentra, el elemento se mueve a la cabeza de la lista (se convierte en el más nuevo) y se devuelve su valor. Si no se encuentra, se devuelve null o se lanza una excepción. La operación put(key, value) inserta un nuevo elemento: si la clave ya existe, se actualiza el valor y el elemento se mueve a la cabeza. Si la caché está llena, se elimina el elemento de la cola antes de la inserción. Todas las operaciones se ejecutan en tiempo constante O(1).

Cómo funciona LRU Cache

El algoritmo LRU Cache se basa en dos principios: conteo de accesos en orden temporal y el mecanismo de desalojo por desbordamiento. Cada elemento se almacena en un nodo de la lista doblemente enlazada, y los punteros a estos nodos se mantienen en la tabla hash. En cada acceso, el elemento se desengancha de su posición actual y se inserta al inicio de la lista.

Cuando el tamaño de la caché alcanza su valor máximo (maxSize) y llega una solicitud de inserción de un nuevo elemento, el algoritmo elimina el elemento de la cola de la lista doblemente enlazada — este es el elemento menos recientemente usado. Después de la eliminación, se libera espacio para el nuevo elemento, que se inserta en la cabeza de la lista. La tabla hash se actualiza en consecuencia: la clave antigua se elimina, se añade una nueva.

Una característica de LRU es su sensibilidad a los patrones de acceso con repetición cíclica. Si la aplicación accede periódicamente a un conjunto de datos mayor que el tamaño de la caché, LRU puede sufrir de thrashing — reemplazo frecuente de elementos donde cada nueva solicitud desaloja la anterior. En tales escenarios, LFU (Least Frequently Used) o los algoritmos adaptativos pueden ser más efectivos.

Tamaño de la caché y métricas

Elegir el tamaño de LRU Cache es un compromiso entre el consumo de memoria y el hit-ratio (porcentaje de accesos exitosos). Valores típicos para aplicaciones móviles: 10–20% de la memoria disponible para caché de imágenes y 50–200 entradas para caché de respuestas de red. Un hit-ratio del 80–95% se considera bueno, donde la caché justifica el costo de memoria. Para monitoreo, se utilizan los contadores hitCount y missCount, disponibles en la implementación de LruCache en Android.

Implementación de LRU Cache: HashMap + Doubly Linked List

La implementación canónica de LRU Cache utiliza una combinación de una tabla hash y una lista doblemente enlazada. La tabla hash proporciona acceso O(1) a cualquier nodo por clave, mientras que la lista doblemente enlazada permite mover un nodo a la cabeza y eliminarlo de la cola en O(1). Es crucial que la lista sea doblemente enlazada: esto permite desenganchar un nodo del medio de la lista sin iterar sobre todos los elementos.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

En la implementación, cada nodo (Node) almacena un valor y referencias a los nodos anterior y siguiente. Los nodos centinela head y tail simplifican los casos extremos — no es necesario verificar null en la inserción y eliminación. El método get mueve el nodo encontrado a la cabeza, y put elimina el elemento de la cola en caso de desbordamiento. Un método separado removeKeyByValue encuentra la clave en la tabla hash por referencia al nodo y la elimina.

Implementación incorporada de LruCache en Android

El SDK de Android proporciona una clase LruCache lista en el paquete android.util, que implementa el algoritmo LRU usando LinkedHashMap en modo access-order. La clase es thread-safe, soporta conteo de hit/miss y proporciona el callback entryRemoved para la limpieza de recursos al desalojar un elemento. El tamaño de la caché se establece en unidades arbitrarias (bytes, número de elementos) — basta con sobrescribir el método sizeOf.

LRU Cache vs FIFO y LIFO

Los tres algoritmos — LRU, FIFO y LIFO — resuelven el mismo problema: limitar el consumo de memoria desalojando elementos al desbordarse. Sin embargo, utilizan criterios fundamentalmente diferentes para seleccionar la víctima, lo que determina su efectividad en diferentes escenarios.

FIFO desaloja el elemento más antiguo por tiempo de inserción, independientemente de la frecuencia con que se haya accedido. Esto puede ser ineficiente si un elemento antiguo sigue siendo relevante. LRU evita este inconveniente al considerar el patrón de acceso. LIFO desaloja el elemento añadido más recientemente — útil para escenarios de deshacer, pero inadecuado para almacenamiento en caché, ya que los datos nuevos suelen ser más necesarios que los antiguos. LRU se considera el equilibrio óptimo entre la complejidad de implementación y el hit-ratio para la mayoría de las aplicaciones.

Ejemplos de código LRU Cache

Consideremos el uso de la clase incorporada LruCache del SDK de Android para almacenar en caché imágenes descargadas. El ejemplo muestra la inicialización de la caché a 1/8 de la memoria disponible de la aplicación, que es la recomendación estándar de Google para el almacenamiento en caché de imágenes.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

El método sizeOf devuelve el tamaño del elemento en las mismas unidades en que se especifica cacheSize. Aquí se utiliza el tamaño del Bitmap en kilobytes (rowBytes × height / 1024). Cuando la suma de sizeOf de todos los elementos supera cacheSize, LruCache desaloja automáticamente los Bitmaps menos recientemente usados. El callback entryRemoved se puede utilizar para llamar a bitmap.recycle() — liberando memoria antes del desalojo.

Implementación de LRU Cache en Swift

iOS no tiene una clase LRU Cache incorporada, pero es fácil de implementar usando NSCache (que utiliza una política de desalojo similar pero no documentada) o mediante una implementación personalizada usando Dictionary + Doubly Linked List, como se muestra a continuación.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

En esta implementación en Swift, Node es una clase interna con campos value, next y prev. El método moveToHead desengancha un nodo de su posición actual y lo inserta al inicio de la lista. En caso de desbordamiento, se elimina la cola — el elemento menos recientemente usado. Para producción, se recomienda añadir seguridad de hilos mediante NSLock o una cola DispatchQueue.