Memoizzazione in Go: Caching di Computazioni Costose nel Modo Corretto

Indice dei contenuti

La memoizzazione e la tecnica di ottimizzazione che consiste nel fare il caching del valore restituito da una funzione pura, in modo che le chiamate ripetute con gli stessi input saltino completamente la computazione. Si applica ogni volta che una funzione e costosa, deterministica e chiamata piu volte con gli stessi argomenti. Fatta correttamente in Go richiede un mutex, e nel codice moderno un wrapper generico la rende riutilizzabile su piu tipi.

La memoizzazione viene spesso introdotta con Fibonacci perche l’esplosione ricorsiva e facile da visualizzare. Ma le applicazioni reali in produzione sono altrove: controlli dei permessi che accedono a un database, lookup di configurazione su rete, o costose computazioni crittografiche. Questo post copre il quadro completo: dall’implementazione di base alla prevenzione delle data race, ai wrapper generici e all’invalidazione con time-to-live (TTL).

La baseline con Fibonacci
#

Il classico Fibonacci ricorsivo ha complessita temporale esponenziale. Ricalcola fib(n-2) da zero ogni volta, anche se ha gia calcolato quel valore poco prima.

fib_naive.go
// fib ha complessita O(2^n). Chiamare fib(40) esegue ~2 miliardi di chiamate.
func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

Una semplice cache con mappa elimina il lavoro ridondante:

fib_memo.go
var fibCache = make(map[int]int)

func fib(n int) int {
    if n <= 1 {
        return n
    }
    if v, ok := fibCache[n]; ok {
        return v
    }
    result := fib(n-1) + fib(n-2)
    fibCache[n] = result
    return result
}

La complessita temporale scende a O(n). Il problema e che questo codice ha una data race.

Il problema della data race
#

La mappa globale fibCache viene letta e scritta da ogni chiamata a fib. In un programma sequenziale questo funziona. In qualsiasi programma in cui fib viene chiamata da piu goroutine in modo concorrente, e un comportamento indefinito. La mappa di Go non e sicura per l’accesso concorrente.

Esegui il race detector e la vedrai immediatamente:

go test -race ./...

La soluzione e un sync.RWMutex. Le letture acquisiscono il read lock (piu lettori simultanei consentiti). Le scritture acquisiscono il write lock esclusivo.

fib_safe.go
package fib

import "sync"

type memoFib struct {
    mu    sync.RWMutex
    cache map[int]int
}

func newMemoFib() *memoFib {
    return &memoFib{cache: make(map[int]int)}
}

func (m *memoFib) compute(n int) int {
    if n <= 1 {
        return n
    }

    m.mu.RLock()
    if v, ok := m.cache[n]; ok {
        m.mu.RUnlock()
        return v
    }
    m.mu.RUnlock()

    // Calcola senza il lock (questo e sicuro perche fib e pura).
    result := m.compute(n-1) + m.compute(n-2)

    m.mu.Lock()
    m.cache[n] = result
    m.mu.Unlock()

    return result
}

Avviso

Non tenere mai un mutex durante una computazione costosa. Nell’esempio sopra, il lock viene rilasciato prima delle chiamate ricorsive e riacquisito solo per la scrittura. Tenere il write lock durante la ricorsione causerebbe un deadlock perche le chiamate annidate cercherebbero di acquisire lo stesso lock.

Un’alternativa per il caso a singolo risultato e sync.Map, ottimizzata per workload read-heavy ma con un’API meno ergonomica e prestazioni peggiori quando le scritture sono frequenti.

Memoizzazione generica (Go 1.18+)
#

Scrivere una nuova struct memoizzata per ogni tipo di funzione e ripetitivo. Con i generics di Go puoi scrivere un unico wrapper riutilizzabile:

memo/memo.go
package memo

import "sync"

// Cache is a thread-safe memoization cache for a function of type func(K) (V, error).
type Cache[K comparable, V any] struct {
    mu    sync.Mutex
    cache map[K]result[V]
    fn    func(K) (V, error)
}

type result[V any] struct {
    value V
    err   error
}

// New creates a Cache wrapping fn. Calls to Get will invoke fn at most once per key.
func New[K comparable, V any](fn func(K) (V, error)) *Cache[K, V] {
    return &Cache[K, V]{
        cache: make(map[K]result[V]),
        fn:    fn,
    }
}

// Get returns the memoized result for key, calling fn(key) if needed.
func (c *Cache[K, V]) Get(key K) (V, error) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if r, ok := c.cache[key]; ok {
        return r.value, r.err
    }

    // Rilascia il lock durante la chiamata costosa.
    // Usa singleflight in produzione per la deduplication sotto carico concorrente.
    c.mu.Unlock()
    v, err := c.fn(key)
    c.mu.Lock()

    c.cache[key] = result[V]{value: v, err: err}
    return v, err
}

L’utilizzo e pulito e type-safe:

usage example
fetchPrice := memo.New(func(ticker string) (float64, error) {
    return marketAPI.GetPrice(ticker)
})

price, err := fetchPrice.Get("AAPL")

Nota

Il Cache generico sopra usa un singolo mutex e sblocca durante la chiamata alla funzione per evitare di tenere il lock durante I/O. Sotto carico concorrente molto alto per la stessa chiave, due goroutine potrebbero entrambe chiamare fn(key) prima che una delle due memorizzi il risultato. Per vera deduplication usa golang.org/x/sync/singleflight.

