LRU (Least Recently Used) es una política de reemplazo de caché que opera bajo la heurística de que los datos que han sido utilizados recientemente tienen más probabilidades de ser utilizados de nuevo en el futuro. Cuando una caché que utiliza LRU alcanza su capacidad máxima y se debe añadir un nuevo elemento, el algoritmo identifica y elimina el elemento que ha permanecido sin ser accedido durante el período de tiempo más largo. Esto se implementa comúnmente utilizando una combinación de una tabla hash (para búsquedas rápidas) y una lista doblemente enlazada (para mantener el orden de uso y facilitar la reordenación de elementos). Cada vez que un elemento es accedido, se mueve al "frente" o "cabeza" de la lista.
La implementación de LRU es ubicua en sistemas donde la gestión eficiente de la memoria caché es crítica. Ejemplos concretos incluyen: sistemas operativos para la gestión de páginas de memoria virtual (por ejemplo, en Linux y Windows), cachés de CPU (aunque a menudo con variantes como pseudo-LRU debido a la complejidad de hardware), bases de datos para la gestión de bloques de datos en memoria (como el Buffer Pool en MySQL InnoDB o PostgreSQL), cachés de objetos en memoria en aplicaciones web (por ejemplo, usando bibliotecas como Guava Cache en Java o `lru-cache` en Node.js), y cachés de CDN para contenido estático. También es fundamental en sistemas de archivos para la gestión de bloques de disco.
Para un arquitecto de sistemas, comprender LRU es crucial para diseñar sistemas con un rendimiento óptimo y una gestión eficiente de recursos. La elección de LRU implica un trade-off: ofrece una buena aproximación al rendimiento óptimo de caché (que sería conocer el futuro), pero tiene un costo computacional y de memoria. Mantener el orden de uso (típicamente con una lista doblemente enlazada) y realizar búsquedas rápidas (con un mapa hash) añade sobrecarga. En escenarios de alta concurrencia o con patrones de acceso muy específicos, otras políticas como LFU (Least Frequently Used) o variantes de LRU (como 2Q o ARC) podrían ser más adecuadas. Un arquitecto debe evaluar los patrones de acceso a los datos, la latencia aceptable, la capacidad de memoria disponible y la complejidad de implementación antes de decidir si LRU es la política de caché más apropiada para un subsistema dado.