Cache

Caching ist ein Begriff aus der Informatik. Die Idee hinter einem Cache (ausgesprochen "Cash" /ˈkæʃ/ KASH ) ist sehr einfach: Sehr oft ist es sehr zeitaufwendig, ein Ergebnis für eine Berechnung zu erhalten, daher ist es im Allgemeinen eine gute Idee, das Ergebnis zu speichern. Es werden zwei Arten von Speichermedien verwendet: Die eine ist normalerweise ziemlich groß, aber der Zugriff darauf ist "langsam"; auf die andere kann viel schneller zugegriffen werden, aber im Allgemeinen ist sie klein. Die Grundidee hinter dem Caching besteht darin, das Medium, auf das schnell zugegriffen werden kann, zu verwenden, um Kopien von Daten zu erhalten. Es gibt keinen Unterschied zwischen der Kopie und dem Original. Der Zugriff auf die Originaldaten kann lange dauern oder teuer sein (z.B. die Ergebnisse eines schwierigen Problems, dessen Lösung viel Zeit in Anspruch nimmt). Aus diesem Grund ist es viel "billiger", einfach die Kopie der Daten aus dem Cache zu verwenden. Anders ausgedrückt: Ein Cache ist ein temporärer Speicherbereich, der Kopien von Daten enthält, die häufig verwendet werden. Wenn sich eine Kopie der Daten in diesem Cache befindet, ist es schneller, diese Kopie zu verwenden, als die Originaldaten neu abzurufen oder neu zu berechnen. Dadurch verkürzt sich die für den Zugriff auf die Daten durchschnittlich benötigte Zeit. Wenn ein neuer Wert in einen Cache gestellt wird, bedeutet dies oft, dass ein älterer Wert ersetzt werden muss. Es gibt verschiedene Ideen (gewöhnlich "Strategien" genannt), wie der zu ersetzende Wert ausgewählt werden kann.

Ein Puffer ist einem Cache sehr ähnlich. Der Unterschied besteht darin, dass der Client, der auf die Daten in einem Puffer zugreift, weiß, dass es einen Puffer gibt; der Puffer wird von der Anwendung verwaltet. Bei einem Cache muss der Client, der auf die Daten zugreift, nicht wissen, dass es einen Cache gibt.

Typische Computeranwendungen greifen auf sehr ähnliche Weise auf Daten zu. Angenommen, die Daten sind in "Blöcke" strukturiert, auf die einzeln zugegriffen werden kann. Wenn eine Anwendung auf einen Block zugreift, ist es sehr wahrscheinlich, dass sie auch auf einen Block zugreift (oder darauf verweist), der "nahe" am ursprünglichen Block liegt. Dies wird als "Lokalität der Referenz" bezeichnet. Es gibt verschiedene Arten einer solchen "Lokalität". Die "Lokalität der Referenz" ist einer der Gründe, warum Caches in vielen Bereichen der Datenverarbeitung gut funktionieren.

Um gut arbeiten zu können, sind die Caches im Vergleich zur gesamten Datenmenge klein. Je größer der Cache, desto länger dauert es, einen Eintrag nachzuschlagen. Größere Caches sind auch teurer zu bauen.

Wie Caches funktionieren

Ein Cache ist ein Speicherblock zum Speichern von Daten, der wahrscheinlich wieder verwendet wird. Die CPU und die Festplatte verwenden häufig einen Cache, ebenso wie Web-Browser und Web-Server.

Ein Cache besteht aus vielen Einträgen, die als Pool bezeichnet werden. Jeder Eintrag enthält ein Datum (ein Datenbit), das eine Kopie eines Datums an einer anderen Stelle ist. Caches verwenden normalerweise einen so genannten Backing Store. Backing-Stores sind im Vergleich zum Cache langsam oder teuer im Zugriff. Ein Platten-Cache verwendet z. B. eine Festplatte als Backup-Speicher. An jeden Eintrag ist auch eine kleine Information angehängt, die als Tag bezeichnet wird. Dieses Tag wird verwendet, um den Ort zu finden, an dem die Originaldaten gespeichert sind.

Caches zum Lesen

Wenn ein Client (eine CPU, ein Web-Browser, ein Betriebssystem) auf ein Datenelement zugreifen möchte, von dem er glaubt, dass es sich im Backing Store befindet, prüft er zunächst, ob das Datenelement im Cache gefunden werden kann. Wenn die Daten im Cache gefunden werden können, kann der Client sie verwenden und muss nicht den Hauptspeicher verwenden. Dies wird als Cache-Treffer bezeichnet. So könnte z. B. ein Web-Browser-Programm seinen lokalen Cache auf der Festplatte daraufhin überprüfen, ob es eine lokale Kopie des Inhalts einer Webseite unter einer bestimmten URL hat. In diesem Beispiel ist die URL das Tag, und der Inhalt der Webseite ist das Datum.

