algorithm caching generalization cache-invalidation

algorithm - Invalidación de caché: ¿hay una solución general?



caching generalization (9)

"Solo hay dos problemas difíciles en informática: la invalidación de caché y el nombramiento de cosas".

Phil Karlton

¿Existe una solución o método general para invalidar un caché? saber cuándo una entrada está obsoleta, por lo que siempre se garantiza la obtención de datos actualizados?

Por ejemplo, considere una función getData() que obtiene datos de un archivo. Lo almacena en caché en función de la última hora modificada del archivo, que comprueba cada vez que se invoca.
A continuación, agrega una segunda función transformData() que transforma los datos y almacena en caché su resultado para la próxima vez que se llame a la función. No tiene conocimiento del archivo. ¿Cómo se agrega la dependencia de que si se cambia el archivo, este caché se vuelve inválido?

Se puede llamar a getData() cada vez que se getData() transformData() y compararlo con el valor que se usó para compilar el caché, pero eso podría terminar siendo muy costoso.

¿Existe una solución o método general para crear un caché, para saber cuándo una entrada está obsoleta, de modo que siempre se garantiza la obtención de datos actualizados?

No, porque todos los datos son diferentes. Algunos datos pueden estar "caducados" después de un minuto, algunos después de una hora, y algunos pueden estar bien por días o meses.

En cuanto a su ejemplo específico, la solución más simple es tener una función de ''comprobación de caché'' para los archivos, a la que llama desde getData y transformData .

De lo que estás hablando es del encadenamiento de dependencia de por vida, una cosa depende de otra y puede modificarse fuera de su control.

Si tiene una función idempotente de a , b , donde, si a y b son iguales, entonces c es el mismo pero el costo de verificar b es alto, entonces usted:

  1. acepte que alguna vez opere con información desactualizada y no siempre revise b
  2. haz tu mejor esfuerzo para que la verificación b más rápida posible

No puedes tener tu pastel y comértelo ...

Si puede superponer un caché adicional sobre la base, esto afecta el problema inicial no un bit. Si eliges 1, entonces tienes la libertad que te hayas dado y puedes almacenar más en caché, pero debes recordar considerar la validez del valor en caché de b . Si elige 2, debe verificar b cada vez, pero puede recurrir a la memoria caché si b a check out.

Si capas cachés debe considerar si ha violado las ''reglas'' del sistema como resultado del comportamiento combinado.

Si sabes que a siempre tiene validez si b hace, puedes organizar tu caché como tal (pseudocódigo):

private map<b,map<a,c>> cache // private func realFunction // (a,b) -> c get(a, b) { c result; map<a,c> endCache; if (cache[b] expired or not present) { remove all b -> * entries in cache; endCache = new map<a,c>(); add to cache b -> endCache; } else { endCache = cache[b]; } if (endCache[a] not present) // important line { result = realFunction(a,b); endCache[a] = result; } else { result = endCache[a]; } return result; }

Obviamente, la estratificación sucesiva (por ejemplo x ) es trivial siempre que, en cada etapa, la validez de la entrada recién agregada coincida con la relación a: b para x : b y x : a .

Sin embargo, es muy posible que pueda obtener tres entradas cuya validez era completamente independiente (o que era cíclica), por lo que no sería posible la creación de capas. Esto significaría que la línea marcada como // importante tendría que cambiar a

if (endCache [a] expiró o no está presente)

El problema en la invalidación de caché es que todo cambia sin que lo sepamos. Por lo tanto, en algunos casos, es posible una solución si hay alguna otra cosa que sí lo sabe y puede notificarnos. En el ejemplo dado, la función getData podría engancharse al sistema de archivos, que conoce todos los cambios en los archivos, independientemente de qué proceso cambie el archivo, y este componente, a su vez, podría notificar al componente que transforma los datos.

No creo que haya una solución mágica general para que el problema desaparezca. Pero en muchos casos prácticos, puede haber oportunidades para transformar un enfoque basado en "encuestas" en uno basado en "interrupciones", que puede hacer que el problema simplemente desaparezca.

En mi humilde opinión, Functional Reactive Programming (FRP) es en cierto sentido una forma general de resolver la invalidación de caché.

Aquí está el por qué: los datos obsoletos en la terminología FRP se llaman glitch . Uno de los objetivos de FRP es garantizar la ausencia de problemas técnicos.

FRP se explica con más detalle en esta charla de "Esencia de FRP" y en esta respuesta SO .

En la charla, las Cell s representan un Objeto / Entidad en caché y una Cell se actualiza si una de sus dependencias se actualiza.

