Implementation is removed on ConcurrentMultimap without racing

Question

I considered the problem of writing parallel Multimap , and I have an implementation supported by Google Guava AbstractSetMultimap and a MapMaker payment card, which creates on-demand collections of values ​​in the form of a given view over ConcurrentHashMap. With some caution about collections of views and various wrappers, I think it's pretty close.

The big problem that has already been discussed by others who have tried this seems to be the removal of collections of values ​​from the base map when they become empty, without introducing race conditions.

There are several options.

• leave empty collections there. This will leak some CHM, but I believe that is at least correct.
• try optimistically to delete the collection when empty and compensate if anything else appears in it. It is full of races and apparently impossible to fix.
• synchronize everything in the collection of values, which will at least allow this deletion, but at the cost of any concurrency after the initial key search.
• for a lesser penalty (maybe depending on usage patterns?), maybe synchronized when creating and deleting a collection of values, you need to check if this covers everything.

Questions:

• Does anyone know of a better implementation than this? Can we better compose a MapMaker bit, or does this need a special ConcurrentHashMultimap written from scratch?
• If this is difficult to improve, is this leak likely to be a significant problem in practice? Well-known collections, such as java.util.HashMap, juc.ConcurrentHashMap and ArrayDeque, do not resize the store down, and ArrayList does not do this automatically. While we are cleaning objects, I wonder if it will be too much.

thanks

---

Edit: See also the discussion here on the guava mailing list.

---

Edit 2: I have since written this. See this area of ​​Google code for implementation. I would really appreciate any feedback from anyone who tries it, and not here.

Answer 1

As a continuation, here are some details that I omitted from the previous discussions that you contacted about my parallel implementation with several modes.

This implementation followed your first suggestion: leaving empty collections on the support map. The following real-time behavior complicates your other suggestions.

Multimap<String, Integer> multimap = HashMultimap.create(); Set<Integer> set = multimap.get("foo"); multimap.put("foo", 1); int count = set.size(); // equals 1 

For a real application, unlike a collection library class, it is likely to be quite smaller than a fully parallel multicast. You can define your own class that implements a subset of the Multimap interface or a limited selection of concurrency guarantees. Or, your application logic can minimize the inconsistency of a synchronized multimap to avoid performance issues.

Answer 2

I asked the same question before and ended up implementing 4 different implementations.

Question: High Performance Parallel MultiMap Java / Scala

Impt (I call it an index) http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314

Answer 3

If you really do not want to filter out an empty collection, you can try to atomically replace it with a placeholder key of the future. Thus, simultaneous addition / removal or addition / addition should be able to achieve a consistent state when expanding again.

Answer 4

Using immutable collections as values ​​is the best way to solve / simplify the main problems of concurrency, as you can remove using the atomic replacement method. Unfortunately, in the general case, there are no immutable collections with fast profiles for copying and updating, so you usually need to do quite expensive copying of everything.