Die andere Situation, die auftreten kann, ist, dass das Datum mit dem Tag nicht im Cache gefunden werden kann. Dies wird als Cache-Miss bezeichnet. Das Datum muss aus dem Sicherungsspeicher geholt werden. Normalerweise wird es in den Cache kopiert, so dass es beim nächsten Mal nicht mehr aus dem Sicherungsspeicher geholt werden muss.

Der Cache hat nur eine begrenzte Größe. Um Platz für den zuvor nicht gecachten Eintrag zu schaffen, muss eventuell ein weiterer gecachter Eintrag aus dem Cache gelöscht werden. Spezielle Regeln werden verwendet, um den Eintrag zu finden, der am besten gelöscht werden sollte. Diese Regeln werden üblicherweise Heuristik genannt. Heuristiken, die verwendet werden, um den Eintrag zu finden, werden Ersetzungsregeln genannt. Eine sehr einfache Regel, die verwendet wird, heißt Least recently used (oder LRU). Sie nimmt einfach den Eintrag, der vor langer Zeit am längsten verwendet wurde. Andere Heuristiken sind unter Cache-Algorithmus aufgeführt...

Caches zum Schreiben

Caches können auch zum Schreiben von Daten verwendet werden; dies hat den Vorteil, dass der Client seinen Betrieb fortsetzen kann, nachdem der Eintrag in den Cache geschrieben wurde; er muss nicht warten, bis der Eintrag in den Sicherungsspeicher geschrieben wurde.

Der Eintrag muss jedoch zu einem bestimmten Zeitpunkt in den Sicherungsspeicher geschrieben werden. Der Zeitpunkt, zu dem dies geschieht, wird durch die Schreibrichtlinie gesteuert.

Bei einem Write-Through-Cache wird jeder Eintrag sofort in den Backing-Store geschrieben und zusätzlich im Cache gespeichert.

Die andere Möglichkeit besteht darin, nur in den Cache zu schreiben und später in den Sicherungsspeicher zu schreiben. Dies wird als Rückschreib-Cache (oder Rückschreib-Cache) bezeichnet. Der Cache markiert die Einträge, die noch nicht in den Sicherungsspeicher geschrieben wurden; die verwendete Markierung wird oft als Dirty-Flag bezeichnet. Bevor die Einträge aus dem Cache gelöscht werden, werden sie in den Backing-Store geschrieben. Dies wird als Lazy-Write bezeichnet. Ein Fehlschlag in einem Rückschreib-Cache (bei dem ein Block durch einen anderen ersetzt werden muss) erfordert oft zwei Speicherzugriffe: einen, um das benötigte Datum zu erhalten, und einen weiteren, um die ersetzten Daten aus dem Cache in den Speicher zu schreiben.

Die Caching-Richtlinie kann auch besagen, dass ein bestimmtes Datum in den Cache geschrieben werden muss. Der Client kann viele Änderungen an dem Datum im Cache vorgenommen haben. Nachdem er dies getan hat, kann er den Cache explizit anweisen, das Datum zurückzuschreiben.

Die schreibfreie Zuweisung ist eine Cache-Richtlinie, bei der nur Lesezugriffe zwischengespeichert werden. Dadurch wird die Notwendigkeit des Zurück- oder Durchschreibens des Caches vermieden. Es wird ständig in den Backing-Store geschrieben.

Der Client ist nicht die Anwendung, die Daten im Backing Store ändert. Wenn die Daten im Backup-Store geändert wurden, ist die Kopie im Cache veraltet oder veraltet. Wenn der Client die Daten im Cache aktualisiert, sind alternativ Kopien dieser Daten in anderen Caches veraltet. Es gibt spezielle Kommunikationsprotokolle, die es Cache-Managern ermöglichen, miteinander zu kommunizieren, um die Daten aussagekräftig zu halten. Diese sind als Kohärenzprotokolle bekannt.

Diagramm eines CPU-Speicher-Caches

Auswählen des zu ersetzenden Eintrags

Ein Cache ist klein, und er wird die meiste Zeit über voll oder fast voll sein. Wenn also ein neuer Wert hinzugefügt wird, muss ein alter entfernt werden. Es gibt verschiedene Möglichkeiten, wie diese Auswahl vorgenommen werden kann:

