Políticas de reemplazo de caché

Con este algoritmo, la caché se comporta como una cola FIFO ; expulsa los bloques en el orden en que se agregaron, independientemente de la frecuencia o la cantidad de veces que se haya accedido a ellos previamente.

La caché se comporta como una pila , y a diferencia de una cola FIFO, elimina primero el bloque añadido más recientemente, independientemente de la frecuencia o la cantidad de veces que se haya accedido a él previamente.

SIEVE es un algoritmo de desalojo simple diseñado específicamente para cachés web, como cachés de clave-valor y redes de entrega de contenido. Utiliza la idea de promoción perezosa y degradación rápida. ^{[ 5 ]} Por lo tanto, SIEVE no actualiza la estructura de datos global en los aciertos de caché y retrasa la actualización hasta el momento del desalojo; mientras tanto, desaloja rápidamente los objetos recién insertados porque las cargas de trabajo de la caché tienden a mostrar altas tasas de un solo acierto, y la mayoría de los objetos nuevos no vale la pena mantenerlos en la caché. SIEVE utiliza una única cola FIFO y una mano móvil para seleccionar los objetos a desalojar. Los objetos en la caché tienen un bit de metadatos que indica si el objeto ha sido solicitado después de ser admitido en la caché. La mano de desalojo apunta al final de la cola al principio y se mueve hacia el principio con el tiempo. En comparación con el algoritmo de desalojo CLOCK, los objetos retenidos en SIEVE permanecen en la posición anterior. Por lo tanto, los objetos nuevos siempre están al principio y los objetos antiguos siempre están al final. A medida que la mano se mueve hacia la cabeza, los nuevos objetos son expulsados ​​rápidamente (degradación rápida). ^{[ 6 ]}

Descarta primero los elementos menos usados. Este algoritmo requiere llevar un registro de lo que se usó y cuándo, lo cual es engorroso. Requiere "bits de antigüedad" para las líneas de caché y rastrea la línea de caché menos usada en función de estos bits de antigüedad. Cuando se usa una línea de caché, la antigüedad de las demás líneas de caché cambia. LRU es una familia de algoritmos de almacenamiento en caché que incluye 2Q de Theodore Johnson y Dennis Shasha ^{[ 7 ]} y LRU/K de Pat O'Neil, Betty O'Neil y Gerhard Weikum ^{[ 8 ]} . La secuencia de acceso para el ejemplo es ABCDEDF:

Cuando ABCD se instala en los bloques con números de secuencia (incrementa 1 por cada nuevo acceso) y se accede a E, se produce un fallo y debe instalarse en un bloque. Con el algoritmo LRU, E reemplazará a A porque A tiene el rango más bajo (A(0)). En el penúltimo paso, se accede a D y se actualiza el número de secuencia. A continuación, se accede a F, reemplazando a B , que tenía el rango más bajo (B(1)). 

El algoritmo de caché menos usado con reconocimiento de tiempo (TLRU) ^{[ 9 ]} es una variante de LRU diseñada para cuando el contenido de una caché tiene una vida útil válida. Este algoritmo es adecuado para aplicaciones de caché de red, como redes centradas en la información (ICN), redes de entrega de contenido (CDN) y redes distribuidas en general. TLRU introduce el término TTU (tiempo de uso), una marca de tiempo del contenido (o de una página) que estipula el tiempo de uso del contenido en función de su ubicación y del editor del contenido. TTU proporciona mayor control al administrador local sobre la gestión del almacenamiento en red.

Cuando llega contenido sujeto a TLRU, un nodo de caché calcula el TTU local basándose en el TTU asignado por el editor del contenido. El valor del TTU local se calcula mediante una función definida localmente. Una vez calculado el valor del TTU local, se reemplaza un subconjunto del contenido total del nodo de caché. TLRU garantiza que el contenido menos popular y de corta duración se reemplace con el contenido entrante.

A diferencia de LRU, MRU descarta primero los elementos usados ​​más recientemente. En la 11.ª conferencia VLDB, Chou y DeWitt afirmaron: «Cuando un archivo se escanea repetidamente en un patrón de referencia [secuencial en bucle], MRU es el mejor algoritmo de reemplazo ». ^{[ 10 ]} Investigadores que presentaron en la 22.ª conferencia VLDB señalaron que, para patrones de acceso aleatorio y escaneos repetidos sobre grandes conjuntos de datos (también conocidos como patrones de acceso cíclico), los algoritmos de caché MRU tienen más aciertos que LRU debido a su tendencia a retener datos más antiguos. ^{[ 11 ]} Los algoritmos MRU son más útiles en situaciones donde cuanto más antiguo es un elemento, mayor es la probabilidad de que se acceda a él. La secuencia de acceso para el ejemplo es ABCDECDB:

