Invalidación de Caché - ¿Hay una solución general?

Question

  

"Sólo hay dos problemas difíciles en Ciencias de la Computación:. Invalidación de caché y nombrar las cosas"

Phil Karlton

¿Hay una solución general o método para invalidar una memoria caché; para saber cuando una entrada es rancio, por lo que está garantizado para conseguir siempre nuevos datos?

Por ejemplo, considere un getData() función que obtiene datos de un archivo. Se almacena en caché basado en la última hora de modificación del archivo, lo que se comprueba cada vez que se llama.
A continuación, se agrega un segundo transformData() función que transforma los datos, y almacena en caché el resultado para la próxima vez que se llama a la función. No tiene conocimiento del archivo -? ¿Cómo se agrega la dependencia que si se cambia el archivo, este se convierte en caché no válido

Se le podría llamar getData() cada transformData() tiempo se llama y compararlo con el valor que se utilizó para construir la memoria caché, pero que podría llegar a ser muy costoso.

Answer 1

Lo que estamos hablando es de encadenamiento de la dependencia de por vida, que una cosa es dependiente de otra que puede ser modificado fuera de ella de control.

Si usted tiene una función idempotente de a, b a c donde, si a y b son los mismos a continuación c es el mismo pero el costo de la comprobación b es alta, entonces ya sea:

1. acepta que en algún momento se opera con información obsoleta y no siempre se comprueba b
2. hacer su mejor nivel para hacer la comprobación b tan rápido como sea posible

No se puede tener su pastel y comérselo ...

Si usted puede capa de una memoria caché adicional basada en a sobre la parte superior, entonces esto afecta el problema inicial no un bit. Si ha elegido 1, entonces usted tiene la libertad lo que dieron a sí mismos y por lo tanto puede almacenar en caché más, pero debe recordar que considerar la validez del valor almacenado en caché de b. Si ha elegido 2 todavía se debe comprobar cada vez que b pero puede recurrir a la memoria caché para a si b comprueba hacia fuera.

Si superpone cachés debe tener en cuenta si se han violado las 'reglas' del sistema como resultado del comportamiento combinado.

Si sabe que a siempre tiene validez si b hace, entonces usted puede arreglar su 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 capas sucesivas (por ejemplo x) es trivial, siempre que, en cada etapa de la validez de la entrada que acaba de agregar coincide con el a: relación b para x: b y x:. a

Sin embargo, es muy posible que usted podría conseguir tres entradas cuya validez era totalmente independiente (o era cíclico), por lo que no sería posible estratificación. Esto significaría la línea marcada // importante tendría que cambiar a

  

si (endCache [a] ha caducado o no está presente)

Answer 2

El problema en la invalidación de caché es que los cambios de cosas sin nosotros saberlo. Así, en algunos casos, una solución es posible si hay alguna otra cosa que no sabe acerca de ello y nos puede notificar. En el ejemplo dado, la función getData podría enganchar en el sistema de archivos, lo que sabemos acerca de todos los cambios en los archivos, independientemente de qué proceso cambia el archivo, y este componente a su vez podría notificar al componente que transforma los datos.

No creo que haya ninguna solución mágica en general para hacer que el problema desaparezca. Pero en muchos casos prácticos que puede muy bien ser oportunidades para transformar una "interrogación" enfoque basado en un "interrumpir" -basado uno, lo que puede hacer que el problema simplemente desaparece.

Answer 3

Si vas a getData () cada vez que se hace la transformación, a continuación, usted ha eliminado todo el beneficio de la caché.

Para su ejemplo, parece que una solución sería que al generar los datos transformados, para almacenar también el nombre del archivo y la fecha de última modificación del archivo de los datos se genera a partir de (ya almacenó esto en cualquier estructura de datos fue devuelto por getData (), por lo que acaba de copiar ese registro en la estructura de datos devuelto por transformData ()) y luego, cuando se llama a transformData () de nuevo, comprobar la última hora de modificación del archivo.

Answer 4

En mi humilde opinión, programación funcional reactivo (FRP) es en cierto sentido una manera general para resolver la invalidación de caché.

Aquí es por qué: datos antiguos en la terminología de FRP se llama fallo . Uno de los objetivos de FRP es la garantía de ausencia de fallos.

FRP se explica con más detalle en este 'Esencia de FRP' hablar y en este SO responder .

En los href="https://m.youtube.com/watch?v=CjEDmJMLEGE" los Cells representar un objeto en caché / Entidad y una Cell es refrescado si uno de ellos es la dependencia es refrescado.

FRP oculta el código de plomería asociada con el gráfico de la dependencia y se asegura de que no hay Cells rancios.

---

