Un algoritm de memorie cache este un algoritm utilizat pentru a gestiona o memorie cache sau un grup de date. Atunci când memoria cache este plină, acesta decide ce element trebuie șters din memoria cache. Cuvântul "hit rate" descrie cât de des poate fi servită o cerere din memoria cache. Termenul latență descrie cât timp poate fi obținut un element din memoria cache. Aloritmurile de memorie cache reprezintă un compromis între rata de acces și latență.

  • Cel mai eficient algoritm de stocare în memoria cache ar fi acela de a elimina întotdeauna informațiile care nu vor fi necesare pentru o perioadă cât mai lungă de timp în viitor. Acest rezultat optim este denumit algoritmul optim al lui Belady sau algoritmul clarvăzător. Deoarece, în general, este imposibil să se prevadă cât de mult timp în viitor vor fi necesare informațiile, acest lucru nu este, în general, implementabil în practică. Minimul practic poate fi calculat numai după experimentare și se poate compara eficacitatea algoritmului de cache ales efectiv cu minimul optim.
  • Least Recently Used (LRU): șterge mai întâi elementele utilizate cel mai recent. Acest algoritm necesită urmărirea a ceea ce a fost folosit și când. Acest lucru este costisitor dacă se dorește ca algoritmul să se asigure că elimină întotdeauna elementul cel mai recent utilizat. Implementările generale ale acestei tehnici necesită păstrarea unor "biți de vârstă" pentru liniile cache și urmărirea liniei cache "cel mai recent utilizate" pe baza acestor biți de vârstă. Într-o astfel de implementare, de fiecare dată când o linie de memorie cache este utilizată, vârsta tuturor celorlalte linii de memorie cache se modifică. LRU este, de fapt, o familie de algoritmi de memorare în memoria cache cu membri care includ: 2Q de Theodore Johnson și Dennis Shasha și LRU/K de Pat O'Neil, Betty O'Neil și Gerhard Weikum.
  • Cel mai recent utilizat (MRU): Acest algoritm șterge mai întâi elementele utilizate cel mai recent. Acest mecanism de memorare este utilizat în mod obișnuit pentru memoria cache a bazelor de date.
  • Pseudo-LRU (PLRU): Există anumite cazuri în care LRU este foarte dificil de implementat. În astfel de cazuri, poate fi suficient să se știe că, în majoritatea cazurilor, unul dintre elementele cel mai recent utilizate este șters. Algoritmul PLRU poate fi utilizat în acest caz, deoarece are nevoie de un singur bit pentru fiecare element din memoria cache pentru a funcționa.
  • 2 way set associative: pentru memoria cache de mare viteză a procesorului, unde chiar și PLRU este prea lent. Adresa unui element nou este utilizată pentru a calcula una dintre cele două locații posibile în memoria cache unde poate fi plasat. LRU dintre cele două este eliminat. Acest lucru necesită un bit pentru fiecare pereche de linii de memorie cache, pentru a indica care dintre cele două a fost cel mai recent utilizat.
  • Memoria cache cu mapare directă: pentru memoria cache de cea mai mare viteză a procesorului, în cazul în care chiar și memoria cache asociativă cu set de 2 căi este prea lentă. Adresa noului element este utilizată pentru a calcula singura locație din memoria cache în care acesta poate fi plasat. Ceea ce a fost acolo înainte este eliminat.
  • Cel mai rar utilizat (LFU): LFU calculează cât de des este necesar un articol. Cele care sunt folosite cel mai rar sunt aruncate primele.
  • Adaptive Replacement Cache (ARC): echilibrează în mod constant între LRU și LFU, pentru a îmbunătăți rezultatul combinat.
  • Algoritm de memorare în memoria cache MQ (Multi Queueue): (de Y. Zhou, J.F. Philbin și Kai Li).

Alte lucruri de luat în considerare:

  • Obiecte cu costuri diferite: păstrați obiectele care sunt scumpe de obținut, de exemplu cele care necesită mult timp pentru a fi obținute.
  • Elemente care ocupă mai multă memorie cache: Dacă elementele au dimensiuni diferite, este posibil ca memoria cache să vrea să renunțe la un element mare pentru a stoca mai multe elemente mai mici.
  • Articole care expiră în timp: Unele cache-uri păstrează informații care expiră (de exemplu, un cache de știri, un cache DNS sau un cache de browser web). Este posibil ca computerul să renunțe la elemente deoarece acestea au expirat. În funcție de dimensiunea memoriei cache, este posibil să nu fie necesar un alt algoritm de memorare pentru a elimina elementele.

Există, de asemenea, diverși algoritmi pentru menținerea coerenței cache-ului. Acest lucru se aplică numai în situațiile în care se utilizează mai multe memorii cache independente pentru aceleași date (de exemplu, mai multe servere de baze de date care actualizează un singur fișier de date partajat).