Java zeitbasierte Map / Cache mit ablaufenden Schlüsseln [geschlossen]

253

Kennt jemand von Ihnen eine Java Map oder einen ähnlichen Standarddatenspeicher, der Einträge nach einer bestimmten Zeit automatisch löscht? Dies bedeutet Altern, bei dem die alten abgelaufenen Einträge automatisch "altern".

Am besten in einer Open-Source-Bibliothek, auf die über Maven zugegriffen werden kann?

Ich kenne Möglichkeiten, die Funktionalität selbst zu implementieren, und habe dies in der Vergangenheit mehrmals getan. Daher bitte ich diesbezüglich nicht um Rat, sondern um Hinweise auf eine gute Referenzimplementierung.

WeakReference- basierte Lösungen wie WeakHashMap sind keine Option, da meine Schlüssel wahrscheinlich nicht internierte Zeichenfolgen sind und ich ein konfigurierbares Zeitlimit möchte, das nicht vom Garbage Collector abhängig ist.

Ehcache ist auch eine Option, auf die ich mich nicht verlassen möchte, da externe Konfigurationsdateien erforderlich sind. Ich suche nach einer Nur-Code-Lösung.

Sean Patrick Floyd
quelle
1
Schauen Sie sich Google Collections (jetzt Guava genannt) an. Es hat eine Karte, die Einträge automatisch zeitlich festlegen kann.
27.
3
Wie seltsam, dass eine Frage mit 253 Upvotes und 176.000 Views - die in Suchmaschinen für dieses Thema einen super hohen Rang einnimmt - geschlossen wurde, da sie nicht den Richtlinien entspricht
Brian,

Antworten:

320

Ja. Google Collections oder Guava, wie es heißt, hat jetzt MapMaker, das genau das kann.

ConcurrentMap<Key, Graph> graphs = new MapMaker()
   .concurrencyLevel(4)
   .softKeys()
   .weakValues()
   .maximumSize(10000)
   .expiration(10, TimeUnit.MINUTES)
   .makeComputingMap(
       new Function<Key, Graph>() {
         public Graph apply(Key key) {
           return createExpensiveGraph(key);
         }
       });

Aktualisieren:

Ab Guava 10.0 (veröffentlicht am 28. September 2011) sind viele dieser MapMaker-Methoden zugunsten des neuen CacheBuilder veraltet :

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
    .maximumSize(10000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build(
        new CacheLoader<Key, Graph>() {
          public Graph load(Key key) throws AnyException {
            return createExpensiveGraph(key);
          }
        });
Shervin Asgari
quelle
5
Genial, ich wusste, dass Guava eine Antwort hatte, aber ich konnte sie nicht finden! (+1)
Sean Patrick Floyd
12
Ab Version 10 sollten Sie stattdessen CacheBuilder ( guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/… ) verwenden, da das Ablaufen usw. in MapMaker
wwadge
49
Achtung ! Die Verwendung weakKeys()impliziert, dass Schlüssel mit der == -Semantik verglichen werden, nicht equals(). Ich habe 30 Minuten verloren, um herauszufinden, warum mein Cache mit String-Schlüssel nicht funktioniert hat :)
Laurent Grégoire
3
Leute, was @Laurent erwähnt hat, weakKeys()ist wichtig. weakKeys()ist in 90% der Fälle nicht erforderlich.
Manu Manjunath
3
@ShervinAsgari Könnten Sie für Anfänger (ich selbst eingeschlossen) Ihr aktualisiertes Guavenbeispiel auf ein Beispiel umstellen, das Cache anstelle von LoadingCache verwendet? Es würde besser zu der Frage passen (da LoadingCache Funktionen hat, die eine Karte mit ablaufenden Einträgen überschreiten und deren Erstellung weitaus komplizierter ist), siehe github.com/google/guava/wiki/CachesExplained#from-a-callable
Jeutnarg
29

Dies ist eine Beispielimplementierung, die ich für die gleiche Anforderung durchgeführt habe, und die Parallelität funktioniert gut. Könnte für jemanden nützlich sein.

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 
 * @author Vivekananthan M
 *
 * @param <K>
 * @param <V>
 */
public class WeakConcurrentHashMap<K, V> extends ConcurrentHashMap<K, V> {

    private static final long serialVersionUID = 1L;

    private Map<K, Long> timeMap = new ConcurrentHashMap<K, Long>();
    private long expiryInMillis = 1000;
    private static final SimpleDateFormat sdf = new SimpleDateFormat("hh:mm:ss:SSS");

    public WeakConcurrentHashMap() {
        initialize();
    }

    public WeakConcurrentHashMap(long expiryInMillis) {
        this.expiryInMillis = expiryInMillis;
        initialize();
    }

    void initialize() {
        new CleanerThread().start();
    }

    @Override
    public V put(K key, V value) {
        Date date = new Date();
        timeMap.put(key, date.getTime());
        System.out.println("Inserting : " + sdf.format(date) + " : " + key + " : " + value);
        V returnVal = super.put(key, value);
        return returnVal;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (K key : m.keySet()) {
            put(key, m.get(key));
        }
    }

