Un algoritmo Cache è un algoritmo utilizzato per gestire una cache o un gruppo di dati. Quando la cache è piena, decide quale elemento deve essere cancellato dalla cache. La parola "hit rate" descrive la frequenza con cui una richiesta può essere servita dalla cache. Il termine latenza descrive per quanto tempo si può ottenere un elemento della cache. Gli aloritmi della cache sono un compromesso tra hit rate e latenza.

  • L'algoritmo di caching più efficiente sarebbe quello di scartare sempre le informazioni che non saranno più necessarie in futuro. Questo risultato ottimale è indicato come l'algoritmo ottimale di Belady o l'algoritmo del chiaroveggente. Poiché è generalmente impossibile prevedere fino a che punto in futuro saranno necessarie informazioni, questo non è generalmente implementabile nella pratica. Il minimo pratico può essere calcolato solo dopo la sperimentazione, e si può confrontare l'efficacia dell'algoritmo di cache effettivamente scelto con il minimo ottimale.
  • Least Recently Used (LRU): elimina prima gli articoli meno usati di recente. Questo algoritmo richiede di tenere traccia di ciò che è stato usato quando. Questo è costoso se si vuole essere sicuri che l'algoritmo elimini sempre l'elemento meno usato di recente. Le implementazioni generali di questa tecnica richiedono di mantenere i "bit di età" per le linee di cache e di tenere traccia della linea di cache "Least Recently Used" basata sui bit di età. In tale implementazione, ogni volta che viene usata una linea di cache, l'età di tutte le altre linee di cache cambia. LRU è in realtà una famiglia di algoritmi di cache con membri che includono: 2Q di Theodore Johnson e Dennis Shasha e LRU/K di Pat O'Neil, Betty O'Neil e Gerhard Weikum.
  • Ultimamente usato (MRU): Questo algoritmo cancella prima gli elementi usati più di recente. Questo meccanismo di caching è comunemente usato per le cache di memoria di database.
  • Pseudo-LRU (PLRU): Ci sono alcuni casi in cui la LRU è molto difficile da implementare. In questi casi può essere sufficiente sapere che nella maggior parte dei casi, uno degli elementi meno utilizzati di recente viene cancellato. L'algoritmo PLRU può essere usato lì, perché ha bisogno di un solo bit per ogni elemento della cache per funzionare.
  • 2-way set associativo: per cache di CPU ad alta velocità dove anche PLRU è troppo lento. L'indirizzo di un nuovo elemento viene utilizzato per calcolare una delle due possibili posizioni nella cache dove è permesso andare. Il LRU dei due viene scartato. Questo richiede un bit per ogni coppia di linee di cache, per indicare quale delle due è stata usata meno di recente.
  • Cache con mappatura diretta: per le cache delle CPU a più alta velocità, dove anche le cache associative a 2 vie sono troppo lente. L'indirizzo del nuovo elemento viene utilizzato per calcolare l'unica posizione nella cache in cui è permesso andare. Qualsiasi cosa ci fosse prima viene scartata.
  • Utilizzato meno frequentemente (LFU): LFU conta la frequenza con cui un articolo è necessario. Quelli che vengono usati meno spesso vengono scartati per primi.
  • Adaptive Replacement Cache (ARC): bilancia costantemente tra LRU e LFU, per migliorare il risultato combinato.
  • Algoritmo di caching multi-coda (MQ): (di Y. Zhou J.F. Philbin e Kai Li).

Altre cose da considerare:

  • Articoli con costi diversi: conservare gli articoli che sono costosi da ottenere, ad esempio quelli che richiedono molto tempo per essere acquistati.
  • Gli elementi che occupano più cache: Se gli articoli hanno dimensioni diverse, la cache potrebbe voler scartare un articolo grande per memorizzarne diversi più piccoli.
  • Articoli che scadono con il tempo: Alcune cache conservano informazioni che scadono con il tempo (ad es. una cache delle notizie, una cache DNS o una cache del browser web). Il computer può scartare gli elementi perché sono scaduti. A seconda delle dimensioni della cache non è necessario un ulteriore algoritmo di caching per eliminare gli elementi.

Esistono anche vari algoritmi per mantenere la coerenza della cache. Ciò vale solo in situazioni in cui vengono utilizzate più cache indipendenti per gli stessi dati (ad esempio più server di database che aggiornano il singolo file di dati condiviso).