Mapa / cache baseado em tempo do Java com chaves expiradas [fechado]

253

Algum de vocês conhece um mapa Java ou um armazenamento de dados padrão semelhante que elimina automaticamente as entradas após um determinado tempo limite? Isso significa envelhecimento, onde as entradas antigas expiradas "vencem automaticamente".

De preferência em uma biblioteca de código aberto acessível através do Maven?

Conheço maneiras de implementar a funcionalidade pessoalmente e já o fiz várias vezes no passado, por isso não estou pedindo conselhos a esse respeito, mas sim indicadores para uma boa implementação de referência.

Soluções baseadas em WeakReference , como o WeakHashMap, não são uma opção, porque minhas chaves provavelmente não são cadeias de caracteres internas e eu quero um tempo limite configurável que não dependa do coletor de lixo.

O Ehcache também é uma opção na qual eu não gostaria de confiar porque precisa de arquivos de configuração externos. Estou procurando uma solução somente de código.

Sean Patrick Floyd
fonte
1
Confira o Google Collections (agora chamado de goiaba). Ele tem um mapa que pode exceder o tempo limite de entradas automaticamente.
dty 27/09/10
3
Quão estranha é que uma pergunta com 253 votos positivos e 176k visualizações - com uma classificação super alta nos mecanismos de pesquisa para este tópico - tenha sido encerrada por não atender às diretrizes
Brian

Respostas:

320

Sim. O Google Collections, ou Guava, como é chamado agora, tem algo chamado MapMaker que pode fazer exatamente isso.

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

Atualizar:

A partir da goiaba 10.0 (lançada em 28 de setembro de 2011), muitos desses métodos do MapMaker foram preteridos em favor do novo 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
fonte
5
Incrível, eu sabia que o Goiaba tinha uma resposta, mas não consegui encontrá-la! (+1)
Sean Patrick Floyd
12
A partir da v10, você deve usar o CacheBuilder ( guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/… ), pois a expiração etc foi descontinuada no MapMaker
wwadge
49
Atenção ! Usar weakKeys()implica que as chaves são comparadas usando a semântica ==, não equals(). Eu perdi 30 minutos tentando descobrir porque meu cache String-com chave não estava funcionando :)
Laurent Grégoire
3
Pessoal, o que o @Laurent mencionou weakKeys()é importante. weakKeys()não é necessário 90% do tempo.
Manu Manjunath
3
@ ShervinAsgari, para iniciantes (inclusive eu), você poderia mudar seu exemplo de goiaba atualizado para um que use Cache em vez de LoadingCache? Ele corresponderia melhor à pergunta (já que o LoadingCache possui recursos que excedem um mapa com entradas expiradas e é muito mais complicado de criar), consulte github.com/google/guava/wiki/CachesExplained#from-a-callable
Jeutnarg
29

Esta é uma implementação de exemplo que eu fiz para o mesmo requisito e simultaneidade funciona bem. Pode ser útil para alguém.

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


Link de repositório Git (com implementação de ouvinte)

https://github.com/vivekjustthink/WeakConcurrentHashMap

Felicidades!!

Vivek
fonte
Por que você executa cleanMap()metade do tempo esperado?
EliuX 18/01/19
Além disso, ele garante que as chaves expiraram (foram removidas) e evita que os threads fiquem em loop extremo.
Vivek
@Vivek, mas com esta implementação, pode haver no máximo (expiryInMillis / 2) número de entradas que já expiraram, mas ainda estão presentes no cache. Como fio exclui entradas após o período expiryInMillis / 2
rishi007bansod
19

Você pode experimentar minha implementação de um mapa de hash auto-expirável. Esta implementação não utiliza threads para remover entradas expiradas; em vez disso, usa DelayQueue que é limpo automaticamente a cada operação.

vasculhar
fonte
I como a versão de goiaba melhor, mas +1 para adicionar plenitude para a imagem
Sean Patrick Floyd
@ piero86 Eu diria que a chamada para delayQueue.poll () no método expireKey (ExpiringKey <K> delayedKey) está errada. Você pode perder uma ExpiringKey arbitrária que não pode ser utilizada posteriormente em cleanup () - um vazamento.
Stefan Zobel
1
Outro problema: você não pode colocar a mesma chave duas vezes com vidas diferentes. Depois de a) put (1, 1, shortLived) e, em seguida, b) put (1, 2, longLived), a entrada do Mapa da chave 1 desaparecerá após o shortLived ms, não importa quanto tempo seja o longLived.
Stefan Zobel
Obrigado pela sua compreensão. Você poderia relatar esses problemas como comentários na essência, por favor?
PCAN
Corrigido de acordo com suas sugestões. Obrigado.
pcan 13/07/16
19

