Concorrenza alta frequente per la cache

Question

Sto imparando il caching e ho una domanda sulla concorrenza della cache.

Come noto, il caching di LRU è implementato con una doppia lista collegata + una tabella hash. In che modo la cache LRU gestisce una concorrenza frequente? Nota che entrambi ricevono i dati dalla cache e mettono i dati nella cache aggiornano la lista collegata e la tabella hash così la cache viene continuamente modificata.

Se utilizziamo il blocco mutex per thread-safe, la velocità non verrà rallentata se la cache viene visitata da una grande quantità di persone? Se non usiamo il lucchetto, quali tecniche vengono utilizzate? Grazie in anticipo.

Answer 1

Le cache LRU tradizionali non sono progettate per una concorrenza elevata a causa dell'hardware limitato e che la penalità per colpire è molto più piccola della penalità di mancato recapito (ad esempio, la ricerca del database). Per la maggior parte delle applicazioni, il blocco della cache è accettabile se viene utilizzato solo per aggiornare la struttura sottostante (non calcolare il valore in caso di errore). Tecniche semplici come segmentare la politica di LRU erano solitamente abbastanza buone quando i lock venivano contesi.

Il modo per creare una scala cache LRU è di evitare l'aggiornamento della politica su ogni accesso. L'osservazione critica da fare è che l'utente della cache non si preoccupa di cosa sia l'ordinamento LRU corrente. L'unica preoccupazione del chiamante è che la cache mantenga una dimensione di soglia e un alto tasso di successo. Ciò apre la porta alle ottimizzazioni evitando di mutare la politica di LRU su ogni lettura.

L'approccio adottato da memcached consiste nello scartare le letture successive all'interno di una finestra temporale, ad es. 1 secondo. Ci si aspetta che la cache sia molto grande quindi c'è una possibilità molto bassa di sfrattare un candidato povero con questa LRU più semplice.

L'approccio adottato da ConcurrentLinkedHashMap (CLHM) e successivamente Guava's Cache, consiste nel registrare l'accesso in un buffer. Questo buffer viene svuotato sotto il blocco della LRU e utilizzando uno try-lock non è necessario bloccare altre operazioni. CLHM utilizza più buffer ad anello che sono lossy se la cache non riesce a tenere il passo, poiché la perdita di eventi è preferibile a prestazioni degradate.

L'approccio adottato da Ehcache e redis è una politica LRU probabilistica. Una lettura aggiorna il timestamp della voce e una scrittura itera la cache per ottenere un campione casuale. La voce più vecchia è sfrattata da quel campione. Se il campione è veloce da costruire e la cache è grande, la voce espulsa è probabilmente un buon candidato.

Probabilmente ci sono altre tecniche e, naturalmente, politiche LRU pseudo (come CLOCK) che offrono una maggiore concorrenza a tassi di successo inferiori.