views:

359

answers:

3

Dear StackOverflow,

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.

HERE'S THE SOLUTION I BUILT, availbable under ApacheV2: http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314

+4  A: 

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

Jon Freedman
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.
Viktor Klang
You're right about the implementation of Syncronized - it locks the whole instance - have you identified this collection as a performance bottlekneck?
Jon Freedman
Yes, this is as central as it gets.
Viktor Klang
A: 

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

khmarbaise
Don't see no multimap let alone a concurrent and high performant one :(
Viktor Klang
+7  A: 

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
How do you implement remove?
Viktor Klang
@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.
Rex Kerr
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.
Viktor Klang
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.
Jon Freedman
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.)
Rex Kerr
Good idea Rex, I'll try that approach and see if it works out.
Viktor Klang
Thanks Rex, the approach seems to hold up: http://gist.github.com/566793
Viktor Klang