LRU Cache — cosa è, algoritmo di espulsione e come funziona

Cos'è LRU Cache?

LRU Cache (Least Recently Used Cache) è una struttura dati di dimensione fissa che memorizza un numero limitato di elementi e rimuove automaticamente quelli a cui si è acceduto meno frequentemente. Quando un'applicazione richiede un elemento, questo si sposta nella parte “fresca” della cache, mentre gli elementi inutilizzati a lungo si spostano verso la fine e vengono rimossi quando viene raggiunto il limite.

Il nome “Least Recently Used” descrive la politica di espulsione: viene rimosso l'elemento che non è stato utilizzato da più tempo tra tutti quelli memorizzati. Ciò si basa sul presupposto della località di riferimento (locality of reference) — i dati richiesti di recente hanno un'alta probabilità di essere nuovamente necessari. Questo è il motivo per cui LRU è considerata una delle strategie di caching più efficaci per la maggior parte delle applicazioni.

L'implementazione classica di LRU Cache richiede due strutture dati: una tabella hash per l'accesso O(1) a qualsiasi elemento per chiave e una lista doppiamente collegata per tracciare l'ordine di utilizzo. La tabella hash memorizza riferimenti ai nodi della lista, e la lista mantiene l'ordine dall'elemento più recente (testa) al più vecchio (coda).

Operazioni di base di LRU Cache

L'operazione get(key) verifica se la chiave esiste nella tabella hash. Se l'elemento viene trovato, si sposta in testa alla lista (diventa il più recente) e il suo valore viene restituito. Se non viene trovato, viene restituito null o lanciata un'eccezione. L'operazione put(key, value) inserisce un nuovo elemento: se la chiave esiste già, il valore viene aggiornato e l'elemento si sposta in testa. Se la cache è piena, l'elemento in coda viene rimosso prima dell'inserimento. Tutte le operazioni vengono eseguite in tempo costante O(1).

Come funziona LRU Cache

L'algoritmo LRU Cache si basa su due principi: conteggio degli accessi in ordine temporale e il meccanismo di espulsione per overflow. Ogni elemento è memorizzato in un nodo della lista doppiamente collegata, e i puntatori a questi nodi sono mantenuti nella tabella hash. Ad ogni accesso, l'elemento viene scollegato dalla sua posizione corrente e inserito in testa alla lista.

Quando la dimensione della cache raggiunge il suo valore massimo (maxSize) e arriva una richiesta di inserimento di un nuovo elemento, l'algoritmo rimuove l'elemento in coda della lista doppiamente collegata — questo è l'elemento meno recentemente usato. Dopo la rimozione, viene liberato spazio per il nuovo elemento, che viene inserito in testa alla lista. La tabella hash viene aggiornata di conseguenza: la vecchia chiave viene rimossa, una nuova viene aggiunta.

Una caratteristica di LRU è la sua sensibilità ai pattern di accesso con ripetizione ciclica. Se l'applicazione accede periodicamente a un insieme di dati più grande della dimensione della cache, LRU può soffrire di thrashing — sostituzione frequente di elementi dove ogni nuova richiesta espelle la precedente. In tali scenari, LFU (Least Frequently Used) o algoritmi adattivi possono essere più efficaci.

Dimensione della cache e metriche

Scegliere la dimensione di LRU Cache è un compromesso tra consumo di memoria e hit-ratio (percentuale di accessi riusciti). Valori tipici per applicazioni mobili: 10–20% della memoria disponibile per la cache di immagini e 50–200 voci per la cache di risposte di rete. Un hit-ratio dell'80–95% è considerato buono, dove la cache giustifica i costi di memoria. Per il monitoraggio, vengono utilizzati i contatori hitCount e missCount, disponibili nell'implementazione LruCache in Android.

Implementazione di LRU Cache: HashMap + Doubly Linked List

L'implementazione canonica di LRU Cache utilizza una combinazione di una tabella hash e una lista doppiamente collegata. La tabella hash fornisce accesso O(1) a qualsiasi nodo per chiave, mentre la lista doppiamente collegata consente di spostare un nodo in testa e rimuoverlo dalla coda in O(1). È fondamentale che la lista sia doppiamente collegata: ciò consente di scollegare un nodo dal centro della lista senza iterare su tutti gli elementi.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

Nell'implementazione, ogni nodo (Node) memorizza un valore e riferimenti ai nodi precedente e successivo. I nodi sentinella head e tail semplificano i casi limite — non è necessario verificare null durante l'inserimento e la rimozione. Il metodo get sposta il nodo trovato in testa, e put rimuove l'elemento in coda in caso di overflow. Un metodo separato removeKeyByValue trova la chiave nella tabella hash per riferimento al nodo e la rimuove.

Implementazione incorporata di LruCache in Android

L'SDK Android fornisce una classe LruCache pronta nel pacchetto android.util, che implementa l'algoritmo LRU utilizzando LinkedHashMap in modalità access-order. La classe è thread-safe, supporta il conteggio hit/miss e fornisce il callback entryRemoved per la pulizia delle risorse durante l'espulsione di un elemento. La dimensione della cache è impostata in unità arbitrarie (byte, numero di elementi) — basta sovrascrivere il metodo sizeOf.

LRU Cache vs FIFO e LIFO

Tutti e tre gli algoritmi — LRU, FIFO e LIFO — risolvono lo stesso problema: limitare il consumo di memoria espellendo gli elementi in caso di overflow. Tuttavia, utilizzano criteri fondamentalmente diversi per selezionare la vittima, il che determina la loro efficacia in diversi scenari.

FIFO espelle l'elemento più vecchio per tempo di inserimento, indipendentemente dalla frequenza di accesso. Questo può essere inefficiente se un elemento vecchio è ancora rilevante. LRU evita questo inconveniente considerando il pattern di accesso. LIFO espelle l'elemento aggiunto più recentemente — utile per scenari di annullamento, ma inadatto per il caching, poiché i nuovi dati sono spesso più necessari di quelli vecchi. LRU è considerato l'equilibrio ottimale tra complessità di implementazione e hit-ratio per la maggior parte delle applicazioni.

Esempi di codice LRU Cache

Consideriamo l'uso della classe incorporata LruCache dell'SDK Android per memorizzare nella cache le immagini scaricate. L'esempio mostra l'inizializzazione della cache a 1/8 della memoria disponibile dell'applicazione, che è la raccomandazione standard di Google per il caching delle immagini.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

Il metodo sizeOf restituisce la dimensione dell'elemento nelle stesse unità in cui è specificato cacheSize. Qui viene utilizzata la dimensione del Bitmap in kilobyte (rowBytes × height / 1024). Quando la somma dei sizeOf di tutti gli elementi supera cacheSize, LruCache espelle automaticamente i Bitmap meno recentemente usati. Il callback entryRemoved può essere utilizzato per chiamare bitmap.recycle() — liberando memoria prima dell'espulsione.

Implementazione di LRU Cache in Swift

iOS non ha una classe LRU Cache incorporata, ma è facile implementarla usando NSCache (che utilizza una politica di espulsione simile ma non documentata) o tramite un'implementazione personalizzata usando Dictionary + lista doppiamente collegata, come mostrato di seguito.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

In questa implementazione Swift, Node è una classe interna con campi value, next e prev. Il metodo moveToHead scollega un nodo dalla sua posizione corrente e lo inserisce in testa alla lista. In caso di overflow, la coda — l'elemento meno recentemente usato — viene rimossa. Per la produzione, si consiglia di aggiungere la sicurezza dei thread tramite NSLock o una coda DispatchQueue.