Cache-algoritm

En cache-algoritm är en algoritm som används för att hantera en cache eller en datagrupp. När cacheminnet är fullt bestämmer den vilket objekt som ska tas bort från cacheminnet. Ordet hit rate beskriver hur ofta en begäran kan betjänas från cacheminnet. Termen latens beskriver hur länge ett objekt i cacheminnet kan erhållas. Cache-algoritmer är en kompromiss mellan träfffrekvens och latenstid.

Den mest effektiva caching-algoritmen är att alltid kasta den information som inte kommer att behövas under den längsta tiden i framtiden. Detta optimala resultat kallas Beladys optimala algoritm eller den klarsynta algoritmen. Eftersom det i allmänhet är omöjligt att förutsäga hur långt fram i tiden information kommer att behövas är detta i allmänhet inte genomförbart i praktiken. Det praktiska minimumet kan beräknas först efter experiment, och man kan jämföra effektiviteten hos den faktiskt valda cache-algoritmen med det optimala minimumet.
LRU (Least Recently Used): raderar de senast använda objekten först. Denna algoritm kräver att man håller reda på vad som användes när. Detta är dyrt om man vill försäkra sig om att algoritmen alltid slänger det senast använda objektet. Generella tillämpningar av denna teknik kräver att man behåller "åldersbitar" för cachelinjer och spårar den "senast använda" cachelinjen på grundval av åldersbitar. I ett sådant genomförande ändras åldern för alla andra cachelinjer varje gång en cachelinje används. LRU är faktiskt en familj av caching-algoritmer med bland annat följande medlemmar: 2Q av Theodore Johnson och Dennis Shasha och LRU/K av Pat O'Neil, Betty O'Neil och Gerhard Weikum.
Senast använda (MRU): Denna algoritm raderar de senast använda objekten först. Denna cachemekanism används ofta för minnescacher i databaser.
Pseudo-LRU (PLRU): Det finns vissa fall där LRU är mycket svårt att genomföra. I sådana fall kan det räcka med att veta att i de flesta fall raderas ett av de minst nyligen använda objekten. PLRU-algoritmen kan användas i dessa fall, eftersom den endast behöver en bit per cacheobjekt för att fungera.

2-vägs associativ uppsättning: för höghastighets-CPU-cacher där även PLRU är för långsamt. Adressen för ett nytt objekt används för att beräkna en av två möjliga platser i cacheminnet där det kan placeras. LRU av de två platserna kasseras. Detta kräver en bit per par cachelinjer för att ange vilken av de två som användes minst nyligen.
Direktmappad cache: för CPU-caches med högsta hastighet där även 2-vägs associativa caches är för långsamma. Adressen för det nya objektet används för att beräkna den plats i cacheminnet där det får placeras. Det som fanns där tidigare slängs.
Minst frekvent använt (LFU): LFU räknar hur ofta en artikel behövs. De artiklar som används minst ofta kasseras först.
Adaptive Replacement Cache (ARC): balanserar ständigt mellan LRU och LFU för att förbättra det kombinerade resultatet.
Algoritm för caching i flera köer (MQ): (av Y. Zhou J.F. Philbin och Kai Li).

Andra saker att tänka på:

Föremål med olika kostnader: behåll föremål som är dyra att få tag på, t.ex. sådana som det tar lång tid att få tag på.
Objekt som tar mer plats i cacheminnet: Om objekt har olika storlek kan det hända att cacheminnet vill kasta ett stort objekt för att lagra flera mindre objekt.
Föremål som upphör att gälla med tiden: Vissa cacher sparar information som löper ut (t.ex. en nyhetscache, en DNS-cache eller en webbläsarcache). Det kan hända att datorn kastar bort information eftersom den har löpt ut. Beroende på hur stor cachen är kan det inte vara nödvändigt med någon ytterligare cachingalgoritm för att kasta objekt.

Det finns också olika algoritmer för att upprätthålla cachekohärens. Detta gäller endast situationer där flera oberoende cacheminnen används för samma data (t.ex. flera databasservrar som uppdaterar en enda delad datafil).

Vilka minnesplatser kan cachelagras av vilka cacheplatser.

Frågor och svar

Fråga: Vad är en cachealgoritm?

S: En cachealgoritm är en algoritm som används för att hantera en cache eller en grupp av data. Den bestämmer vilket objekt som ska tas bort från cacheminnet när det är fullt.

F: Vad är träfffrekvens?

S: Träfffrekvens beskriver hur ofta en begäran kan betjänas från cacheminnet.

F: Vad beskriver latenstid?

S: Latency beskriver hur länge en cachad artikel kan hämtas.

F: Vad är Beladys optimala algoritm?

S: Beladys optimala algoritm, även känd som den klärvoajanta algoritmen, är en effektiv caching-algoritm som alltid kastar bort den information som inte kommer att behövas under den längsta tiden i framtiden. Detta resultat kan i allmänhet inte tillämpas i praktiken eftersom det kräver att man förutsäger vad som kommer att behövas långt in i framtiden.

F: Hur fungerar LRU (Least Recently Used)?

S: LRU raderar de minst nyligen använda objekten först och kräver att man håller reda på vad som användes när genom att använda "åldersbitar" för varje cachelinje och spåra vilken linje som användes minst nyligen baserat på åldersbitar. Varje gång en cachelinje används ändras alla andra cachelinjers ålder i enlighet med detta.

Fråga: Hur fungerar MRU (Most Recently Used)?

S: MRU raderar de senast använda objekten först, och denna cachemekanism används ofta för minnescacher i databaser.

F: Vilka andra algoritmer finns det för att upprätthålla cachekohärens?

S: Det finns olika algoritmer för att upprätthålla cachekoherens när flera oberoende cacheminnen används för delade data, t.ex. när flera databasservrar uppdaterar en enda delad datafil.