"In der Informatik gibt es nur zwei schwierige Probleme: die Ungültigmachung des Caches und die Benennung von Dingen."
Phil Karlton
Gibt es eine allgemeine Lösung oder Methode zum Ungültigmachen eines Caches? Um zu wissen, wann ein Eintrag veraltet ist, damit Sie garantiert immer neue Daten erhalten?
Stellen Sie sich beispielsweise eine Funktion vor getData()
, die Daten aus einer Datei abruft. Es speichert es basierend auf der letzten geänderten Zeit der Datei zwischen, die es bei jedem Aufruf überprüft.
Anschließend fügen Sie eine zweite Funktion hinzu, transformData()
die die Daten transformiert und das Ergebnis für den nächsten Aufruf der Funktion zwischenspeichert. Die Datei ist nicht bekannt. Wie können Sie die Abhängigkeit hinzufügen, dass dieser Cache ungültig wird, wenn die Datei geändert wird?
Sie können getData()
jedes Mal aufrufen, wenn transformData()
es aufgerufen wird, und es mit dem Wert vergleichen, der zum Erstellen des Caches verwendet wurde. Dies kann jedoch sehr kostspielig werden.
"The two hardest things in Computer Science are cache invalidation, naming things, and off-by-one errors."
Antworten:
Sie sprechen von einer lebenslangen Abhängigkeitsverkettung, bei der eine Sache von einer anderen abhängig ist, die außerhalb ihrer Kontrolle geändert werden kann.
Wenn Sie eine idempotente Funktion von
a
,b
nachc
wo haben, wenna
und gleichb
sind, dannc
sind sie gleich, aber die Kosten für die Überprüfungb
sind hoch, dann haben Sie entweder:b
b
so schnell wie möglich zu gestaltenSie können Ihren Kuchen nicht haben und ihn essen ...
Wenn Sie einen zusätzlichen Cache überlagern können,
a
wirkt sich dies auf das anfängliche Problem nicht ein Bit aus. Wenn Sie 1 gewählt haben, haben Sie die Freiheit, die Sie sich selbst gegeben haben, und können somit mehr zwischenspeichern, müssen jedoch die Gültigkeit des zwischengespeicherten Werts von berücksichtigenb
. Wenn Sie 2 gewählt haben, müssen Sie immer nochb
jedes Mal nachsehen, können aber auf den Cache zurückgreifen,a
wenn Sieb
auschecken.Wenn Sie Caches überlagern, müssen Sie prüfen, ob Sie aufgrund des kombinierten Verhaltens gegen die 'Regeln' des Systems verstoßen haben.
Wenn Sie wissen, dass dies
a
immer Gültigkeitb
hat, können Sie Ihren Cache wie folgt anordnen (Pseudocode):Offensichtlich aufeinanderfolgende Schichtung (sagen wir
x
) ist trivial , so lange, in jeder Stufe die Gültigkeit des neu hinzugefügten Eingangseinstimmta
:b
Beziehungx
:b
undx
:a
.Es ist jedoch durchaus möglich, dass Sie drei Eingaben erhalten, deren Gültigkeit völlig unabhängig (oder zyklisch) war, sodass keine Überlagerung möglich wäre. Dies würde bedeuten, dass die mit // wichtig gekennzeichnete Zeile geändert werden muss
quelle
Das Problem bei der Cache-Ungültigmachung ist, dass sich Dinge ändern, ohne dass wir davon erfahren. In einigen Fällen ist eine Lösung möglich, wenn etwas anderes darüber Bescheid weiß und uns benachrichtigen kann. In dem angegebenen Beispiel könnte sich die Funktion getData in das Dateisystem einbinden, das alle Änderungen an Dateien kennt, unabhängig davon, welcher Prozess die Datei ändert, und diese Komponente könnte wiederum die Komponente benachrichtigen, die die Daten transformiert.
Ich glaube nicht, dass es eine allgemeine magische Lösung gibt, um das Problem zu lösen. In vielen praktischen Fällen besteht jedoch möglicherweise die Möglichkeit, einen auf "Polling" basierenden Ansatz in einen auf "Interrupt" basierenden Ansatz umzuwandeln, wodurch das Problem einfach behoben werden kann.
quelle
Wenn Sie jedes Mal, wenn Sie die Transformation durchführen, getData () erhalten, haben Sie den gesamten Vorteil des Caches beseitigt.
In Ihrem Beispiel scheint es eine Lösung zu sein, beim Generieren der transformierten Daten auch den Dateinamen und die letzte Änderungszeit der Datei zu speichern, aus der die Daten generiert wurden (Sie haben dies bereits in der von getData zurückgegebenen Datenstruktur gespeichert). ), kopieren Sie also einfach diesen Datensatz in die von transformData ()) zurückgegebene Datenstruktur und überprüfen beim erneuten Aufruf von transformData () die zuletzt geänderte Zeit der Datei.
quelle
IMHO, Functional Reactive Programming (FRP) ist in gewissem Sinne eine allgemeine Methode zur Lösung der Cache-Ungültigkeit.
Hier ist der Grund: Veraltete Daten in der FRP-Terminologie werden als Panne bezeichnet . Eines der Ziele von FRP ist es, das Fehlen von Störungen zu gewährleisten.
FRP wird in diesem 'Essence of FRP'-Vortrag und in dieser SO-Antwort ausführlicher erläutert .
Im Vortrag stellen die
Cell
s ein zwischengespeichertes Objekt / eine zwischengespeicherte Entität dar und aCell
wird aktualisiert, wenn eine ihrer Abhängigkeiten aktualisiert wird.FRP verbirgt den mit dem Abhängigkeitsdiagramm verknüpften Installationscode und stellt sicher, dass keine veralteten
Cell
s vorhanden sind.Eine andere Möglichkeit (anders als FRP), die ich mir vorstellen kann, besteht darin, den berechneten Wert (vom Typ
b
) in eine Art Schreibmonade zu verpacken,Writer (Set (uuid)) b
in derSet (uuid)
(Haskell-Notation) alle Bezeichner der veränderlichen Werte enthält, von denen der berechnete Wertb
abhängt. Es handelt sich alsouuid
um eine Art eindeutigen Bezeichner, der den veränderlichen Wert / die veränderbare Variable (z. B. eine Zeile in einer Datenbank) identifiziert, von der der berechnete Wertb
abhängt.Kombinieren Sie diese Idee mit Kombinatoren, die mit dieser Art von Writer-Monade arbeiten und die zu einer allgemeinen Lösung für die Ungültigmachung des Caches führen können, wenn Sie diese Kombinatoren nur zur Berechnung einer neuen verwenden
b
. Solche Kombinatoren (z. B. eine spezielle Version vonfilter
) verwenden Writer-Monaden und(uuid, a)
-s als Eingaben, wobeia
es sich um veränderbare Daten / Variablen handelt, die durch gekennzeichnet sinduuid
.Jedes Mal, wenn Sie die "ursprünglichen" Daten
(uuid, a)
(z. B. die normalisierten Daten in einer Datenbank, aus derb
berechnet wurde) ändern, von denen der berechnete Wert vom Typb
abhängt, können Sie den enthaltenen Cache ungültig machen,b
wenn Sie einen Wert mutieren,a
von dem der berechneteb
Wert abhängt , weil anhand derSet (uuid)
in der Writer-Monade können Sie erkennen, wann dies geschieht.Jedes Mal, wenn Sie etwas mit einem bestimmten Wert mutieren
uuid
, senden Sie diese Mutation an alle Cache-s, und sie machen die Werte ungültig, dieb
von dem mit dem genannten veränderlichen Wert abhängen,uuid
da die Writer-Monade, in die der Wert eingeschlossen ist, erkennenb
kann, ob diesb
vomuuid
oder abhängt nicht.Das zahlt sich natürlich nur aus, wenn Sie viel öfter lesen als schreiben.
Ein dritter praktischer Ansatz besteht darin, materialisierte Ansichten in Datenbanken zu verwenden und sie als Cache zu verwenden. AFAIK zielen sie auch darauf ab, das Invalidierungsproblem zu lösen. Dies begrenzt natürlich die Operationen, die die veränderlichen Daten mit den abgeleiteten Daten verbinden.
quelle
Ich arbeite gerade an einem Ansatz, der auf PostSharp- und Memoizing-Funktionen basiert . Ich habe es an meinem Mentor vorbeigeführt, und er stimmt zu, dass es eine gute Implementierung von Caching auf inhaltsunabhängige Weise ist.
Jede Funktion kann mit einem Attribut markiert werden, das den Ablaufzeitraum angibt. Jede auf diese Weise markierte Funktion wird gespeichert und das Ergebnis im Cache gespeichert, wobei ein Hash des Funktionsaufrufs und der Parameter als Schlüssel verwendet werden. Ich verwende Velocity für das Backend, das die Verteilung der Cache-Daten übernimmt.
quelle
Nein, da alle Daten unterschiedlich sind. Einige Daten können nach einer Minute "veraltet" sein, andere nach einer Stunde, und einige können für Tage oder Monate in Ordnung sein.
In Bezug auf Ihre speziellen Beispiel ist die einfachste Lösung , die eine ‚Cache - Überprüfung‘ Funktion für Dateien zu haben, die man von beiden nennen
getData
undtransformData
.quelle
Es gibt keine allgemeine Lösung, aber:
Ihr Cache kann als Proxy (Pull) fungieren. Angenommen, Ihr Cache kennt den Zeitstempel der letzten Ursprungsänderung. Wenn jemand anruft
getData()
, fragt der Cache den Ursprung nach dem Zeitstempel der letzten Änderung. Wenn dies der Fall ist, gibt er den Cache zurück, andernfalls aktualisiert er seinen Inhalt mit dem Quellstempel und gibt seinen Inhalt zurück. (Eine Variation besteht darin, dass der Client den Zeitstempel direkt auf die Anforderung sendet. Die Quelle würde nur dann Inhalt zurückgeben, wenn der Zeitstempel unterschiedlich ist.)Sie können weiterhin einen Benachrichtigungsprozess (Push) verwenden. Der Cache beobachtet die Quelle. Wenn sich die Quelle ändert, sendet er eine Benachrichtigung an den Cache, die dann als "schmutzig" gekennzeichnet wird. Wenn jemand
getData()
den Cache aufruft, der zuerst auf die Quelle aktualisiert wird, entfernen Sie das "schmutzige" Flag. Geben Sie dann den Inhalt zurück.Die Wahl hängt im Allgemeinen ab von:
getData()
würden einen Push bevorzugen, um zu vermeiden, dass die Quelle von einer getTimestamp-Funktion überflutet wirdHinweis: Da die Verwendung des Zeitstempels die traditionelle Arbeitsweise von http-Proxys ist, besteht ein anderer Ansatz darin, einen Hash des gespeicherten Inhalts freizugeben. Die einzige Möglichkeit, wie ich weiß, dass zwei Entitäten zusammen aktualisiert werden, besteht darin, dass ich Sie anrufe (Pull) oder mich anrufe (Push). Das ist alles.
quelle
Der Cache ist schwierig, da Sie Folgendes berücksichtigen müssen: 1) Der Cache besteht aus mehreren Knoten, für die ein Konsens erforderlich ist. 2) Ungültigmachungszeit. 3) Race-Bedingung, wenn mehrere get / set auftreten
Dies ist eine gute Lektüre: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/
quelle
Möglicherweise sind Algorithmen ohne Cache am allgemeinsten (oder zumindest weniger abhängig von der Hardwarekonfiguration), da sie zuerst den schnellsten Cache verwenden und von dort aus fortfahren. Hier ist ein MIT-Vortrag dazu: Cache Oblivious Algorithms
quelle