FRP oculta el código de plomería asociado con el gráfico de dependencia y se asegura de que no haya Cell obsoletas.

Otra forma (diferente de FRP) que puedo pensar es ajustar el valor calculado (de tipo b ) en algún tipo de escritor Monad Writer (Set (uuid)) b donde Set (uuid) (notación Haskell) contiene todos los identificadores de los valores mutables de los cuales depende el valor calculado b . Entonces, uuid es un tipo de identificador único que identifica el valor / variable mutable (digamos una fila en una base de datos) de la cual depende el valor de b calculado.

Combine esta idea con los combinadores que operan en este tipo de escritor Monad y que pueden conducir a algún tipo de solución de invalidación de caché general si solo utiliza estos combinadores para calcular un nuevo b . Dichos combinadores (digamos una versión especial de filter ) toman Writer mónadas y (uuid, a) -s como entradas, donde a es una variable / variable mutable, identificada por uuid .

Así que cada vez que cambie los datos "originales" (uuid, a) (digamos los datos normalizados en una base de datos desde la cual se calculó b ) de los cuales depende el valor calculado de tipo b entonces puede invalidar el caché que contiene b si muta cualquier valor a del cual depende el valor de b calculado, porque basado en el Set (uuid) en la mónada de escritor se puede saber cuándo sucede esto.

Así que cada vez que mutes algo con un uuid dado, transmites esta mutación a todos los cachés e invalidan los valores b que dependen del valor mutable identificado con dicho uuid porque la mónada Writer en la que se envuelve b puede indicar si eso b depende de dicho uuid o no.

Por supuesto, esto solo vale la pena si lees mucho más a menudo de lo que escribes.

Un tercer enfoque práctico es usar vistas materializadas en bases de datos y usarlas como caché. AFAIK también intentan resolver el problema de invalidación. Esto, por supuesto, limita las operaciones que conectan los datos mutables a los datos derivados.

Estoy trabajando en un enfoque en este momento basado en las funciones PostSharp y de memoria . Lo he pasado por alto a mi mentor, y él está de acuerdo en que es una buena implementación del almacenamiento en caché de una manera independiente del contenido.

Cada función se puede marcar con un atributo que especifica su período de vencimiento. Cada función marcada de esta manera se memoriza y el resultado se almacena en la memoria caché, con un hash de la llamada a la función y los parámetros utilizados como la clave. Estoy usando Velocity para el backend, que maneja la distribución de los datos de caché.

No hay una solución general, pero

  • Tu caché puede actuar como un proxy (pull). Suponga que su caché conoce la marca de tiempo del último cambio de origen, cuando alguien llama a getData() , el caché le pide al origen su marca de tiempo del último cambio, si es el mismo, devuelve el caché, de lo contrario actualiza su contenido con el de origen y devuelve su contenido . (Una variación es que el cliente envíe directamente la marca de tiempo en la solicitud, la fuente solo devolverá el contenido si su marca de tiempo es diferente).

  • Aún puede usar un proceso de notificación (push), la memoria caché observa la fuente, si la fuente cambia, envía una notificación a la memoria caché que luego se marca como "sucia". Si alguien llama a getData() la caché primero se actualizará a la fuente, eliminará la bandera "sucia"; luego devuelve su contenido.

La elección generalmente hablando depende de:

  • La frecuencia: muchas llamadas en getData() preferirían un impulso para evitar que la fuente se inunde con una función getTimestamp
  • Su acceso a la fuente: ¿Es usted propietario del modelo de origen? Si no, es probable que no pueda agregar ningún proceso de notificación.

Nota: Como el uso de la marca de tiempo es la manera tradicional en que los proxies http están funcionando, otro enfoque es compartir un hash del contenido almacenado. La única manera que conozco de que 2 entidades se actualicen juntas es o te llamo (pull) o me llamas ... (push) eso es todo.

Quizás los algoritmos de caché ajena sean los más generales (o al menos, menos dependientes de la configuración de hardware), ya que usarán primero el caché más rápido y continuarán desde allí. Aquí hay una conferencia del MIT sobre esto: Algoritmos Olvidables de Caché

Si vas a obtenerData () cada vez que haces la transformación, entonces has eliminado todo el beneficio de la memoria caché.

Para su ejemplo, parece que una solución sería para cuando genera los datos transformados, también para almacenar el nombre de archivo y la última hora de modificación del archivo desde el que se generaron los datos (ya lo almacenó en cualquier estructura de datos devuelta por getData ( ), entonces simplemente copie ese registro en la estructura de datos devuelta por transformData ()) y luego cuando vuelva a llamar a transformData (), verifique la última hora modificada del archivo.