Los bloques ABCD se colocan en la caché, ya que hay espacio disponible. En el quinto acceso (E), el bloque que contenía D se reemplaza por E, puesto que este bloque se utilizó más recientemente. En el siguiente acceso (a D), se reemplaza C, puesto que fue el bloque al que se accedió justo antes de D.

Una caché SLRU se divide en dos segmentos: de prueba y protegido. Las líneas de cada segmento se ordenan desde las más recientes hasta las menos recientes. Los datos de los fallos se añaden a la caché en el extremo más reciente del segmento de prueba. Los aciertos se eliminan de donde se encuentran y se añaden al extremo más reciente del segmento protegido; las líneas del segmento protegido se han accedido al menos dos veces. El segmento protegido es finito; la migración de una línea del segmento de prueba al segmento protegido puede forzar la migración de la línea LRU del segmento protegido al extremo más reciente del segmento de prueba, lo que le da a esta línea otra oportunidad de ser accedida antes de ser reemplazada. El límite de tamaño del segmento protegido es un parámetro SLRU que varía según los patrones de carga de trabajo de E/S . Cuando se deben descartar datos de la caché, las líneas se obtienen del extremo LRU del segmento de prueba. ^{[ 12 ]}

La técnica LRU puede resultar costosa en cachés con alta asociatividad . El hardware práctico suele emplear una aproximación para lograr un rendimiento similar a un menor coste.

Pseudo-LRU (PLRU)

Para cachés de CPU con alta asociatividad (generalmente > cuatro vías), el costo de implementación de LRU se vuelve prohibitivo. En muchas cachés de CPU, un algoritmo que casi siempre descarta uno de los elementos menos usados ​​recientemente es suficiente; muchos diseñadores de CPU optan por un algoritmo PLRU, que solo necesita un bit por elemento de caché para funcionar. PLRU suele tener una tasa de fallos ligeramente peor, una latencia ligeramente mejor , consume un poco menos de energía que LRU y tiene una sobrecarga menor que LRU.

Los bits funcionan como un árbol binario de punteros de un bit que apuntan a un subárbol menos utilizado. Siguiendo la cadena de punteros hasta el nodo hoja se identifica el candidato de reemplazo. Con un acceso, todos los punteros en la cadena desde el nodo hoja de la ruta accedida hasta el nodo raíz se configuran para apuntar a un subárbol que no contiene la ruta accedida. La secuencia de acceso en el ejemplo es ABCDE:

Cuando se accede a un valor (como A) y este no se encuentra en la caché, se carga desde la memoria y se coloca en el bloque al que apuntan las flechas en el ejemplo. Una vez colocado dicho bloque, las flechas se invierten para apuntar en la dirección opuesta. Se colocan A, B, C y D; E reemplaza a A a medida que se llena la caché, ya que era hacia donde apuntaban las flechas, y las flechas que conducían a A se invierten para apuntar en la dirección opuesta (hacia B, el bloque que se reemplazará en el siguiente fallo de caché).

El algoritmo LFU contabiliza la frecuencia de uso de un elemento; los menos utilizados se descartan primero. Es similar a LRU, con la diferencia de que se almacena el número de veces que se accedió a un bloque, en lugar de la fecha de acceso más reciente. Durante una secuencia de acceso, el bloque menos utilizado se elimina de la caché.

El algoritmo de uso reciente menos frecuente (LFRU) ^{[ 16 ]} combina las ventajas de LFU y LRU. LFRU es adecuado para aplicaciones de caché de red como ICN , CDN y redes distribuidas en general. En LFRU, la caché se divide en dos particiones: privilegiada y no privilegiada. La partición privilegiada está protegida; si el contenido es popular, se coloca en ella. Para reemplazar la partición privilegiada, LFRU elimina el contenido de la partición no privilegiada, lo transfiere de la privilegiada a la no privilegiada e inserta nuevo contenido en la privilegiada. Se utiliza LRU para la partición privilegiada y un algoritmo LFU aproximado (ALFU) para la partición no privilegiada.

