Come implementeresti una cache LRU in Java?
https://stackoverflow.com/questions/221525
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Per favore, non dire EHCache o OSCache, ecc. Supponi ai fini di questa domanda che voglio implementare il mio usando solo l'SDK (imparando facendo). Dato che la cache verrà utilizzata in un ambiente multithread, quali strutture di dati useresti? Ne ho già implementato uno utilizzando LinkedHashMap e Collections # synchronizedMap , ma sono curioso di sapere se una qualsiasi delle nuove raccolte simultanee sarebbe candidati migliori.
AGGIORNAMENTO: stavo solo leggendo il l'ultimo di Yegge quando ho trovato questo nugget:
Se hai bisogno di un accesso a tempo costante e desideri mantenere l'ordine di inserimento, non puoi fare di meglio di una LinkedHashMap, una struttura di dati davvero meravigliosa. L'unico modo in cui potrebbe essere più meraviglioso è se ci fosse una versione concorrente. Ma ahimè.
Stavo pensando quasi esattamente la stessa cosa prima di procedere con l'implementazione di LinkedHashMap + Collections # synchronizedMap che ho menzionato sopra. Bello sapere che non avevo appena trascurato qualcosa.
Sulla base delle risposte finora, sembra che la mia scommessa migliore per un LRU altamente concorrente sarebbe quella di estendere ConcurrentHashMap usando parte della stessa logica usata da LinkedHashMap .
Soluzione 3
Se lo facessi nuovamente da zero oggi, userei Guava's CacheBuilder .
Altri suggerimenti
Mi piacciono molti di questi suggerimenti, ma per ora penso che rimarrò con LinkedHashMap + Collections.synchronizedMap . Se lo rivedrò in futuro, probabilmente lavorerò sull'estensione di ConcurrentHashMap nello stesso modo in cui LinkedHashMap estende HashMap .
UPDATE:
Su richiesta, ecco l'essenza della mia attuale implementazione.
private class LruCache<A, B> extends LinkedHashMap<A, B> {
private final int maxEntries;
public LruCache(final int maxEntries) {
super(maxEntries + 1, 1.0f, true);
this.maxEntries = maxEntries;
}
/**
* Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
* created.
*
* <p>
* This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
* <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
* <code>LinkedHashMap</code>.
* </p>
*
* @param eldest
* the <code>Entry</code> in question; this implementation doesn't care what it is, since the
* implementation is only dependent on the size of the cache
* @return <tt>true</tt> if the oldest
* @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
*/
@Override
protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
return super.size() > maxEntries;
}
}
Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));
O utilizzare questa struttura di dati di Apache Commons:
Questo è il secondo round.
Il primo round è stato quello che mi è venuto in mente, poi ho riletto i commenti con il dominio un po 'più radicato nella mia testa.
Quindi ecco la versione più semplice con un unit test che mostra che funziona in base ad alcune altre versioni.
Prima la versione non simultanea:
import java.util.LinkedHashMap;
import java.util.Map;
public class LruSimpleCache<K, V> implements LruCache <K, V>{
Map<K, V> map = new LinkedHashMap ( );
public LruSimpleCache (final int limit) {
map = new LinkedHashMap <K, V> (16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
return super.size() > limit;
}
};
}
@Override
public void put ( K key, V value ) {
map.put ( key, value );
}
@Override
public V get ( K key ) {
return map.get(key);
}
//For testing only
@Override
public V getSilent ( K key ) {
V value = map.get ( key );
if (value!=null) {
map.remove ( key );
map.put(key, value);
}
return value;
}
@Override
public void remove ( K key ) {
map.remove ( key );
}
@Override
public int size () {
return map.size ();
}
public String toString() {
return map.toString ();
}
}
Il flag vero seguirà l'accesso di get e put. Vedi JavaDocs. RemoveEdelstEntry senza il vero flag per il costruttore implementerebbe solo una cache FIFO (vedere le note seguenti su FIFO e removeEldestEntry).
Ecco il test che dimostra che funziona come una cache LRU:
public class LruSimpleTest {
@Test
public void test () {
LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
cache.put ( 4, 4 );
cache.put ( 5, 5 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == 4 || die ();
ok |= cache.getSilent ( 5 ) == 5 || die ();
cache.get ( 2 );
cache.get ( 3 );
cache.put ( 6, 6 );
cache.put ( 7, 7 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == null || die ();
ok |= cache.getSilent ( 5 ) == null || die ();
if ( !ok ) die ();
}
Ora per la versione simultanea ...
pacchetto org.boon.cache;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {
final CacheMap<K, V>[] cacheRegions;
private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
private final ReadWriteLock readWriteLock;
private final int limit;
CacheMap ( final int limit, boolean fair ) {
super ( 16, 0.75f, true );
this.limit = limit;
readWriteLock = new ReentrantReadWriteLock ( fair );
}
protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
return super.size () > limit;
}
@Override
public V put ( K key, V value ) {
readWriteLock.writeLock ().lock ();
V old;
try {
old = super.put ( key, value );
} finally {
readWriteLock.writeLock ().unlock ();
}
return old;
}
@Override
public V get ( Object key ) {
readWriteLock.writeLock ().lock ();
V value;
try {
value = super.get ( key );
} finally {
readWriteLock.writeLock ().unlock ();
}
return value;
}
@Override
public V remove ( Object key ) {
readWriteLock.writeLock ().lock ();
V value;
try {
value = super.remove ( key );
} finally {
readWriteLock.writeLock ().unlock ();
}
return value;
}
public V getSilent ( K key ) {
readWriteLock.writeLock ().lock ();
V value;
try {
value = this.get ( key );
if ( value != null ) {
this.remove ( key );
this.put ( key, value );
}
} finally {
readWriteLock.writeLock ().unlock ();
}
return value;
}
public int size () {
readWriteLock.readLock ().lock ();
int size = -1;
try {
size = super.size ();
} finally {
readWriteLock.readLock ().unlock ();
}
return size;
}
public String toString () {
readWriteLock.readLock ().lock ();
String str;
try {
str = super.toString ();
} finally {
readWriteLock.readLock ().unlock ();
}
return str;
}
}
public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
int cores = Runtime.getRuntime ().availableProcessors ();
int stripeSize = cores < 2 ? 4 : cores * 2;
cacheRegions = new CacheMap[ stripeSize ];
for ( int index = 0; index < cacheRegions.length; index++ ) {
cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
}
}
public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {
cacheRegions = new CacheMap[ concurrency ];
for ( int index = 0; index < cacheRegions.length; index++ ) {
cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
}
}
private int stripeIndex ( K key ) {
int hashCode = key.hashCode () * 31;
return hashCode % ( cacheRegions.length );
}
private CacheMap<K, V> map ( K key ) {
return cacheRegions[ stripeIndex ( key ) ];
}
@Override
public void put ( K key, V value ) {
map ( key ).put ( key, value );
}
@Override
public V get ( K key ) {
return map ( key ).get ( key );
}
//For testing only
@Override
public V getSilent ( K key ) {
return map ( key ).getSilent ( key );
}
@Override
public void remove ( K key ) {
map ( key ).remove ( key );
}
@Override
public int size () {
int size = 0;
for ( CacheMap<K, V> cache : cacheRegions ) {
size += cache.size ();
}
return size;
}
public String toString () {
StringBuilder builder = new StringBuilder ();
for ( CacheMap<K, V> cache : cacheRegions ) {
builder.append ( cache.toString () ).append ( '\n' );
}
return builder.toString ();
}
}
Puoi capire perché copro prima la versione non concorrente. Quanto sopra tenta di creare alcune strisce per ridurre la contesa di blocco. Quindi noi hash la chiave e poi cerca quell'hash per trovare la cache effettiva. Questo rende la dimensione del limite più di un suggerimento / ipotesi approssimativa all'interno di una discreta quantità di errore a seconda di quanto bene sia l'algoritmo di hash delle chiavi.
Ecco il test per dimostrare che probabilmente la versione concorrente funziona. :) (Test sotto tiro sarebbe il vero modo).
public class SimpleConcurrentLRUCache {
@Test
public void test () {
LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
cache.put ( 4, 4 );
cache.put ( 5, 5 );
puts (cache);
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == 4 || die ();
ok |= cache.getSilent ( 5 ) == 5 || die ();
cache.get ( 2 );
cache.get ( 3 );
cache.put ( 6, 6 );
cache.put ( 7, 7 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
cache.put ( 8, 8 );
cache.put ( 9, 9 );
ok |= cache.getSilent ( 4 ) == null || die ();
ok |= cache.getSilent ( 5 ) == null || die ();
puts (cache);
if ( !ok ) die ();
}
@Test
public void test2 () {
LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
for (int index =0 ; index < 5_000; index++) {
cache.get(0);
cache.get ( 1 );
cache.put ( 2, index );
cache.put ( 3, index );
cache.put(index, index);
}
boolean ok = cache.getSilent ( 0 ) == 0 || die ();
ok |= cache.getSilent ( 1 ) == 1 || die ();
ok |= cache.getSilent ( 2 ) != null || die ();
ok |= cache.getSilent ( 3 ) != null || die ();
ok |= cache.size () < 600 || die();
if ( !ok ) die ();
}
}
Questo è l'ultimo post .. Il primo post che ho eliminato in quanto era una LFU non una cache LRU.
Ho pensato di fare un altro tentativo. Stavo provando a trovare la versione più semplice di una cache LRU usando il JDK standard senza troppa implementazione.
Ecco cosa mi è venuto in mente. Il mio primo tentativo è stato un po 'un disastro quando ho implementato un LFU invece di e LRU, e poi ho aggiunto FIFO e il supporto LRU ad esso ... e poi ho capito che stava diventando un mostro. Poi ho iniziato a parlare con il mio amico John che era a malapena interessato, e poi ho descritto a fondo come ho implementato un LFU, LRU e FIFO e come potevi cambiarlo con un semplice arg ENUM, e poi ho capito che tutto ciò che volevo davvero era un semplice LRU. Quindi ignora il mio precedente post e fammi sapere se vuoi vedere una cache LRU / LFU / FIFO commutabile tramite un enum ... no? Ok .. eccolo qui.
L'LRU più semplice possibile usando solo JDK. Ho implementato sia una versione simultanea che una versione non simultanea.
Ho creato un'interfaccia comune (è un minimalismo quindi probabilmente mi mancano alcune funzionalità che vorresti, ma funziona per i miei casi d'uso, ma lascia che se desideri vedere la funzione XYZ fammi sapere ... Vivo per scrivere codice.).
public interface LruCache<KEY, VALUE> {
void put ( KEY key, VALUE value );
VALUE get ( KEY key );
VALUE getSilent ( KEY key );
void remove ( KEY key );
int size ();
}
Potresti chiederti cosa sia getSilent . Lo uso per i test. getSilent non modifica il punteggio LRU di un elemento.
Prima quello non simultaneo ....
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {
Map<KEY, VALUE> map = new HashMap<> ();
Deque<KEY> queue = new LinkedList<> ();
final int limit;
public LruCacheNormal ( int limit ) {
this.limit = limit;
}
public void put ( KEY key, VALUE value ) {
VALUE oldValue = map.put ( key, value );
/*If there was already an object under this key,
then remove it before adding to queue
Frequently used keys will be at the top so the search could be fast.
*/
if ( oldValue != null ) {
queue.removeFirstOccurrence ( key );
}
queue.addFirst ( key );
if ( map.size () > limit ) {
final KEY removedKey = queue.removeLast ();
map.remove ( removedKey );
}
}
public VALUE get ( KEY key ) {
/* Frequently used keys will be at the top so the search could be fast.*/
queue.removeFirstOccurrence ( key );
queue.addFirst ( key );
return map.get ( key );
}
public VALUE getSilent ( KEY key ) {
return map.get ( key );
}
public void remove ( KEY key ) {
/* Frequently used keys will be at the top so the search could be fast.*/
queue.removeFirstOccurrence ( key );
map.remove ( key );
}
public int size () {
return map.size ();
}
public String toString() {
return map.toString ();
}
}
Il queue.removeFirstOccurrence è un'operazione potenzialmente costosa se si dispone di una cache di grandi dimensioni. Si potrebbe prendere come esempio LinkedList e aggiungere una mappa hash di ricerca inversa da elemento a nodo per rendere le operazioni di rimozione MOLTO PIÙ RAPIDE e più coerenti. Ho iniziato anche io, ma poi ho capito che non ne avevo bisogno. Ma ... forse ...
Quando viene chiamato put , la chiave viene aggiunta alla coda. Quando viene chiamato get , la chiave viene rimossa e aggiunta nuovamente nella parte superiore della coda.
Se la tua cache è piccola e la costruzione di un oggetto è costosa, questa dovrebbe essere una buona cache. Se la tua cache è davvero grande, la ricerca lineare potrebbe essere un collo di bottiglia, soprattutto se non hai aree calde della cache. Più intensi sono i punti caldi, più veloce è la ricerca lineare poiché gli elementi caldi sono sempre in cima alla ricerca lineare. Ad ogni modo ... ciò che è necessario per farlo più velocemente è scrivere un altro LinkedList che ha un'operazione di rimozione che ha l'elemento inverso alla ricerca del nodo per la rimozione, quindi la rimozione sarebbe rapida quanto la rimozione di una chiave da una mappa hash.
Se hai una cache con meno di 1.000 elementi, questo dovrebbe funzionare bene.
Ecco un semplice test per mostrare le sue operazioni in azione.
public class LruCacheTest {
@Test
public void test () {
LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 0 ) == 0 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
cache.put ( 4, 4 );
cache.put ( 5, 5 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 0 ) == null || die ();
ok |= cache.getSilent ( 1 ) == null || die ();
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == 4 || die ();
ok |= cache.getSilent ( 5 ) == 5 || die ();
if ( !ok ) die ();
}
}
L'ultima cache LRU era a thread singolo, e per favore non racchiuderla in nulla sincronizzato ....
Ecco una pugnalata a una versione concorrente.
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;
public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {
private final ReentrantLock lock = new ReentrantLock ();
private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
private final Deque<KEY> queue = new LinkedList<> ();
private final int limit;
public ConcurrentLruCache ( int limit ) {
this.limit = limit;
}
@Override
public void put ( KEY key, VALUE value ) {
VALUE oldValue = map.put ( key, value );
if ( oldValue != null ) {
removeThenAddKey ( key );
} else {
addKey ( key );
}
if (map.size () > limit) {
map.remove ( removeLast() );
}
}
@Override
public VALUE get ( KEY key ) {
removeThenAddKey ( key );
return map.get ( key );
}
private void addKey(KEY key) {
lock.lock ();
try {
queue.addFirst ( key );
} finally {
lock.unlock ();
}
}
private KEY removeLast( ) {
lock.lock ();
try {
final KEY removedKey = queue.removeLast ();
return removedKey;
} finally {
lock.unlock ();
}
}
private void removeThenAddKey(KEY key) {
lock.lock ();
try {
queue.removeFirstOccurrence ( key );
queue.addFirst ( key );
} finally {
lock.unlock ();
}
}
private void removeFirstOccurrence(KEY key) {
lock.lock ();
try {
queue.removeFirstOccurrence ( key );
} finally {
lock.unlock ();
}
}
@Override
public VALUE getSilent ( KEY key ) {
return map.get ( key );
}
@Override
public void remove ( KEY key ) {
removeFirstOccurrence ( key );
map.remove ( key );
}
@Override
public int size () {
return map.size ();
}
public String toString () {
return map.toString ();
}
}
Le differenze principali sono l'uso di ConcurrentHashMap invece di HashMap e l'uso del Lock (avrei potuto scappare con la sincronizzazione, ma ...).
Non l'ho testato sotto tiro, ma sembra una semplice cache LRU che potrebbe funzionare nell'80% dei casi d'uso in cui è necessaria una semplice mappa LRU.
Accolgo con favore il feedback, tranne il motivo per cui non usi la libreria a, b o c. Il motivo per cui non uso sempre una libreria è perché non voglio sempre che ogni file di guerra sia di 80 MB e scrivo librerie, quindi tendo a rendere il plug-in libs con una soluzione abbastanza valida e qualcuno può collegarlo -in un altro provider di cache, se lo desiderano. :) Non so mai quando qualcuno potrebbe aver bisogno di Guava o ehcache o qualcos'altro che non voglio includerli, ma se rendo la cache inseribile, non li escluderò neanche.
La riduzione delle dipendenze ha una sua ricompensa. Adoro ricevere feedback su come renderlo ancora più semplice o veloce o entrambi.
Anche se qualcuno sa di un pronto per partire ....
Ok .. So cosa stai pensando ... Perché non usa semplicemente la voce removeEldest da LinkedHashMap, e dovrei ma ... ma ... ma .. Sarebbe un FIFO non un LRU e stavamo cercando di implementare un LRU.
Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {
@Override
protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
return this.size () > limit;
}
};
Questo test ha esito negativo per il codice sopra ...
cache.get ( 2 );
cache.get ( 3 );
cache.put ( 6, 6 );
cache.put ( 7, 7 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == null || die ();
ok |= cache.getSilent ( 5 ) == null || die ();
Quindi ecco una cache FIFO veloce e sporca che usa removeEldestEntry.
import java.util.*;
public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {
final int limit;
Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {
@Override
protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
return this.size () > limit;
}
};
public LruCacheNormal ( int limit ) {
this.limit = limit;
}
public void put ( KEY key, VALUE value ) {
map.put ( key, value );
}
public VALUE get ( KEY key ) {
return map.get ( key );
}
public VALUE getSilent ( KEY key ) {
return map.get ( key );
}
public void remove ( KEY key ) {
map.remove ( key );
}
public int size () {
return map.size ();
}
public String toString() {
return map.toString ();
}
}
I FIFO sono veloci. Nessuna ricerca in giro. Potresti fronteggiare un FIFO di fronte a un LRU e questo gestirà abbastanza bene la maggior parte delle voci hot. Un LRU migliore avrà bisogno di quell'elemento inverso alla funzione Nodo.
Comunque ... ora che ho scritto un po 'di codice, lasciami passare le altre risposte e vedi cosa mi sono perso ... la prima volta che le ho scansionate.
LinkedHashMap è O (1), ma richiede la sincronizzazione. Non è necessario reinventare la ruota lì.
2 opzioni per aumentare la concorrenza:
1.
Crea più LinkedHashMap e esegui l'hash:
esempio: LinkedHashMap [4], indice 0, 1, 2, 3 . Sulla chiave fai key% 4 (o binario OR su [key, 3] ) per scegliere quale mappa fare un put / get / rimuovere.
2.
Puoi fare una LRU 'quasi' estendendo ConcurrentHashMap e avendo una mappa hash collegata come una struttura in ciascuna delle regioni al suo interno. Il blocco avverrebbe in modo più granulare di un LinkedHashMap sincronizzato. Su un put o putIfAbsent è necessario solo un lucchetto in testa e in coda alla lista (per regione). Per rimuovere o ottenere l'intera regione deve essere bloccata. Sono curioso di sapere se elenchi Atomic collegati di qualche tipo potrebbero aiutare qui - probabilmente così per il capo della lista. Forse per di più.
La struttura non manterrebbe l'ordine totale, ma solo l'ordine per regione. Finché il numero di voci è molto più grande del numero di regioni, questo è abbastanza buono per la maggior parte delle cache. Ogni regione dovrà avere il proprio conteggio delle entrate, questo verrà utilizzato anziché il conteggio globale per l'attivazione dello sfratto.
Il numero predefinito di regioni in un ConcurrentHashMap è 16, che è abbastanza per la maggior parte dei server oggi.
-
sarebbe più facile da scrivere e più veloce in una concorrenza moderata.
-
sarebbe più difficile da scrivere ma scalare molto meglio con una concorrenza molto elevata. Sarebbe più lento per l'accesso normale (proprio come
ConcurrentHashMapè più lento diHashMapdove non c'è concorrenza)
Esistono due implementazioni open source.
Apache Solr ha ConcurrentLRUCache: https: // lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html
Esiste un progetto open source per una ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/
Vorrei prendere in considerazione l'utilizzo di java.util.concurrent. PriorityBlockingQueue , con priorità determinata da un "numeroUtilizzo" contatore in ogni elemento. Vorrei molto, molto attento per ottenere tutta la mia sincronizzazione corretta, poiché il "quotOfUses" counter implica che l'elemento non può essere immutabile.
L'oggetto element sarebbe un wrapper per gli oggetti nella cache:
class CacheElement {
private final Object obj;
private int numberOfUsers = 0;
CacheElement(Object obj) {
this.obj = obj;
}
... etc.
}
Spero che questo aiuti.
import java.util.*;
public class Lru {
public static <K,V> Map<K,V> lruCache(final int maxSize) {
return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {
private static final long serialVersionUID = -3588047435434569014L;
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
};
}
public static void main(String[] args ) {
Map<Object, Object> lru = Lru.lruCache(2);
lru.put("1", "1");
lru.put("2", "2");
lru.put("3", "3");
System.out.println(lru);
}
}
La cache LRU può essere implementata utilizzando un ConcurrentLinkedQueue e un ConcurrentHashMap che può essere utilizzato anche in uno scenario multithreading. Il capo della coda è quell'elemento che è stato nella coda il più a lungo. La coda della coda è quell'elemento che è stato sulla coda il più breve tempo. Quando esiste un elemento nella mappa, possiamo rimuoverlo da LinkedQueue e inserirlo nella coda.
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
public class LRUCache<K,V> {
private ConcurrentHashMap<K,V> map;
private ConcurrentLinkedQueue<K> queue;
private final int size;
public LRUCache(int size) {
this.size = size;
map = new ConcurrentHashMap<K,V>(size);
queue = new ConcurrentLinkedQueue<K>();
}
public V get(K key) {
//Recently accessed, hence move it to the tail
queue.remove(key);
queue.add(key);
return map.get(key);
}
public void put(K key, V value) {
//ConcurrentHashMap doesn't allow null key or values
if(key == null || value == null) throw new NullPointerException();
if(map.containsKey(key) {
queue.remove(key);
}
if(queue.size() >= size) {
K lruKey = queue.poll();
if(lruKey != null) {
map.remove(lruKey);
}
}
queue.add(key);
map.put(key,value);
}
}
Ecco la mia implementazione per LRU. Ho usato PriorityQueue, che funziona fondamentalmente come FIFO e non sicuro per i thread. Comparatore usato basato sulla creazione del tempo della pagina e basato sull'esecuzione dell'ordine delle pagine per il tempo usato meno di recente.
Pagine da considerare: 2, 1, 0, 2, 8, 2, 4
La pagina aggiunta alla cache è: 2
La pagina aggiunta alla cache è: 1
La pagina aggiunta alla cache è: 0
Pagina: 2 già esistenti nella cache. Ultimo aggiornamento dell'ultimo accesso
Errore di pagina, PAGINA: 1, Sostituito con PAGINA: 8
La pagina aggiunta alla cache è: 8
Pagina: 2 già esistenti nella cache. Ultimo aggiornamento dell'ultimo accesso
Errore di pagina, PAGINA: 0, Sostituito con PAGINA: 4
La pagina aggiunta alla cache è: 4
USCITA
Pagine LRUCache
-------------
PageName: 8, PageCreationTime: 1365957019974
PageName: 2, PageCreationTime: 1365957020074
PageName: 4, PageCreationTime: 1365957020174
inserisci il codice qui
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
public class LRUForCache {
private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
public static void main(String[] args) throws InterruptedException {
System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
System.out.println("----------------------------------------------\n");
LRUForCache cache = new LRUForCache();
cache.addPageToQueue(new LRUPage("2"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("1"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("0"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("2"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("8"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("2"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("4"));
Thread.sleep(100);
System.out.println("\nLRUCache Pages");
System.out.println("-------------");
cache.displayPriorityQueue();
}
public synchronized void addPageToQueue(LRUPage page){
boolean pageExists = false;
if(priorityQueue.size() == 3){
Iterator<LRUPage> iterator = priorityQueue.iterator();
while(iterator.hasNext()){
LRUPage next = iterator.next();
if(next.getPageName().equals(page.getPageName())){
/* wanted to just change the time, so that no need to poll and add again.
but elements ordering does not happen, it happens only at the time of adding
to the queue
In case somebody finds it, plz let me know.
*/
//next.setPageCreationTime(page.getPageCreationTime());
priorityQueue.remove(next);
System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
pageExists = true;
break;
}
}
if(!pageExists){
// enable it for printing the queue elemnts
//System.out.println(priorityQueue);
LRUPage poll = priorityQueue.poll();
System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());
}
}
if(!pageExists){
System.out.println("Page added into cache is : " + page.getPageName());
}
priorityQueue.add(page);
}
public void displayPriorityQueue(){
Iterator<LRUPage> iterator = priorityQueue.iterator();
while(iterator.hasNext()){
LRUPage next = iterator.next();
System.out.println(next);
}
}
}
class LRUPage{
private String pageName;
private long pageCreationTime;
public LRUPage(String pagename){
this.pageName = pagename;
this.pageCreationTime = System.currentTimeMillis();
}
public String getPageName() {
return pageName;
}
public long getPageCreationTime() {
return pageCreationTime;
}
public void setPageCreationTime(long pageCreationTime) {
this.pageCreationTime = pageCreationTime;
}
@Override
public boolean equals(Object obj) {
LRUPage page = (LRUPage)obj;
if(pageCreationTime == page.pageCreationTime){
return true;
}
return false;
}
@Override
public int hashCode() {
return (int) (31 * pageCreationTime);
}
@Override
public String toString() {
return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
}
}
class LRUPageComparator implements Comparator<LRUPage>{
@Override
public int compare(LRUPage o1, LRUPage o2) {
if(o1.getPageCreationTime() > o2.getPageCreationTime()){
return 1;
}
if(o1.getPageCreationTime() < o2.getPageCreationTime()){
return -1;
}
return 0;
}
}
Ecco la mia implementazione della cache LRU simultanea con le migliori prestazioni testata senza alcun blocco sincronizzato:
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
/**
* @param key - may not be null!
* @param value - may not be null!
*/
public void put(final Key key, final Value value) {
if (map.containsKey(key)) {
queue.remove(key); // remove the key from the FIFO queue
}
while (queue.size() >= maxSize) {
Key oldestKey = queue.poll();
if (null != oldestKey) {
map.remove(oldestKey);
}
}
queue.add(key);
map.put(key, value);
}
/**
* @param key - may not be null!
* @return the value associated to the given key or null
*/
public Value get(final Key key) {
return map.get(key);
}
}
Questa è la cache LRU che uso, che incapsula una LinkedHashMap e gestisce la concorrenza con un semplice blocco di sincronizzazione che protegge i punti succosi. Tocca " tocca " elementi come vengono utilizzati in modo che diventino il "più fresco" di nuovo l'elemento, in modo che sia effettivamente LRU. Ho anche avuto il requisito che i miei elementi avessero una durata minima, che puoi anche considerare come "tempo di inattività massimo". consentito, quindi sei pronto per lo sfratto.
Tuttavia, sono d'accordo con la conclusione di Hank e ho accettato la risposta: se dovessi ricominciare da capo oggi, darei un'occhiata al CacheBuilder di Guava.
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class MaxIdleLRUCache<KK, VV> {
final static private int IDEAL_MAX_CACHE_ENTRIES = 128;
public interface DeadElementCallback<KK, VV> {
public void notify(KK key, VV element);
}
private Object lock = new Object();
private long minAge;
private HashMap<KK, Item<VV>> cache;
public MaxIdleLRUCache(long minAgeMilliseconds) {
this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
}
public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
this(minAgeMilliseconds, idealMaxCacheEntries, null);
}
public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
this.minAge = minAgeMilliseconds;
this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
private static final long serialVersionUID = 1L;
// This method is called just after a new entry has been added
public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
// let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
long age = System.currentTimeMillis() - eldest.getValue().birth;
if (age > MaxIdleLRUCache.this.minAge) {
if ( callback != null ) {
callback.notify(eldest.getKey(), eldest.getValue().payload);
}
return true; // remove it
}
return false; // don't remove this element
}
};
}
public void put(KK key, VV value) {
synchronized ( lock ) {
// System.out.println("put->"+key+","+value);
cache.put(key, new Item<VV>(value));
}
}
public VV get(KK key) {
synchronized ( lock ) {
// System.out.println("get->"+key);
Item<VV> item = getItem(key);
return item == null ? null : item.payload;
}
}
public VV remove(String key) {
synchronized ( lock ) {
// System.out.println("remove->"+key);
Item<VV> item = cache.remove(key);
if ( item != null ) {
return item.payload;
} else {
return null;
}
}
}
public int size() {
synchronized ( lock ) {
return cache.size();
}
}
private Item<VV> getItem(KK key) {
Item<VV> item = cache.get(key);
if (item == null) {
return null;
}
item.touch(); // idle the item to reset the timeout threshold
return item;
}
private static class Item<T> {
long birth;
T payload;
Item(T payload) {
this.birth = System.currentTimeMillis();
this.payload = payload;
}
public void touch() {
this.birth = System.currentTimeMillis();
}
}
}
Bene, per una cache in genere cercherete alcuni dati tramite un oggetto proxy, (un URL, una stringa ....) in modo da poter desiderare una mappa. ma per dare il via alle cose vuoi una coda come la struttura. Internamente manterrei due strutture di dati, una Priority-Queue e una HashMap. ecco un'implementazione che dovrebbe essere in grado di fare tutto in O (1) volta.
Ecco una lezione che ho preparato abbastanza velocemente:
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
int maxSize;
int currentSize = 0;
Map<K, ValueHolder<K, V>> map;
LinkedList<K> queue;
public LRUCache(int maxSize)
{
this.maxSize = maxSize;
map = new HashMap<K, ValueHolder<K, V>>();
queue = new LinkedList<K>();
}
private void freeSpace()
{
K k = queue.remove();
map.remove(k);
currentSize--;
}
public void put(K key, V val)
{
while(currentSize >= maxSize)
{
freeSpace();
}
if(map.containsKey(key))
{//just heat up that item
get(key);
return;
}
ListNode<K> ln = queue.add(key);
ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
map.put(key, rv);
currentSize++;
}
public V get(K key)
{
ValueHolder<K, V> rv = map.get(key);
if(rv == null) return null;
queue.remove(rv.queueLocation);
rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
return rv.value;
}
}
class ListNode<K>
{
ListNode<K> prev;
ListNode<K> next;
K value;
public ListNode(K v)
{
value = v;
prev = null;
next = null;
}
}
class ValueHolder<K,V>
{
V value;
ListNode<K> queueLocation;
public ValueHolder(V value, ListNode<K> ql)
{
this.value = value;
this.queueLocation = ql;
}
}
class LinkedList<K>
{
ListNode<K> head = null;
ListNode<K> tail = null;
public ListNode<K> add(K v)
{
if(head == null)
{
assert(tail == null);
head = tail = new ListNode<K>(v);
}
else
{
tail.next = new ListNode<K>(v);
tail.next.prev = tail;
tail = tail.next;
if(tail.prev == null)
{
tail.prev = head;
head.next = tail;
}
}
return tail;
}
public K remove()
{
if(head == null)
return null;
K val = head.value;
if(head.next == null)
{
head = null;
tail = null;
}
else
{
head = head.next;
head.prev = null;
}
return val;
}
public void remove(ListNode<K> ln)
{
ListNode<K> prev = ln.prev;
ListNode<K> next = ln.next;
if(prev == null)
{
head = next;
}
else
{
prev.next = next;
}
if(next == null)
{
tail = prev;
}
else
{
next.prev = prev;
}
}
}
Ecco come funziona. Le chiavi sono memorizzate in un elenco collegato con le chiavi più vecchie nella parte anteriore dell'elenco (le nuove chiavi vanno sul retro), quindi quando è necessario "espellere" qualcosa, è sufficiente aprirlo dalla parte anteriore della coda e quindi utilizzare il tasto per rimuove il valore dalla mappa. Quando viene referenziato un oggetto, prendi ValueHolder dalla mappa e quindi usi la variabile queuelocation per rimuovere la chiave dalla sua posizione corrente nella coda e poi mettila sul retro della coda (è ora l'ultima usata). Aggiungere cose è praticamente lo stesso.
Sono sicuro che ci sono un sacco di errori qui e non ho implementato alcuna sincronizzazione. ma questa classe fornirà O (1) aggiunta alla cache, O (1) rimozione di vecchi elementi e O (1) recupero di elementi cache. Anche una banale sincronizzazione (basta sincronizzare ogni metodo pubblico) avrebbe comunque poca contesa di blocco a causa del tempo di esecuzione. Se qualcuno ha qualche trucco di sincronizzazione intelligente sarei molto interessato. Inoltre, sono sicuro che ci sono alcune ottimizzazioni che potresti implementare usando la variabile maxsize rispetto alla mappa.
Dai un'occhiata a ConcurrentSkipListMap . Dovresti dare a log (n) tempo per testare e rimuovere un elemento se è già contenuto nella cache e tempo costante per aggiungerlo nuovamente.
Avresti solo bisogno di qualche contatore ecc. ed elemento wrapper per forzare l'ordine dell'ordine LRU e assicurarti che le cose recenti vengano scartate quando la cache è piena.
Ecco la mia breve implementazione, per favore criticalo o miglioralo!
package util.collection;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
* Limited size concurrent cache map implementation.<br/>
* LRU: Least Recently Used.<br/>
* If you add a new key-value pair to this cache after the maximum size has been exceeded,
* the oldest key-value pair will be removed before adding.
*/
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private int currentSize = 0;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
private synchronized void freeSpace() {
Key key = queue.poll();
if (null != key) {
map.remove(key);
currentSize = map.size();
}
}
public void put(Key key, Value val) {
if (map.containsKey(key)) {// just heat up that item
put(key, val);
return;
}
while (currentSize >= maxSize) {
freeSpace();
}
synchronized(this) {
queue.add(key);
map.put(key, val);
currentSize++;
}
}
public Value get(Key key) {
return map.get(key);
}
}
Ecco la mia implementazione per questo problema
simplelrucache fornisce una cache LRU thread-safe, molto semplice e non distribuita con supporto TTL. Fornisce due implementazioni:
- concorrente basato su ConcurrentLinkedHashMap
- Sincronizzato in base a LinkedHashMap
Puoi trovarlo qui: http://code.google.com/p/simplelrucache/
Sto cercando una cache LRU migliore usando il codice Java. È possibile condividere il proprio codice cache LRU Java utilizzando LinkedHashMap e Collections # synchronizedMap ? Attualmente sto usando LRUMap implementa Map e il codice funziona bene, ma sto ottenendo ArrayIndexOutofBoundException sui test di carico utilizzando 500 utenti con il metodo seguente. Il metodo sposta l'oggetto recente in primo piano nella coda.
private void moveToFront(int index) {
if (listHead != index) {
int thisNext = nextElement[index];
int thisPrev = prevElement[index];
nextElement[thisPrev] = thisNext;
if (thisNext >= 0) {
prevElement[thisNext] = thisPrev;
} else {
listTail = thisPrev;
}
//old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
// prev[0 old head] = new head right ; next[new head] = old head
prevElement[index] = -1;
nextElement[index] = listHead;
prevElement[listHead] = index;
listHead = index;
}
}
get (Chiave oggetto) e put (Chiave oggetto, Valore oggetto) chiama il precedente metodo moveToFront .
Volevo aggiungere un commento alla risposta data da Hank ma alcuni come non sono in grado di fare - per favore trattalo come un commento
LinkedHashMap mantiene l'ordine di accesso e si basa sul parametro passato nel suo costruttore Mantiene una lista doppiamente allineata per mantenere l'ordine (Vedi LinkedHashMap.Entry)
@Pacerier è corretto che LinkedHashMap mantenga lo stesso ordine durante l'iterazione se l'elemento viene aggiunto di nuovo ma questo è solo in caso di modalità ordine di inserimento.
questo è quello che ho trovato nei documenti java dell'oggetto LinkedHashMap.Entry
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
questo metodo si occupa di spostare l'elemento di recente accesso alla fine dell'elenco. Tutto sommato, LinkedHashMap è la migliore struttura di dati per l'implementazione di LRUCache.
Un altro pensiero e persino una semplice implementazione che utilizza la raccolta LinkedHashMap di Java.
LinkedHashMap ha fornito il metodo removeEldestEntry e che può essere sovrascritto nel modo indicato nell'esempio. Per impostazione predefinita l'implementazione di questa struttura di raccolta è falsa. Se la sua vera e dimensione di questa struttura va oltre la capacità iniziale rispetto agli elementi più vecchi o più vecchi verranno rimossi.
Possiamo avere un pageno e il contenuto della pagina nel mio caso pageno è intero e il contenuto di pagina ho mantenuto la stringa dei valori del numero di pagina.
import java.util.LinkedHashMap; import java.util.Map; /** * @author Deepak Singhvi * */ public class LRUCacheUsingLinkedHashMap { private static int CACHE_SIZE = 3; public static void main(String[] args) { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99"); System.out.println("----------------------------------------------\n"); // accessOrder is true, so whenever any page gets changed or accessed, // its order will change in the map, LinkedHashMap<Integer,String> lruCache = new LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) { private static final long serialVersionUID = 1L; protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) { return size() > CACHE_SIZE; } }; lruCache.put(2, "2"); lruCache.put(1, "1"); lruCache.put(0, "0"); System.out.println(lruCache + " , After first 3 pages in cache"); lruCache.put(2, "2"); System.out.println(lruCache + " , Page 2 became the latest page in the cache"); lruCache.put(8, "8"); System.out.println(lruCache + " , Adding page 8, which removes eldest element 2 "); lruCache.put(2, "2"); System.out.println(lruCache+ " , Page 2 became the latest page in the cache"); lruCache.put(4, "4"); System.out.println(lruCache+ " , Adding page 4, which removes eldest element 1 "); lruCache.put(99, "99"); System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 "); } }
Il risultato dell'esecuzione del codice precedente è il seguente:
Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
{2=2, 1=1, 0=0} , After first 3 pages in cache
{2=2, 1=1, 0=0} , Page 2 became the latest page in the cache
{1=1, 0=0, 8=8} , Adding page 8, which removes eldest element 2
{0=0, 8=8, 2=2} , Page 2 became the latest page in the cache
{8=8, 2=2, 4=4} , Adding page 4, which removes eldest element 1
{2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8
Seguendo il concetto di @sanjanab (ma dopo le correzioni) ho realizzato la mia versione di LRUCache fornendo anche il consumatore che consente di fare qualcosa con gli elementi rimossi, se necessario.
public class LRUCache<K, V> {
private ConcurrentHashMap<K, V> map;
private final Consumer<V> onRemove;
private ConcurrentLinkedQueue<K> queue;
private final int size;
public LRUCache(int size, Consumer<V> onRemove) {
this.size = size;
this.onRemove = onRemove;
this.map = new ConcurrentHashMap<>(size);
this.queue = new ConcurrentLinkedQueue<>();
}
public V get(K key) {
//Recently accessed, hence move it to the tail
if (queue.remove(key)) {
queue.add(key);
return map.get(key);
}
return null;
}
public void put(K key, V value) {
//ConcurrentHashMap doesn't allow null key or values
if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");
V existing = map.get(key);
if (existing != null) {
queue.remove(key);
onRemove.accept(existing);
}
if (map.size() >= size) {
K lruKey = queue.poll();
if (lruKey != null) {
V removed = map.remove(lruKey);
onRemove.accept(removed);
}
}
queue.add(key);
map.put(key, value);
}
}