Otra forma (diferente de FRP) que puedo pensar es envolver el valor calculado (de tipo b) en una especie de escritor Mónada Writer (Set (uuid)) b donde Set (uuid) (Haskell notación) contiene todos los identificadores de los valores mutables en la que el b valor calculado depende. Así, uuid es una especie de un identificador único que identifica el valor mutable / variable (por ejemplo un registro en una base de datos) de la que depende la b computarizada.

Combinar esta idea con combinadores que operan en este tipo de escritor Mónada y que podría dar lugar a algún tipo de una solución general de invalidación de caché si sólo utiliza estos combinadores para calcular un nuevo b. Tales combinadores (dicen una versión especial de filter) tomar mónadas escritor y (uuid, a)-s como entradas, donde a es un dato variable / mutable, identificadas por uuid.

Así que cada vez que cambie el (uuid, a) datos "original" (decir los datos normalizados en una base de datos de la que se calcula b) en la que el valor calculado de tipo b depende entonces se puede invalidar el caché que contiene b si mutar cualquier a valor de la que depende el valor b computarizada, porque se basa en la Set (uuid) en el escritor Mónada se puede decir cuando esto sucede.

Así que cada vez que mutar algo con un uuid dado, la emisión en esta mutación a toda la caché-s y que invalida los valores b que depende del valor mutable identificado con dicho uuid porque la mónada escritor en el que se envuelve el b puede decir si b que depende de dicho uuid o no.

Por supuesto, esto sólo es rentable si se lee con mucha más frecuencia de lo que escribe.

---

Una tercera, práctico, enfoque consiste en utilizar vistas materializadas-s en bases de datos y utilizarlos como caché-es. Que yo sepa que también tienen como objetivo resolver el problema de invalidación. Por supuesto, esto limita las operaciones que conectan los datos mutables a los datos derivados.

Answer 5

Estoy trabajando en un enfoque basado en este momento PostSharp y funciones memoizing . Me he encontrado que más allá de mi mentor, y él está de acuerdo que es una buena aplicación de almacenamiento en caché de una manera independiente del contenido.

Cada función puede ser marcado con un atributo que especifica su periodo de caducidad. Cada función marcada de esta manera se memoized 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 clave. Estoy usando velocidad para el backend, que se encarga de la distribución de la datos de la caché.

Answer 6

  

¿Hay una solución general o método para crear una memoria caché, para saber cuando una entrada está demasiado cargado, por lo que está garantizado para conseguir siempre nuevos datos?

No, porque todos los datos es diferente. Algunos datos pueden ser "vieja" 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 sencilla es tener una 'comprobación de la caché' función de archivos, que se llama desde ambos getData y transformData.

Answer 7

No hay una solución general, sino:

• caché puede actuar como un proxy (pull). Suponga que su caché sabe fecha y hora del último cambio de origen, cuando getData() alguien llamada, el caché preguntar el origen por su marca de tiempo del último cambio, si la misma, devuelve la caché, si no actualiza su contenido con el de origen y regresar a su contenido. (Una variación es que el cliente envíe directamente la fecha y hora de la solicitud, la fuente sólo volvería contenido si su marca de tiempo es diferente.)

• Puede seguir utilizando un proceso de notificación (push), la caché de observar la fuente, si cambia la fuente, se envía una notificación a la caché que luego se marca como "sucio". Si alguien llama getData() la memoria caché en primer lugar se actualizan a la fuente, quitar el indicador "sucio"; luego regresar a su contenido.

La elección general depende de:

• La frecuencia: muchas llamadas en getData() preferirían un empujón de modo de evitar la fuente a ser inundado por una función getTimestamp
• Su acceso a la fuente: ¿Está poseer el modelo de código? Si no es así, lo más probable es que no se puede añadir cualquier proceso de notificación.

Nota: A medida que el uso de la marca de tiempo es la forma tradicional proxies HTTP están trabajando, otro enfoque está compartiendo un hash del contenido almacenado. La única forma que conozco para 2 entidades que se actualizan juntos son bien os (pull) llamo o me llaman ... (push) eso es todo.

Answer 8

caché es difícil porque hay que tener en cuenta: 1) la caché es de múltiples nodos, la necesidad de consenso para ellos 2) Tiempo de invalidación 3) condición de carrera cuando multple get / set suceda

esta es una buena lectura: https://www.confluent.io / blog / convertir-la-base-dentro-fuera-de-Apache-samza /

Answer 9

Tal vez algoritmos de caché-ajeno sería el (o al menos, menos dependiente de la configuración del hardware) más general, ya que vamos a usar la memoria caché más rápida primero y pasar de allí. Aquí está una conferencia del MIT en él: caché Ajeno Algoritmos