Programando un LRUCache en Go con Github

En el post anterior contaba mi experiencia probando Copilot durante una semana. En este vamos a implementar una estructura de datos, LRUCache, utilizando asistentes con IA para ver qué tal funcionan.

Desde que empecé con los ordenadores siempre me han llamado la atención las estructuras de datos. Me encanta estudiarlas, entenderlas y conocer qué casos de uso reales tienen. Al final una de las cosas que me encanta es la optimización y pensar cómo hacer más rápidos los algoritmos que utilizamos de forma cotidiana en nuestro día a día sin darnos cuenta: procesamiento de imágenes, streaming de vídeo, lectura de datos de disco... hay un sin fin de ejemplos que podría traer.

Luego también están los contra ejemplos, y es que al final hoy en día muchas aplicaciones terminan siendo "simples" CRUDs, y es relativamente fácil hacer que vayan lentos y esto es algo que no deja de sorprenderme, ya que en mi caso valoro mucho la optimización y el cuidado de ciertas partes de un producto.

Es por esto mismo que me encanta estudiar las estructuras de datos y, una que llevo un tiempo queriendo implementar es una LRUCache. Que además suele ser una pregunta de entrevista en muchas ocasiones para ver cómo una persona razona y qué estructuras de datos conoce.

En el vídeo que acompaña al post puedes ver el desarrollo de esta estructura de datos, utilizando GitHub Copilot para sacar tu mismo tus propias conclusiones, y puedes ver el código en el siguiente repositorio.

¿Qué es una LRUCache?

Una LRUCache es una estructura de datos que se utiliza para almacenar y acceder a una serie de datos, pero limitando el espacio o la capacidad, de forma que si llego al máximo de elementos sea computacionalmente fácil eliminar los elementos menos accedidos. Hay otra variante que es la LFU perp hoy no entraré ahí.

Por tanto la LRUCache es una estructura que necesita dos estructuras de datos internamente:

• Utiliza un tabla HashMap para almacenar los datos, que es eficiente a la hora de insertar y recuperar la información.
• Utiliza un LinkedList para ordenar los elementos que almacena, de forma que el último elemento sea siempre el que no se ha accedido y por otro lado, sea computacionalmente fácil mover un elemento al inicio de la lista cuando se accede.

Precisamente por esto mismo es una estructura de datos muy eficiente para el acceso y para acceder al elemento que queremos invalidar. Si hablamos de notación Big O es O(n) para el almacenamiento, O(1) para el acceso (gracias al hashmap) y O(1) para acceder al elemento menos utilizado. En cuanto al almacenamiento a pesar de ser O(n), como tiene dos estructuras de datos, estamos duplicando parte de la información.

El algoritmo LRU

Esta estructura de datos es relativamente simple y tiene multitud de aplicaciones hoy en día. La primera que se viene a mi mente es tener un servidor web, por ejemplo una página con Next.js, que es computacionalmente costoso de renderizar ya que al final trabaja con strings. Por tanto si nuestra página tiene mucho tráfico, nos interesará tener en caché estos datos para ahorrar y reducir la cantidad de CPU necesario.

Por tanto cuando añadimos capas de caché, por ejemplo un Redis, una política que se puede utilizar es la LRU. Y si lo piensas es una estrategia que es realmente buena a pesar de lo simple que es ya que, en la mayoría de casos, lo que más se accede se mantendrá en memoria mientras que lo que menos se accede podrá ser eliminado. Este es un algoritmo de predicción muy sencillo pero tiene una buena base lógica detrás.

Esta afirmación hay que analizarla bien ya que, si no dispones de suficiente memoria para tener la mayoría de los datos que se acceden, o el patrón de acceso a tu información tiende a ser aleatorio, posiblemente la caché no sea de utilidad en estos casos.

Incluso por ejemplo piensa en un servidor de los de un CDN como Cloudflare o Amazon Cloudfront. En un disco duro normal no cabe toda la información, incluso en un propio servidor, por lo que tendrán la información distribuida con patrones de acceso, y posiblemente en estos algoritmos existirá un LRUCache que decida qué información es la que más se accede para tenerla "caliente" y traer de otros servidores de datos que no sean los edge aquella información que no cabe y que se accede en menor medida.

De hecho el mismo razonamiento lo puedes aplicar a las cachés del CPU cuando debe traerse información del disco.

Conclusión

En este caso quiero utilizar GitHub Copilot para analizar si las sugerencias realmente son una ayuda o no implementando algo más complejo que un CRUD, aunque es difícil valorar si yo solo, utilizando o no copilot, voy más rápido. Porque puede ser que me haga más productivo gracias a las sugerencias aunque estas no sean correctas.