Invalidazione della cache - c'è una soluzione generale?

StackOverflow https://stackoverflow.com/questions/1188587

Domanda

  

"Ci sono solo due problemi difficili in informatica:. Invalidazione della cache e nominare le cose"

Phil Karlton

C'è una soluzione generale o metodo per invalidare una cache; di sapere quando una voce è stantio, così si sono garantiti per ottenere sempre nuovi dati?

Per esempio, si consideri una funzione getData() che ottiene i dati da un file. Si memorizza nella cache in base alla data dell'ultima modifica del file, che controlla ogni volta che viene chiamato.
Poi si aggiunge una seconda funzione transformData() che trasforma i dati, e memorizza nella cache il risultato per la prossima volta viene chiamata la funzione. E non è a conoscenza del file -? Come si fa ad aggiungere la dipendenza che se il file viene modificato, questa cache non è più valido

Si può chiamare getData() ogni volta che viene chiamato transformData() e confrontarlo con il valore che è stato utilizzato per costruire la cache, ma che potrebbe finire per essere molto costoso.

È stato utile?

Soluzione

Che cosa si sta parlando è la vita di dipendenza concatenamento, che una cosa dipende da un altro che può essere modificato al di fuori di esso di controllo.

Se si dispone di una funzione di idempotente da a, b a c dove, se a e b sono gli stessi quindi c è lo stesso, ma il costo del controllo b è alto si ha o:

  1. accettare che qualche volta si opera con fuori delle informazioni di data e non si controlla sempre b
  2. fare del tuo meglio per rendere il controllo b il più velocemente possibile

Non si può avere la botte piena e la moglie ubriaca ...

Se è possibile sovrapporre una cache aggiuntiva in base a sopra le righe, allora questo influenza il problema iniziale non un bit. Se si sceglie 1 allora si ha tutto ciò che ti sei dato la libertà e possono quindi memorizzare nella cache di più, ma deve ricordare di prendere in considerazione la validità del valore memorizzato nella cache di b. Se si è scelto 2 è comunque necessario controllare b ogni volta, ma può ripiegare sulla cache per a se b controlli fuori.

Se utilizzi questa cache è necessario considerare se hai violato le 'regole' del sistema a seguito del comportamento combinato.

Se si sa che è sempre a validità se b fa allora si può organizzare la cache in questo modo (pseudocodice): 

private map<b,map<a,c>> cache // 
private func realFunction    // (a,b) -> c

get(a, b) 
{
    c result;
    map<a,c> endCache;
    if (cache[b] expired or not present)
    {
        remove all b -> * entries in cache;   
        endCache = new map<a,c>();      
        add to cache b -> endCache;
    }
    else
    {
        endCache = cache[b];     
    }
    if (endCache[a] not present)     // important line
    {
        result = realFunction(a,b); 
        endCache[a] = result;
    }
    else   
    {
        result = endCache[a];
    }
    return result;
}

Ovviamente successiva stratificazione (diciamo x) è banale purché, in ogni fase della validità dell'ingresso appena aggiunto corrisponde alla a: rapporto b per x: b e x:. a

Tuttavia, è molto probabile che si potrebbe ottenere tre ingressi la cui validità era del tutto indipendente (o era ciclico), in modo che nessun stratificazione sarebbe possibile. Ciò significherebbe la linea marcata // importante avrebbe dovuto cambiare a

  

if (endCache [a] scaduto o non presente)

Altri suggerimenti

Il problema in invalidazione della cache è che i cambiamenti roba senza di noi lo sappia. Così, in alcuni casi, una soluzione è possibile se c'è qualche altra cosa che non sapeva nulla e ci può informare. Nell'esempio riportato, la funzione getData potrebbe agganciare nel file system, che non sa su tutte le modifiche ai file, indipendentemente da quale processo cambia il file, e questo componente, a sua volta potrebbe avvisare il componente che trasforma i dati.

Non credo che ci sia alcuna soluzione magica generale per rendere il problema andare via. Ma in molti casi pratici ci possono benissimo essere le opportunità per trasformare un approccio basata su "polling" in un "interrupt" -based uno, che può rendere il problema semplicemente andare via.

Se avete intenzione di getData () ogni volta che si fa il trasformare, allora hai eliminato l'intera prestazione della cache.

Per il vostro esempio, sembra che una soluzione sarebbe per quando si generano i dati trasformati, per archiviare anche il nome del file e la data dell'ultima modifica del file di dati è stato generato da (che già memorizzato questo in qualunque struttura di dati è stato restituito da getData (), quindi basta copiare quel disco nella struttura di dati restituito da transformData ()) e poi quando si chiama transformData () di nuovo, controllare la data dell'ultima modifica del file.

IMHO, funzionale programmazione reattiva (FRP) è in un certo senso un modo generico per risolvere invalidazione della cache.

Ecco perché: dati non aggiornati in FRP terminologia è chiamato problema tecnico . Uno degli obiettivi di FRP è quello di garantire l'assenza di difetti.

FRP è spiegato più in dettaglio in questo 'Essenza di FRP' parlare in questo SO rispondere .

Negli href="https://m.youtube.com/watch?v=CjEDmJMLEGE" i Cells rappresentano un oggetto in cache / Entità e Cell è rinfrescato se uno dei suoi dipendenza viene aggiornata.

