Invalidation du cache – Existe-t-il une solution générale?

Ce dont vous parlez, c’est l’enchaînement des dépendances de durée de vie, une chose dépend d’une autre qui peut être modifiée en dehors de son contrôle.

Si vous avez une fonction idempotente de a , b à c où, si a et b sont identiques, alors c est le même mais le coût de la vérification de b est élevé alors vous avez soit:

1. accepter que vous opériez parfois avec des informations obsolètes et ne vérifie pas toujours b
2. faites de votre mieux pour vérifier le plus vite possible

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

Si vous pouvez superposer un cache supplémentaire basé sur a cache supérieur, cela affecte le problème initial, pas un bit. Si vous avez choisi 1, vous disposez de la liberté que vous vous êtes donnée et pouvez donc mettre davantage de cache en mémoire, mais vous devez vous rappeler de considérer la validité de la valeur en cache de b . Si vous avez choisi 2, vous devez quand même vérifier b chaque fois, mais vous pouvez utiliser le cache pour effectuer a vérification si b .

Si vous superposez des caches, vous devez déterminer si vous avez enfreint les “règles” du système en raison du comportement combiné.

Si vous savez qu’une validité a toujours lieu si vous le faites, vous pouvez organiser votre cache comme ceci (pseudocode):

 private map> cache // private func realFunction // (a,b) -> c get(a, b) { c result; map endCache; if (cache[b] expired or not present) { remove all b -> * ensortinges in cache; endCache = new map(); 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; } 

De toute évidence, la superposition successive (disons x ) est sortingviale tant que, à chaque étape, la validité de la nouvelle entrée ajoutée correspond à la relation a: b pour x : b et x : a .

Cependant, il est fort possible que vous ayez trois entrées dont la validité était entièrement indépendante (ou cyclique), donc aucune superposition ne serait possible. Cela signifierait que la ligne marquée // important devrait changer pour

si (endCache [a] expiré ou non présent)

Le problème de l’invalidation du cache est que les choses changent sans que nous le sachions. Ainsi, dans certains cas, une solution est possible s’il ya une autre chose qui est connue et qui peut nous avertir. Dans l’exemple donné, la fonction getData peut être connectée au système de fichiers, qui connaît toutes les modifications apscopes aux fichiers, quel que soit le processus modifiant le fichier. Ce composant peut à son tour notifier le composant qui transforme les données.

Je ne pense pas qu’il y ait de solution miracle pour que le problème disparaisse. Mais dans de nombreux cas concrets, il peut très bien être possible de transformer une approche basée sur le sondage en une approche basée sur les interruptions, ce qui peut faire disparaître le problème.

Si vous voulez getData () chaque fois que vous effectuez la transformation, vous avez éliminé tout le bénéfice du cache.

Pour votre exemple, il semble qu’une solution consisterait à générer les données transformées, à stocker également le nom de fichier et l’heure de la dernière modification du fichier à partir duquel les données ont été générées (vous les avez déjà enregistrées dans la structure de données renvoyée par getData ( ), il vous suffit donc de copier cet enregistrement dans la structure de données renvoyée par transformData ()) puis, lorsque vous appelez à nouveau transformData (), vérifiez la dernière heure de modification du fichier.

IMHO, Functional Reactive Programming (FRP) est en quelque sorte un moyen général de résoudre l’invalidation du cache.

Voici pourquoi: les données obsolètes dans la terminologie FRP sont appelées un pépin . L’un des objectives de FRP est de garantir l’absence de problèmes.

Le FRP est expliqué plus en détail dans cette discussion sur l’essence de FRP et dans cette réponse SO .

Dans la conversation, les Cell représentent un object / une entité en cache et une Cell est actualisée si l’une de ses dépendances est actualisée.

FRP masque le code de plomberie associé au graphe de dépendance et s’assure qu’il n’y a pas de Cell obsolètes.

Une autre façon de penser (différente de FRP) consiste à envelopper la valeur calculée (de type b ) dans une sorte d’écrivain Monad Writer (Set (uuid)) b où Set (uuid) (notation Haskell) contient tous les identificateurs des valeurs mutables dont dépend la valeur calculée b . Ainsi, uuid est une sorte d’identificateur unique qui identifie la valeur / variable mutable (par exemple, une ligne dans une firebase database) dont dépend le calcul b .

