고성능 동시 MultiMap Java / Scala

고성능 동시 MultiMap Java / Scala

---

고성능 동시 MultiMap을 찾고 있습니다. 어디에서나 검색했지만 ConcurrentHashMap과 동일한 접근 방식을 사용하는 솔루션을 찾을 수 없습니다 (해시 배열의 세그먼트 만 잠그기).

멀티 맵은 자주 읽고 추가되고 제거됩니다.

멀티 맵 키는 문자열이며 값은 임의입니다.

주어진 키에 대한 모든 값을 찾으려면 O (1)이 필요하고 O (N)은 제거해도 괜찮지 만 O (logN)이 선호됩니다.

주어진 키에 대한 마지막 값을 제거하면 메모리 누수를 방지하기 위해 키에서 값 컨테이너가 제거되는 것이 중요합니다.

ApacheV2에서 사용할 수있는 내가 만든 솔루션은 다음과 같습니다. 인덱스 (멀티 맵)

---

ConcurrentHashMap [T, ConcurrentLinkedQueue [U]]를 멋진 Scala와 유사한 메서드 (예 : Iterable 로의 암시 적 변환 또는 필요한 것이 무엇이든 업데이트 메서드)로 래핑하지 않는 이유는 무엇입니까?

---

Google 컬렉션을 사용해 보셨습니까? 다양한 멀티 맵 구현이 있습니다.

---

이 akka 한 나는 그것을 사용하지 않은 있지만.

---

저는 mutable.MultiMap 믹스 인을 확장 하는 ConcurrentMultiMap 믹스 인을 만들었으며 동시 .Map [A, Set [B]] 자체 유형을 가지고 있습니다. O (n) 공간 복잡성이있는 키당 잠금이지만 특히 쓰기 작업이 많지 않은 경우 시간 복잡성이 꽤 좋습니다.

---

ctries 를 시도 해야합니다 . 여기에 pdf가 있습니다.

---

Map<Comparable, Set<Comparable>>맵에 어디에 삽입이 동시에 이루어져야하고 해당 세트에도 있어야한다는 요구 사항이 있었지만 키가 맵에서 소비되면 삭제해야합니다. 2 초마다 실행되는 작업으로 생각하면 Set<Comparable>특정 키에서 전체 를 소비 하지만 삽입은 완전히 동시 적이므로 Job이 시작될 때 대부분의 값이 버퍼링됩니다. 여기에 내 구현이 있습니다.

참고 : Guava의 도우미 클래스 Maps를 사용하여 동시지도를 생성합니다. 또한이 솔루션은 연습 목록 5.19에서 Java 동시성을 에뮬레이트합니다 .

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

}

---

Real time 등을위한 Javalution 과 물론 고성능 을 보셨나요 ?

---

토론은 늦었지만 ...

When it comes to high performance concurrent stuff, one should be prepared to code the solution. With Concurrent the statement the Devil is in the details has a complete meaning. It's possible to implement the structure fully concurrent and lock-free.

Starting base would be the NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/ and then depending how many values per key and how often need to add/remove some copy on write Object[] for values or an array based Set with semaphore/spin lock.

---

I am a bit late on this topic but I think, nowadays, you can use Guava like this:

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

참고URL : https://stackoverflow.com/questions/3635292/high-performance-concurrent-multimap-java-scala