Cache-algoritme
En cache-algoritme er en algoritme, der bruges til at administrere en cache eller en gruppe af data. Når cachen er fuld, beslutter den, hvilket element der skal slettes fra cachen. Ordet hitrate beskriver, hvor ofte en forespørgsel kan betjenes fra cachen. Udtrykket latency beskriver, hvor længe et element i cachen kan hentes. Cache-algoritmer er en afvejning af hit-rate og latenstid.
- Den mest effektive caching-algoritme er altid at kassere de oplysninger, der ikke vil være nødvendige i længst tid fremover. Dette optimale resultat kaldes Belady's optimale algoritme eller den clairvoyante algoritme. Da det generelt er umuligt at forudsige, hvor langt ude i fremtiden der vil være behov for oplysninger, kan dette ikke gennemføres i praksis. Det praktiske minimum kan kun beregnes efter forsøg, og man kan sammenligne effektiviteten af den faktisk valgte cache-algoritme med det optimale minimum.
- LRU (Least Recently Used): sletter de mindst brugte elementer først. Denne algoritme kræver, at man holder styr på, hvad der blev brugt hvornår. Det er dyrt, hvis man vil sikre sig, at algoritmen altid kasserer det senest anvendte element. Generelle implementeringer af denne teknik kræver, at man beholder "aldersbits" for cache-linjer og sporer den "senest anvendte" cache-linje på grundlag af aldersbits. I en sådan implementering ændres alderen for alle andre cache-linjer, hver gang en cache-linje anvendes. LRU er faktisk en familie af caching-algoritmer med bl.a. følgende medlemmer: 2Q af Theodore Johnson og Dennis Shasha og LRU/K af Pat O'Neil, Betty O'Neil og Gerhard Weikum.
- Senest anvendte (MRU): Denne algoritme sletter de senest anvendte elementer først. Denne caching-mekanisme anvendes almindeligvis til databasehukommelsescaches.
- Pseudo-LRU (PLRU): I visse tilfælde er det meget vanskeligt at gennemføre LRU. I sådanne tilfælde kan det være tilstrækkeligt at vide, at i de fleste tilfælde slettes et af de mindst anvendte elementer. PLRU-algoritmen kan anvendes i disse tilfælde, fordi den kun har brug for én bit pr. cache-element for at fungere.
- 2-vejs sæt associativ: til højhastigheds-CPU-cacher, hvor selv PLRU er for langsomt. Adressen på et nyt element bruges til at beregne en af to mulige placeringer i cachen, hvor det kan placeres. Den LRU af de to steder kasseres. Dette kræver en bit pr. par cache-linjer for at angive, hvilken af de to der blev brugt mindst for nylig.
- Direct-mapped cache: til de hurtigste CPU-caches, hvor selv 2-vejs-sæt associative caches er for langsomme. Adressen på det nye element bruges til at beregne den ene placering i cachen, hvor det må placeres. Det, der var der før, bliver kasseret.
- Mindst hyppigt anvendt (LFU): LFU tæller, hvor ofte der er brug for en vare. De varer, der bruges mindst ofte, kasseres først.
- Adaptive Replacement Cache (ARC): balancerer konstant mellem LRU og LFU for at forbedre det samlede resultat.
- Multi Queue (MQ) caching-algoritme: (af Y. Zhou J.F. Philbin og Kai Li).
Andre ting, du skal overveje:
- Varer med forskellige omkostninger: behold varer, der er dyre at få fat i, f.eks. varer, der tager lang tid at få fat i.
- Elementer, der optager mere cache: Hvis elementer har forskellige størrelser, vil cachen måske kassere et stort element for at gemme flere mindre elementer.
- Varer, der udløber med tiden: Nogle caches gemmer oplysninger, der udløber (f.eks. en nyhedscache, en DNS-cache eller en webbrowsercache). Computeren kan kassere elementer, fordi de er udløbet. Afhængigt af cachens størrelse kan det ikke være nødvendigt med en yderligere caching-algoritme til at kassere elementer.
Der findes også forskellige algoritmer til at opretholde cache-kohærens. Dette gælder kun i situationer, hvor der anvendes flere uafhængige caches til de samme data (f.eks. flere databaseservere, der opdaterer en enkelt delt datafil).
Hvilke hukommelsesplaceringer kan caches af hvilke cache-placeringer
Spørgsmål og svar
Spørgsmål: Hvad er en Cache-algoritme?
A: En Cache-algoritme er en algoritme, der bruges til at administrere en cache eller en gruppe af data. Den bestemmer, hvilket element der skal slettes fra cachen, når den er fuld.
Spørgsmål: Hvad er hit rate?
A: Hit rate beskriver, hvor ofte en anmodning kan betjenes fra cachen.
Spørgsmål: Hvad beskriver latenstid?
Svar: Latency beskriver, hvor længe et element i cachen kan hentes.
Spørgsmål: Hvad er Belady's optimale algoritme?
Svar: Beladys optimale algoritme, også kendt som den clairvoyante algoritme, er en effektiv caching-algoritme, som altid kasserer de oplysninger, der ikke vil blive brugt i længst tid fremover. Dette resultat kan generelt ikke gennemføres i praksis, fordi det kræver, at man kan forudsige, hvad der vil blive brug for langt ude i fremtiden.
Spørgsmål: Hvordan fungerer LRU (Least Recently Used)?
Svar: LRU sletter de elementer, der er brugt mindst for nylig, først og kræver, at man holder styr på, hvad der blev brugt hvornår, ved at bruge "aldersbits" for hver cache-linje og spore, hvilken linje der blev brugt mindst for nylig på grundlag af aldersbits. Hver gang en cache-linje bruges, ændres alle andre cache-linjers alder tilsvarende.
Spørgsmål: Hvordan fungerer MRU (Most Recently Recently Used)?
Svar: MRU sletter de senest anvendte elementer først, og denne cachingmekanisme anvendes almindeligvis til databasehukommelsescaches.
Spørgsmål: Hvilke andre algoritmer findes der til at opretholde cachekohærens?
Svar: Der findes forskellige algoritmer til at opretholde cachekohærens, når flere uafhængige caches anvendes til delte data, f.eks. flere databaseservere, der opdaterer en enkelt delt datafil.
