Высокопроизводительная параллельная MultiMap Java/Scala

Я ищу высокопроизводительный параллельный MultiMap. Я искал везде, но я просто не могу найти решение, которое использует тот же подход, что и ConcurrentHashMap (только блокировка сегмента хэш-массива).

Мультимап будет часто считываться, добавляться и удаляться из него.

Ключ мультимапа будет строкой, и это значение будет произвольным.

Мне нужно O (1), чтобы найти все значения для данного ключа, O (N) в порядке для удаления, но O (logN) было бы предпочтительным.

Крайне важно, чтобы удаление последнего значения для данного ключа удаляло контейнер значений из ключа, чтобы не утечка памяти.

ЗДЕСЬ РЕШЕНИЕ, ПОСТРОЕННОЕ, доступное под ApacheV2: Index (multimap)

Ответ 1

Почему бы не переместить ConcurrentHashMap [T, ConcurrentLinkedQueue [U]] с некоторыми хорошими методами Scala (например, неявное преобразование в Iterable или что-то, что вам нужно, и метод обновления)?

Ответ 2

Вы пробовали Google Collections? Они имеют различные Multimap.

Ответ 3

Существует один в akka, хотя я его не использовал.

Ответ 4

Я сделал ConcurrentMultiMap mixin, который расширяет mutable.MultiMap mixin и имеет concurrent.Map [A, Set [B]] self type. Он блокирует каждую клавишу, которая имеет сложность O (n), но ее временная сложность довольно хороша, если вы не особенно тяжелы для записи.

Ответ 5

вам следует дать ctries. здесь pdf.

Ответ 6

У меня было требование, когда я должен был иметь Map<Comparable, Set<Comparable>>, где вставка на карте была бы параллельной, а также в соответствующем наборе, но после того, как ключ был израсходован с карты, его нужно было удалить, подумайте, Работа, выполняемая каждые две секунды, которая потребляет всего Set<Comparable> из определенного ключа, но вставка должна быть полностью параллельной, чтобы большинство значений буферизовалось при запуске задания, вот моя реализация:

Примечание.. Я использую классы-помощники Guava Maps для создания параллельных Карт. Кроме того, это решение эмулирует Java concurrency в Практическом листинге 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();
  }

}

Ответ 7

Я немного опаздываю на эту тему, но думаю, теперь вы можете использовать Guava так:

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

Ответ 8

Вы взглянули на Javalution, который предназначен для реального времени и т.д. и, конечно же, высокой производительности.

Ответ 9

Это поздно для обсуждения, но...

Когда речь заходит о высокопроизводительных параллельных вещах, нужно подготовить код для решения. С одновременным утверждением, что Дьявол в деталях имеет полный смысл. Это позволяет реализовать структуру, полностью параллельную и незакрепленную.

Исходной базой будет NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/, а затем в зависимости от того, сколько значений за ключ и как часто нужно добавлять/удалять какую-либо копию на запись Object [] для значений или массива на основе Set с блокировкой семафора/спина.