Cache-Algorithmus

Ein Cache-Algorithmus steuert mittels einer detaillierten Folge von unterschiedlichen Anweisungen, welche Objekte im Pufferspeicher eines Rechners ausgetauscht werden.   

Zu den Cache-Algorithmen gehören unter anderem:

Least Frequently Used (LFU): Bei diesem Cache-Algorithmus wird für jeden Eintrag ein Zähler geführt, der die Anzahl an Anfragen festhält. Der Eintrag, auf den am wenigsten häufig zugegriffen wurde und dementsprechend den kleinsten Zählerwert aufweist, wird ersetzt. Ein Problem dabei ist jedoch, dass Objekte mit eingangs zahlreichen Zugriffen aufgrund ihres dadurch hohen Zählerstandes selbst dann im Cache verbleiben, wenn sie über einen langen Zeitraum nicht mehr abgefragt wurden. Aus diesem Grund kommt der LFU-Algorithmus seltener zum Einsatz.

Least Recently Used (LRU): Im Gegensatz zu LFU steht beim LRU-Algorithmus der Abfragezeitpunkt und nicht die Abrufhäufigkeit im Vordergrund. Objekte werden zugriffsbasierend in einer Liste sortiert und zuletzt abgerufene beziehungsweise neue Elemente ganz oben eingefügt. Ist der Cache voll, werden die am Ende der Liste eingetragenen und damit am längsten nicht mehr verwendeten Daten ausgelagert. Die Implementierung des LRU-Algorithmus kann sich allerdings als recht kostspielig erweisen, da für jedes Objekt das „Referenzierungsalter“ registriert werden muss. Die Steuerung erfolgt über Referenz-Bits, die den letzten Zugriffszeitpunkt genau anzeigen. Sobald mittels des LRU-Cache-Algorithmus ein Element ausgelagert wird, ändern sich die für alle weiteren Objekte gesetzten Referenz-Bits ebenfalls.

Adaptive Replacement Cache (ARC): Der von IBM im Almaden Research Center entwickelte Adaptive-Replacement-Cache-Algorithmus identifiziert neben den zuletzt gelöschten Cache-Einträgen ebenso die am wenigsten (LFU) und die zuletzt genutzten Objekte (LRU). Durch diese Kombination lässt sich der verfügbare Cache optimal nutzen.

Most Recently Used (MRU): Der MRU-Cache-Algorithmus ersetzt zuletzt genutzte Daten zuerst und bietet sich in Szenarien an, in denen die Zugriffswahrscheinlichkeit vom Alter des Objekts bestimmt wird – je älter die Daten, desto wahrscheinlicher ist, dass diese abgerufen werden.

Folgen Sie SearchStorage.de auch auf Twitter, Google+, Xing und Facebook!