Construyendo una caché LRU concurrente y eficiente en Go: Un tutorial con código

7 de noviembre de 2025, 11:01:24 Diario Tecnología 18 min lectura

En el vertiginoso mundo del desarrollo de software, donde cada milisegundo cuenta, la optimización del rendimiento es una búsqueda constante. Nos esforzamos por construir sistemas que respondan más rápido, procesen más datos y escalen sin esfuerzo. Una de las herramientas más poderosas y omnipresentes en este arsenal de optimización es la caché. Pero no cualquier caché; hoy nos centraremos en una estrategia particularmente efectiva y ampliamente utilizada: la caché de "menos recientemente usado" o LRU (Least Recently Used). En este tutorial, no solo exploraremos los fundamentos de esta técnica, sino que también nos sumergiremos en una implementación práctica y concurrente en Go, el lenguaje que muchos de nosotros hemos llegado a apreciar por su simplicidad y potencia en la gestión de la concurrencia. Si alguna vez te has preguntado cómo hacer que tus aplicaciones manejen datos de forma más eficiente sin reinventar la rueda, o si simplemente buscas reforzar tus conocimientos en estructuras de datos y concurrencia en Go, este post es para ti.

¿Qué es una caché y por qué la necesitamos?

Two people enjoy a peaceful sunset on Batumi's rocky coast, embodying tranquility and connection.

Una caché es un componente de almacenamiento de alta velocidad que guarda datos a los que se accede con frecuencia, de modo que futuras solicitudes de esos datos puedan servirse más rápidamente que si tuvieran que recuperarse de su ubicación de almacenamiento original y más lenta. Imagina que tu aplicación necesita consultar repetidamente la misma información de una base de datos remota o de una API externa. Cada vez que se realiza la consulta, se incurre en latencia de red, tiempo de procesamiento en el servidor de origen y, potencialmente, costos de recursos. Una caché local intercepta estas solicitudes. Si los datos ya están en la caché, se devuelven instantáneamente; si no, la aplicación recupera los datos de la fuente original, los almacena en la caché para futuras solicitudes y luego los devuelve.

La necesidad de cachés surge de la "brecha de rendimiento" entre los diferentes niveles de almacenamiento. La CPU es increíblemente rápida, pero la memoria RAM es más lenta. Los discos SSD son mucho más lentos que la RAM, y las unidades de disco duro tradicionales son aún más lentas. Las redes introducen aún más latencia. Las cachés actúan como un amortiguador, reduciendo la necesidad de acceder a los niveles de almacenamiento más lentos y costosos. Esto no solo mejora la velocidad de respuesta de la aplicación, sino que también reduce la carga en los servicios de respaldo, lo que puede traducirse en ahorros significativos y una mayor estabilidad del sistema. En entornos de microservicios o arquitecturas distribuidas, una estrategia de caché bien implementada puede ser la diferencia entre un sistema robusto y uno frágil.

Entendiendo la caché LRU

Existen diversas estrategias de caché para decidir qué elementos expulsar cuando la caché alcanza su capacidad máxima. Algunas son FIFO (First-In, First-Out), LFU (Least Frequently Used), MRU (Most Recently Used), entre otras. Sin embargo, la estrategia LRU es una de las más populares y efectivas en muchos escenarios.

Principios de la caché LRU

La lógica detrás de LRU es bastante intuitiva: si un elemento ha sido utilizado recientemente, es probable que se vuelva a utilizar pronto. Por el contrario, si un elemento no se ha utilizado en mucho tiempo, es menos probable que se necesite en un futuro inmediato. Por lo tanto, cuando la caché está llena y necesitamos espacio para un nuevo elemento, el algoritmo LRU expulsa el elemento que ha sido "menos recientemente usado". Esta aproximación se basa en la heurística de que el pasado predice el futuro, lo cual a menudo resulta ser una suposición válida en el comportamiento de acceso a datos.

Las ventajas de LRU son claras: tiende a mantener los datos "calientes" (frecuentemente accedidos) en la caché, lo que lleva a altas tasas de aciertos (cache hits). Sin embargo, también tiene sus desventajas. La principal es la complejidad de su implementación, ya que requiere un seguimiento constante del "tiempo" de acceso de cada elemento. Además, no es ideal para patrones de acceso de una sola vez o para datos que se acceden de forma secuencial y que no se repiten. Pese a esto, en la mayoría de las aplicaciones web y de propósito general, LRU ofrece un excelente equilibrio entre complejidad y rendimiento.

Estructuras de datos clave

Para implementar eficientemente una caché LRU, necesitamos dos estructuras de datos principales trabajando en conjunto:

