Adaptive Replacement Cache ( ARC ) es un algoritmo de reemplazo de páginas con un mejor rendimiento [1] que LRU (menos recientemente utilizado). Esto se logra manteniendo un registro de las páginas utilizadas con frecuencia y de las utilizadas recientemente, además de un historial de desalojo reciente para ambas. El algoritmo se desarrolló [2] en el IBM Almaden Research Center . En 2006, IBM obtuvo una patente para la política de caché de reemplazo adaptativo.
La LRU básica mantiene una lista ordenada (el directorio de caché) de las entradas de recursos en la caché, con un orden de clasificación basado en el momento del acceso más reciente. Las nuevas entradas se agregan en la parte superior de la lista, después de que se haya eliminado la entrada inferior. Los accesos a la caché se mueven a la parte superior, desplazando a todas las demás entradas hacia abajo.
ARC mejora la estrategia básica de LRU al dividir el directorio de caché en dos listas, T1 y T2, para las entradas a las que se hace referencia recientemente y con frecuencia. A su vez, cada una de ellas se amplía con una lista fantasma (B1 o B2), que se adjunta al final de las dos listas. Estas listas fantasma actúan como cuadros de mando al realizar un seguimiento del historial de las entradas de caché recientemente expulsadas, y el algoritmo utiliza los resultados fantasma para adaptarse a los cambios recientes en el uso de los recursos. Tenga en cuenta que las listas fantasma solo contienen metadatos (claves para las entradas) y no los datos del recurso en sí, es decir, cuando se expulsa una entrada en una lista fantasma , sus datos se descartan. El directorio de caché combinado está organizado en cuatro listas LRU:
T1 y B1 juntos se denominan L1, una combinación de antecedentes de referencias únicas recientes. De manera similar, L2 es la combinación de T2 y B2.
Todo el directorio de caché se puede visualizar en una sola línea:
. . . [ B1 <- [ T1 <- ! -> T2 ] -> B2 ] . . [ . . . . [ . . . . . ! . . ^ . . . . ] . . . . ] [ tamaño de caché fijo (c) ]
Los corchetes internos [ ] indican el caché real, que aunque tiene un tamaño fijo, puede moverse libremente a través del historial B1 y B2.
L1 ahora se muestra de derecha a izquierda, comenzando en la parte superior, indicado por el marcador ! . ^ indica el tamaño objetivo para T1, y puede ser igual, menor o mayor que el tamaño real (como lo indica ! ).
Las entradas que ingresan o vuelven a ingresar al caché (T1, T2) harán que ! se mueva hacia el marcador de destino ^ . Si no existe espacio libre en el caché, este marcador también determina si T1 o T2 expulsarán una entrada.
ARC está actualmente implementado en los controladores de almacenamiento DS6000/ DS8000 de IBM .
El sistema de archivos escalable ZFS de Sun Microsystems utiliza una variante [3] de ARC como alternativa al caché de páginas del sistema de archivos Solaris tradicional en la memoria virtual. Se ha modificado para permitir páginas bloqueadas que están actualmente en uso y no se pueden desocupar.
PostgreSQL utilizó ARC en su administrador de buffer por un breve tiempo (versión 8.0.0), pero rápidamente lo reemplazó con otro algoritmo, citando preocupaciones sobre una patente de IBM sobre ARC. [4]
vSAN (anteriormente Virtual SAN) de VMware es un producto de almacenamiento definido por software (SDS) hiperconvergente desarrollado por VMware. Utiliza una variante de ARC en su algoritmo de almacenamiento en caché. [5]
OpenZFS admite el uso de ARC y L2ARC en una caché de varios niveles como cachés de lectura. En OpenZFS, las lecturas de disco a menudo alcanzan la caché de disco de primer nivel en RAM mediante ARC. Si se configura un SSD para almacenar la caché de disco de segundo nivel, se denomina L2ARC. L2ARC utiliza el mismo algoritmo ARC, pero en lugar de almacenar los datos en caché en RAM, L2ARC almacena los datos en caché en un SSD rápido. [6] [7] [8] [9] [10] [11]