FRP nasconde il codice impianto idraulico associato con il grafico dipendenza e fa in modo che non vi siano Cells aggiornati.

Un altro modo (diverso da FRP) che posso pensare è avvolgendo il valore calcolato (di tipo b) in una sorta di uno scrittore Monade Writer (Set (uuid)) b dove Set (uuid) (Haskell notazione) contiene tutti gli identificativi dei valori mutevoli su cui la calcolato valore b dipende. Quindi, uuid è una sorta di un identificatore univoco che identifica il valore mutevole / variabile (ad esempio una riga in un database) da cui dipende il b calcolata.

Combinate questa idea con combinatori che operano su questo tipo di scrittore Monade e che potrebbe portare ad una sorta di una soluzione generale invalidazione della cache se si utilizza solo questi combinatori per calcolare un nuovo b. Tali combinatori (dicono una versione speciale di filter) fa monadi scrittore e (uuid, a)-s come ingressi, dove a è un data / variabile mutabile, identificate dal uuid.

Quindi, ogni volta che si cambia il (uuid, a) dati "originale" (dicono i dati normalizzati in un database da cui è stata calcolata b) su cui il valore calcolato di tipo b dipende allora si può invalidare la cache che contiene b se processo di mutazione qualsiasi valore a in cui il valore b calcolato dipende, perché in base alla Set (uuid) nel Writer Monade si può dire quando questo accade.

Quindi, ogni volta processo di mutazione qualcosa con un dato uuid, è in onda questa mutazione a tutti i cache-s e invalidare i b valori che dipendono dal valore mutevole identificato con detto uuid perché la monade Writer in cui è avvolto il b può dire se che b dipende detto uuid oppure no.

Naturalmente, questo paga solo fuori se si leggono molto più spesso di quanto si scrive.

Un terzo, pratico, l'approccio è quello di utilizzare vista materializzata-s in banche dati e li usa come cache-es. Per quanto ne so hanno anche lo scopo di risolvere il problema invalidazione. Questo, naturalmente, limita le operazioni che collegano i dati mutabili ai dati derivati.

Sto lavorando su un approccio in questo momento sulla base di PostSharp e funzioni memoizing . Ho eseguito è passato il mio mentore, e lui è d'accordo che si tratta di una buona implementazione di caching in modo content-agnostico.

Ogni funzione può essere contrassegnato con un attributo che specifica il suo periodo di scadenza. Ogni funzione contrassegnata in questo modo è memoized e il risultato viene memorizzato nella cache, con un hash della chiamata di funzione e parametri utilizzati come chiave. Sto utilizzando Velocity per il back-end, che gestisce la distribuzione del dati della cache.

  

C'è una soluzione generale o un metodo per la creazione di una cache, per sapere quando una voce è stantio, così si sono garantiti per ottenere sempre nuovi dati?

No, perché tutti i dati sono diversi. Alcuni dati possono essere "stantio", dopo un minuto, un po 'dopo un'ora, e alcuni possono andare bene per giorni o mesi.

Per quanto riguarda il tuo esempio specifico, la soluzione più semplice è quella di avere un 'cache di controllo' funzione per i file, che voi chiamate sia da getData e transformData.

Non c'è una soluzione generale, ma:

  • È la cache può agire come un proxy (pull). Assumere la cache conosce timestamp dell'ultimo cambiamento origine, quando qualcuno chiamata getData(), la cache di chiedere l'origine per la sua timestamp di ultima modifica, se lo stesso, restituisce la cache, altrimenti si aggiorna il suo contenuto con la fonte di uno e restituisce il suo contenuto. (Una variante è il client di inviare direttamente il timestamp in merito alla richiesta, la fonte sarebbe tornato solo il contenuto se il suo timestamp è diverso.)

  • È comunque possibile utilizzare un processo di notifica (push), la cache di osservare la fonte, se la sorgente cambia, invia una notifica alla cache che viene poi contrassegnato come "sporco". Se qualcuno chiama getData() la cache verrà aggiornata per prima la sorgente, rimuovere il flag "sporco"; per poi tornare al suo contenuto.

La scelta in generale dipende da:

  • La frequenza: molte chiamate su getData() preferirebbero una spinta in modo da evitare la sorgente da inondata da una funzione getTimestamp
  • L'accesso alla fonte: Stai possedere il modello di origine? In caso contrario, è probabile che non è possibile aggiungere qualsiasi processo di notifica.

Nota: Come utilizzare il timestamp è il modo tradizionale proxy HTTP stanno lavorando, un altro approccio è la condivisione di un hash del contenuto memorizzato. L'unico modo che conosco per 2 soggetti per ottenere aggiornati insieme sono o si (pull) chiamo o mi chiami ... (push) questo è tutto.

La cache è difficile perché è necessario prendere in considerazione: 1) la cache è più nodi, hanno bisogno del consenso per loro 2) Tempo di invalidazione 3) race condition quando multple get / set accadere

Questa è una buona lettura: https://www.confluent.io / / blog girare-la-Database-inside-out-con-apache-samza /

Forse algoritmi della cache-ignaro sarebbe la più generale (o almeno, meno configurazione hardware dipendente), dal momento che useranno la cache più veloce prima e andare avanti da lì. Ecco una conferenza MIT su di esso: Cache Incurante Algoritmi

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top