Cache-algoritme

Een Cache-algoritme is een algoritme dat wordt gebruikt om een cache of een groep gegevens te beheren. Wanneer de cache vol is, beslist het welk item uit de cache moet worden verwijderd. Het woord hit rate beschrijft hoe vaak een verzoek uit de cache kan worden verwijderd. De term latency beschrijft hoe lang een cache-item kan worden verkregen. Cache alorithms zijn een afweging tussen hit rate en latency.

Het meest efficiënte caching-algoritme zou zijn om altijd de informatie weg te gooien die het langst niet nodig is in de toekomst. Dit optimale resultaat wordt het optimale algoritme van Belady of het helderziende algoritme genoemd. Aangezien het over het algemeen onmogelijk is om te voorspellen hoe ver in de toekomst informatie nodig zal zijn, is dit in de praktijk meestal niet uitvoerbaar. Het praktische minimum kan pas na het experiment worden berekend en men kan de effectiviteit van het daadwerkelijk gekozen cache-algoritme vergelijken met het optimale minimum.
Minst recentelijk gebruikt (LRU): verwijdert de minst recent gebruikte items eerst. Dit algoritme vereist het bijhouden van wat wanneer is gebruikt. Dit is duur als men er zeker van wil zijn dat het algoritme altijd het minst recent gebruikte item weggooit. Algemene implementaties van deze techniek vereisen het bijhouden van "age bits" voor cache-lijnen en het bijhouden van de "Least Recently Used" cache-lijn op basis van age-bits. Bij een dergelijke implementatie verandert de leeftijd van alle andere cache-lijnen telkens wanneer een cache-lijn wordt gebruikt. LRU is eigenlijk een familie van cache-algoritmes met onder andere leden: 2Q van Theodore Johnson en Dennis Shasha en LRU/K van Pat O'Neil, Betty O'Neil en Gerhard Weikum.
Meest recentelijk gebruikt (MRU): Dit algoritme verwijdert de meest recent gebruikte items als eerste. Dit caching mechanisme wordt vaak gebruikt voor databasegeheugencaches.
Pseudo-LRU (PLRU): Er zijn bepaalde gevallen waarin de hoofdspoorwegonderneming zeer moeilijk te implementeren is. In dergelijke gevallen kan het voldoende zijn om te weten dat in de meeste gevallen een van de minst recentelijk gebruikte items wordt verwijderd. Het OURU-algoritme kan daar gebruikt worden, omdat het slechts één bit per cache-item nodig heeft om te werken.

2-weg set associatief: voor hogesnelheids CPU-caches waar zelfs PLRU te traag is. Het adres van een nieuw item wordt gebruikt om een van de twee mogelijke locaties in de cache te berekenen waar het mag komen. De LRU van de twee wordt weggegooid. Dit vereist een bit per paar cachinelijnen, om aan te geven welke van de twee het minst recentelijk is gebruikt.
Direct-mapped cache: voor de CPU-caches met de hoogste snelheid waar zelfs 2-wegs set associatieve caches te traag zijn. Het adres van het nieuwe item wordt gebruikt om de ene locatie in de cache te berekenen waar het mag komen. Wat er eerder was wordt weggegooid.
Minst frequent gebruikt (LFU): LFU telt hoe vaak een item nodig is. Degenen die het minst vaak worden gebruikt, worden het eerst weggegooid.
Adaptieve vervangingscache (ARC): een constante balans tussen LRU en LFU, om het gecombineerde resultaat te verbeteren.
Multi Queue (MQ) caching algoritme: (door Y. Zhou J.F. Philbin en Kai Li).

Andere dingen om te overwegen:

Items met verschillende kosten: bewaar items die duur zijn om te verkrijgen, bijvoorbeeld die die lang duren om te krijgen.
Items die meer cache innemen: Als de items verschillende maten hebben, kan het zijn dat de cache een groot item wil weggooien om meerdere kleinere items op te slaan.
Items die met de tijd verlopen: Sommige caches bewaren informatie die vervalt (bijvoorbeeld een nieuwscache, een DNS-cache of een webbrowser-cache). De computer kan items weggooien omdat ze verlopen zijn. Afhankelijk van de grootte van de cache kan het zijn dat er geen verder cache-algoritme nodig is om items weg te gooien.

Er bestaan ook verschillende algoritmen om de cache-coherency te behouden. Dit geldt alleen voor situaties waarin meerdere onafhankelijke caches worden gebruikt voor dezelfde gegevens (bijvoorbeeld meerdere databaseservers die het ene gedeelde gegevensbestand updaten).

Welke geheugenlocaties kunnen worden gecached door welke cache-locaties

Vragen en antwoorden

V: Wat is een Cache-algoritme?

A: Een Cache-algoritme is een algoritme dat gebruikt wordt om een cache of een groep gegevens te beheren. Het beslist welk item uit de cache moet worden verwijderd wanneer deze vol is.

V: Wat is hit rate?

A: Hit rate beschrijft hoe vaak een verzoek uit de cache kan worden geserveerd.

V: Wat beschrijft latency?

A: Latency beschrijft hoe lang een item in de cache kan worden opgevraagd.

V: Wat is het optimale algoritme van Belady?

A: Het optimale algoritme van Belady, ook bekend als het helderziende algoritme, is een efficiënt caching-algoritme dat altijd de informatie weggooit die het langst in de toekomst niet nodig zal zijn. Dit resultaat kan over het algemeen niet in de praktijk worden gebracht omdat hiervoor moet worden voorspeld wat ver in de toekomst nodig zal zijn.

V: Hoe werkt Least Recently Used (LRU)?

A: LRU verwijdert eerst de minst recent gebruikte items en vereist dat wordt bijgehouden wat wanneer is gebruikt door voor elke cache-regel "age-bits" te gebruiken en op basis van age-bits bij te houden welke het minst recent is gebruikt. Telkens wanneer een cache-regel wordt gebruikt, wordt de leeftijd van alle andere cache-regels dienovereenkomstig gewijzigd.

V: Hoe werkt Most Recently Used (MRU)?

A: MRU verwijdert de meest recent gebruikte items als eerste en dit cachingmechanisme wordt vaak gebruikt voor databasegeheugencaches.

V: Welke andere algoritmen bestaan er om de cachecoherentie te handhaven?

A: Er bestaan verschillende algoritmen om de cachecoherentie te handhaven wanneer meerdere onafhankelijke caches worden gebruikt voor gedeelde gegevens, zoals meerdere databaseservers die een enkel gedeeld gegevensbestand bijwerken.