Hoy en día los tiempos de respuesta de las aplicaciones se ha convertido de gran consideración para los usuarios, observamos que nuestros sitios favoritos como Amazon, Netflix y Spotify nos ofrece un dashboard con artículos que nos pudiera interesar o posiblemente mostrar nuestras últimas películas o series vistas pero no terminadas, y todo esto lo obtenemos casi al instante solo después de hacer un inicio de sesión.

y muchos de ustedes se preguntarán, Cómo le hacen estos sitios para mostrar todo este menu de artículos, películas y canciones en tan poco tiempo?, si sabemos que hacer  una petición o request que viaja a través de internet transcurre por un determinado tiempo para pasar por capa de negocios, colectar la información y enseguida hacer un query a la base de datos y para agregar cargarle que nos trae imágenes.

Toda esta magia se hace a través de una estrategia de cacheo llamada LRU Cache, donde la principal idea es tener un número de elementos N puestos en cache, y que estos elementos muestren la fotografía actual de los elementos mas solicitados por el usuario en un tiempo determinado.

Pongamos la siguiente analogía del vendedor de la tiendita o abarrote familiar.

La persona que atiende este establecimiento tiene un estante con los artículos mas solicitados por los clientes, de manera que no tenga que ir hasta la bodega para traer ese articulo, por lo que hace el servicio al cliente mucho mas rápido y eficiente, lo mismo sucede con las aplicaciones de (Amazon, Netflix y Spotify) al momento de tener un cache con los elementos mas utilizados por los usuarios hace que el servicio sea proveído de manera inmediata, mejorando tiempos de respuesta y también evitando viajes a la base de datos y consumir recursos de red, procesamiento y datos.

LRU Cache (Least Recently Used Cached)

LRU Cache ha llegado a convertirse una de las estrategias favoritas de cacheo, y la más utilizada por muchos de los sitios de internet más populares, el concepto es que tienes un cache limitado, con N elementos, y cuentas con 2 referencias, una referencia que apunta al elemento más nuevo de la lista (mostRecentlyUsed) y la segunda referencia apunta al elemento más antiguo de la lista llamado el elemento menos recientemente usado (leastRecentlyUsed).

Regresando a las analogías, imaginemos que vamos a nuestro supermercado favorito a la sección de panadería y encontramos el siguiente estante con Pan.

Este seria nuestro cache en memoria donde cada Pan representaría un objeto, que es consumido por los diferentes usuarios, pero que pasa cuando nuestros objetos ó panes empiezan a envejecer y se entrega nuevo surtido.

Fuentes: https://www.mentalfloss.com/article/556314/safety-primer-for-dealing-with-moldy-foods

El personal de Panadería, empiezan a desalojar los panes mas antiguos del estante, lo que se traduce a desalojar objetos de nuestro cache y dejando los objetos más recientes., a esta política de desalojo se le llama "Cache Eviction", y este desalojo viene por la referencia del menos recientemente usado (LeastRecentlyUsed).

Ejemplo:

Nuestro cache tiene capacidad de 4 elementos y esta lleno, al llegar un nuevo elemento, un elemento debe desalojarse de manera que el elemento más reciente entre en el cache.

El elemento menos recientemente usado es desalojado y el puntero LRU, apunta al nuevo menos recientemente usado, y el nuevo elemento que entro a nuestro cache se introduce al principio de la lista y es apuntado por la referencia de mostRecentlyUsed.

Lectura

Cada vez que se accede a un elemento que se encuentra en el cache hace algo llamado "Cache Hit", y ese nuevo elemento pasa a ser el nuevo mas recientemente usado (mostRecentlyUsed).

Lectura de Nodo 2 (CacheNode2) haciendo un cache hit.
El Elemento más recientemente accesado pasa al principio de la lista.

Implementación.

De manera que tengamos un cache sumamente rápido, necesitamos de 2 estructuras de datos, un HashMap y una lista doblemente ligada, el HashMap nos ayudará a encontrar objetos basados en su llave (key) en tiempo constante O(1).

La Inserción del nuevo elemento al cache, es hecho utilizando la la lista doblemente ligada, donde el elemento introducido se inserta al principio de la lista, otorgándonos tiempo constante O(1).

Donde el concepto de las dos estructuras de datos quedaría de la siguiente manera:

Mapa hace referencia a cada elemento de la lista cacheada, otorgando el objeto en O(1)

LRU Cache Ventajas

  1. Acceso Súper Rápido
  2. Actualizaciones Súper Rápidas

LRU Cache Desventajas

  1. Mucho Espacio en Memoria ( 2 Estructuras de datos conteniendo mismo número de elementos)

En el siguiente video explico cómo efectuar la implementación de LRU Cache usando Java.

También tenemos la explicación en video.

Si te interesa como implementar LRU Cache a tu Microservicio utilizando Redis, en el siguiente curso te lo explicamos.

https://www.centripio.io/courses/microservicios-spring-boot-essentials

https://www.centripio.io/courses/microservicios-spring-boot-essentials