Un mapa hash (o diccionario): En Go, esto es un map. Su función es permitirnos buscar elementos por su clave en tiempo constante (O(1)). Cuando un elemento es accedido o añadido, necesitamos encontrarlo rápidamente. El mapa almacenará la clave del elemento y un puntero a su ubicación en la segunda estructura de datos.
Una lista doblemente enlazada: Esta lista se utiliza para mantener el orden de recencia. Cada vez que se accede a un elemento, se mueve al "frente" de la lista, indicando que es el más recientemente usado. Cuando la caché necesita expulsar un elemento, simplemente se elimina el elemento del "final" de la lista, que corresponde al menos recientemente usado. Las operaciones de añadir y eliminar de los extremos, así como mover un nodo en una lista doblemente enlazada, también se realizan en tiempo constante (O(1)). En Go, la librería estándar container/list nos proporciona una implementación eficiente de una lista doblemente enlazada.

La combinación de estas dos estructuras nos permite realizar las operaciones de Get (obtener) y Put (añadir/actualizar) en un tiempo promedio de O(1), lo cual es crucial para una caché de alto rendimiento.

Implementando una caché LRU básica en Go

Comencemos con una implementación básica que no considera la concurrencia, para entender los fundamentos.

Definición de estructuras

Necesitamos una estructura para los elementos que guardaremos en la caché y otra para la propia caché.

package lru

import (
	"container/list"
)

// Entry representa un elemento en la caché.
type Entry struct {
	key   interface{}
	value interface{}
}

// LRUCache es la estructura principal de la caché LRU.
type LRUCache struct {
	capacity int
	ll       *list.List                  // Lista doblemente enlazada para el orden de recencia
	cache    map[interface{}]*list.Element // Mapa para acceso rápido a los elementos de la lista
}

Aquí, Entry es una estructura simple para almacenar la clave y el valor. LRUCache contiene la capacidad máxima, la lista doblemente enlazada (ll) y el mapa (cache) que vincula las claves con los elementos de la lista. Usamos interface{} para las claves y valores para hacer la caché genérica, permitiendo almacenar cualquier tipo de datos.

Inicialización de la caché

Una función constructora es esencial para inicializar nuestra caché de forma segura.

// NewLRUCache crea una nueva instancia de LRUCache con la capacidad dada.
func NewLRUCache(capacity int) *LRUCache {
	if capacity <= 0 {
		panic("La capacidad de la caché debe ser mayor que cero")
	}
	return &LRUCache{
		capacity: capacity,
		ll:       list.New(),
		cache:    make(map[interface{}]*list.Element),
	}
}

El método 'Get': Recuperando elementos

Cuando un cliente solicita un valor por su clave, nuestra caché debe hacer dos cosas: verificar si el elemento existe y, si existe, actualizar su posición en la lista doblemente enlazada para reflejar que acaba de ser accedido (es decir, moverlo al frente).

// Get recupera un valor de la caché por su clave.
// Si el elemento existe, se mueve al frente de la lista.
func (c *LRUCache) Get(key interface{}) (value interface{}, ok bool) {
	if ele, hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele) // Mueve el elemento al frente (más recientemente usado)
		return ele.Value.(*Entry).value, true
	}
	return nil, false // No se encontró el elemento
}

Es bastante directo. Buscamos la clave en el mapa. Si encontramos un elemento (hit), lo movemos al frente de la lista con c.ll.MoveToFront(ele) y devolvemos su valor. Si no se encuentra, regresamos nil y false.

El método 'Put': Añadiendo o actualizando elementos

El método Put es más complejo porque maneja tanto la adición de nuevos elementos como la actualización de los existentes, y también la lógica de expulsión cuando la caché está llena.

// Put añade o actualiza un valor en la caché.
// Si la clave ya existe, se actualiza el valor y se mueve al frente.
// Si la clave es nueva y la caché está llena, se expulsa el elemento menos recientemente usado.
func (c *LRUCache) Put(key, value interface{}) {
	if ele, hit := c.cache[key]; hit {
		// El elemento ya existe, actualiza su valor y muévelo al frente.
		c.ll.MoveToFront(ele)
		ele.Value.(*Entry).value = value
		return
	}

	// El elemento no existe, agrégalo.
	entry := &Entry{key: key, value: value}
	ele := c.ll.PushFront(entry) // Añade el nuevo elemento al frente
	c.cache[key] = ele         // Guárdalo en el mapa

	// Si la caché ha excedido su capacidad, expulsa el elemento menos recientemente usado.
	if c.ll.Len() > c.capacity {
		c.removeOldest()
	}
}

