Perché l'invalidazione della cache è considerata difficile?

Presumo che vi riferiate alla citazione spesso ripetuta sulle "due cose difficili nell'informatica: l'invalidazione della cache e la denominazione delle cose". (A volte umoristicamente esteso come "invalidazione della cache, nominare le cose e gli errori off-by-one.")

Questo si applica sia nella programmazione che nell'hardware: è facile conservare una copia di qualcosa. È molto più difficile sapere quando lasciare andare quella copia, e invece recuperare di nuovo dall'elemento originale. Poiché è un problema generale, risponderò ad alto livello.

Generalmente, si hanno due ragioni per mettere in cache un pezzo di dati:

1. È relativamente costoso recuperare i dati la prima volta.
2. Si prevede di leggere gli stessi dati più volte, quindi c'è un beneficio nel mantenere i dati localmente per evitare di sostenere la spesa di recuperare i dati più di una volta.

Questo si applica alle cache a tutti i livelli, sia che si tratti di una cache hardware che conserva una copia della memoria esterna vicino alla CPU, o di un browser web che conserva una copia di un documento recuperato da un server web.

La cache è attraente perché permette di risparmiare tempo, eliminando il costo di leggere l'originale quando lo si rilegge più tardi. Ma cosa succede se il valore originale può cambiare? Come ci si assicura che ogni copia in cache nel sistema rifletta alla fine i dati aggiornati, senza incorrere in costi che superano il beneficio della cache? E, se i dati possono essere aggiornati da più attori nel sistema, come ci si assicura che tutti vedano una serie coerente di aggiornamenti?

Per esempio, supponiamo di avere una pagina web che potrebbe essere messa in cache da migliaia o milioni di browser web. Questo risparmia sia la latenza che la larghezza di banda: i browser recuperano una copia una volta, e non hanno bisogno di consultare nuovamente il server web. Ma cosa succede se la pagina sul server cambia? Non invierà un messaggio a migliaia o milioni di browser per dire loro di recuperarla di nuovo.

In questo esempio, i browser hanno invece bisogno di una politica per sapere quando ricontrollare il server per vedere se la pagina è cambiata. E la politica giusta per ogni dato URL sarà diversa a seconda degli aggiornamenti previsti, come avere una data di scadenza nella cache, inviare una richiesta più leggera "Ehi, è cambiato?" al server, e così via. La risposta giusta non è sempre ovvia, ed è facile azzeccare la "maggior parte delle volte" e trascurare una oscura modalità di fallimento.

Similmente per i filesystem di rete, i filesystem locali se i programmi hanno cache interne, i database con più processi che leggono il database, e così via.

Le cache di memoria hardware, anche se decisamente difficili, forse hanno vita più facile dei sistemi informatici distribuiti: Se tutti gli accessi ad una particolare memoria fisica passano attraverso un controller comune, allora almeno il controller comune ha la possibilità di essere in grado di informare tutte le cache sopra di esso di una scrittura in modo piuttosto tempestivo. Il sistema di memoria è almeno autonomo. Anche allora, avete ancora bisogno di assicurarvi che i messaggi di invalidazione vengano processati in un modo che assicuri che gli aggiornamenti della memoria siano coerenti per tutti i lettori, e farlo in modo efficiente è ancora difficile.

Senza addentrarci in tutti i possibili protocolli per l'invalidazione, questa è l'essenza del problema.