Invalidation de cache — y a-t-il une Solution générale ?

Question

"Il y a deux problèmes difficiles dans l'Informatique: l'invalidation du cache et de nommer les choses."

Phil Karlton

Est-il une solution générale ou de la méthode de l'invalidation d'une cache; à savoir quand une entrée est périmé, alors vous êtes assurés de toujours obtenir de nouvelles données?

Par exemple, considérons une fonction getData() qui récupère les données d'un fichier. Il met en cache en fonction de la dernière date de modification du fichier, qui se vérifie à chaque fois qu'il appelle.
Ensuite, vous ajoutez une deuxième fonction transformData() qui transforme les données, et les caches de son résultat pour la prochaine fois que la fonction est appelée. Il n'a aucune connaissance du fichier - comment pouvez-vous ajouter la dépendance que si le fichier est modifié, le cache est-il invalide?

Vous pourriez l'appeler getData() chaque fois transformData() est appelé et le comparer avec la valeur qui a été utilisée pour le cache, mais qui pourrait finir par être très coûteux.

Answer 1

Ce dont vous parlez est la durée de vie de dépendance de l'enchaînement, qu'une chose dépend d'un autre qui peut être modifié en dehors de son contrôle.

Si vous avez un idempotent de la fonction d' a, b de c si a et b sont le même, alors c est la même, mais le coût de la vérification de l' b est élevé, alors vous pouvez soit:

1. accepter que vous parfois fonctionner avec des informations de date et ne sont pas toujours vérifiez b
2. faites de votre mieux pour faire de vérification b aussi vite que possible

Vous ne pouvez pas avoir votre gâteau et le manger...

Si vous pouvez couche supplémentaire de cache basé sur a sur le haut, puis cela affecte le problème initial pas d'un poil. Si vous avez choisi 1, puis vous avez ce que la liberté que vous avez donné vous-même et peut donc cache plus mais sans oublier de s'interroger sur la validité de la valeur mise en cache de l' b. Si vous avez choisi 2, vous devez toujours vérifier l' b à chaque fois mais peut revenir sur le cache de l' a si b des contrôles.

Si vous caches de couches vous devez vous demander si vous n'avez pas respecté les "règles" du système comme un résultat de la combinaison de comportements.

Si vous savez qu' a a toujours validité b ne puis vous pouvez organiser votre cache comme (pseudo-code):

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;
}

Évidemment successives de superposition (disons x) est trivial si longtemps que, à chaque étape de la validité de la nouvelle prise d'entrée correspond à l' a:b relation pour x:b et x:a.

Cependant, il est tout à fait possible que vous pourriez obtenir à trois entrées dont la validité a été entièrement indépendant (ou cyclique), donc pas de superposition serait possible. Cela signifie que la ligne // important devrait changer pour

si (endCache[a] a expiré ou n'est pas présent)

Answer 2

Le problème de l'invalidation du cache, c'est que des trucs de modifications sans nous connaître. Ainsi, dans certains cas, une solution est possible si il y a une autre chose qui ne savent et peuvent nous en informer. Dans l'exemple donné, la fonction getData pourrait accrocher dans le système de fichiers, qui est de ne savoir au sujet de toutes les modifications de fichiers, indépendamment de ce processus modifie le fichier, et cette composante pourrait informer le composant qui transforme les données.

Je ne pense pas qu'il y est toute la magie correctif pour le problème. Mais dans de nombreux cas pratiques, il peut très bien être l'occasion de transformer une "interrogation"approche fondée sur une "interruption", ce qui peut rendre le problème il suffit d'aller loin.

Answer 3

Je suis en train de travailler sur une approche de droit maintenant basé sur PostSharp et memoizing fonctions. J'ai couru passé mon mentor, et il est d'accord que c'est une bonne mise en œuvre de la mise en cache dans un contenu de façon agnostique.

Chaque fonction peut être marqué avec un attribut spécifie sa période d'expiration. Chaque fonction marqué de cette façon est memoized et le résultat est stocké dans le cache, avec une valeur de hachage de l'appel de la fonction et des paramètres utilisés comme clé. Je suis l'aide de Vitesse pour le backend, qui gère la distribution des données en cache.

Answer 4

Si vous allez à getData() chaque fois que vous faites de la transformation, alors vous avez éliminé la totalité de la prestation de la cache.

Pour votre exemple, il semble comme une solution pourrait être que lorsque vous générez les données transformées pour stocker le nom du fichier et la date de dernière modification du fichier de données a été généré à partir (vous avez déjà stocké ce quelle que soit la structure de données a été retourné par getData(), il vous suffit de copier ce dossier dans la structure de données retourné par transformData()) et puis quand vous appelez transformData() encore une fois, vérifiez la date de dernière modification du fichier.

Answer 5

Est-il une solution générale ou de la méthode de création d'un cache, à savoir quand une entrée est périmé, alors vous êtes assurés de toujours obtenir de nouvelles données?

Non, car toutes les données sont différentes. Certaines données peuvent être "obsolète" au bout d'une minute, certains au bout d'une heure, et certains peuvent être à l'aise pendant des jours ou des mois.

Quant à votre exemple, la solution la plus simple est d'avoir un 'cache la vérification de la fonction pour les fichiers, que vous appelez à partir de deux getData et transformData.