High-performance Concurrent MultiMap Java/Scala

views:

359

answers:

+13 Q:

High-performance Concurrent MultiMap Java/Scala

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 2010-09-03 11:35:32

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 2010-09-03 11:45:44

You're right about the implementation of Syncronized - it locks the whole instance - have you identified this collection as a performance bottlekneck?

Jon Freedman 2010-09-03 12:43:42

Yes, this is as central as it gets.

Viktor Klang 2010-09-03 14:00:30

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

khmarbaise 2010-09-03 12:14:24

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

Viktor Klang 2010-09-03 12:40:58

+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 2010-09-03 13:22:54

How do you implement remove?

Viktor Klang 2010-09-03 13:27:55

@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 2010-09-03 13:42:01

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 2010-09-03 13:45:29

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 2010-09-03 13:49:48

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 2010-09-03 13:50:14

Good idea Rex, I'll try that approach and see if it works out.

Viktor Klang 2010-09-03 14:00:10

Thanks Rex, the approach seems to hold up: http://gist.github.com/566793

Viktor Klang 2010-09-06 13:16:35

ansaurus

tags:

views:

answers:

High-performance Concurrent MultiMap Java/Scala

related questions