implementing ConcurrentMultimap remove

[Joe Kearney]

Hi,

I've been looking at the problem of writing a concurrent multimap, and I have an implementation backed by AbstractSetMultimap and a MapMaker computing map that creates on demand the values-collections as a set view over a ConcurrentHashMap. With some care over the view collections and various wrappers, I think it gets pretty close.

The big problem, which has already been discussed by others who have tried this, appears to be that of removing the values-collection from the underlying map when they become empty, without introducing race conditions.

A couple of options appear to exist.

• leave the empty collections there. This is leaky, but I believe it to be at least correct.
• try optimistically to remove the collection when empty and compensate if anything else appears in it. This is full of races and seems intrinsically impossible to fix.
• synchronise everything on the values-collection, which would at least allow this removal, but at the cost of any concurrency after the initial lookup by key.
• for a smaller penalty (perhaps, depending on usage patterns?), perhaps synchronise on values-collection creation and removal, need to check whether that covers everything.

Jared wrote "I actually wrote one, but its code quality and usefulness aren't strong enough..." on the guava issue – I'd be interested to know whether that implementation handles this issue.

Has anyone done any better than this? Can we do any better composing bits of MapMaker, or does this need a specialised ConcurrentHashMultimap written from scratch?

The other question that I'm slightly hesitant to ask: is this leak likely to be much of an issue in practice? Notable collections such as java.util.HashMap, juc.ConcurrentHashMap and ArrayDeque do not resize the backing store downwards, and ArrayList does not do so automatically. As long as we clear out the objects, I wonder whether this will matter too much.

Thanks,

Joe

[Chris Povirk]

The values collections our implementation uses are immutable. Every
put(), remove(), etc. requires creating a new collection containing
the other existing values. We then ConcurrentMap.replace(K, V, V) the
old immutable values with the new immutable values. Since the value
collection itself is never modified, we can ConcurrentMap.remove(K, V)
the values collection when removing the last element with the
knowledge that it will either (a) succeed, meaning that the collection
really is empty throughout the operation or (b) fail, meaning that
some modification occurred and we can start over with a
ConcurrentMap.replace(K, V, V).

This would be very inefficient for some use cases, possibly more so
than synchronizedMultimap(), and that's a big part of Jared's concerns
about releasing it.

> Has anyone done any better than this? Can we do any better composing bits of
> MapMaker, or does this need a specialised ConcurrentHashMultimap written
> from scratch?

I think we have a bug filed internally along the lines of "Think about
having a MultimapMaker," but even the thinking phase may be years off,
since it's likely to be complex and, of course, the remaining work on
MapMaker itself is a higher priority.

> The other question that I'm slightly hesitant to ask: is this leak likely to
> be much of an issue in practice? Notable collections such as
> java.util.HashMap, juc.ConcurrentHashMap and ArrayDeque do not resize the
> backing store downwards, and ArrayList does not do so automatically. As long
> as we clear out the objects, I wonder whether this will matter too much.

In most cases, I suspect that it's no problem. If someone skips over
the warnings, though (and I can easily see myself doing that unless
the class name is ConcurrentMultimapThatNeverShrinks), it's not hard
to imagine, say, a mapping from session ID to data that accumulates a
huge number of empty values collections.

[Benjamin Manes]

Has anyone experimented with a striped-lock based implementation yet? That should be fairly simple, not have the copy overhead, and likely have less contention since concurrent updates in the immutable version still bang against the striped locks in ConcurrentHashMap. 

--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com

This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

[Jared Levy]

There are a couple of factors that complicate a concurrent multimap implementation. A multimap is a two-dimensional data structure with many methods and views. That makes a concurrent multimap more difficult to construct than a concurrent map.

Since a synchronized multimap performs well when there isn't much contention, as is generally the case, we can't really justify the effort that's needed to implement and maintain a high-quality concurrent multimap.

[Joe Kearney]

>a synchronized multimap performs well when there isn't much contention, as is generally the case

True. It's the high contention case I'm looking at, in particular I expect lots of concurrent access for different keys.

I'll have a look at striping, which I guess will boil down to doing everything under the segment lock. The ideal that I was aiming for was to have concurrently accessible view collections too, but we can abandon that for now to look at striping across buckets of keys. I suppose most contention is likely to arise across the keys anyway.

Thanks all for your input.

Joe

2010/9/28 Jared Levy <jared....@gmail.com>

[Joe Kearney]

Ok, I've written a striped locking SetMultimap implementation based heavily on juc.ConcurrentHashMap and it works a charm. I'm sure it'll generalise to an XxxMultimap version too. The only substantive changes were that the HashEntry value is a Set and the iterators needed some tlc to fit with both the Entry<K,V> and asMap views. I'll see what I can do about making it public, if anyone would be interested.

Thanks,

Joe

[Joe Kearney]

2010/9/28 Benjamin Manes <bma...@google.com>

Has anyone experimented with a striped-lock based implementation yet? That should be fairly simple, not have the copy overhead, and likely have less contention since concurrent updates in the immutable version still bang against the striped locks in ConcurrentHashMap. 

Hi,

I've finally gotten around to uploading this. If anyone cares to try it, I would greatly appreciate any comments or criticisms.

http://code.google.com/p/libjoe/source/browse/trunk/src/com/google/common/collect/ConcurrentHashMultimap.java

There's a jar available to download as well. It depends only on Guava r07. The class is in the com.google.common.collect package only because it needs access to AbstractMultimap and friends. Are there any plans for this to be made public? At all, if not soon?

Thanks,

Joe