Cache-algoritmen: definitie, werking en populaire technieken (LRU, LFU, ARC)

Ontdek definitie, werking en populaire technieken (LRU, LFU, ARC) van cache-algoritmen — verbeter hitrate, verlaag latency en kies de optimale cachingstrategie voor uw systeem.

Een cache-algoritme is een algoritme dat bepaalt welke gegevens tijdelijk in een cache worden bewaard en — wanneer de cache vol is — welk item moet worden verwijderd om plaats te maken voor nieuwere gegevens. Twee belangrijke meetwaarden zijn de hit rate (hoe vaak een verzoek in de cache wordt gevonden) en latency (hoe lang het duurt om een cache-item te verkrijgen). In ontwerp en keuze van een cache-algoritme zoekt men een goede balans tussen hoge hit rate, lage latency en beheersbare implementatiecomplexiteit.

Optimale vervanging: Belady's algoritme

Het theoretisch meest efficiënte vervangingsbeleid is om altijd het item te verwijderen dat het verst in de toekomst het eerst opnieuw nodig zal zijn. Dit wordt het optimale algoritme van Belady genoemd (ook wel het helderziende algoritme genoemd). Omdat dit beleid vereist dat je precies weet hoe toekomstige toegangspatronen eruitzien, is het in de praktijk vrijwel nooit direct toepasbaar. Het optimale beleid fungeert echter als nuttige ondergrens: door simulatie op toegangs-traces kan men het optimale resultaat berekenen en hiermee de effectiviteit van praktische algoritmen vergelijken.

Algemeen gebruikte vervangingsstrategieën

• Minst recentelijk gebruikt (LRU): verwijdert het item dat het langst niet is gebruikt. LRU berust op het principe van temporele localiteit en is in veel workloads zeer effectief. Implementaties variëren van exacte LRU (bijvoorbeeld met een gelinkte lijst of stack-counters) tot hardware- en ruimte-efficiënte benaderingen (bijv. een "clock"-algoritme of age-bits). Exacte LRU kan duur zijn in tijd of geheugen, daarom bestaan er families en varianten zoals LRU-gebaseerde algoritmen waaronder 2Q (Theodore Johnson en Dennis Shasha) en LRU/K (Pat O'Neil, Betty O'Neil en Gerhard Weikum).
• Meest recentelijk gebruikt (MRU): verwijdert juist de meest recent gebruikte items. MRU is zinvol in scenario's waar recent gebruikte data waarschijnlijk niet snel opnieuw wordt opgevraagd (bijvoorbeeld bij bepaalde database-workloads of bij sequentiële scans).
• Pseudo-LRU (PLRU): een benadering die met veel lagere overhead probeert dicht bij LRU te komen. PLRU gebruikt meestal een klein aantal bits per set (bijvoorbeeld tree-PLRU) en verwijdert in de praktijk vaak een van de minst recent gebruikte items zonder volledige volgorde bij te houden. PLRU is populair in hardwarecaches waar geheugen en tijd schaars zijn.
• Minst frequent gebruikt (LFU): telt hoe vaak elk item wordt aangesproken en verwijdert de items met de laagste frequentie. LFU is goed wanneer sommige items consistent populair blijven, maar kan problemen hebben met items die ooit populair waren maar daarna niet meer (cache-pollutie). Daarom worden vaak verouderingsmechanismen of frequentieverval (decay) toegepast om oude tellers te laten afnemen.
• Adaptieve vervangingscache (ARC): een zelf-tunend algoritme dat adaptief de balans zoekt tussen LRU-achtige en LFU-achtige gedrag om van beide voordelen te profiteren. ARC houdt meerdere lijsten bij (recente items, frequent gebruikte items en recente evicties) en past dynamisch de grootte van die lijsten aan op basis van toegangspatronen, zodat het zich kan aanpassen aan veranderende workloads.
• Multi-Queue (MQ): een hiërarchisch algoritme (o.a. van Y. Zhou, J.F. Philbin en Kai Li) dat items over meerdere queues (op basis van leeftijd en frequentie) verplaatst. MQ onderscheidt zich door zowel korte- als langlopende populariteitspatronen te kunnen volgen.

