Nella progettazione di sistemi sotto carico, decidere quale dato buttare via quando lo spazio finisce conta quanto la scelta della tecnologia di cache. Ma la domanda «qual è la politica migliore» non ha risposta: ogni politica è una scommessa su come verranno letti i dati, e la politica giusta è quella la cui scommessa corrisponde al vostro traffico.
Le politiche, e la scommessa di ciascuna#
| Politica | Scommette che… | Costo | Fallisce quando |
|---|---|---|---|
| LRU Least Recently Used | ciò che è servito ora servirà ancora | O(1), pochi metadati | una scansione sequenziale la azzera |
| LFU Least Frequently Used | la popolarità è stabile nel tempo | un contatore per chiave | i gusti cambiano e la storia pesa troppo |
| MRU Most Recently Used | ciò che è appena servito non servirà più | O(1) | quasi sempre — è per casi specifici |
| TTL | il dato ha una freschezza dichiarabile | una scadenza per chiave | usata da sola: non limita la memoria |
| FIFO | l'età conta più dell'uso | minimo | con qualunque località di accesso |
| Random | i metadati costano più di quanto rendano | zero | raramente, ed è la sorpresa |
| Due livelli | esistono un «caldo» piccolo e un «tiepido» grande | due sistemi da gestire | l'incoerenza fra livelli non è tollerabile |
LRU, e perché quasi sempre basta#
// LRU in O(1): mappa hash per la ricerca, lista doppiamente concatenata// per l'ordine. In JavaScript la Map è già ordinata per inserimento,// quindi la lista è gratis — basta cancellare e reinserire.class LRU { constructor(capienza) { this.capienza = capienza; this.m = new Map(); } get(k) { if (!this.m.has(k)) return undefined; const v = this.m.get(k); this.m.delete(k); // togliere e rimettere sposta la chiave this.m.set(k, v); // in fondo: è il "recently used" return v; } set(k, v) { if (this.m.has(k)) this.m.delete(k); else if (this.m.size >= this.capienza) { // il primo elemento dell'iteratore è il meno recente this.m.delete(this.m.keys().next().value); } this.m.set(k, v); }}In JavaScript l'implementazione è più corta che altrove perché Map mantiene l'ordine di inserimento: cancellare e reinserire una chiave la sposta in fondo, e il primo elemento dell'iteratore è per costruzione il meno recente. Nessuna lista concatenata da gestire a mano.
LRU è il default sensato perché la sua scommessa — la località temporale — è vera nella stragrande maggioranza delle applicazioni. Il profilo di una sessione utente, il listino consultato da tutti, l'articolo appena pubblicato: quello che serve adesso, tra un minuto servirà ancora.
Il caso in cui LRU crolla#
// Il caso patologico di LRU, e il motivo per cui i database non la usano// da sola: una scansione sequenziale più grande della cache la azzera.//// cache: 3 posti scansione: A B C D A B C D ...//// A → miss, [A]// B → miss, [A B]// C → miss, [A B C]// D → miss, evict A → [B C D]// A → miss, evict B → [C D A] ← A era appena stato sfrattato// B → miss, evict C → [D A B]// ...// tasso di successo: 0%. Peggio: la scansione ha buttato fuori i dati// caldi che servivano al resto dell'applicazione.//// È il motivo per cui un job notturno di esportazione può far crollare// i tempi di risposta del sito la mattina dopo: non ha consumato CPU,// ha svuotato la cache.Questo non è un caso teorico ed è il motivo per cui i motori di database non usano LRU pura. Uno scenario che si ripete: un job notturno esporta l'intero catalogo e per farlo lo legge tutto, una riga alla volta. Nessuno di quei dati verrà riletto. Ma passando dalla cache li ha promossi tutti, sfrattando i dati che davvero servivano — e la mattina dopo il sito è lento per un'ora, mentre la cache si riscalda.
LFU e il peso della storia#
// LFU tiene un contatore per chiave. Il difetto è il "peso della storia":// una chiave popolarissima nel 2024 resta in cache nel 2026.//// La correzione standard è l'invecchiamento: periodicamente si dimezzano// tutti i contatori. Costa una passata, e trasforma "quante volte in// assoluto" in "quante volte di recente".function invecchia(contatori) { for (const [k, n] of contatori) { const nuovo = n >> 1; // dimezza if (nuovo === 0) contatori.delete(k); // e dimentica del tutto else contatori.set(k, nuovo); }}// Redis usa una variante più raffinata (LFU con contatore logaritmico// e decadimento temporale) proprio per non pagare il costo di un// contatore esatto per chiave.Senza invecchiamento, LFU è un archivio di popolarità storica: una chiave che ha accumulato centomila accessi durante una campagna di due anni fa resta in cache più a lungo di una che ne ha ricevuti mille questa settimana. Il dimezzamento periodico dei contatori — che costa una passata e si fa in un momento di calma — converte «quante volte in assoluto» in «quante volte di recente», che è quello che si voleva misurare fin dall'inizio.
TTL: la domanda è chi se ne accorge#
// TTL: la domanda non è "come scade" ma "CHI se ne accorge".// Tre strategie, con costi molto diversi.// 1. Pigra: si controlla alla lettura. Costo zero a riposo, ma le chiavi// scadute occupano memoria finché qualcuno non le chiede.get(k) { const e = this.m.get(k); if (!e) return undefined; if (e.scadenza <= Date.now()) { this.m.delete(k); return undefined; } return e.valore;}// 2. Campionaria: ogni tanto si estraggono N chiavi a caso e si buttano// le scadute. È quello che fa Redis: costo prevedibile, memoria che// resta entro una percentuale nota di spreco.function pulizia(m, campione = 20) { const chiavi = [...m.keys()]; let scadute = 0; for (let i = 0; i < campione && chiavi.length; i++) { const k = chiavi[(Math.random() * chiavi.length) | 0]; if (m.get(k).scadenza <= Date.now()) { m.delete(k); scadute++; } } // se più di un quarto del campione era scaduto, probabilmente ce ne // sono molte altre: si ripete subito invece di aspettare il giro dopo if (scadute > campione / 4) pulizia(m, campione);}// 3. Attiva: un timer per chiave. Precisa e inutilizzabile su volumi// veri — un milione di chiavi significa un milione di timer.La strategia campionaria è quella che usa Redis, ed è un buon esempio di ingegneria pragmatica: non garantisce di rimuovere ogni chiave scaduta subito, garantisce che la percentuale di chiavi scadute ancora in memoria resti sotto una soglia nota. È una garanzia più debole e infinitamente più economica di un timer per chiave.
Il problema vero: il cache stampede#
Nella pratica, la politica di eviction raramente è ciò che vi mette in difficoltà. Quello che vi mette in difficoltà è questo: una chiave molto richiesta scade, e nell'istante successivo mille richieste la trovano assente. Mille miss simultanei, mille query identiche allo stesso database.
// Il problema che si presenta sempre in produzione e mai in sviluppo:// mille richieste chiedono la stessa chiave nell'istante in cui scade.// Mille miss, mille query identiche, database in ginocchio.// ✓ Difesa 1 — coalescenza: la prima richiesta calcola, le altre// aspettano LA STESSA promise. Dieci righe, risolve il 90% dei casi.const inVolo = new Map();async function conCache(chiave, calcola, ttl) { const v = cache.get(chiave); if (v !== undefined) return v; if (inVolo.has(chiave)) return inVolo.get(chiave); // ← ci pensa già un altro const p = calcola() .then(r => { cache.set(chiave, r, ttl); return r; }) .finally(() => inVolo.delete(chiave)); inVolo.set(chiave, p); return p;}La coalescenza è la difesa a miglior rapporto costo/beneficio dell'intera categoria: dieci righe, e le richieste concorrenti sulla stessa chiave diventano una sola. Le altre attendono la medesima promise già in volo.
// ✓ Difesa 2 — jitter: senza, mille chiavi scritte nello stesso momento// (dopo un riavvio, dopo un deploy) scadono nello stesso momento.// Il gregge non si forma su una chiave: si forma su tutte insieme.function ttlConJitter(base, percentuale = 0.2) { const delta = base * percentuale; return base + (Math.random() * 2 - 1) * delta; // ±20%}// ✓ Difesa 3 — ricalcolo anticipato probabilistico: più ci si avvicina// alla scadenza, più è probabile che UNA richiesta decida di rinfrescare// in anticipo, mentre le altre continuano a leggere il valore ancora// valido. Nessuno aspetta mai, e il gregge non si forma per costruzione.function scadutoInAnticipo(voce, beta = 1) { const delta = voce.costoDiCalcolo; // quanto è costato produrlo const scarto = delta * beta * Math.log(Math.random()); return Date.now() - scarto >= voce.scadenza;}Il jitter chiude un caso che la coalescenza non tocca: dopo un riavvio o un deploy, migliaia di chiavi vengono scritte nello stesso secondo e quindi scadranno nello stesso secondo. Il gregge non si forma su una chiave — si forma su tutte insieme, ed è un picco molto più difficile da assorbire.
Il ricalcolo anticipato probabilistico è la soluzione più elegante delle tre: man mano che ci si avvicina alla scadenza cresce la probabilità che una richiesta decida di rinfrescare il valore in anticipo, mentre tutte le altre continuano a leggere quello ancora valido. Nessuno aspetta mai, e il gregge non si forma per costruzione.
Due livelli#
// Due livelli: memoria del processo (nanosecondi, non condivisa) sopra// una cache di rete (frazioni di millisecondo, condivisa).async function leggi(k) { const l1 = memoria.get(k); // ~50 ns if (l1 !== undefined) return l1; const l2 = await redis.get(k); // ~200 µs, ma condiviso if (l2 !== null) { memoria.set(k, l2, TTL_L1); // promozione return l2; } const v = await origine(k); // ~20 ms await redis.set(k, v, 'PX', TTL_L2); memoria.set(k, v, TTL_L1); return v;}// La trappola del primo livello: con N istanze ci sono N copie che si// invalidano in momenti diversi. Il TTL di L1 va tenuto BREVE (secondi,// non minuti): è la finestra massima di incoerenza fra due utenti serviti// da repliche diverse. Se quella finestra non è accettabile, il primo// livello va tolto o va aggiunta un'invalidazione via pub/sub.Il rapporto fra i tempi giustifica da solo l'architettura: una lettura dalla memoria del processo costa nanosecondi, una da Redis centinaia di microsecondi, una dall'origine decine di millisecondi. Il primo livello assorbe le chiavi caldissime senza nemmeno toccare la rete.
Il prezzo, che va messo in conto esplicitamente, è la coerenza. Con tre repliche esistono tre copie del primo livello, che scadono in momenti diversi: due utenti serviti da repliche diverse possono vedere dati diversi per tutta la durata del TTL locale. Se quella finestra è accettabile, il primo livello va tenuto a pochi secondi; se non lo è, va tolto — oppure serve un canale di invalidazione, con tutta la complessità che comporta.
Prima di scegliere, misurare#
# Il numero che conta non è "quante chiavi ho": è il tasso di successo.# Sotto l'80% la cache sta pagando memoria senza restituire granché.redis-cli info stats | grep keyspacekeyspace_hits:8412337keyspace_misses:412998# 8412337 / (8412337 + 412998) = 95,3% di successoredis-cli info memory | grep -E 'used_memory_human|maxmemory_policy|evicted'used_memory_human:1.84Gmaxmemory_policy:allkeys-lruevicted_keys:0# evicted_keys a 0 con maxmemory impostato significa che la cache non# e' mai piena: la politica di eviction, qualunque sia, non e' mai# entrata in funzione. Si sta discutendo di un problema che non c'e'.È la parte che salta quasi sempre, e produce discussioni lunghe su un problema che non esiste. I due numeri da guardare sono il tasso di successo — sotto l'80% la cache costa memoria senza restituire granché, e vale la pena chiedersi se le chiavi siano troppo granulari o i TTL troppo corti — e le chiavi sfrattate: se sono zero, la cache non si è mai riempita e state ottimizzando una politica che non è mai entrata in funzione.
| Situazione | Politica | Perché |
|---|---|---|
| Cache HTTP, sessioni, oggetti applicativi | allkeys-lru | la località temporale è quasi sempre vera |
| Catalogo con pochi articoli molto richiesti | allkeys-lfu | la popolarità è stabile e vale la pena ricordarla |
| Solo chiavi con scadenza, memoria abbondante | volatile-ttl | sfratta prima ciò che sarebbe scaduto comunque |
| Dati che non devono sparire (code, contatori) | noeviction | meglio un errore in scrittura che una perdita silenziosa |
| Scansioni e job batch | escluderli dalla cache | non è un problema di politica, è di percorso |
| Dataset molto più grande della RAM | due livelli | il caldo in memoria, il tiepido su un livello più capiente |
La sintesi: una cache non è un contenitore, è una previsione. La politica di eviction dichiara su cosa si scommette, i TTL dichiarano quanto si è disposti a mentire sulla freschezza, e la protezione dal gregge dichiara cosa succede quando la previsione sbaglia — che è il momento in cui si scopre com'è fatto davvero il sistema.