High-performance Concurrent MultiMap Java/Scala

Question

I am looking for a high-performance, concurrent, MultiMap. I have searched everywhere but I simply cannot find a solution that uses the same approach as ConcurrentHashMap (Only locking a segment of the hash array).

The multimap will be both read, added to and removed from often.

The multimap key will be a String and it's value will be arbitrary.

I need O(1) to find all values for a given key, O(N) is OK for removal, but O(logN) would be preferred.

It is crucial that removal of the last value for a given key will remove the container of values from the key, as to not leak memory.

EDIT: HERE'S THE SOLUTION I BUILT, available under ApacheV2: Index (multimap)

• ziggystar: There's no Map with O(1) lookup (except the bucket algorithm stuff, as usual). HashMaps have O(cn) with very small c.
• Thomas Kappler: ziggystar, it depends on how well the hashing function distributes the keys. If it does so randomly - which you could expect of a modern hash, for arbitrary strings - then lookup is O(1). This is also what the HashMap Javadoc says.
• Viktor Klang: I have a registry of potentially millions of objects and they may share some properties, and I need an index for said properties, so I can retrieve all objects having a certain property.
• Daniel C. Sobral: Perhaps it is time to search for your answer on cstheory.stackexchange.com? It looks like you'll be rolling your own data structure...
• Viktor Klang: @John V: Here's what I built: gist.github.com/566793

Answer 1

Why not wrap ConcurrentHashMap[T,ConcurrentLinkedQueue[U]] with some nice Scala-like methods (e.g. implicit conversion to Iterable or whatever it is that you need, and an update method)?

• Rex Kerr: @Viktor - If you have the (key,value) pair, map.get(key).remove(value) should do the trick as long as you leave the empty queue there as a placeholder when you remove a key and catch the exception if it's not there (including the NPE off of get). If you can't leave the queue as a placeholder, then it's difficult to ensure safety unless you do lock the entire map while you clean out the cruft.
• Viktor Klang: Can't leave the queue since it will leak memory. I'm actually considering using the ConcurrentHashMap source and bend it to my will, but it seems like a very crude approach.
• Jon Freedman: This may be the best solution, you can constrain locking the entire collection to only occur when you find a Queue which is empty, I'm not sure you can get away from either writing your own implementation, or changing the way you want to use this to handle this nested structure rather than a Multimap.
• Rex Kerr: Can you tolerate locking the queue when you get it, and then holding the queue while you send an update to the map to empty that (k,v) pair? That is, use the lock on the queue rather than on the whole map to avoid collisions? (And add logic to handle the case where you get a queue but then, before you can lock it, it's emptied out and removed from the map--all you have to do is check when you get the lock that it is non-empty. If it is empty, assume it's been removed.)
• Jean-Philippe Pellet: For those looking for Viktor's implementation, you can find it as akka.util.ConcurrentMultiMap. Thanks a lot, Viktor!

Answer 2

Have you tried Google Collections? They have various Multimap implementations.

• Viktor Klang: Yes, but I am not looking for just a multimap, I am looking for a high-performance concurrent multimap. When I checked their source code earlier today, their concurrent multimap locked the entire map, which creates a serial structure.
• Jon Freedman: You're right about the implementation of Syncronized - it locks the whole instance - have you identified this collection as a performance bottlekneck?
• Viktor Klang: Yes, this is as central as it gets.

Answer 3

There is one in akka although I haven't used it.

Answer 4

I had a requirement where I had to have a Map<Comparable, Set<Comparable>> where insertion on the Map be concurrent and also on the corresponding Set, but once a Key was consumed from the Map, it had to be deleted, think if as a Job running every two seconds which is consuming the whole Set<Comparable> from an specific Key but insertion be totally concurrent so that most values be buffered when the Job kicks in, here is my implementation:

Note: I use Guava's helper class Maps to create the concurrent Maps, also, this solution emulates Java concurrency in Practice Listing 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 5

I made a ConcurrentMultiMap mixin which extends the mutable.MultiMap mixin and has a concurrent.Map[A, Set[B]] self type. It locks per key, which has O(n) space complexity, but its time complexity is pretty good, if you aren't particularly write-heavy.

Answer 6

you should give ctries a try. here is the pdf.

• Viktor Klang: Aleks s coming to visit me at the office next week, I'll talk to him then.
• Shlomi: iam curious to hear how the talk went. did you find ctries useful?
• Viktor Klang: Not for the multimap purpose, I talked to Bagwell and Prokopec about making an implementation that would work as a multimap, but I don't think there was enough time. Ctries are going into Scala 2.10

Answer 7

It's late for the discussion, yet...

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.

Answer 8

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

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

• breandan: Does Multimaps.newSetMultimap(...) support concurrent updates? According to the Javadoc, "The multimap is not threadsafe when any concurrent operations update the multimap, even if map and the instances generated by factory are." cf. google.github.io/guava/releases/23.0/api/docs/com/google/common/…
• Radu Toader: so by reading the docs, and the previous answer will this work ? : Multimaps.synchronizedSetMultimap(Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet))

Answer 9

Use MultiMaps from Gauava. Multimaps.synchronizedMultimap(HashMultimap.create())

• Stefan Haberl: Your solution is synchronized. Note what the OP was looking for.

Answer 10

Have you taken a look to Javalution which is intended for Real time etc. and of course high performance.

• Viktor Klang: Don't see no multimap let alone a concurrent and high performant one :(