Wie würden Sie einen LRU-Cache in Java implementieren?
Ich mag viele dieser Vorschläge, aber im Moment bleibe ich bei LinkedHashMap + Collections.synchronizedMap . Wenn ich dies in Zukunft wiederhole, werde ich wahrscheinlich daran arbeiten, ConcurrentHashMap zu erweitern ebenso LinkedHashMap erweitert HashMap .
UPDATE:
Auf Wunsch hier das Wesentliche meiner aktuellen Implementierung.
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));
Wenn ich das heute noch einmal von Grund auf neu machen würde, würde ich Guavas CacheBuilder verwenden .
Das ist Runde zwei.
Die erste Runde war das, was ich mir ausgedacht habe, dann habe ich die Kommentare noch einmal gelesen, wobei die Domain ein bisschen tiefer in meinem Kopf verankert war.
Hier ist also die einfachste Version mit einem Komponententest, der zeigt, dass sie auf der Grundlage einiger anderer Versionen funktioniert.
Zuerst die nicht gleichzeitige Version:
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 ();
}
}
Das True-Flag verfolgt den Zugriff von Gets und Puts. Siehe JavaDocs. Das removeEdelstEntry ohne das True-Flag für den Konstruktor würde nur einen FIFO-Cache implementieren (siehe Anmerkungen unten zu FIFO und removeEldestEntry).
Hier ist der Test, der beweist, dass es als LRU-Cache funktioniert:
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 ();
}
Nun zur Concurrent-Version...
Paket 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 ();
}
}
Sie können sehen, warum ich zuerst die nicht gleichzeitige Version behandle. Die obigen Versuche, einige Streifen zu erstellen, um Sperrkonflikte zu reduzieren. Also hashen wir den Schlüssel und suchen dann nach diesem Hash, um den tatsächlichen Cache zu finden. Dies macht die Grenzgröße eher zu einem Vorschlag/einer groben Schätzung mit einer angemessenen Fehlerquote, je nachdem, wie weit Ihr Schlüssel-Hash-Algorithmus verbreitet ist.
Hier ist der Test, um zu zeigen, dass die gleichzeitige Version wahrscheinlich funktioniert. :) (Test unter Beschuss wäre der richtige Weg).
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 ();
}
}
Dies ist der letzte Beitrag.. Den ersten Beitrag habe ich gelöscht, da es sich um einen LFU- und nicht um einen LRU-Cache handelte.
Ich dachte, ich würde es noch einmal versuchen. Ich habe versucht, die einfachste Version eines LRU-Cache mit dem Standard-JDK ohne zu viel Implementierung zu entwickeln.
Hier ist, was ich mir ausgedacht habe. Mein erster Versuch war eine kleine Katastrophe, da ich eine LFU anstelle von LRU implementierte und dann FIFO und LRU-Unterstützung hinzufügte ... und dann wurde mir klar, dass es ein Monster wurde. Dann fing ich an, mit meinem Kumpel John zu reden, der kaum interessiert war, und dann habe ich ausführlich beschrieben, wie ich ein LFU, LRU und FIFO implementiert habe und wie man es mit einem einfachen ENUM-Argument umschalten kann, und dann wurde mir klar, dass das alles war, was ich wirklich wollte war eine einfache LRU. Ignorieren Sie also den früheren Beitrag von mir und lassen Sie mich wissen, ob Sie einen LRU/LFU/FIFO-Cache sehen möchten, der über eine Aufzählung umschaltbar ist ... nein? Ok... hier ist er.
Die einfachstmögliche LRU, die nur das JDK verwendet. Ich habe sowohl eine gleichzeitige als auch eine nicht gleichzeitige Version implementiert.
Ich habe eine gemeinsame Schnittstelle erstellt (es ist Minimalismus, so dass wahrscheinlich ein paar Funktionen fehlen, die Sie möchten, aber es funktioniert für meine Anwendungsfälle, aber lassen Sie es mich wissen, wenn Sie Feature XYZ sehen möchten ... Ich lebe, um Code zu schreiben.) .
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 ();
}
Sie fragen sich vielleicht, was getSilent ist ist. Ich benutze das zum Testen. getSilent ändert den LRU-Score eines Elements nicht.
Zuerst die nicht gleichzeitige....
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 ();
}
}
Das queue.removeFirstOccurrence ist ein potenziell teurer Vorgang, wenn Sie einen großen Cache haben. Man könnte LinkedList als Beispiel nehmen und eine Reverse-Lookup-Hash-Map von Element zu Knoten hinzufügen, um Entfernungsvorgänge VIEL SCHNELLER und konsistenter zu machen. Ich habe auch angefangen, aber dann gemerkt, dass ich es nicht brauche. Aber... vielleicht...
Wenn put aufgerufen wird, wird der Schlüssel der Warteschlange hinzugefügt. Wenn erhalten aufgerufen wird, wird der Schlüssel entfernt und wieder ganz oben in die Warteschlange eingefügt.
Wenn Ihr Cache klein und das Bauen eines Gegenstands teuer ist, sollte dies ein guter Cache sein. Wenn Ihr Cache wirklich groß ist, kann die lineare Suche ein Engpass sein, insbesondere wenn Sie keine heißen Cache-Bereiche haben. Je intensiver die Hotspots sind, desto schneller ist die lineare Suche, da Hot Items immer ganz oben in der linearen Suche stehen. Wie auch immer ... was benötigt wird, damit dies schneller geht, ist, eine andere LinkedList zu schreiben, die eine Entfernungsoperation hat, die eine umgekehrte Element-zu-Knoten-Suche zum Entfernen hat, dann wäre das Entfernen ungefähr so schnell wie das Entfernen eines Schlüssels aus einer Hash-Map.
Wenn Sie einen Cache mit weniger als 1.000 Elementen haben, sollte dies problemlos funktionieren.
Hier ist ein einfacher Test, um seine Operationen in Aktion zu zeigen.
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 ();
}
}
Der letzte LRU-Cache war Single-Threaded, und bitte verpacken Sie ihn nicht in etwas Synchronisiertes....
Hier ist ein Versuch einer gleichzeitigen Version.
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 ();
}
}
Die Hauptunterschiede sind die Verwendung von ConcurrentHashMap anstelle von HashMap und die Verwendung von Lock (ich hätte mit synchronisiert davonkommen können, aber ...).
Ich habe es nicht unter Beschuss getestet, aber es scheint ein einfacher LRU-Cache zu sein, der in 80 % der Anwendungsfälle funktionieren könnte, in denen Sie eine einfache LRU-Karte benötigen.
Ich freue mich über Feedback, außer warum verwenden Sie nicht Bibliothek a, b oder c. Der Grund, warum ich nicht immer eine Bibliothek verwende, ist, dass ich nicht immer möchte, dass jede Kriegsdatei 80 MB groß ist, und ich Bibliotheken so schreibe Ich neige dazu, die Libs mit einer ausreichend guten Lösung Plug-in-fähig zu machen, und jemand kann einen anderen Cache-Anbieter anschließen, wenn er möchte. :) Ich weiß nie, wann jemand Guava oder ehcache oder etwas anderes braucht. Ich möchte sie nicht einbeziehen, aber wenn ich Caching Plug-fähig mache, werde ich sie auch nicht ausschließen.
Die Reduzierung von Abhängigkeiten hat seinen eigenen Lohn. Ich freue mich über Feedback, wie man dies noch einfacher oder schneller oder beides machen kann.
Auch wenn jemand eine fahrbereite kennt....
Ok ... ich weiß, was Sie denken ... Warum verwendet er nicht einfach den Eintrag removeEldest von LinkedHashMap, und das sollte ich tun, aber ... aber ... aber ... das wäre ein FIFO, kein LRU, und wir waren es versuchen, eine LRU zu implementieren.
Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {
@Override
protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
return this.size () > limit;
}
};
Dieser Test schlägt für den obigen Code fehl...
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 ();
Hier ist also ein schneller und schmutziger FIFO-Cache mit 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 ();
}
}
FIFOs sind schnell. Kein Herumsuchen. Sie könnten einen FIFO vor einer LRU platzieren, und das würde die meisten heißen Einträge recht gut handhaben. Eine bessere LRU wird diese Umkehrelement-zu-Knoten-Funktion benötigen.
Wie auch immer ... jetzt, wo ich einen Code geschrieben habe, lassen Sie mich die anderen Antworten durchgehen und sehen, was ich verpasst habe ... das erste Mal, als ich sie gescannt habe.