Combinez cette idée avec des combinateurs qui fonctionnent sur ce type d’écrivain Monad et qui pourraient mener à une sorte de solution d’invalidation générale du cache si vous utilisez uniquement ces combinateurs pour calculer un nouveau b . De tels combinateurs (disons une version spéciale de filter ) prennent en entrée les monades Writer et (uuid, a) -s, où a est une donnée / variable mutable, identifiée par uuid .

Donc, chaque fois que vous changez les données “d’origine” (uuid, a) (disons les données normalisées dans une firebase database à partir de laquelle b été calculé) dont dépend la valeur de type b vous pouvez invalider le cache contenant b si vous modifiez toute valeur dont dépend la valeur b calculée, car sur la base de l’ Set (uuid) de la Writer Monad, vous pouvez déterminer quand cela se produit.

Donc, chaque fois que vous modifiez quelque chose avec un uuid donné, vous uuid cette mutation à tous les cache-s et ils invalident les valeurs b qui dépendent de la valeur mutable identifiée avec cet uuid car la monade Writer dans laquelle le b est enveloppé peut dire si b dépend de cet uuid ou non.

Bien sûr, cela ne vaut que si vous lisez beaucoup plus souvent que vous écrivez.

Une troisième approche pratique consiste à utiliser des vues matérialisées dans les bases de données et à les utiliser comme cache-es. AFAIK ils visent également à résoudre le problème d’invalidation. Cela limite évidemment les opérations qui connectent les données mutables aux données dérivées.

Je travaille actuellement sur une approche basée sur PostSharp et les fonctions de mémorisation . Je l’ai passé devant mon mentor, et il convient que c’est une bonne implémentation de la mise en cache de manière indépendante du contenu.

Chaque fonction peut être marquée avec un atsortingbut qui spécifie sa période d’expiration. Chaque fonction ainsi marquée est mémorisée et le résultat est stocké dans le cache, avec un hachage de l’appel de la fonction et des parameters utilisés comme clé. J’utilise Velocity pour le backend, qui gère la dissortingbution des données du cache.

Existe-t-il une solution ou une méthode générale pour créer un cache, pour savoir à quel moment une entrée est périmée? Vous êtes donc assuré de toujours obtenir des données fraîches?

Non, car toutes les données sont différentes. Certaines données peuvent être “obsolètes” après une minute, d’autres après une heure et d’autres peuvent durer des jours ou des mois.

En ce qui concerne votre exemple spécifique, la solution la plus simple consiste à avoir une fonction de «vérification du cache» pour les fichiers, que vous appelez à la fois à partir de getData et de transformData .

Il n’y a pas de solution générale mais:

• Vous mettez en cache peut agir en tant que proxy (pull). Supposons que votre cache connaisse l’horodatage du dernier changement d’origine, lorsque quelqu’un appelle getData() , le cache demande l’origine de l’horodatage de sa dernière modification, s’il renvoie le cache, sinon il met à jour son contenu . (Une variante est que le client envoie directement l’horodatage sur la demande, la source ne renverra le contenu que si son horodatage est différent.)

• Vous pouvez toujours utiliser un processus de notification (push), le cache observe la source, si la source change, il envoie une notification au cache qui est alors marqué comme “sale”. Si quelqu’un appelle getData() le cache sera d’abord mis à jour à la source, supprimera l’indicateur “sale”; puis retourner son contenu.

Le choix en général dépend de:

• La fréquence: beaucoup d’appels sur getData() préféreraient un push pour éviter que la source soit inondée par une fonction getTimestamp
• Votre access à la source: possédez-vous le modèle source? Sinon, il y a de fortes chances que vous ne puissiez pas append de processus de notification.

Remarque: L’utilisation de l’horodatage étant la méthode traditionnelle utilisée par les proxies http, une autre approche consiste à partager un hachage du contenu stocké. La seule façon que je connaisse pour 2 entités de se mettre à jour ensemble est soit que je vous appelle (pull) ou que vous m’appeliez… (push) c’est tout.

le cache est difficile parce que vous devez prendre en compte: 1) le cache est constitué de plusieurs nœuds, nécessite un consensus pour eux 2) temps d’invalidation 3) condition de concurrence lorsque plusieurs mises en / hors jeu se produisent

c’est une bonne lecture: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/

Peut-être que les algorithmes de mémoire cache seraient les plus généraux (ou du moins, moins dépendants de la configuration matérielle), car ils utiliseront d’abord le cache le plus rapide et partiront de là. Voici une conférence du MIT à ce sujet: Algorithmes Cache Oblivious