    @Override
    public V putIfAbsent(K key, V value) {
        if (!containsKey(key))
            return put(key, value);
        else
            return get(key);
    }

    class CleanerThread extends Thread {
        @Override
        public void run() {
            System.out.println("Initiating Cleaner Thread..");
            while (true) {
                cleanMap();
                try {
                    Thread.sleep(expiryInMillis / 2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }

        private void cleanMap() {
            long currentTime = new Date().getTime();
            for (K key : timeMap.keySet()) {
                if (currentTime > (timeMap.get(key) + expiryInMillis)) {
                    V value = remove(key);
                    timeMap.remove(key);
                    System.out.println("Removing : " + sdf.format(new Date()) + " : " + key + " : " + value);
                }
            }
        }
    }
}


Git Repo Link (mit Listener-Implementierung)

https://github.com/vivekjustthink/WeakConcurrentHashMap

Prost!!

Vivek
quelle
Warum führen Sie die cleanMap()Hälfte der angegebenen Zeit aus?
EliuX
Bcoz stellt sicher, dass die Schlüssel abgelaufen (entfernt) sind und verhindert, dass der Thread extrem schleift.
Vivek
@Vivek, aber mit dieser Implementierung kann es maximal (expiryInMillis / 2) Anzahl von Einträgen geben, die bereits abgelaufen sind, aber noch im Cache vorhanden sind. Als Thread löscht Einträge nach AblaufInMillis / 2 Zeitraum
rishi007bansod
19

Sie können meine Implementierung einer selbst ablaufenden Hash-Map ausprobieren . Diese Implementierung verwendet keine Threads, um abgelaufene Einträge zu entfernen, sondern verwendet DelayQueue , das bei jedem Vorgang automatisch bereinigt wird.

pcan
quelle
Ich mag Guavas Version besser, aber +1 für die Vollständigkeit des Bildes
Sean Patrick Floyd
@ piero86 Ich würde sagen, der Aufruf von delayQueue.poll () in der Methode expireKey (ExpiringKey <K> delayKey) ist falsch. Möglicherweise verlieren Sie einen beliebigen ExpiringKey, der später nicht mehr für cleanup () verwendet werden kann - ein Leck.
Stefan Zobel
1
Ein weiteres Problem: Sie können denselben Schlüssel nicht zweimal mit unterschiedlichen Lebensdauern einsetzen. Nach a) put (1, 1, shortLived), dann b) put (1, 2, longLived) wird der Map-Eintrag für Schlüssel 1 nach shortLived ms gelöscht, egal wie lange longLived ist.
Stefan Zobel
Vielen Dank für Ihren Einblick. Könnten Sie diese Probleme bitte als Kommentare im Kern melden?
pcan
Nach Ihren Vorschlägen behoben. Vielen Dank.
pcan
19

Apache Commons hat einen Dekorator für Map, mit dem Einträge ablaufen: PassiveExpiringMap Es ist einfacher als Caches aus Guava.

PS Vorsicht, es ist nicht synchronisiert.

Guram Savinov
quelle
1
Es ist einfach, überprüft die Ablaufzeit jedoch erst, nachdem Sie auf einen Eintrag zugegriffen haben.
Badie
Gemäß der Javadoc : Wenn Methoden aufrufen, die den gesamten Karteninhalte beinhalten Zugriff (dh containsKey (Object), entrySet (), etc.) dieser Dekorateur alle abgelaufenen Einträge entfernt vor dem Ausführen von tatsächlich den Aufruf.
NS du Toit
Wenn Sie sehen möchten, welche Version dieser Bibliothek (Apache commons commons-collection4) aktuell
NS du Toit,
3

Klingt so, als ob ehcache für das, was Sie wollen, übertrieben ist. Beachten Sie jedoch, dass keine externen Konfigurationsdateien erforderlich sind.

Es ist im Allgemeinen eine gute Idee, die Konfiguration in deklarative Konfigurationsdateien zu verschieben (Sie müssen also nicht neu kompilieren, wenn für eine neue Installation eine andere Ablaufzeit erforderlich ist), dies ist jedoch überhaupt nicht erforderlich. Sie können sie dennoch programmgesteuert konfigurieren. http://www.ehcache.org/documentation/user-guide/configuration

Dan Carter
quelle
2

Google-Sammlungen (Guave) verfügen über den MapMaker, in dem Sie das Zeitlimit (für den Ablauf) festlegen und bei der Auswahl mithilfe einer Factory-Methode weiche oder schwache Referenzen verwenden können, um Instanzen Ihrer Wahl zu erstellen.

Emil
quelle
2

Wenn jemand eine einfache Sache braucht, folgt ein einfacher Satz, dessen Schlüssel abläuft. Es kann leicht in eine Karte konvertiert werden.

public class CacheSet<K> {
    public static final int TIME_OUT = 86400 * 1000;

