Cache-Algorithmus
Ein Cache-Algorithmus ist ein Algorithmus, der zur Verwaltung eines Caches oder einer Gruppe von Daten verwendet wird. Wenn der Cache voll ist, entscheidet er, welches Element aus dem Cache gelöscht werden soll. Das Wort Trefferquote beschreibt, wie oft eine Anforderung aus dem Cache bedient werden kann. Der Begriff Latenz beschreibt, wie lange ein zwischengespeichertes Element erhalten werden kann. Cache-Alorhythmen sind ein Kompromiss zwischen Trefferquote und Latenz.
- Der effizienteste Caching-Algorithmus wäre es, immer die Informationen zu verwerfen, die für die längste Zeit in der Zukunft nicht benötigt werden. Dieses optimale Ergebnis wird als Belady's optimaler Algorithmus oder hellseherischer Algorithmus bezeichnet. Da es im Allgemeinen unmöglich ist, vorherzusagen, wie weit in der Zukunft Informationen benötigt werden, ist dies in der Praxis in der Regel nicht umsetzbar. Das praktische Minimum kann erst nach dem Experiment berechnet werden, und man kann die Wirksamkeit des tatsächlich gewählten Cache-Algorithmus mit dem optimalen Minimum vergleichen.
- Least Recently Used (LRU): löscht zuerst die am wenigsten kürzlich verwendeten Elemente. Bei diesem Algorithmus muss verfolgt werden, was wann verwendet wurde. Dies ist kostspielig, wenn man sicherstellen will, dass der Algorithmus immer das am wenigsten kürzlich verwendete Element verwirft. Allgemeine Implementierungen dieser Technik erfordern es, "Altersbits" für Cache-Zeilen aufzubewahren und die "Least Recently Used"-Cache-Zeile basierend auf Altersbits zu verfolgen. Bei einer solchen Implementierung ändert sich jedes Mal, wenn eine Cache-Zeile verwendet wird, das Alter aller anderen Cache-Zeilen. LRU ist eigentlich eine Familie von Cache-Algorithmen, zu der auch Mitglieder gehören: 2Q von Theodore Johnson und Dennis Shasha und LRU/K von Pat O'Neil, Betty O'Neil und Gerhard Weikum.
- Zuletzt benutzt (MRU): Dieser Algorithmus löscht die zuletzt verwendeten Elemente zuerst. Dieser Caching-Mechanismus wird häufig für Datenbank-Speicher-Caches verwendet.
- Pseudo-LRU (PLRU): Es gibt bestimmte Fälle, in denen FEVU sehr schwer umzusetzen ist. In solchen Fällen kann es ausreichen, zu wissen, dass in den meisten Fällen eines der zuletzt verwendeten Elemente gelöscht wird. Dort kann der PLRU-Algorithmus verwendet werden, da er nur ein Bit pro Cache-Element benötigt, um zu funktionieren.
- 2-Wege-Satz assoziativ: für schnelle CPU-Caches, bei denen selbst PLRU zu langsam ist. Die Adresse eines neuen Elements wird verwendet, um eine von zwei möglichen Stellen im Cache zu berechnen, an die es gehen darf. Die LRU der beiden wird verworfen. Dies erfordert ein Bit pro Paar von Cache-Zeilen, um anzuzeigen, welche der beiden Zeilen am wenigsten kürzlich verwendet wurde.
- Direct-mapped Cache: für CPU-Caches mit der höchsten Geschwindigkeit, bei denen selbst 2-Wege-Set-Assoziativ-Caches zu langsam sind. Die Adresse des neuen Elements wird verwendet, um die eine Stelle im Cache zu berechnen, an die es gehen darf. Was auch immer vorher dort war, wird verworfen.
- Least Frequently Used (LFU): LFU zählt, wie oft ein Artikel benötigt wird. Diejenigen, die am wenigsten häufig gebraucht werden, werden zuerst weggeworfen.
- Adaptive Replacement Cache (ARC): ständiger Ausgleich zwischen LRU und LFU, um das kombinierte Ergebnis zu verbessern.
- Multi Queue (MQ)-Caching-Algorithmus: (von Y. Zhou J.F. Philbin und Kai Li).
Andere Dinge, die zu berücksichtigen sind:
- Artikel mit unterschiedlichen Kosten: Bewahren Sie Artikel auf, die teuer zu beschaffen sind, z.B. solche, deren Beschaffung viel Zeit in Anspruch nimmt.
- Elemente nehmen mehr Cache in Anspruch: Wenn Elemente unterschiedliche Größen haben, möchte der Cache möglicherweise ein großes Element verwerfen, um mehrere kleinere zu speichern.
- Artikel, die mit der Zeit ablaufen: Einige Caches speichern Informationen, die mit der Zeit ablaufen (z.B. ein News-Cache, ein DNS-Cache oder ein Web-Browser-Cache). Der Computer kann Elemente verwerfen, weil sie abgelaufen sind. Abhängig von der Größe des Caches ist möglicherweise kein weiterer Cache-Algorithmus zum Verwerfen von Elementen erforderlich.
Es gibt auch verschiedene Algorithmen zur Aufrechterhaltung der Cache-Kohärenz. Dies gilt nur für Situationen, in denen mehrere unabhängige Caches für die gleichen Daten verwendet werden (z. B. mehrere Datenbankserver, die die einzige gemeinsame Datendatei aktualisieren).
Welche Speicherplätze können von welchen Cache-Plätzen zwischengespeichert werden
Fragen und Antworten
F: Was ist ein Cache-Algorithmus?
A: Ein Cache-Algorithmus ist ein Algorithmus zur Verwaltung eines Caches oder einer Gruppe von Daten. Er entscheidet, welches Element aus dem Cache gelöscht werden soll, wenn dieser voll ist.
F: Was ist die Trefferrate?
A: Die Trefferquote beschreibt, wie oft eine Anfrage aus dem Cache bedient werden kann.
F: Was beschreibt die Latenzzeit?
A: Die Latenzzeit beschreibt, wie lange ein Objekt aus dem Cache abgerufen werden kann.
F: Was ist der optimale Algorithmus von Belady?
A: Der optimale Algorithmus von Belady, auch bekannt als der hellsichtige Algorithmus, ist ein effizienter Caching-Algorithmus, der immer die Informationen verwirft, die am längsten in der Zukunft nicht mehr benötigt werden. Dieses Ergebnis lässt sich in der Regel nicht in die Praxis umsetzen, da es voraussetzt, dass man vorhersagen kann, was weit in der Zukunft benötigt wird.
F: Wie funktioniert Least Recently Used (LRU)?
A: LRU löscht die am wenigsten genutzten Elemente zuerst und erfordert eine Nachverfolgung, was wann genutzt wurde, indem "Altersbits" für jede Cache-Zeile verwendet werden und anhand der Altersbits verfolgt wird, welche Zeile am wenigsten genutzt wurde. Jedes Mal, wenn eine Cache-Zeile verwendet wird, wird das Alter aller anderen Cache-Zeilen entsprechend geändert.
F: Wie funktioniert die Funktion Most Recently Used (MRU)?
A: MRU löscht die zuletzt verwendeten Elemente zuerst. Dieser Caching-Mechanismus wird üblicherweise für Datenbank-Speicher-Caches verwendet.
F: Welche anderen Algorithmen gibt es zur Erhaltung der Cache-Kohärenz?
A: Es gibt verschiedene Algorithmen zur Aufrechterhaltung der Cache-Kohärenz, wenn mehrere unabhängige Caches für gemeinsam genutzte Daten verwendet werden, z.B. wenn mehrere Datenbankserver eine einzige gemeinsame Datendatei aktualisieren.
