Alto rendimiento MultiMap Java/Scala simultáneo

concurrency

Question

Estoy buscando un MultiMap simultáneo de alto rendimiento. He buscado en todas partes, pero simplemente no puedo encontrar una solución que use el mismo enfoque que ConcurrentHashMap (solo bloqueando un segmento de la matriz de hash).

El multimap será leído, agregado y eliminado a menudo.

La clave multimap será una cadena y su valor será arbitrario.

Necesito O (1) para encontrar todos los valores para una clave determinada, O (N) está bien para su eliminación, pero O (logN) sería preferible.

Es crucial que la eliminación del último valor para una clave determinada elimine el contenedor de valores de la clave, para no perder memoria.

AQUÍ ESTÁ LA SOLUCIÓN QUE CONSTRUYE, disponible bajo ApacheV2: Index (multimap)

Answer 1

¿Has echado un vistazo a Javalution que está destinado a tiempo real, etc. y, por supuesto, de alto rendimiento.

Answer 2

¿Has probado Google Collections? Tienen varias implementaciones Multimap .

Answer 3

¿Por qué no envolver ConcurrentHashMap [T, ConcurrentLinkedQueue [U]] con algunos buenos métodos tipo Scala (por ejemplo, la conversión implícita a Iterable o lo que sea que necesites, y un método de actualización)?

Answer 4

Es tarde para la discusión, aún ...

Cuando se trata de cosas simultáneas de alto rendimiento, uno debe estar preparado para codificar la solución. Concurrente la declaración del Demonio está en los detalles tiene un significado completo. Es posible implementar la estructura totalmente simultánea y sin bloqueos.

La base de inicio sería NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/ y luego dependiendo de cuántos valores por clave y con qué frecuencia se necesita agregar / eliminar alguna copia en Write Object [] para valores o conjunto basado en matriz con semáforo / bloqueo de giro.

Answer 5

Estoy un poco retrasado en este tema, pero creo que, hoy en día, puedes usar la guayaba de esta manera:

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

Answer 6

Hay uno en Akka aunque no lo he usado.

Answer 7

Hice un mixin ConcurrentMultiMap que amplía el mixin mutable.MultiMap y tiene un self-type [A, Set [B]] concurrente. Se bloquea por clave, que tiene una complejidad de espacio O (n), pero su complejidad de tiempo es bastante buena, si no es particularmente pesado para escribir.

Answer 8

Tenía un requisito en el que tenía que tener un Map<Comparable, Set<Comparable>> donde la inserción en el Mapa era concurrente y también en el Conjunto correspondiente, pero una vez que se consumía una Clave del Mapa, tenía que ser eliminada, pensar si como una tarea que se ejecuta cada dos segundos que consume todo el conjunto Set<Comparable> de una clave específica, pero la inserción es totalmente simultánea, de modo que la mayoría de los valores se almacenan en búfer cuando se inicia el trabajo, aquí está mi implementación:

Nota: uso los mapas de la clase de ayuda de Guava para crear los mapas simultáneos, también, esta solución emula la concurrencia de Java en el Listado de Práctica 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();
  }

}

Answer 9

ctries probar ctries . aquí está el pdf .