1. Home
  2. Docs
  3. Redis
  4. Introduzione
  5. Le policy

Le policy

Esistono doversi tipi di policy che si possono adottare per la gestione della Cache.

Quella utilizzata più frequentemente è la Least Recently Used o LRU.

Esistono diversi tipi di algoritmi che possono essere utilizzati per determinare una policy della cache.

OPT

L’algoritmo ottimale, tecnicamente identificato dalla sigla OPT, è realizzabile solo concettualmente ma non effettivamente.
L’OPT si basa sull’ipotesi di conoscere in anticipo quali saranno le informazioni utilizzate e in che sequenza, in modo da renderle disponibili in cache fin da subito.
Chiaramente in un sistema applicativo questo algoritmo non trova un riscontro reale e non è adottabile come policy.

FIFO

L’algoritmo FIFO (First In First Out) è il più semplice di tutti.
Sfruttando una tabella di allocazione, l’algoritmo mette in cache ogni nuova richiesta fino al raggiungimento della dimensione massima della cache. Quando la dimensione massima è raggiunta viene eliminata la più vecchia informazione presente, ovvero la prima ad essere entrata, per far posto ad una nuova informazione.
Questo algoritmo è molto semplice e di rapida esecuzione, tuttavia ha lo svantaggio di eliminare le informazioni più vecchie anche se sono utilizzate di frequente.

Second chance

Per migliorare l’algoritmo FIFO in modo semplice è possibile adottare l’algoritmo denominato Seconda Scelta o Second Chance, noto anche come algoritmo dell’orologio.
Aggiungendo un flag (bit) alla tabella che tiene traccia delle informazioni in cache è possibile porre a 1 ogni informazione che viene acceduta oppure aggiunta. L’algoritmo verifica l’informazione in fondo allo stack e se la trova impostata con bit a 1 la imposta a 0, se invece è impostata a 0 la elimina dallo stack. In questo modo, le informazioni utilizzate più di frequente hanno l’alta probabilità di rimanere in cache.

LRU

Il miglior algoritmo conosciuto è denominato Least Recently Used.
L’LRU sfrutta uno stack con marca temporale e sposta le informazioni inutilizzate da più tempo (Least Recently Used) in fondo. In questo modo le informazioni accedute più frequentemente risultano in testa allo stack e mantenute in cache.

LFU e MFU

Esistono inoltre algoritmi basati sul conteggio del numero di riferimenti, ossia della quantità di accessi anziché dal momento in cui sono stati effettuati, come nel caso dell’LRU.

  • LFU (Least Frequently Used): elimina dalla cache l’informazione con il minor numero di accessi. Un’informazione molto usata ha un conteggio alto, mentre una che serve a poco avrà un conteggio basso.
  • MFU (Most Frequently Used): elimina dalla cache l’informazione con il maggior numero di riferimenti. Un’informazione con un conteggio basso è stata probabilmente caricata da poco, quindi è utile mantenerla.

Considerazioni

Non esiste un sistema assoluto e perfetto per ogni esigenza di caching, tuttavia l’approccio LRU è generalmente il più utilizzato per le applicazioni di uso generale. L’LFU e l’MFU sono approcci molto validi, soprattutto se è necessario utilizzare la cache per gestire informazioni come le News oppure i prodotti da proporre in un sistema di e-commerce. Mentre l’approccio Second Chance è il più veloce perché richiede la minore capacità computazionale.

Was this article helpful to you? Yes No

How can we help?