O Apache Commons possui um decorador para o Map expirar as entradas: PassiveExpiringMap É mais simples que os caches do Guava.

PS tenha cuidado, não está sincronizado.

Guram Savinov
fonte
1
É simples, mas verifica o tempo de expiração somente após o acesso a uma entrada.
21419 Badie
De acordo com o Javadoc : Ao chamar métodos que envolvem o acesso a todo o conteúdo do mapa (por exemplo, containsKey (Object), entrySet (), etc.), esse decorador remove todas as entradas expiradas antes de realmente concluir a chamada.
NS du Toit
Se você deseja ver qual é a versão mais recente desta biblioteca (Apache commons commons-collections4), acesse um link para a biblioteca relevante no mvnrepository
NS du Toit
3

Parece que o ehcache é um exagero para o que você deseja, no entanto, observe que ele não precisa de arquivos de configuração externos.

Geralmente, é uma boa ideia mover a configuração para um arquivo de configuração declarativo (para que você não precise recompilar quando uma nova instalação requer um tempo de expiração diferente), mas isso não é de todo necessário, você ainda pode configurá-lo programaticamente. http://www.ehcache.org/documentation/user-guide/configuration

dan carter
fonte
2

As coleções do Google (goiaba) possuem o MapMaker no qual você pode definir o limite de tempo (para expiração) e pode usar referências suaves ou fracas ao escolher um método de fábrica para criar instâncias de sua escolha.

Emil
fonte
2

Se alguém precisar de uma coisa simples, a seguir é um conjunto simples de expiração de chave. Pode ser convertido em um mapa facilmente.

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
fonte
2
Isso é bom para uma situação de thread único, mas seria quebrado miseravelmente em uma situação simultânea.
Sean Patrick Floyd
@SeanPatrickFloyd você quer dizer com o próprio LinkedHashMap ?! "ele deve ser sincronizado externamente", como LinkedHashMap, HashMap ... o nome dele.
palindrom
sim, como todos aqueles, mas ao contrário de cache do Guava (a resposta aceita)
Sean Patrick Floyd
Além disso, considere o uso System.nanoTime()para calcular diferenças de horário, pois System.currentTimeMillis () não é consistente, pois depende do horário do sistema e pode não ser contínuo.
Ercksen
2

Normalmente, um cache deve manter os objetos por algum tempo e expô-los algum tempo depois. O momento ideal para armazenar um objeto depende do caso de uso. Eu queria que essa coisa fosse simples, sem threads ou agendadores. Essa abordagem funciona para mim. Ao contrário de SoftReferences, é garantido que os objetos estejam disponíveis por um período mínimo de tempo. No entanto, eles não ficam na memória até o sol se transformar em um gigante vermelho .

Como exemplo de uso, pense em um sistema de resposta lenta que poderá verificar se uma solicitação foi feita recentemente e, nesse caso, para não executar a ação solicitada duas vezes, mesmo que um usuário agitado aperte o botão várias vezes. Mas, se a mesma ação for solicitada algum tempo depois, ela deverá ser executada novamente.

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
fonte
bom, obrigado
bigbadmouse
1
O HashMap não é seguro para threads, devido a condições de corrida, operação map.put ou redimensionamento do mapa, pode levar à corrupção de dados. Veja aqui: mailinator.blogspot.com/2009/06/beautiful-race-condition.html
Eugene Maysyuk
Isso é verdade. De fato, a maioria das classes Java não é segura para threads. Se você precisar de segurança de encadeamento, verifique todas as classes afetadas do seu design para ver se ele atende aos requisitos.
Matthias Ronge
1

O cache da goiaba é fácil de implementar. Podemos expirar a chave na base de tempo usando o cache da goiaba. Eu li totalmente post e abaixo dá a chave do meu estudo.

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

              }

Referência: exemplo de cache de goiaba

Anuj Dhiman
fonte
1
atualize o link como ele não está funcionando agora
smaiakov