First in First out: Ersetzen Sie einfach den Eintrag, der vor längerer Zeit in den Cache aufgenommen wurde
Am wenigsten kürzlich benutzt: Diese Idee ähnelt dem obigen FIFO, aber wenn ein Eintrag verwendet wird, wird sein Zeitstempel/Alter aktualisiert.
Am wenigsten häufig verwendet: Wieder ähnlich wie im FIFO-Fall, verwenden Sie statt eines Zeitstempels einen Zähler, der bei jeder Verwendung eines Eintrags erhöht wird.
Wählen Sie einen Eintrag nach dem Zufallsprinzip aus

Geschichte

Das Wort Cache wurde erstmals 1967 in der Informatik verwendet, als ein wissenschaftlicher Artikel für die Veröffentlichung im IBM Systems Journal vorbereitet wurde. Der Artikel handelte von einer neuen Verbesserung des Speichers in Modell 85. Modell 85 war ein Computer der IBM System/360-Produktlinie. Der Herausgeber des Journals wollte ein besseres Wort für Hochgeschwindigkeitspuffer, das in dem Artikel verwendet wurde. Er erhielt keinen Input und schlug Cache vom französischen Cacher vor, was "verstecken" bedeutet. Der Artikel wurde Anfang 1968 veröffentlicht, und die Autoren wurden von IBM geehrt. Ihre Arbeit wurde allgemein begrüßt und verbessert. Cache wurde bald zum Standard in der Computerliteratur.

Wo Caches verwendet werden

CPU-Caches

Kleine Speicher auf oder nahe dem CPU-Chip können schneller gemacht werden als der viel größere Hauptspeicher. Die meisten CPUs seit den 1980er Jahren verwenden einen oder mehrere Cachespeicher. Moderne Allzweck-CPUs in Personalcomputern können bis zu einem halben Dutzend haben. Jeder Cache kann auf einen anderen Teil der Aufgabe, Programme auszuführen, spezialisiert sein.

Platten-Caches

CPU-Caches werden im Allgemeinen vollständig durch Hardware verwaltet, andere Caches werden durch eine andere Art von Software verwaltet. Das Betriebssystem verwaltet normalerweise einen Seiten-Cache im Hauptspeicher. Benutzer außerhalb der Informatik nennen diesen Cache gewöhnlich virtuellen Speicher. Er wird vom Kernel des Betriebssystems verwaltet.

Moderne Festplatten haben Plattenpuffer. Diese werden manchmal "Plattencache" genannt, aber das ist falsch. Die Hauptfunktion dieser Puffer besteht darin, Schreibvorgänge auf der Festplatte anzuordnen und Lesevorgänge zu verwalten. Wiederholte Cache-Treffer sind selten, da der Puffer im Vergleich zur Größe der Festplatte sehr klein ist.

Lokale Festplatten sind im Vergleich zu anderen Speichergeräten, wie z. B. Remote-Servern, lokalen Bandlaufwerken oder optischen Jukeboxen, schnell. Die Verwendung lokaler Festplatten als Caches ist das Hauptkonzept der hierarchischen Speicherverwaltung.

Web-Caches

Web-Browser und Web-Proxy-Server verwenden Caches, um frühere Antworten von Web-Servern, wie z.B. Webseiten, zu speichern. Web-Caches reduzieren die Menge der Informationen, die über das Netzwerk übertragen werden müssen. Informationen, die zuvor im Cache gespeichert wurden, können oft wiederverwendet werden. Dies reduziert die Bandbreiten- und Verarbeitungsanforderungen des Webservers und trägt dazu bei, die Reaktionsfähigkeit für die Benutzer des Webs zu verbessern.

Moderne Web-Browser verwenden einen eingebauten Web-Cache, aber einige Internet-Service-Provider oder Organisationen verwenden auch einen Caching-Proxy-Server. Dabei handelt es sich um einen Web-Cache, der von allen Benutzern dieses Netzwerks gemeinsam genutzt wird.

Suchmaschinen stellen oft auch Webseiten, die sie indiziert haben, aus ihrem Cache zur Verfügung. Beispielsweise stellt Google neben jedem Suchergebnis einen "Cached"-Link zur Verfügung. Dies ist nützlich, wenn Webseiten von einem Webserver aus vorübergehend nicht zugänglich sind.

Caching mit unzuverlässigen Netzwerken

Der Write-Through-Betrieb ist in unzuverlässigen Netzwerken (wie einem Ethernet-LAN) üblich. Das Protokoll, mit dem sichergestellt wird, dass die Daten im Schreib-Cache sinnvoll sind, wenn mehrere Schreib-Caches verwendet werden, ist in einem solchen Fall sehr komplex.

Zum Beispiel sind Webseiten-Caches und Client-seitige Netzwerk-Dateisystem-Caches (wie die in NFS oder SMB) normalerweise schreibgeschützt oder schreibgeschützt, um das Netzwerkprotokoll einfach und zuverlässig zu halten.

