ti-enxame.com

Alto desempenho simultâneo MultiMap Java/Scala

Eu estou procurando um MultiMap de alto desempenho, simultâneo. Eu tenho procurado em todos os lugares, mas eu simplesmente não consigo encontrar uma solução que usa a mesma abordagem como ConcurrentHashMap (apenas o bloqueio de um segmento da matriz de hash).

O multimap será lido, adicionado e removido com frequência.

A chave multimap será uma String e seu valor será arbitrário.

Eu preciso O(1) para encontrar todos os valores para uma dada chave, O(N) é OK para remoção, mas O(logN) seria preferível .

É crucial que a remoção do último valor de uma determinada chave removerá o contêiner de valores da chave, para não vazar memória.

AQUI ESTÁ A SOLUÇÃO I BUILT, disponível no ApacheV2: Index (multimap)

56
Viktor Klang

Por que não agrupar ConcurrentHashMap [T, ConcurrentLinkedQueue [U]] com alguns métodos semelhantes ao Scala (por exemplo, conversão implícita para Iterable ou o que for necessário e um método de atualização)?

12
Rex Kerr

Você já experimentou o Google Collections? Eles têm vários Multimap implementações.

8
Jon Freedman

um em akka embora eu não tenha usado.

4
lisak

Fiz um ConcurrentMultiMap mixin que estende o mix de mutable.MultiMap e tem um tipo self simultâneo .Map [A, Set [B]]. Ele bloqueia por chave, o que tem complexidade de espaço O(n), mas sua complexidade de tempo é muito boa, se você não estiver particularmente pesado na gravação.

3
nnythm

você deve dar ctries a try. aqui está o pdf .

1
Shlomi

Eu tinha um requisito onde eu tinha que ter um Map<Comparable, Set<Comparable>> onde a inserção no mapa fosse simultânea e também no conjunto correspondente, mas uma vez que uma chave fosse consumida do mapa, tinha que ser deletada, pense se como um trabalho rodando a cada dois segundos que está consumindo o Set<Comparable> inteiro de uma chave específica, mas a inserção é totalmente simultânea para que a maioria dos valores seja armazenada em buffer quando o trabalho entra em ação, aqui está minha implementação:

Note: Eu uso os mapas da classe auxiliar de Guava para criar os Mapas simultâneos, também, esta solução emula simultaneidade Java na Listagem prática 5.19 :

import com.google.common.collect.MapMaker;
import com.google.common.collect.Sets;

import Java.util.Collection;
import Java.util.Set;
import Java.util.concurrent.ConcurrentMap;

/**
 * A general purpose Multimap implementation for delayed processing and concurrent insertion/deletes.
 *
 * @param <K> A comparable Key
 * @param <V> A comparable Value
 */
public class ConcurrentMultiMap<K extends Comparable, V extends Comparable>
{
  private final int size;
  private final ConcurrentMap<K, Set<V>> cache;
  private final ConcurrentMap<K, Object> locks;

  public ConcurrentMultiMap()
  {
    this(32, 2);
  }

  public ConcurrentMultiMap(final int concurrencyLevel)
  {
    this(concurrencyLevel, 2);
  }

  public ConcurrentMultiMap(final int concurrencyLevel, final int factor)
  {
    size=concurrencyLevel * factor;
    cache=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(concurrencyLevel).makeMap();
    locks=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(concurrencyLevel).weakKeys().weakValues().makeMap();
  }

  private Object getLock(final K key){
    final Object object=new Object();
    Object lock=locks.putIfAbsent(key, object);
    if(lock == null){
      lock=object;
    }
    return lock;
  }

  public void put(final K key, final V value)
  {
    synchronized(getLock(key)){
      Set<V> set=cache.get(key);
      if(set == null){
        set=Sets.newHashSetWithExpectedSize(size);
        cache.put(key, set);
      }
      set.add(value);
    }
  }

  public void putAll(final K key, final Collection<V> values)
  {
    synchronized(getLock(key)){
      Set<V> set=cache.get(key);
      if(set == null){
        set=Sets.newHashSetWithExpectedSize(size);
        cache.put(key, set);
      }
      set.addAll(values);
    }
  }

  public Set<V> remove(final K key)
  {
    synchronized(getLock(key)){
      return cache.remove(key);
    }
  }

  public Set<K> getKeySet()
  {
    return cache.keySet();
  }

  public int size()
  {
    return cache.size();
  }

}
1
Guido Medina

Estou um pouco atrasado sobre esse assunto, mas acho que hoje em dia você pode usar o Guava assim:

Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet)
0
teo

Você já deu uma olhada em Javalution que se destina a tempo real etc. e, claro, alto desempenho.

0
khmarbaise

É tarde para a discussão, ainda ...

Quando se trata de material concorrente de alto desempenho, deve-se estar preparado para codificar a solução. Com Concorrente a declaração o Diabo está nos detalhes tem um significado completo. É possível implementar a estrutura totalmente simultânea e sem bloqueio. 

A base inicial seria o Hashtable NonBlocking http://sourceforge.net/projects/high-scale-lib/ e, em seguida, dependendo de quantos valores por chave e com que freqüência precisa adicionar/remover alguma cópia no objeto de gravação [] para valores ou uma matriz baseada em Set with semaphore/spin lock.

0
bestsss