Cache Invalidation - Y at-il une solution générale?

Question

  

« Il n'y a que deux problèmes difficiles en informatique. Infirmation cache et nommer les choses »

Phil Karlton

Y at-il une solution générale ou méthode pour invalider un cache; à savoir quand une entrée est périmé, vous êtes assuré d'obtenir toujours de nouvelles données?

Par exemple, considérons une getData() fonction qui obtient des données à partir d'un fichier. Il met en cache en fonction de la dernière modification du fichier, qu'il vérifie à chaque fois qu'il est appelé.
Ensuite, vous ajoutez une seconde fonction transformData() qui transforme les données, et met en cache le résultat pour la prochaine fois que la fonction est appelée. Il n'a pas connaissance du dossier - comment voulez-vous ajouter la dépendance que si le fichier est modifié, ce cache devient invalide

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

Answer 1

Qu'est-ce que vous parlez de dépendance est Enchaînement à vie, qu'une chose est dépendante d'une autre qui peut être modifiée en dehors de celui-ci de contrôle.

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

1. acceptez que vous utilisez parfois avec de l'information à jour et ne cochez pas toujours b
2. faire de votre mieux pour faire vérifier b aussi vite que possible

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

Si vous pouvez superposer un cache supplémentaire basée sur a sur le dessus alors cela affecte le problème initial pas un seul bit. Si vous avez choisi 1 alors vous avez tout ce que la liberté que vous vous avez donné et peut mettre en cache donc plus, mais doit se rappeler d'examiner la validité de la valeur de mise en cache b. Si vous avez choisi 2 vous devez toujours vérifier b chaque fois, mais peut se rabattre sur le cache pour a si b vérifie.

Si vous superposez caches vous devez vous demander si vous avez violé les « règles » du système en raison du comportement combiné.

Si vous savez que a a toujours validité si b ne vous pouvez organiser votre cache comme si (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;
}

Il est évident que la superposition successive (par exemple x) est trivial tant que, à chaque étape la validité de l'entrée nouvellement ajoutée correspond à la a: relation b pour x: b et x:. a

Cependant, il est tout à fait possible que vous pourriez obtenir trois entrées dont la validité était entièrement indépendante (ou était cyclique), donc pas de stratification serait possible. Cela signifierait la ligne marquée // importante devrait changer à

  

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

Answer 2

Le problème en cache est infirmation que les changements de trucs sans nous connaître à ce sujet. Ainsi, dans certains cas, une solution est possible s'il y a une autre chose qui ne sait à ce sujet et peut nous en informer. Dans l'exemple donné, la fonction getData pourrait accrocher dans le système de fichiers, qui ne connaissent tous les modifications apportées aux fichiers, quel que soit ce processus modifie le fichier, et ce composant pourrait à son tour notifier le composant qui transforme les données.

Je ne pense pas qu'il y ait une solution magique générale pour faire disparaître le problème. Mais dans de nombreux cas pratiques, il peut très bien être possible de transformer une approche fondée sur « polling » dans une « interruption » à base d'un, ce qui peut rendre le problème va tout simplement.

Answer 3

Si vous allez getData () chaque fois que vous ne le transformez, vous avez éliminé tout l'avantage du cache.

Pour exemple, il apparaît comme une solution serait lorsque vous générez les données transformées, pour stocker également le nom du fichier et de dernière modification du fichier les données ont été générées à partir (vous avez déjà stocké ce quelle que soit la structure des données a été renvoyé par getData (), de sorte que vous venez de copier cet enregistrement dans la structure de données renvoyées par transformData ()) puis lorsque vous appelez transformData () à nouveau, vérifiez la dernière modification du fichier.

Answer 4

à mon humble avis, la programmation réactive fonctionnelle (FRP) est dans un sens d'une manière générale pour résoudre l'invalidation du cache.

Voici pourquoi: les données obsolètes dans la terminologie FRP est appelé un pépin . L'un des objectifs de FRP est de garantir l'absence de défauts.

FRP est expliqué plus en détail dans ce 'Essence de FRP' talk dans ce SO répondre .

Dans les les Cells représentent un objet / entité en cache et un Cell est rafraîchi si l'un de ses dépendances est rafraîchi.

