Come implementare una cache utilizzata più di recente

Question

Quale sarebbe il modo migliore per implementare una cache di oggetti utilizzata più di recente?

Ecco i requisiti e le restrizioni ...

• Gli oggetti vengono memorizzati come coppie chiave/valore Oggetto/oggetto, in modo l'interfaccia sarebbe un po 'come Hashtable ricevere/messo
• Una chiamata a' ottenere 'dovrebbe contrassegnare quell'oggetto come l'ultimo utilizzato.
• In qualsiasi momento, l'oggetto utilizzato meno di recente può essere eliminato dalla cache.
• Le ricerche e gli spurghi devono essere veloci (come in Hashtable veloce)
• Il numero di oggetti può essere grande, quindi le ricerche nell'elenco non sono sufficienti.
• L'implementazione deve essere eseguita utilizzando JavaME, quindi c'è poco spazio per l'utilizzo di codice di terze parti o classi di librerie pulite dalle librerie Java standard. Per questo motivo cerco di più le risposte algoritmiche piuttosto che le raccomandazioni di soluzioni off-the-peg.

Answer 1

Java Collezioni forniscono LinkedHashMap fuori dalla scatola, che è particolarmente adatto alla costruzione di cache. Probabilmente non hanno questo in Java ME, ma si può afferrare il codice sorgente qui:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

Se non si può semplicemente copia-incolla, guardandolo dovrebbe cominciare attuare uno per inclusione nella tua app mobile. L'idea di base è solo quella di includere una lista collegata attraverso gli elementi della mappa. Se mantieni questo aggiornamento ogni volta che qualcuno fa o ottiene, puoi monitorare in modo efficiente l'ordine di accesso e utilizzare l'ordine.

I documenti contengono istruzioni per la creazione di una cache MRU sostituendo il metodo .Tutto ciò che dovete fare è fare una classe che estende LinkedHashMap e l'override del metodo in questo modo:

private static final int MAX_ENTRIES = 100; 

protected boolean removeEldestEntry(Map.Entry eldest) { 
    return size() > MAX_ENTRIES; 
} 

C'è anche un constructor che permette di specificare se si desidera che la classe per memorizzare le cose in ordine di inserimento o per l'uso , così hai un po 'di flessibilità per la vostra politica di sfratto, troppo:

public LinkedHashMap(int initialCapacity, 
        float loadFactor, 
        boolean accessOrder) 

Passo vero per l'uso su ordinazione e falsa per ordine di inserimento.

Answer 2

Perché implementare qualcosa già implementato? Utilizzare Ehcache.

Tuttavia, se librerie di terze parti sono totalmente fuori questione, penso che si sta cercando di implementare una struttura dati che sembra qualcosa di simile:

• è fondamentalmente un HashMap (si estende HashMap<Object, Object> se lo sarà)
• Ogni valore nella mappa punta a un oggetto in un elenco ordinato, in base al quale è più utilizzato.
• oggetti utilizzati di recente vengono aggiunti alla testa della lista - O(1)
• spurgo meno recentemente utilizzato mezzi troncando il fine della lista - O(1)
• dà ancora di mappare le ricerche, ma ancora mantiene gli elementi usati di recente prima ...

Answer 3

Un altro approccio può essere quello di dare un'occhiata alla sezione 5.6 in Java Concurrency in Practice di Brian Goetz: "Creazione di una cache dei risultati efficiente e scalabile". Dai un'occhiata al Memoizer, anche se potresti doverlo personalizzare per i tuoi scopi.

Per inciso, ciò che non riesco a capire è perché Java non abbia una ConcurrentLinkedHashMap pronta all'uso. Questa struttura di dati sarebbe molto utile per costruire una cache.

Answer 4

A ConcurrentLinkedHashMap è difficile da costruire, a causa dei requisiti di blocco. Una LinkedHashMap con un blocco è semplice, ma non sempre performante. Una versione concorrente tenterebbe di ridurre la quantità di blocco, sia attraverso la divisione del blocco che idealmente rendendo le operazioni CAS per rendere il blocco molto economico. Se le operazioni CAS diventano sempre costose, può essere utile anche la suddivisione in bucket. Dato che una LRU richiede scritture per ogni operazione di accesso e utilizza una lista doppiamente collegata, è molto difficile da implementare con le semplici operazioni CAS. L'ho provato, ma ho bisogno di continuare a maturare il mio algoritmo. Se cerchi ConcurrentLinkedHashMap, vedrai la mia pagina di progetto ...

Se Java ME non supporta le operazioni CAS, che mi aspetto essere vero, la sincronizzazione di base è tutto ciò che puoi fare. Questo è probabilmente abbastanza buono con un LHM, dato che ho visto solo problemi di prestazioni con un numero elevato di thread sul lato server. Quindi +1 alle risposte sopra.