Alto rendimiento Concurrent MultiMap Java/Scala

Question

Estoy buscando un alto rendimiento, concurrente, MultiMap. 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 se leerá, se agregará y se eliminará a menudo.

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

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

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í tienes la solución I construyó, bajo availbable ApacheV2: Index (multimap)

Answer 1

Ha intentado Google Colecciones? Tienen varias implementaciones Multimap.

Answer 2

Ha echado un vistazo al Javalution que está diseñado para en tiempo real, etc. y, por supuesto, de alto rendimiento.

Answer 3

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

Answer 4

deberías probar ctries. aquí está el pdf.

Answer 5

Es tarde para la discusión, sin embargo ...

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

Base inicial 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 una matriz basada en Set con semáforo/spin lock.

Answer 6

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, piense si como un Trabajo que sale cada dos segundos, lo que está consumiendo toda la Set<Comparable> de una clave específica pero la inserción ser totalmente concurrente por lo que la mayoría de los valores de búfer cuando manda el empleo en, aquí está mi aplicación:

Nota: utilizo clase de ayuda de guayaba Mapas para crear los mapas simultáneos, también, esta solución emula 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 7

Hay one in akka aunque yo no lo he utilizado.

Answer 8

Hice un ConcurrentMultiMap mixin que amplía el mixte mutable.MultiMap y tiene un mismo tipo de archivo concurrent.Map [A, Set [B]].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 9

Estoy un poco tarde en este tema, pero creo que, hoy en día, puede utilizar la guayaba como esto:

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