Caching-Strategien: FIFO, LFU, LRU, MRU

3 Kommentare
Mischa Sameli, Geschäftsführer & Leiter Entwicklung

Was man nicht weiss, macht mich nicht heiss. Blöderweise bin ich heute bei der Konfiguration einer Applikation auf genau die Schlagworte im Titel gestossen. Und hatte logischerweise keine Ahnung von dem Zeugs, das simpel als Eviction Policy bei Cache-Einstellungen zu finden war. Eviction Policy, alles klar oder? Und vor allem was jetzt LRU oder LFU?

Das ist eben der Mist an der Auswahl: man muss sich entscheiden. Und wenn man sich entscheiden muss, sollte man eben auch wissen, wozu man sich eigentlich entscheiden muss. Denn logischerweise haben haben beide Einstellungen Vor- und Nachteilen. Aber nun erst einmal der Reihe nach.
Mit der Eviction Policy wird der Verdrängungsmechanismus im Cache beschrieben. In jedem Cache, egal was für ein Cache nun auch immer gemeint ist. Der Verdrängungsmechanismus wird dann effektiv, wenn der für den Cache reservierte Platz (Festplatte, RAM, was auch immer) voll wird oder ist. Dann heisst es nämlich für den Cache-Verwalter ausmisten. Und die Eviction Policy beschreibt, nach welchem Prozedere vorgegangen wird. Und jetzt zu den einzelnen Verfahren, die im Titel mit Abkürzungen umschrieben worden sind.

  • FIFO
    FIFO steht für "First in First Out". Der erste Eintrag, der in den Cache geschrieben worden ist, fällt auch wieder als erster raus. Tönt logisch und einfach zu verwalten. Das Problem bei dieser Methode ist aber, dass man schnell Performance-Probleme feststellt, wenn viel mehr Einträge im Cache verwaltet werden sollen, als der Cache auf einmal aufnehmen kann. Sprich wenn der reservierte Platz im Verhältnis zur erwarteten Menge an Daten einfach zu klein ist. Wenn der Cache einmal voll ist, muss dauernd etwas gelöscht werden, nur damit wieder Neues rein geschrieben werden kann.
  • LFU
    LFU steht für Least Frequently Used und dies wiederum steht für die am wenigsten gebrauchten Einträge. Im Vergleich zu FIFO ist dies sicher effizienter, wenn gewisse Einträge immer wieder verwendet werden. Diese Einträge bleiben dann sehr lange im Cache und es werden nur noch selten verwendete Einträge regelmässig ausgetauscht. Die Optimierung der Auslastung ist hier schon ein wenig einfacher – vorausgesetzt man kennt die Bedürfnisse der Applikation, die den Cache benutzt.
  • LRU
    LRU steht für Least Recently Used, also für die Einträge, auf die am längsten nicht zugegriffen wurde. Im Vergleich zu FIFO wird also nicht nur die Erstellung des Eintrags bewertet, sondern wann er zum letzten Mal benutzt worden ist. Dies wiederum im Vergleich zu LFU, wo der Zeitpunkt nicht wichtig ist, sondern nur die Anzahl Verwendungen. Häufig verwendete Einträge bleiben auch so relativ lange im Cache, wenn aber aus irgendwelchen Gründen andere Einträge wichtiger werden, können sie trotzdem relativ spontan aus dem Cache entfernt werden. Nehmen wir an, Eintrag a wurde 1000 mal aufgerufen, Eintrag b 1. Bei LFU ist a damit schon ein sehr wichtiger Eintrag, b überhaupt nicht. Bei LRU ebenfalls. 10 Sekunden später. b wurde 10 mal aufgerufen, aber kein weiteres mal, also immer noch 1000 mal. Bei LFU hat b damit im Vergleich zu a immer noch überhaupt keine Relevanz. Bei LRU ist er aber im ansehen bereits gestiegen. Denn es sieht so aus, als würde a nicht mehr so häufig gebraucht werden. LRU kann also gut auf Veränderungen am Verhalten einer Applikation eingehen, während FIFO und LFU eher statisch agieren, respektive von einem statischen oder kontinuierlichen Verhalten ausgehen.
  • MRU
    MRU steht für Most Recently Used, also die zuletzt am häufigsten gebraucht Objekte. Und hier hört für mich der Spass dann auf. Warum sollte man genau die Einträge aus dem Cache entfernen wollen, die zuletzt am häufigsten gebraucht wurden? Widerspricht das nicht dem Sinn und Zweck des Caches? Ich habe bislang noch keine Erklärung gefunden, aber vielleicht hat ja jemand ein passendes Beispiel…

Die Wahl der Verdrängungsmethode hat also sehr direkten Einfluss auf die Performance des Systems. Und die Schwierigkeit ist tatsächlich, die richtige Strategie zu finden. Oder auf der anderen Seite die Applikation optimal auf die Standard-Strategie abzustimmen, wenn man keine Wahl hat. Im Moment weiss ich gar nicht so recht, was mir lieber ist. Manchmal stirbt man wirklich lieber dumm…

neuen Kommentar erstellen

Fabian's Gravatar
Interessante Sache! Beim MRU-Löschen gehts, soweit ich mal gelesen habe, primär um Sicherheitsaspekte. Das heisst, beispielsweise wenn man fröhlich vor sich hinarbeitet und jenste wichtige Dateien oft aufmacht, landen diese natürlich im Cache (Stichwort: "zuletzt geöffnete Dateien"). Solche Listen machen es ungebetenen Eindringlingen natürlich relativ einfach. Wenn daher die wichtigsten, häufgsten Einträge gelöscht werden, kann man da unter Umständen vorbeugen.

So habe ich es auf alle Fälle verstanden, als ich vor einiger Zeit mal über ein Tool namens "MRU Blaster" gestolpert bin.
Fabian, am 19. März 2009 um 16:51 Uhr
Mischa Sameli's Gravatar
Das tönt nach einer einleuchtenden Erklärung, danke für den Tipp. Stellt sich aber immer noch die Frage, weshalb dies ein System automatisch machen sollte. Als manuelle Strategie zur Bereinigung kann ich mir das schon vorstellen, aber wozu dann noch unterscheiden? Ich meine, man könnte dann ja auch gleich den ganzen Mist auf einmal raus schmeissen - das wäre dann sicher, oder?

Aber eigentlich handelt es sich ja um Strategien und nicht um fixe Prozesse. Dies habe ich bei meinen Überlegungen nicht bedacht. Der MRU Blaster geht folglich nach der MRU-Strategie vor. Und diese macht in diesem Fall logischerweise Sinn. Scho wieder öppis glernt :-)
Mischa Sameli, am 19. März 2009 um 17:01 Uhr
Frank's Gravatar
Schon ein Weilchen her, aber weil ich den Spaß gerade lerne...
MRU ist praktisch, wenn du streng sequentielle Zugriffe hast. Dann wirst du das eben Gelesene nicht mehr brauchen, wohl aber das was danach kommt. Also kann das gern aus dem Cache und dafür anderes, was länger her ist auch noch drin bleiben.
Frank, am 28. November 2010 um 16:09 Uhr
Bitte lassen Sie dieses Feld leer
Kommentar hinzufügen


Bitte lassen Sie dieses Feld leer
Beitrag als E-Mail verschicken
E-Mail via Webmail versenden

Schön, dass Ihnen unser Beitrag gefallen hat. Benutzen Sie folgende Social Networking Dienste, um den Beitrag abzulegen und zu verteilen. Selbstverstädlich können Sie ein direktes Lesezeichen auf diesen Artikel setzen.