Una variante, LFU con envejecimiento dinámico (LFUDA), utiliza el envejecimiento dinámico para acomodar cambios en un conjunto de objetos populares; agrega un factor de antigüedad de caché al contador de referencias cuando se agrega un nuevo objeto a la caché o se vuelve a referenciar un objeto existente. LFUDA incrementa la antigüedad de la caché al desalojar bloques estableciéndola al valor de clave del objeto desalojado, y la antigüedad de la caché siempre es menor o igual al valor de clave mínimo en la caché. ^{[ 17 ]} Si un objeto fue accedido frecuentemente en el pasado y se vuelve impopular, permanecerá en la caché durante mucho tiempo (impidiendo que objetos nuevos o menos populares lo reemplacen). El envejecimiento dinámico reduce la cantidad de tales objetos, haciéndolos aptos para ser reemplazados, y LFUDA reduce la contaminación de la caché causada por LFU cuando una caché es pequeña.

Este es un nuevo algoritmo de desalojo diseñado en 2023. En comparación con los algoritmos existentes, que en su mayoría se basan en LRU (menos usado recientemente), S3-FIFO solo utiliza tres colas FIFO: una cola pequeña que ocupa el 10% del espacio de caché, una cola principal que utiliza el 90% del espacio de caché y una cola fantasma que solo almacena metadatos de objetos. La cola pequeña se utiliza para filtrar objetos de un solo acceso (objetos a los que solo se accede una vez en un corto período de tiempo); la cola principal se utiliza para almacenar objetos populares y utiliza la reinserción para mantenerlos en la caché; y la cola fantasma se utiliza para capturar objetos potencialmente populares que se desalojaron de la cola pequeña. Los objetos se insertan primero en la cola pequeña (si no se encuentran en la cola fantasma, de lo contrario se insertan en la cola principal); Al ser expulsado de la cola pequeña, si un objeto ha sido solicitado, se reinserta en la cola principal; de lo contrario, se expulsa y los metadatos se rastrean en la cola fantasma. ^{[ 18 ]}

RRIP ^{[ 20 ]} es una política flexible, propuesta por Intel , que busca brindar una buena resistencia al escaneo al tiempo que permite la expulsión de líneas de caché antiguas que no se han reutilizado. Todas las líneas de caché tienen un valor de predicción, el RRPV (valor de predicción de re-referencia), que debería correlacionarse con el momento en que se espera que la línea se reutilice. El RRPV suele ser alto al insertar; si una línea no se reutiliza pronto, se expulsará para evitar escaneos (grandes cantidades de datos utilizados solo una vez) que llenen la caché. Cuando una línea de caché se reutiliza, el RRPV se establece en cero, lo que indica que la línea se ha reutilizado una vez y es probable que se reutilice de nuevo.

En caso de fallo de caché, se elimina la línea con un RRPV igual al máximo posible; con valores de 3 bits, se elimina una línea con un RRPV de 2³ ^- 1 = 7. Si ninguna línea tiene este valor, todos los RRPV del conjunto se incrementan en 1 hasta que uno lo alcance. Se necesita un criterio de desempate, que generalmente es la primera línea de la izquierda. Este incremento es necesario para asegurar que las líneas más antiguas se gestionen correctamente y se eliminen si no se reutilizan.

Hawkeye ^{[ 19 ]} intenta emular el algoritmo de Bélády utilizando accesos anteriores de una PC para predecir si los accesos que produce generan accesos amigables con la caché (utilizados posteriormente) o accesos adversos a la caché (no utilizados posteriormente). Muestrea una serie de conjuntos de caché no alineados y utiliza un historial de longitud${\displaystyle 8\times {\text{el tamaño de la caché}}}$y emula el algoritmo de Bélády en estos accesos. Esto permite que la política determine qué líneas deberían haberse almacenado en caché y cuáles no, prediciendo si una instrucción es amigable con la caché o no. Estos datos se introducen en un RRIP; los accesos desde instrucciones amigables con la caché tienen un valor RRPV más bajo (probablemente se desalojarán más tarde), y los accesos desde instrucciones no amigables con la caché tienen un valor RRPV más alto (probablemente se desalojarán antes). El backend del RRIP toma las decisiones de desalojo. La caché muestreada y el generador OPT establecen el valor RRPV inicial de las líneas de caché insertadas. Hawkeye ganó el campeonato de caché CRC2 en 2017, ^{[ 23 ]} y Harmony ^{[ 24 ]} es una extensión de Hawkeye que mejora el rendimiento de la precarga.