// removeOldest elimina el elemento menos recientemente usado (el de atrás de la lista).
func (c *LRUCache) removeOldest() {
	ele := c.ll.Back() // Obtiene el elemento al final de la lista
	if ele != nil {
		c.ll.Remove(ele) // Lo remueve de la lista
		kv := ele.Value.(*Entry)
		delete(c.cache, kv.key) // Lo remueve del mapa
	}
}

// Len devuelve el número actual de elementos en la caché.
func (c *LRUCache) Len() int {
	return c.ll.Len()
}

Aquí, si la clave ya existe, actualizamos su valor y lo movemos al frente. Si es un nuevo elemento:

Creamos una nueva Entry.
La añadimos al frente de la lista (PushFront).
Guardamos el puntero al elemento de la lista en el mapa.
Finalmente, verificamos si la caché ha excedido su capacidad. Si es así, llamamos a removeOldest() que toma el elemento del final de la lista (ll.Back()), lo elimina tanto de la lista como del mapa.

Consideraciones sobre 'Remove' (opcional)

Aunque no siempre es estrictamente necesario para una caché LRU funcional, un método Remove explícito puede ser útil para invalidar elementos manualmente.

// Remove elimina un elemento de la caché por su clave.
func (c *LRUCache) Remove(key interface{}) {
	if ele, hit := c.cache[key]; hit {
		c.ll.Remove(ele)
		delete(c.cache, key)
	}
}

Este método es simple: busca el elemento en el mapa, y si lo encuentra, lo elimina de la lista y del mapa.

Probando nuestra implementación básica

Veamos un pequeño ejemplo para entender cómo funciona la caché LRU.

package main

import (
	"fmt"
	"lru" // Asumiendo que tu código de caché LRU está en un paquete llamado "lru"
)

func main() {
	cache := lru.NewLRUCache(3) // Capacidad de 3 elementos

	fmt.Println("Poniendo (1, 'uno')")
	cache.Put(1, "uno") // {1: uno}
	fmt.Println("Poniendo (2, 'dos')")
	cache.Put(2, "dos") // {1: uno, 2: dos}
	fmt.Println("Poniendo (3, 'tres')")
	cache.Put(3, "tres") // {1: uno, 2: dos, 3: tres}

	fmt.Printf("Elementos en caché: %d\n", cache.Len())

	// Accedemos a '1'. Ahora '1' es el más reciente.
	// Orden de recencia: 2, 3, 1 (LRU es 2)
	val, ok := cache.Get(1)
	if ok {
		fmt.Printf("Obtenido 1: %s\n", val)
	}

	fmt.Println("Poniendo (4, 'cuatro')")
	// La caché está llena, expulsará el menos recientemente usado (2).
	// Orden de recencia: 3, 1, 4 (LRU es 3)
	cache.Put(4, "cuatro") // {1: uno, 3: tres, 4: cuatro} (2 fue expulsado)

	val, ok = cache.Get(2) // Intentamos obtener 2, que ya fue expulsado
	fmt.Printf("Intentando obtener 2: %v, %v\n", val, ok) // nil, false

	val, ok = cache.Get(3) // Accedemos a 3. Ahora 3 es el más reciente.
	if ok {
		fmt.Printf("Obtenido 3: %s\n", val) // Orden de recencia: 1, 4, 3 (LRU es 1)
	}

	fmt.Println("Poniendo (5, 'cinco')")
	// La caché está llena, expulsará el menos recientemente usado (1).
	// Orden de recencia: 4, 3, 5 (LRU es 4)
	cache.Put(5, "cinco") // {3: tres, 4: cuatro, 5: cinco} (1 fue expulsado)

	fmt.Printf("Elementos en caché al final: %d\n", cache.Len())
}

La salida de este programa mostrará cómo la caché expulsa el elemento 2 y luego el 1 a medida que se añaden nuevos elementos, manteniendo solo los capacity elementos más recientemente accedidos. Este comportamiento es justo lo que esperamos de una caché LRU.

Haciendo nuestra caché LRU concurrente y segura en Go

Nuestra implementación actual funciona perfectamente en un entorno de un solo hilo. Sin embargo, en el ecosistema de Go, las goroutines son la norma, y múltiples goroutines podrían intentar acceder y modificar la caché simultáneamente. Esto llevaría a las temidas "race conditions" (condiciones de carrera), donde el comportamiento del programa se vuelve impredecible y erróneo debido a accesos no sincronizados a la memoria compartida.

El problema de la concurrencia

Una "race condition" ocurre cuando dos o más goroutines acceden a la misma variable o recurso compartido concurrentemente y al menos una de las goroutines está realizando una operación de escritura. Sin una sincronización adecuada, el orden de las operaciones puede variar, llevando a un estado de datos inconsistente. En nuestra caché LRU, el mapa (c.cache) y la lista doblemente enlazada (c.ll) son recursos compartidos que son modificados por los métodos Get, Put y removeOldest. Si una goroutine está actualizando la lista mientras otra la está leyendo o modificando, podríamos tener punteros rotos en la lista o un estado incorrecto en el mapa.