Caso d’uso reale: chiamata API con TTL
#

Memoizzare una chiamata API per sempre e raramente sicuro. Configurazione, permessi e feature flag cambiano. Hai bisogno di invalidazione basata sul tempo.

memo/ttl_cache.go
package memo

import (
    "sync"
    "time"
)

type entry[V any] struct {
    value     V
    err       error
    expiresAt time.Time
}

// TTLCache memoizes function results for a fixed duration.
type TTLCache[K comparable, V any] struct {
    mu    sync.Mutex
    cache map[K]entry[V]
    fn    func(K) (V, error)
    ttl   time.Duration
}

func NewTTL[K comparable, V any](fn func(K) (V, error), ttl time.Duration) *TTLCache[K, V] {
    return &TTLCache[K, V]{
        cache: make(map[K]entry[V]),
        fn:    fn,
        ttl:   ttl,
    }
}

func (c *TTLCache[K, V]) Get(key K) (V, error) {
    c.mu.Lock()
    if e, ok := c.cache[key]; ok && time.Now().Before(e.expiresAt) {
        c.mu.Unlock()
        return e.value, e.err
    }
    c.mu.Unlock()

    v, err := c.fn(key)

    c.mu.Lock()
    c.cache[key] = entry[V]{
        value:     v,
        err:       err,
        expiresAt: time.Now().Add(c.ttl),
    }
    c.mu.Unlock()

    return v, err
}

Un controllo dei permessi che altrimenti colpirebbe il database ad ogni richiesta ora lo colpisce al massimo una volta al minuto:

permission service
var permCache = memo.NewTTL(func(userID string) ([]string, error) {
    return db.GetUserPermissions(context.Background(), userID)
}, time.Minute)

func hasPermission(userID, action string) (bool, error) {
    perms, err := permCache.Get(userID)
    if err != nil {
        return false, err
    }
    return slices.Contains(perms, action), nil
}

Quando NON memoizzare
#

Funzioni con effetti collaterali

La memoizzazione salta il corpo della funzione su cache hit. Se la funzione invia un’email, scrive su un database o incrementa un contatore, quegli effetti collaterali non avverranno nelle chiamate ripetute. Memoizza solo funzioni pure o funzioni il cui unico effetto osservabile e il loro valore di ritorno.

Funzioni con input grandi o illimitati

Fare il caching di ogni set di input unico per una funzione che accetta input stringa arbitrario fara crescere la cache senza limiti. O limita la dimensione della cache con una politica di eviction LRU o aggiungi l’invalidazione TTL. La libreria standard non ha un LRU built-in; usa golang.org/x/exp/cache o un’implementazione di terze parti ben mantenuta.

Funzioni gia veloci di per se

La memoizzazione introduce un’acquisizione del mutex e un lookup nella mappa ad ogni chiamata. Per una funzione che gia si completa in nanosecondi, questo overhead puo superare i risparmi. Esegui un benchmark prima e dopo.

Mutazione concorrente del valore cached

Se il valore cached e un puntatore a una struct che i chiamanti modificano dopo averla ricevuta, due chiamanti che condividono lo stesso puntatore cached vedranno le mutazioni dell’altro. Fai il cache di valori immutabili (stringhe, interi, copie di struct) o restituisci una deep copy.

Benchmark
#

Ecco un benchmark che quantifica il miglioramento delle prestazioni dalla memoizzazione su Fibonacci:

fib_bench_test.go
package fib_test

import (
    "testing"
    "github.com/yourorg/fib"
)

func BenchmarkFibNaive(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fib.Naive(30)
    }
}

func BenchmarkFibMemo(b *testing.B) {
    m := fib.NewMemo()
    // Riscalda la cache prima di misurare.
    m.Compute(30)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        m.Compute(30)
    }
}

Output di esempio:

BenchmarkFibNaive-10    1000    1,832,455 ns/op    0 B/op    0 allocs/op
BenchmarkFibMemo-10     1000000000    0.87 ns/op   0 B/op    0 allocs/op

La versione memoizzata e circa due milioni di volte piu veloce per fib(30). La differenza cresce esponenzialmente con n.

Nota

Memoizzazione vs caching: questi termini vengono spesso usati in modo intercambiabile ma hanno una distinzione precisa. La memoizzazione e un’ottimizzazione specifica per le funzioni pure: dati gli stessi input, produce sempre lo stesso output, quindi fai il cache. Il caching e il concetto piu ampio di memorizzare dati calcolati o recuperati per evitare di ripetere lavoro costoso. Il caching include politiche di eviction (LRU, LFU), TTL, segnali di invalidazione e layer distribuiti. Tutta la memoizzazione e caching, ma la maggior parte delle cache di produzione non e memoizzazione.

Se vuoi approfondire questi argomenti, offro sessioni di coaching 1:1 per ingegneri che lavorano su integrazione AI, architetture cloud e platform engineering. Prenota una sessione (50 EUR / 60 min) o scrivimi a manuel.fedele+website@gmail.com.

La baseline con Fibonacci#

Il problema della data race#

Memoizzazione generica (Go 1.18+)#

Caso d’uso reale: chiamata API con TTL#

Quando NON memoizzare#

Benchmark#

Articoli correlati