Algoritmo de caché
Un algoritmo de caché es un algoritmo utilizado para gestionar una caché o un grupo de datos. Cuando la caché está llena, decide qué elemento debe ser eliminado de la caché. El término tasa de aciertos describe la frecuencia con la que se puede servir una solicitud desde la caché. El término latencia describe durante cuánto tiempo se puede obtener un elemento de la caché. Los aloritmos de la caché son un compromiso entre la tasa de aciertos y la latencia.
- El algoritmo de almacenamiento en caché más eficiente sería descartar siempre la información que no se vaya a necesitar durante el mayor tiempo posible en el futuro. Este resultado óptimo se conoce como el algoritmo óptimo de Belady o el algoritmo clarividente. Dado que, por lo general, es imposible predecir hasta cuándo se necesitará la información en el futuro, esto no suele ser posible en la práctica. El mínimo práctico sólo puede calcularse tras la experimentación, y se puede comparar la eficacia del algoritmo de caché realmente elegido con el mínimo óptimo.
- Least Recently Used (LRU): borra primero los elementos menos utilizados. Este algoritmo requiere llevar un registro de lo que se ha utilizado y cuándo. Esto es costoso si se quiere asegurar que el algoritmo siempre descarte el elemento menos usado recientemente. Las implementaciones generales de esta técnica requieren mantener "bits de edad" para las líneas de caché y rastrear la línea de caché "menos usada recientemente" basándose en los bits de edad. En esta implementación, cada vez que se utiliza una línea de caché, la edad de todas las demás líneas de caché cambia. LRU es en realidad una familia de algoritmos de caché con miembros que incluyen: 2Q de Theodore Johnson y Dennis Shasha y LRU/K de Pat O'Neil, Betty O'Neil y Gerhard Weikum.
- Usado más recientemente (MRU): Este algoritmo borra primero los elementos utilizados más recientemente. Este mecanismo de almacenamiento en caché se utiliza habitualmente en las cachés de memoria de las bases de datos.
- Pseudo-LRU (PLRU): Hay ciertos casos en los que la LRU es muy difícil de implementar. En estos casos puede ser suficiente saber que en la mayoría de los casos se elimina uno de los elementos utilizados más recientemente. El algoritmo PLRU puede utilizarse en estos casos, ya que sólo necesita un bit por elemento de la caché para funcionar.
- Conjunto asociativo de 2 vías: para cachés de CPU de alta velocidad donde incluso PLRU es demasiado lento. La dirección de un nuevo elemento se utiliza para calcular una de las dos posibles ubicaciones en la caché a las que puede ir. La LRU de las dos se descarta. Esto requiere un bit por cada par de líneas de caché, para indicar cuál de las dos fue la menos utilizada recientemente.
- Caché de mapeo directo: para las cachés de CPU de mayor velocidad, donde incluso las cachés asociativas de 2 vías son demasiado lentas. La dirección del nuevo elemento se utiliza para calcular la ubicación en la caché a la que puede ir. Lo que había antes se descarta.
- Uso menos frecuente (LFU): El LFU cuenta la frecuencia con la que se necesita un artículo. Los que se utilizan con menos frecuencia se descartan primero.
- Adaptive Replacement Cache (ARC): equilibra constantemente entre LRU y LFU, para mejorar el resultado combinado.
- Algoritmo de almacenamiento en caché de colas múltiples (MQ): (por Y. Zhou J.F. Philbin y Kai Li).
Otras cosas a tener en cuenta:
- Artículos con diferente coste: guarda los artículos que son caros de obtener, por ejemplo, los que tardan mucho tiempo en conseguirse.
- Artículos que ocupan más caché: Si los artículos tienen diferentes tamaños, la caché puede querer descartar un artículo grande para almacenar varios más pequeños.
- Elementos que caducan con el tiempo: Algunas cachés guardan información que caduca (por ejemplo, una caché de noticias, una caché de DNS o una caché de navegador web). El ordenador puede descartar elementos porque han caducado. Dependiendo del tamaño de la caché, puede que no sea necesario ningún algoritmo de caché para descartar elementos.
También existen varios algoritmos para mantener la coherencia de la caché. Esto sólo se aplica a las situaciones en las que se utilizan varias cachés independientes para los mismos datos (por ejemplo, varios servidores de bases de datos que actualizan el mismo archivo de datos compartido).
Qué ubicaciones de memoria pueden ser almacenadas en caché por qué ubicaciones de caché
Preguntas y respuestas
P: ¿Qué es un algoritmo de caché?
R: Un algoritmo de caché es un algoritmo utilizado para gestionar una caché o un grupo de datos. Decide qué elemento debe eliminarse de la caché cuando ésta está llena.
P: ¿Qué es la tasa de aciertos?
R: La tasa de aciertos describe la frecuencia con la que una solicitud puede ser servida desde la caché.
P: ¿Qué describe la latencia?
R: La latencia describe durante cuánto tiempo se puede obtener un elemento de la caché.
P: ¿Qué es el algoritmo óptimo de Belady?
R: El algoritmo óptimo de Belady, también conocido como algoritmo clarividente, es un algoritmo eficiente de almacenamiento en caché que descarta siempre la información que no se necesitará durante más tiempo en el futuro. Por lo general, este resultado no puede aplicarse en la práctica porque requiere predecir lo que se necesitará en un futuro lejano.
P: ¿Cómo funciona LRU (Least Recently Used)?
R: LRU borra primero los elementos utilizados menos recientemente y requiere llevar un registro de qué se utilizó y cuándo mediante el uso de "bits de antigüedad" para cada línea de caché y el seguimiento de cuál se utilizó menos recientemente en función de los bits de antigüedad. Cada vez que se utiliza una línea de caché, las edades de todas las demás líneas de caché se modifican en consecuencia.
P: ¿Cómo funciona MRU (Most Recently Used)?
R: MRU borra primero los elementos utilizados más recientemente y este mecanismo de almacenamiento en caché se utiliza habitualmente para las memorias caché de las bases de datos.
P: ¿Qué otros algoritmos existen para mantener la coherencia de la caché?
R: Existen varios algoritmos para mantener la coherencia de la caché cuando se utilizan varias cachés independientes para datos compartidos, como cuando varios servidores de bases de datos actualizan un único archivo de datos compartidos.
