Fast MultiMap in Multi-Thread Environments

Question

I am currently using Guava Multimap implementation.

map = Multimaps.synchronizedSetMultimap(HashMultimap.<K, R> create());

However I found that my program performance is now bounded by the synchronization block synchronized (mutex) used in Multimaps.synchronizedSetMultimap.

Therefore I am finding if there are ANY alternatives to have a synchronized multimap, which hopefully can help improve program performance in multi-threading environment.

I don't mind if extra restrictions are imposed, like only one thread for updating (create, modify or removal), as long as I can read multimap data using multiple threads and at the same time, allow write operation. In addition, for my project usage, I would mostly read data (>99% if time) and seldom write data (< 1%), so I do not care too much on writing performance when compared to read performance).

---

From High-performance Concurrent MultiMap Java/Scala, someone suggest use of

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

and since I am using Java 7, I convert the above code as follows:

map = Multimaps.newSetMultimap(new ConcurrentHashMap<K, Collection<R>>(), new Supplier<Set<R>>() {
    public Set<R> get() {
        return Sets.newSetFromMap(new ConcurrentHashMap<R, Boolean>());
    }
});

which seems working really well. But again from the documentation, it states the following:

The multimap is not threadsafe when any concurrent operations update the multimap, even if map and the instances generated by factory are. Concurrent read operations will work correctly. To allow concurrent update operations, wrap the multimap with a call to synchronizedSetMultimap(com.google.common.collect.SetMultimap<K, V>).

However I have created a test code for concurrent read write, and it seems that it works (without any exceptions like ConcurrentModificationException). My current Java version is Java 7 and using Guava 14.0.1.

So my question is,

1. How can I create a test in multi-thread environment such that Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet) fails to work properly? Or it simply just works accidentally with ConcurrentHashMap?
2. If this line of code does NOT work for multiple threads environment, can anyone suggest me a way to improve multimap READ performance in multi-threads handling?

Many thanks.

Answer 1

You could use:

ConcurrentMap<K, CopyOnWriteArraySet<V>> multimap = new ConcurrentHashMap<>();

You could implement:

class ConcurrentArraySetMultimap<K, V> implements SetMultimap<K, V> {

on top of it.

---

If the Javadoc states Multimaps.newSetMultimap() is not thread-safe, I would not try to prove it wrong. I looked at the implementation, and the reason likely is that additional logic is run on top of the decorated Map and Set.

Answer 2

However I have created a test code for concurrent read write, and it seems that it works (without any exceptions like ConcurrentModificationException)."

You can't really test thread-safety. Thread-safety bugs don't always happen -- they happen only sometimes, and they are extremely confusing when they do.

As linked by Xaerxess in the comments, there is no real way to support the entire Multimap interface concurrently with decent performance. The solution instead is not to use the Multimap interface, but to have your own ConcurrentMap<K, Set<V>> and be very, very careful. (This will be considerably harder in Java 7, with the more restricted ConcurrentMap interface without atomic update operations.)