caché de reemplazo adaptativo

La caché de reemplazo adaptativo ( ARC ) es un algoritmo de reemplazo de páginas con un rendimiento superior ^{[ 1 ]} al de LRU (menos usado recientemente). Esto se logra mediante el seguimiento de las páginas usadas con frecuencia y las usadas recientemente, además de un historial de eliminación reciente para ambas. El algoritmo fue desarrollado ^{[ 2 ]} en el Centro de Investigación Almaden de IBM . En 2006, IBM obtuvo una patente para la política de caché de reemplazo adaptativo .

El algoritmo LRU básico mantiene una lista ordenada (el directorio de caché) de las entradas de recursos en la caché, con el orden de clasificación basado en la hora 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 última entrada. Los aciertos de caché se mueven a la parte superior, desplazando todas las demás entradas hacia abajo.

ARC mejora la estrategia LRU básica dividiendo el directorio de caché en dos listas, T1 y T2, para las entradas referenciadas recientemente y con frecuencia. A su vez, cada una de estas listas se extiende con una lista fantasma (B1 o B2), que se adjunta al final de las dos listas. Estas listas fantasma actúan como marcadores al registrar el historial de entradas de caché recientemente eliminadas, y el algoritmo utiliza los resultados de las listas fantasma para adaptarse a los cambios recientes en el uso de recursos. Cabe destacar que las listas fantasma solo contienen metadatos (claves para las entradas) y no los datos del recurso en sí; es decir, cuando una entrada se elimina a una lista fantasma , sus datos se descartan. El directorio de caché combinado se organiza en cuatro listas LRU:

1. T1, para entradas recientes de la caché.
2. T2, para entradas frecuentes, referenciadas al menos dos veces.
3. B1, entradas fantasma recientemente eliminadas de la caché T1, pero que aún se rastrean.
4. B2, entradas fantasma similares , pero expulsado de T2.

T1 y B1, en conjunto, se denominan L1, un historial combinado de referencias individuales 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 la 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 desde la parte superior, indicada por el marcador ! . ^ indica el tamaño objetivo para T1, y puede ser igual, menor o mayor que el tamaño real (como se indica con ! ).

• Las nuevas entradas entran en T1, a la izquierda de ! , y son empujadas gradualmente hacia la izquierda, hasta que finalmente son expulsadas de T1 a B1, y finalmente salen por completo.
• Cualquier entrada en L1 que se vuelva a mencionar, tiene otra oportunidad y entra en L2, justo a la derecha del marcador central ! . Desde allí, se desplaza de nuevo hacia afuera, desde T2 hasta B2. Las entradas en L2 que vuelven a ser mencionadas pueden repetir este proceso indefinidamente, hasta que finalmente desaparecen en el extremo derecho de B2.

Actualmente, ARC está 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 a la caché de páginas del sistema de archivos Solaris tradicional en memoria virtual . Se ha modificado para permitir páginas bloqueadas que están actualmente en uso y no se pueden liberar.

PostgreSQL utilizó ARC en su gestor de búferes durante un breve período (versión 8.0.0), pero rápidamente lo reemplazó con otro algoritmo, alegando preocupaciones sobre una patente de IBM sobre ARC. ^{[ 4 ]}

vSAN de VMware (anteriormente Virtual SAN) 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é multinivel como cachés de lectura. En OpenZFS, las lecturas de disco suelen acceder a la caché de disco de primer nivel en la RAM mediante ARC. Si se configura una 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 la RAM, los almacena en una SSD rápida. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}

• Reloj con reemplazo adaptativo
• Algoritmo de almacenamiento en caché de LIRS

• ARC: Una caché de reemplazo autoajustable y de baja sobrecarga (2003) por Nimrod Megiddo, Dharmendra Modha
• Wiki de gestión de memoria de Linux
• Borbonés, Roch. Dinámica ZFS
• Implementación en Python, receta 576532
• Comparación de LRU, ARC y otros