Czasowa mapa Java / pamięć podręczna z wygasającymi kluczami [zamknięte]

253

Czy ktoś z was zna mapę Java lub podobny standardowy magazyn danych, który automatycznie usuwa wpisy po upływie określonego czasu? Oznacza to starzenie się, w którym stare wygasłe wpisy automatycznie „wygasają”.

Najlepiej w bibliotece open source, która jest dostępna za pośrednictwem Maven?

Znam sposoby samodzielnego wdrożenia tej funkcji i robiłem to już kilka razy w przeszłości, więc nie proszę o radę w tym zakresie, ale o wskazówki dotyczące dobrej implementacji referencyjnej.

Rozwiązania oparte na WeakReference , takie jak WeakHashMap, nie są opcją, ponieważ moje klucze prawdopodobnie są ciągami nie internowanymi i chcę konfigurowalnego limitu czasu, który nie zależy od śmieciarza.

Ehcache to także opcja, na której nie chciałbym polegać, ponieważ potrzebuje zewnętrznych plików konfiguracyjnych. Szukam rozwiązania tylko do kodu.

Sean Patrick Floyd
źródło
1
Sprawdź Kolekcje Google (obecnie Guava). Ma mapę, która może automatycznie limitować czas wpisów.
dty
3
Jak dziwne jest to, że pytanie z 253 głosami pozytywnymi i liczbą wyświetleń 176 000 - które zajmuje bardzo wysoką pozycję w wyszukiwarkach tego tematu - zostało zamknięte, ponieważ nie spełnia wytycznych
Brian

Odpowiedzi:

320

Tak. Kolekcje Google lub Guava, jak się nazywa, ma teraz coś o nazwie MapMaker, który może to zrobić dokładnie.

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);
         }
       });

Aktualizacja:

Od wersji guava 10.0 (wydanej 28 września 2011 r.) Wiele z tych metod MapMaker zostało wycofanych na korzyść nowego CacheBuilder :

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
źródło
5
Wspaniale, wiedziałem, że Guava ma odpowiedź, ale nie mogłem jej znaleźć! (+1)
Sean Patrick Floyd
12
Począwszy od wersji 10, powinieneś używać CacheBuilder ( guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/... ), ponieważ data wygaśnięcia itp. Została wycofana w MapMaker
wwadge
49
Ostrzeżenie ! Używanie weakKeys()oznacza, że ​​klucze są porównywane przy użyciu semantyki ==, a nie equals(). Straciłem 30 minut, zastanawiając się, dlaczego moja pamięć podręczna z kluczem nie działa :)
Laurent Grégoire,
3
Ludzie, rzecz, o której wspominał @Laurent, weakKeys()jest ważna. weakKeys()nie jest wymagane 90% czasu.
Manu Manjunath
3
@ShervinAsgari ze względu na początkujących (w tym mnie), czy mógłbyś zmienić swój zaktualizowany przykład guawy na taki, który używa Cache zamiast LoadingCache? Lepiej pasowałoby do pytania (ponieważ LoadingCache ma funkcje przekraczające mapę z wygasającymi wpisami i jest znacznie bardziej skomplikowane w tworzeniu) patrz github.com/google/guava/wiki/CachesExplained#from-a-callable
Jeutnarg
29

To jest przykładowa implementacja, którą zrobiłem dla tego samego wymagania, a współbieżność działa dobrze. Może być przydatny dla kogoś.

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 (z implementacją Listener)

https://github.com/vivekjustthink/WeakConcurrentHashMap

Twoje zdrowie!!

Vivek
źródło
Dlaczego wykonujesz cleanMap()połowę określonego czasu?
EliuX,
Bcoz upewnia się, że klucze wygasły (zostały usunięte) i pozwala uniknąć ekstremalnego zapętlenia wątku.
Vivek
@Vivek, ale dzięki tej implementacji może istnieć maksymalna (expiryInMillis / 2) liczba wpisów, które już wygasły, ale nadal znajdują się w pamięci podręcznej. Wątek usuwa wpisy po wygaśnięciuInMillis / 2 period
rishi007bansod
19

Możesz wypróbować moją implementację wygasającej mapy skrótów. Ta implementacja nie wykorzystuje wątków do usuwania wygasłych wpisów, zamiast tego używa DelayQueue, która jest czyszczona automatycznie przy każdej operacji.

pcan
źródło
Bardziej podoba mi się wersja Guavy, ale +1 za dodanie kompletności do zdjęcia
Sean Patrick Floyd
@ piero86 Powiedziałbym, że wywołanie delayQueue.poll () w metodzie expireKey (ExpiringKey <K> delayedKey) jest nieprawidłowe. Możesz stracić dowolny klucz ExpiringKey, którego nie można później wykorzystać w cleanup () - wyciek.
Stefan Zobel,
1
Kolejny problem: nie można umieścić tego samego klucza dwa razy w różnych okresach życia. Po a) wstawieniu (1, 1, shortLived), a następnie b) umieszczeniu (1, 2, longLived), wpis mapy dla klucza 1 zniknie po ms shortLived, bez względu na to, jak długo to trwa.
Stefan Zobel,
Dziękuję za wgląd. Czy możesz zgłosić te problemy jako komentarze w treści?
pcan
Naprawiono zgodnie z twoimi sugestiami. Dzięki.
pcan
19