Der Unterschied zwischen Puffer und Cache

Puffer und Cache schließen sich nicht gegenseitig aus; sie werden auch oft zusammen verwendet. Der Grund, warum sie verwendet werden, ist jedoch ein anderer. Ein Puffer ist eine Speicherstelle im Speicher, die traditionell verwendet wird, weil CPU-Befehle nicht direkt auf in Peripheriegeräten gespeicherte Daten zugreifen können. Der Computerspeicher wird als Zwischenspeicher verwendet.

Darüber hinaus kann ein solcher Puffer möglich sein, wenn ein großer Datenblock zusammengesetzt oder zerlegt wird (wie es ein Speichergerät erfordert), oder wenn die Daten in einer anderen Reihenfolge als der, in der sie produziert werden, geliefert werden. Außerdem wird normalerweise ein ganzer Puffer von Daten sequentiell übertragen (z.B. auf die Festplatte), so dass das Puffern selbst manchmal die Übertragungsleistung erhöht. Diese Vorteile sind selbst dann vorhanden, wenn die gepufferten Daten einmal in den Puffer geschrieben und einmal aus dem Puffer gelesen werden.

Ein Cache erhöht auch die Übertragungsleistung. Ein Teil des Anstiegs ist ebenfalls auf die Möglichkeit zurückzuführen, dass mehrere kleine Übertragungen zu einem großen Block zusammengefasst werden. Der Hauptleistungsgewinn ergibt sich jedoch daraus, dass eine gute Chance besteht, dass dasselbe Datum mehrmals aus dem Cache gelesen wird oder dass geschriebene Daten bald gelesen werden. Der einzige Zweck von Caches besteht darin, die Zugriffe auf den zugrunde liegenden langsameren Speicher zu reduzieren. Der Cache ist in der Regel auch eine Abstraktionsschicht, die so konzipiert ist, dass sie aus der Perspektive benachbarter Schichten unsichtbar ist. Auf diese Weise sind sich die Anwendungen oder Clients möglicherweise nicht bewusst, dass ein Cache vorhanden ist.

Fragen und Antworten

F: Was ist Caching?

A: Caching ist ein Begriff aus der Informatik, der sich auf das Speichern von Kopien häufig genutzter Daten bezieht, um schneller auf sie zugreifen zu können, als die Originaldaten erneut abzurufen oder zu berechnen.

F: Wie funktioniert das Caching?

A: Beim Caching werden zwei Arten von Speichermedien verwendet: eines, das in der Regel recht groß ist, auf das aber nur langsam zugegriffen werden kann, und ein anderes, auf das viel schneller zugegriffen werden kann, das aber im Allgemeinen kleiner ist. Die Idee hinter der Zwischenspeicherung ist, das schnelle Medium zum Speichern von Kopien der Daten zu verwenden, so dass der Zugriff auf die Originaldaten weniger Zeit in Anspruch nimmt oder weniger teuer ist.

F: Was ist ein Puffer?

A: Ein Puffer ist einem Cache insofern ähnlich, als er Kopien von Daten für einen schnelleren Zugriff speichert. Bei einem Puffer weiß der Client, der auf die Daten zugreift, jedoch, dass es einen Puffer gibt und dass dieser von einer Anwendung verwaltet wird, während bei einem Cache die Clients nicht wissen müssen, dass es einen Cache gibt.

F: Was bedeutet die Lokalität der Referenz?

A: Lokalität der Referenz bedeutet, dass eine Anwendung, die auf bestimmte Blöcke strukturierter Daten zugreift, wahrscheinlich auch auf andere Blöcke zugreift, die sich in der Nähe der Blöcke befinden, auf die ursprünglich zugegriffen wurde. Dies trägt dazu bei, dass Caches gut funktionieren, da sie im Vergleich zu allen verfügbaren Daten in der Regel klein sind.

F: Warum brauchen größere Caches länger, um Einträge nachzuschlagen?

A: Größere Caches brauchen länger, weil sie mehr gespeicherte Informationen enthalten und daher mehr Zeit für die Suche benötigen. Sie sind auch teurer, da sie mehr Ressourcen für die Speicherung benötigen.

F: Wie kann die Lokalisierung dazu beitragen, dass Caches besser funktionieren?

A: Lokalität trägt dazu bei, dass Caches besser funktionieren, denn wenn Anwendungen auf bestimmte Blöcke strukturierter Daten zugreifen, benötigen sie wahrscheinlich auch andere Blöcke in der Nähe, die dann schnell aus dem Cache abgerufen werden können, anstatt sie von einem anderen Ort zu holen oder neu zu berechnen.