Solución con sync.Mutex

Go proporciona primitivas de sincronización poderosas y fáciles de usar en su paquete sync. Para proteger nuestra caché LRU, utilizaremos un sync.Mutex. Un mutex (mutual exclusion) es un mecanismo que permite que solo una goroutine acceda a una sección crítica de código a la vez.

Necesitamos añadir un sync.Mutex a nuestra estructura LRUCache y asegurar que todos los métodos que modifican o leen el estado interno de la caché adquieran y liberen este mutex.

package lru

import (
	"container/list"
	"sync" // Importamos el paquete sync
)

// LRUCache es la estructura principal de la caché LRU.
type LRUCache struct {
	capacity int
	ll       *list.List
	cache    map[interface{}]*list.Element
	mu       sync.Mutex // Añadimos un Mutex para proteger el acceso concurrente
}

// NewLRUCache crea una nueva instancia de LRUCache con la capacidad dada.
func NewLRUCache(capacity int) *LRUCache {
	if capacity <= 0 {
		panic("La capacidad de la caché debe ser mayor que cero")
	}
	return &LRUCache{
		capacity: capacity,
		ll:       list.New(),
		cache:    make(map[interface{}]*list.Element),
		mu:       sync.Mutex{}, // Inicializamos el Mutex
	}
}

// Get recupera un valor de la caché por su clave.
func (c *LRUCache) Get(key interface{}) (value interface{}, ok bool) {
	c.mu.Lock()         // Bloquea el mutex antes de acceder a la caché
	defer c.mu.Unlock() // Asegura que el mutex se desbloquee al salir de la función

	if ele, hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele)
		return ele.Value.(*Entry).value, true
	}
	return nil, false
}

// Put añade o actualiza un valor en la caché.
func (c *LRUCache) Put(key, value interface{}) {
	c.mu.Lock()         // Bloquea el mutex
	defer c.mu.Unlock() // Desbloquea el mutex

	if ele, hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele)
		ele.Value.(*Entry).value = value
		return
	}

	entry := &Entry{key: key, value: value}
	ele := c.ll.PushFront(entry)
	c.cache[key] = ele

	if c.ll.Len() > c.capacity {
		c.removeOldest() // Esta llamada también necesita estar protegida por el mutex
	}
}

// removeOldest elimina el elemento menos recientemente usado.
// Nótese que esta función es interna y ya es llamada dentro de un contexto bloqueado por `Put`,
// por lo que no necesita adquirir y liberar el mutex de nuevo.
func (c *LRUCache) removeOldest() {
	ele := c.ll.Back()
	if ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*Entry)
		delete(c.cache, kv.key)
	}
}

// Remove elimina un elemento de la caché por su clave.
func (c *LRUCache) Remove(key interface{}) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if ele, hit := c.cache[key]; hit {
		c.ll.Remove(ele)
		delete(c.cache, key)
	}
}

// Len devuelve el número actual de elementos en la caché.
func (c *LRUCache) Len() int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.ll.Len()
}

Al añadir c.mu.Lock() y defer c.mu.Unlock() en cada método público (Get, Put, Remove, Len), nos aseguramos de que solo una goroutine pueda acceder a los datos internos de la caché a la vez, eliminando las condiciones de carrera. Es importante que removeOldest sea llamado después de que se haya adquirido el mutex en Put, y que la llamada a Len también esté protegida, ya que accede al estado interno de c.ll. El uso de defer es una práctica idiomática en Go para asegurar que los recursos se liberen (o los mutexes se desbloqueen) incluso si ocurren errores.

La librería estándar de Go, con su paquete sync, facilita enormemente la escritura de código concurrente seguro. Personalmente, encuentro la claridad de sync.Mutex y defer muy superior a los enfoques más complejos de otros lenguajes para tareas de sincronización similares.

Ejemplos de uso y casos prácticos

Una caché LRU concurrente como la que hemos construido tiene innumerables aplicaciones en el desarrollo de software moderno:

APIs web y microservicios: Almacenar en caché respuestas de endpoints populares o resultados de llamadas a servicios de terceros. Por ejemplo, una API de perfiles de usuario podría cachear los perfiles más solicitados.
Capas de acceso a bases de datos: Reducir la carga de la base de datos al almacenar los resultados de consultas frecuentes. Esto es común en ORM o librerías de acceso a datos.
Almacenamiento de sesiones: En sistemas donde las sesiones de usuario son costosas de recrear o recuperar (por ejemplo, de una base de datos distribuida), una caché LRU pued