Apache Commons ma dekoratora dla Map, aby wygasać wpisy: PassiveExpiringMap To jest prostsze niż skrzynki z Guawy .

PS bądź ostrożny, nie jest zsynchronizowany.

Guram Savinov
źródło
1
Jest to proste, ale sprawdza czas wygaśnięcia dopiero po uzyskaniu dostępu do wpisu.
Badie
Zgodnie z Javadoc : Przy wywoływaniu metod obejmujących dostęp do całej zawartości mapy (tj. ZawieraKlucz (Obiekt), entrySet () itp.) Ten dekorator usuwa wszystkie wygasłe wpisy przed faktycznym zakończeniem wywołania.
NS du Toit
Jeśli chcesz zobaczyć, jaka jest najnowsza wersja tej biblioteki (Apache commons commons-collections4) , jest link do odpowiedniej biblioteki w mvnrepository
NS du Toit
3

Wygląda na to, że ehcache przesadza z tym, czego chcesz, jednak pamiętaj, że nie potrzebuje zewnętrznych plików konfiguracyjnych.

Zasadniczo dobrym pomysłem jest przeniesienie konfiguracji do deklaratywnych plików konfiguracyjnych (więc nie ma potrzeby ponownej kompilacji, gdy nowa instalacja wymaga innego czasu wygaśnięcia), ale nie jest to wcale wymagane, nadal można ją skonfigurować programowo. http://www.ehcache.org/documentation/user-guide/configuration

Dan Carter
źródło
2

Kolekcje Google (guava) mają MapMakera, w którym możesz ustawić limit czasu (do wygaśnięcia) i możesz użyć miękkiego lub słabego odniesienia, wybierając metodę fabryczną, aby utworzyć wybrane instancje.

Emil
źródło
2

Jeśli ktoś potrzebuje prostej rzeczy, to prosty zestaw, który traci ważność. Można go łatwo przekonwertować na mapę.

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
źródło
2
Jest to dobre w przypadku sytuacji z jednym wątkiem, ale w przypadku równoczesnej sytuacji byłoby to nieskuteczne.
Sean Patrick Floyd,
@SeanPatrickFloyd masz na myśli jak sama LinkedHashMap ?! „musi być zsynchronizowany zewnętrznie”, tak jak LinkedHashMap, HashMap ... nazywasz to.
palindrom
tak, jak wszyscy, ale w przeciwieństwie do skrytki Guava (zaakceptowana odpowiedź)
Sean Patrick Floyd
Należy również rozważyć użycie System.nanoTime()do obliczania różnic czasowych, ponieważ System.currentTimeMillis () nie jest spójny, ponieważ zależy od czasu systemowego i może nie być ciągły.
Ercksen
2

Zazwyczaj pamięć podręczna powinna przechowywać obiekty przez pewien czas i ujawniać je później. To, kiedy najlepiej trzymać przedmiot, zależy od przypadku użycia. Chciałem, żeby to było proste, bez wątków i harmonogramów. To podejście działa dla mnie. W przeciwieństwie do SoftReferences, obiekty są gwarantowane przez pewien minimalny czas. Nie pozostają jednak w pamięci, dopóki słońce nie zmieni się w czerwonego olbrzyma .

Jako przykład użycia pomyśl o wolno reagującym systemie, który będzie w stanie sprawdzić, czy żądanie zostało wykonane całkiem niedawno, iw takim przypadku nie wykona żądanego działania dwa razy, nawet jeśli gorączkowy użytkownik kliknie przycisk kilka razy. Ale jeśli jakiś czas później zażąda się tego samego działania, należy je wykonać ponownie.

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
źródło
miło, dziękuję
bigbadmouse
1
HashMap nie jest bezpieczny dla wątków, ze względu na warunki wyścigu, działanie map.put lub zmiana rozmiaru mapy może prowadzić do uszkodzenia danych. Zobacz tutaj: mailinator.blogspot.com/2009/06/beautiful-race-condition.html
Eugene Maysyuk
To prawda. Rzeczywiście, większość klas Java nie jest bezpieczna dla wątków. Jeśli potrzebujesz ochrony wątków, musisz sprawdzić każdą klasę projektu, której dotyczy problem, aby sprawdzić, czy spełnia ona wymagania.
Matthias Ronge
1

Pamięć podręczna guava jest łatwa do wdrożenia. Klucz wygasa na podstawie czasu, korzystając z pamięci podręcznej guava. Przeczytałem w pełni post i poniżej daje klucz do moich badań.

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);
                }

              }

Odniesienie: przykład pamięci podręcznej guava

Anuj Dhiman
źródło
1
zaktualizuj link, ponieważ teraz nie działa
smaiakov,