Mockingjay ^{[ 25 ]} intenta mejorar Hawkeye de varias maneras. Elimina la predicción binaria, lo que le permite tomar decisiones más precisas sobre qué líneas de caché desalojar, y deja la decisión sobre qué línea de caché desalojar para cuando haya más información disponible.

Mockingjay mantiene una caché muestreada de accesos únicos, las PC que los produjeron y sus marcas de tiempo. Cuando se accede nuevamente a una línea en la caché muestreada, la diferencia de tiempo se enviará al predictor de distancia de reutilización. El RDP utiliza aprendizaje de diferencia temporal , ^{[ 26 ]} donde el nuevo valor de RDP se incrementará o disminuirá en un número pequeño para compensar los valores atípicos; el número se calcula como${\displaystyle w=\min \left(1,{\frac {\text{diferencia de marca de tiempo}}{16}}\right)}$Si el valor no se ha inicializado, se inserta directamente la distancia de reutilización observada. Si la caché muestreada está llena y es necesario descartar una línea, se le indica al RDP que el PC que accedió por última vez a ella genera accesos en flujo continuo.

En caso de acceso o inserción, el tiempo estimado de reutilización (ETR) de esta línea se actualiza para reflejar la distancia de reutilización prevista. En caso de fallo de caché, se elimina la línea con el valor ETR más alto. Mockingjay ofrece resultados muy similares al algoritmo óptimo de Bélády.

LIRS es un algoritmo de reemplazo de páginas con un rendimiento superior al de LRU y otros algoritmos de reemplazo más recientes. La distancia de reutilización es una métrica para clasificar dinámicamente las páginas accedidas y tomar una decisión de reemplazo. ^{[ 31 ]} LIRS aborda las limitaciones de LRU utilizando la recencia para evaluar la recencia entre referencias (IRR) y así tomar una decisión de reemplazo.

En el diagrama, X indica que se accede a un bloque en un momento determinado. Si se accede al bloque A1 en el tiempo 1, su recencia será 0; este es el primer bloque al que se accede y el IRR será 1, ya que predice que se volverá a acceder a A1 en el tiempo 3. En el tiempo 2, dado que se accede a A4, la recencia se convertirá en 0 para A4 y en 1 para A1; A4 es el objeto al que se accedió más recientemente, y el IRR se convertirá en 4. En el tiempo 10, el algoritmo LIRS tendrá dos conjuntos: un conjunto LIR = {A1, A2} y un conjunto HIR = {A3, A4, A5}. En el tiempo 10, si hay acceso a A4 ocurre un fallo; LIRS desalojará A5 en lugar de A2 debido a su mayor recencia.

La caché de reemplazo adaptativo (ARC) equilibra constantemente entre LRU y LFU para mejorar el resultado combinado. ^{[ 32 ]} Mejora SLRU utilizando información sobre elementos de caché recientemente desalojados para ajustar el tamaño de los segmentos protegidos y de prueba para hacer el mejor uso del espacio de caché disponible. ^{[ 33 ]}

El reloj con reemplazo adaptativo (CAR) combina las ventajas de ARC y Clock . CAR ofrece un rendimiento comparable al de ARC y supera a LRU y Clock. Al igual que ARC, CAR se autoajusta y no requiere parámetros especificados por el usuario.

El algoritmo de reemplazo de múltiples colas (MQ) se desarrolló para mejorar el rendimiento de una caché de búfer de segundo nivel, como una caché de búfer de servidor, y fue presentado en un artículo de Zhou, Philbin y Li. ^{[ 34 ]} La caché MQ contiene m colas LRU: Q ₀ , Q ₁ , ..., Q _{m -1} . El valor de m representa una jerarquía basada en la vida útil de todos los bloques en esa cola. ^{[ 35 ]}

Pannier ^{[ 36 ]} es un mecanismo de almacenamiento en caché flash basado en contenedores que identifica aquellos contenedores cuyos bloques tienen patrones de acceso variables. Pannier tiene una estructura de cola de supervivencia basada en una cola de prioridad para clasificar los contenedores según su tiempo de supervivencia, que es proporcional a los datos activos en el contenedor.