    LinkedHashMap<K, Hit> linkedHashMap = new LinkedHashMap<K, Hit>() {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, Hit> eldest) {
            final long time = System.currentTimeMillis();
            if( time - eldest.getValue().time > TIME_OUT) {
                Iterator<Hit> i = values().iterator();

                i.next();
                do {
                    i.remove();
                } while( i.hasNext() && time - i.next().time > TIME_OUT );
            }
            return false;
        }
    };


    public boolean putIfNotExists(K key) {
        Hit value = linkedHashMap.get(key);
        if( value != null ) {
            return false;
        }

        linkedHashMap.put(key, new Hit());
        return true;
    }

    private static class Hit {
        final long time;


        Hit() {
            this.time = System.currentTimeMillis();
        }
    }
}
Palindrom
quelle
2
Dies ist in Ordnung für eine Single-Thread-Situation, würde aber in einer gleichzeitigen Situation kläglich brechen.
Sean Patrick Floyd
@ SeanPatrickFloyd meinst du wie LinkedHashMap selbst?! "Es muss extern synchronisiert werden", genau wie LinkedHashMap, HashMap ... Sie nennen es.
Palindrom
Ja, wie alle, aber im Gegensatz zu Guavas Cache (die akzeptierte Antwort)
Sean Patrick Floyd
System.nanoTime()Erwägen Sie außerdem die Verwendung zur Berechnung von Zeitunterschieden, da System.currentTimeMillis () nicht konsistent ist, da es von der Systemzeit abhängt und möglicherweise nicht kontinuierlich ist.
Ercksen
2

In der Regel sollte ein Cache Objekte einige Zeit aufbewahren und einige Zeit später verfügbar machen. Was ein guter Zeitpunkt ist, um ein Objekt zu halten, hängt vom Anwendungsfall ab. Ich wollte, dass dieses Ding einfach ist, keine Threads oder Scheduler. Dieser Ansatz funktioniert bei mir. Im Gegensatz zu SoftReferences ist für Objekte eine Mindestdauer garantiert. Sie bleiben jedoch nicht in Erinnerung, bis sich die Sonne in einen roten Riesen verwandelt .

Stellen Sie sich als Verwendungsbeispiel ein langsam reagierendes System vor, das in der Lage sein soll, zu überprüfen, ob eine Anforderung erst vor kurzem ausgeführt wurde, und in diesem Fall die angeforderte Aktion nicht zweimal auszuführen, selbst wenn ein hektischer Benutzer mehrmals auf die Schaltfläche drückt. Wenn dieselbe Aktion jedoch einige Zeit später angefordert wird, muss sie erneut ausgeführt werden.

class Cache<T> {
    long avg, count, created, max, min;
    Map<T, Long> map = new HashMap<T, Long>();

    /**
     * @param min   minimal time [ns] to hold an object
     * @param max   maximal time [ns] to hold an object
     */
    Cache(long min, long max) {
        created = System.nanoTime();
        this.min = min;
        this.max = max;
        avg = (min + max) / 2;
    }

    boolean add(T e) {
        boolean result = map.put(e, Long.valueOf(System.nanoTime())) != null;
        onAccess();
        return result;
    }

    boolean contains(Object o) {
        boolean result = map.containsKey(o);
        onAccess();
        return result;
    }

    private void onAccess() {
        count++;
        long now = System.nanoTime();
        for (Iterator<Entry<T, Long>> it = map.entrySet().iterator(); it.hasNext();) {
            long t = it.next().getValue();
            if (now > t + min && (now > t + max || now + (now - created) / count > t + avg)) {
                it.remove();
            }
        }
    }
}
Matthias Ronge
quelle
schön, danke
bigbadmouse
1
HashMap ist nicht threadsicher, da die Race.put-Operation oder die Größenänderung der Map aufgrund von Race-Bedingungen zu einer Beschädigung der Daten führen kann. Siehe hier: mailinator.blogspot.com/2009/06/beautiful-race-condition.html
Eugene Maysyuk
Das ist richtig. In der Tat sind die meisten Java-Klassen nicht threadsicher. Wenn Sie Thread-Sicherheit benötigen, müssen Sie jede betroffene Klasse Ihres Entwurfs überprüfen, um festzustellen, ob sie die Anforderungen erfüllt.
Matthias Ronge
1

Der Guaven-Cache ist einfach zu implementieren. Mit dem Guaven-Cache können wir den Schlüssel zeitlich ablaufen lassen. Ich habe den Beitrag vollständig gelesen und unten den Schlüssel meiner Studie angegeben.

cache = CacheBuilder.newBuilder().refreshAfterWrite(2,TimeUnit.SECONDS).
              build(new CacheLoader<String, String>(){
                @Override
                public String load(String arg0) throws Exception {
                    // TODO Auto-generated method stub
                    return addcache(arg0);
                }

              }

Referenz: Beispiel für einen Guaven-Cache

Anuj Dhiman
quelle
1
Bitte aktualisieren Sie den Link, da er jetzt nicht funktioniert
smaiakov