FRP cache le code de plomberie associé au graphe de dépendance et fait en sorte qu'il n'y a pas Cells périmées.

---

Une autre façon (différente de FRP) que je peux penser est envelopper la valeur calculée (de type b) en une sorte d'un écrivain Monade Writer (Set (uuid)) b où Set (uuid) (notation Haskell) contient tous les identifiants des valeurs mutables sur lequel le calculée valeur b dépend. Ainsi, uuid est une sorte d'un identifiant unique qui identifie la valeur mutable / variable (par exemple une ligne dans une base de données) sur laquelle le b calculé dépend.

Combiner cette idée avec combinateurs qui fonctionnent sur ce genre d'écrivain Monade et qui pourraient conduire à une sorte d'une solution de cache générale infirmation si vous utilisez uniquement ces combinateurs pour calculer une nouvelle b. Ces combinateurs (disons une version spéciale de filter) prendre Writer monades et (uuid, a)-s comme entrées, où a est une donnée mutable / variables, identifiées par uuid.

Ainsi, chaque fois que vous changez la (uuid, a) de données « original » (dire que les données normalisées dans une base de données à partir de laquelle b a été calculée) sur laquelle la valeur calculée de type b dépend alors vous pouvez invalider le cache qui contient b si vous muter tout valeur a sur laquelle la valeur calculée b dépend, parce que sur la base du Set (uuid) dans la Writer Monad vous pouvez dire quand cela se produit.

Donc, chaque fois que vous muter quelque chose avec un uuid donné, vous diffusez cette mutation à tous les cache-s et ils invalident les valeurs b qui dépendent de la valeur mutable identifiée avec ledit uuid parce que l'écrivain monade dans lequel le b est enveloppé peut dire si cela dépend de b dudit uuid ou non.

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

---

Une troisième approche pratique consiste à utiliser la vue matérialisée-s dans les bases de données et les utiliser comme cache-es. Autant que je sache, ils visent aussi à résoudre le problème de infirmation. Bien sûr, cela limite les opérations qui relient les données mutables aux données dérivées.

Answer 5

Je travaille sur une approche actuellement basée sur PostSharp et fonctions memoizing . J'ai couru ce passé mon mentor, et il convient que c'est une bonne mise en œuvre de la mise en cache de manière agnostique contenu.

Chaque fonction peut être marquée avec un attribut qui spécifie sa période d'expiration. Chaque fonction marquée de cette manière est memoized et le résultat est stocké dans le cache, avec un hachage de l'appel de fonction et les paramètres utilisés comme clé. J'utilise Velocity pour le backend, qui gère la distribution du les données du cache.

Answer 6

  

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

Non, parce que toutes les données sont différentes. Certaines données peuvent être « périmées » après une minute, un peu après une heure, et certains peuvent être très bien pendant des jours ou des mois.

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

Answer 7

There is no general solution but:

• You cache can act as a proxy (pull). Assume your cache knows the last origin change's timestamp, when someone call getData(), the cache ask the origin for it's last change's timestamp, if the same, it returns the cache, otherwise it updates its content with the source one and return its content. (A variation is the client to directly send the timestamp on the request, the source would only return content if its timestamp is different.)

• You can still use a notification process (push), the cache observe the source, if the source changes, it sends a notification to the cache which is then flagged as "dirty". If someone calls getData() the cache will first get updated to the source, remove the "dirty" flag; then return its content.

The choice generally speaking depends on:

• The frequency: many calls on getData() would prefer a push so to avoid the source to be flooded by a getTimestamp function
• Your access to the source: Are you owning the source model ? If not, chances are you cannot add any notification process.

Note: As using the timestamp is the traditional way http proxies are working, another approach is sharing a hash of the content stored. The only way I know for 2 entities to get updated together are either I call you (pull) or you call me… (push) that's all.

Answer 8

cache is hard because you need to consider: 1)the cache is multiple nodes,need consensus for them 2)invalidation time 3)race condition when multple get/set happen

this is good reading: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/

Answer 9

Perhaps cache-oblivious algorithms would be the most general (Or at least, less hardware configuration dependent), since they'll use the fastest cache first and move on from there. Here's a MIT lecture on it: Cache Oblivious Algorithms