El algoritmo de reemplazo de caché más eficiente [cerrado]

Supongo que la mejor respuesta es que depende. En mi experiencia, hay muchos factores que intervienen en la elección de los algoritmos de almacenamiento en caché.

Factores a considerar

1. Equilibrio de lectura / escritura. (¿Qué porcentaje de accesos son lecturas frente a escrituras)?
2. Cantidad de caché.
3. Tipo de medio detrás de la caché. (¿Son unidades SATA lentas o unidades SSD rápidas?)
4. Hits vs Misses. (¿Con qué frecuencia se reescriben o releen las cosas?)
5. Tamaño de acceso promedio (para elegir el tamaño de la página)
6. ¿Qué tan caras son las lecturas y las escrituras?

Una vez que tenga en cuenta todos los diferentes factores, deberá encontrar un algoritmo de caché que lo maneje mejor. Por ejemplo, digamos que tiene una aplicación donde hay muchas escrituras, algunas reescrituras, lecturas de datos escritos recientemente y algún tipo de medio de giro. En este caso, querría una especie de algoritmo de caché híbrido. Para manejar los datos de escritura, es posible que desee algo como Wise order of Writes (WOW) y un algoritmo LRU para los datos que se han leído del disco. La razón de esto es que los accesos al disco son muy caros y el algoritmo WOW hará que sea más eficiente escribir los datos y la LRU mantendrá los datos a los que se accede con frecuencia siempre en caché.

Supongamos que tiene discos SSD, que tienen un tiempo de acceso muy rápido, es posible que desee orientar su elección hacia el algoritmo LRU, ya que los accesos a los discos son relativamente económicos.

En realidad, lo que quiero decir es que no hay una "mejor" respuesta. La mejor respuesta es conocer los factores que se aplican a usted y elegir el algoritmo que mejor los maneje.

Cómo encontrar el algoritmo para ti

Perfila tu sistema. Esto generalmente implica agregar código para mantener las estadísticas de los accesos a la memoria. Al perfilar puede ver qué factores son los más importantes para usted.

En el pasado, he agregado código para rastrear todos los accesos a la memoria durante un período de tiempo. Luego más tarde busco patrones. Busco re-lecturas, re-escrituras, acceso secuencial, acceso aleatorio, etc.

Una vez que haya identificado las cosas de importancia, debe observar todos los diferentes tipos de algoritmos de almacenamiento en caché para ver qué manejan qué cosas son las mejores.

Suponiendo que no sepa casi nada sobre la aplicación que va a desarrollar, debe saber más sobre ella antes de elegir e implementar un sistema de caché. En otras palabras, no hay implementaciones predeterminadas: algunas son buenas para algunos propósitos y son totalmente malas para otras .

Por ejemplo, tome solo dos implementaciones: Usado menos recientemente y Usado menos frecuentemente. ¿Cómo decidir cuál usar antes que otro?

• LRU es bueno cuando está bastante seguro de que el usuario accederá con más frecuencia a los elementos más recientes y nunca o casi nunca volverá a los antiguos. Un ejemplo: un uso general de un cliente de correo electrónico. En la mayoría de los casos, los usuarios acceden constantemente a los correos más recientes. Los leen, los posponen, regresan en unos minutos, horas o días, etc. Pueden encontrar un correo electrónico que recibieron hace dos años, pero es menos frecuente que acceder a los correos electrónicos que recibieron las últimas dos horas.

• Por otra parte, LRU no tiene sentido en el contexto donde el usuario accederá a algunos elementos con mucha más frecuencia que otros. Un ejemplo: con frecuencia escucho la música que me gusta, y puede suceder que en 400 canciones, escuche las mismas cinco al menos una vez por semana, mientras que escuche como máximo una vez al año 100 canciones que no me gustan también mucho. En este caso, LFU es mucho más apropiado.

Al tomar solo dos de las implementaciones, verá que no hay un algoritmo "predeterminado" que pueda usar cuando no quiera pensar cuál es mejor o si no tiene suficiente información sobre la aplicación. Es, bueno, como preguntar si por defecto, debes sumar, restar, multiplicar o dividir dos números para encontrar el resultado de un cálculo cuando no sabes nada al respecto.

¿Por qué limitar sus opciones solo a Wikipedia? Si tiene acceso a una base de datos de investigación como la Biblioteca digital ACM , encontrará aún más algoritmos. También tenga en cuenta sobre el desorden con las patentes. Por ejemplo, ARC es un buen algoritmo, pero desafortunadamente está patentado.

Podría pasar mucho tiempo agonizando sobre el "mejor" algoritmo, o simplemente podría implementar un algoritmo simple y ponerse en marcha con el resto del sistema. Cuando tengas algo verificable, entonces te preocupas por el algoritmo.

Optimización prematura ...

No hay un algoritmo de caché perfecto, siempre puedes encontrar un caso que se comporte muy mal.

Por lo tanto, es importante conocer el problema que se almacena en la memoria caché para determinar el que se comportará menos mal.

Además, debes considerar cuánto tiempo necesitas para almacenar en caché las cosas y por cuánto tiempo puedes almacenar en caché las cosas ...