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

Question

"Solo hay dos problemas difíciles en Informática: invalidación de caché y nombrar cosas".

Phil Karlton

¿Hay una solución general o método para invalidar una memoria 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é según la última hora modificada del archivo, que comprueba cada vez que se invoca.
Luego 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?

Puede llamar al getData() cada vez que se llama transformData() y compararlo con el valor que se usó para construir el caché, pero que podría terminar siendo muy costoso.

Answer 1

De lo que estás hablando es del encadenamiento de dependencia de por vida, una cosa depende de otra que se puede modificar fuera de su 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 que en algún momento de operar con información obsoleta y no siempre se comprueba b
2. hacer su mejor nivel para hacer la comprobación b lo más rápido posible

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

Si puede capa un caché adicional basada en a sobre la parte superior, entonces 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, igualmente debe marcar b cada vez, pero puede recurrir a la memoria caché para a si b se retira.

Si capas cachés debe considerar si ha 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; 
} 

estratificación Obviamente sucesiva (por ejemplo x) es trivial, siempre que, en cada etapa la validez de la entrada recién agregada coincide 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 la línea marcada // importante tendría que cambiar a

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

Answer 2

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 la caché más rápida primero y continuarán desde allí. Aquí hay una conferencia del MIT: Cache Oblivious Algorithms

Answer 3

Estoy trabajando en un enfoque basado en PostSharp y memoizing functions. 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 caducidad. 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é.

Answer 4

¿Existe una solución o método general para crear un caché, para saber cuándo una entrada está obsoleta, por lo 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 los que llama desde getData y transformData.

Answer 5

Si va a obtenerData() cada vez que hace la transformación, entonces ha 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 del archivo y la última hora modificada del archivo de los datos (ya lo almacenó en cualquier estructura de datos devuelto por getData(), de modo que solo 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.

Answer 6

El problema en la invalidación de caché es que los cambios de cosas sin nosotros sabiendo sobre eso. 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 ninguna solución mágica general para hacer desaparecer el problema. 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.

Answer 7

No existe una solución general, sino:

• Usted caché puede actuar como un proxy (pull).Supongamos que su caché conoce la marca de tiempo del último cambio de origen, cuando alguien llama al 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).

• Todavía 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 al getData(), la caché primero se actualizará a la fuente, eliminará la bandera "sucia"; luego devuelve 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: ¿Eres 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.

Answer 8

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

He aquí 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 este 'Essence of FRP' talk y en este SO answer.

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

FRP oculta el código de fontanería asociado con el gráfico de dependencias y se asegura de que no haya rangos Cell s.