Cache-organisaties en associativiteit

• 2-way set-associatief: gebruikt bij hogesnelheids CPU-caches wanneer volledige associativiteit te duur is. Een adres wordt toegewezen aan een set met (bijvoorbeeld) twee mogelijke plaatsen; de LRU van de twee wordt bij een miss vervangen. Voor elke pair is meestal één bit nodig om aan te geven welke van de twee het minst recent gebruikt is.
• Direct-mapped cache: de eenvoudigste en snelste variant: elk adres wijst naar precies één locatie in de cache. Bij een write of miss wordt die locatie overschreven. Direct-mapped caches zijn snel maar kunnen leiden tot meer conflict-misses.

Praktische verbeteringen en varianten

• 2Q: combineert een korte termijn LRU-achtige lijst voor nieuwe items en een tweede lijst voor items die meermaals worden gebruikt. Dit vermindert het effect van éénmalige toegangspatronen op LFU/LRU-resultaten.
• LRU/K: houdt niet alleen bij wanneer een item recentelijk is gebruikt, maar ook de K-de meest recente gebruikstijden, zodat items die vaker op lange termijn gebruikt worden hogere prioriteit krijgen.
• TinyLFU: een veelgebruikte approximation van LFU die gebruikmaakt van compacte frequentietellers (bv. met een sketch) om een lage overhead maar toch goede beslissingen te bereiken.
• Cost- en size-aware strategieën: sommige caches houden rekening met de kosten van het halen van een item (latency, netwerkkosten) en de grootte van items. Voorbeelden: Greedy-Dual-Size en gewichtstoekenning aan items zodanig dat dure of compacte items langer blijven.

Andere belangrijke aspecten

• Items met verschillende kosten: bewaar items die duur of traag zijn om te verkrijgen (bijvoorbeeld over het netwerk), ook als ze minder vaak worden gebruikt.
• Items met verschillende groottes: als itemgroottes verschillen, kan het slimmer zijn één groot item te vervangen om meerdere kleinere en vaker gebruikte items te accomoderen.
• Items die vervallen: sommige caches (DNS, webcache, nieuwsdiensten) kennen een TTL of vervaltijd. Verlopen items kunnen automatisch worden verwijderd, waardoor een eenvoudiger vervangingsbeleid volstaat als de cache niet vol raakt.
• Metingen en evaluatie: beoordeel caches met metrics als hit rate, miss rate, gemiddelde latency en doorvoer. Gebruik trace-driven simulatie en realistische workloads. Vergelijk resultaten eventueel met de optimale Belady-waarde voor inzicht in marge voor verbetering.
• Ruimtelijke en temporele localiteit: veel caches functioneren goed omdat toegangspatronen lokale herhaling en nabijheid vertonen; ontwerp moet hiermee rekening houden (prefetching, blokkengrootte).
• Cache-coherency: voor systemen met meerdere caches die dezelfde data kunnen updaten (bijvoorbeeld meerdere database- of processorcaches) bestaan aparte protocollen en algoritmen om de cache-coherency te behouden en consistente lees-/schrijftoegang te garanderen.

Tot slot: in de praktijk kiezen ontwerpers vaak voor hybride of adaptieve strategieën (zoals ARC, MQ of TinyLFU-gecombineerde benaderingen) en stemmen implementatie en parameters af op het typische toegangspatroon, de hardwarebeperkingen en de kosten van het ophalen van gegevens. Evaluatie met representatieve traces en monitoring in productie is essentieel om te bepalen welk algoritme voor een specifieke toepassing het meest geschikt is.

Vragen en antwoorden

V: Wat is een Cache-algoritme?

V: Wat is hit rate?

V: Wat beschrijft latency?

V: Wat is het optimale algoritme van Belady?

V: Hoe werkt Least Recently Used (LRU)?

V: Hoe werkt Most Recently Used (MRU)?

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

Zoek op letter