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,

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?
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.

As `ConcurrentHashMap` states: "Similarly, Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException." But that does not mean that the resulting Multimap is correct, some operations will not be as atomic as they should be. You could perhaps try to wrap it in a class using a [`ReadWriteLock`](https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/concurrent/locks/ReadWriteLock.html) or similar construct for locking. — Hulk, Dec 16 '20 at 08:07
Or perhaps [the implementation in this answer](https://stackoverflow.com/a/12385841/2513200) of the question you linked to yourself works for you? — Hulk, Dec 16 '20 at 08:15
@Hulk Thanks for reply. I know that ConcurrentHashMap would not throw any exception during iteration. But from https://stackoverflow.com/questions/3768554/is-iterating-concurrenthashmap-values-thread-safe, it seems to me that if I use an iterator on each thread, I would be fine. Is that true? In addition, though the docs does not specify the map is up to date, i.e. if there are new update, it may or may not reflect during iteration, which seems fine to me as well. — CHANist, Dec 16 '20 at 08:20
I don't know guava's implementation well enough to answer that with certainty, but I suspect that while the individual maps will be safe enough, you could see some on-between state (i.e. some inconsistencies) of the entire Multimap. — Hulk, Dec 16 '20 at 08:26
For example, if it is implemented similar to the version I linked to in the previous comment, but without the additional locking provided by `synchronized(getLock(key))`, then concurrent `put`-operations to previously absent keys could occasionally be lost. I'm sure there may be other, similar problems. — Hulk, Dec 16 '20 at 08:31
I am not sure, but actually I just do not want the term `synchronized` as it just makes thing slower. Definitely, may be because the default implementation is synchronizing the whole map which makes me feel slow, if synchronizing a portion (by key basis) could improve speed a lot. I am not sure that yet, but I would try that out. Thanks. But as far as I know `ConcurrentHashMap` uses some clever trick to skip `synchronized` so it works much faster than using `Collections.synchronizedMap(new HashMap<>())`, I would rather stick to this end for more performance improvement whenever available. — CHANist, Dec 16 '20 at 08:50
It may be possible to come up with a lock-free version, but I don't know any. Thus my suggestions, to either use more fine-grained (per key) locking or a `ReadWriteLock` to allow relatively efficient concurrent reads, but lock when writing, which may help if writes are rare compared to reads. — Hulk, Dec 16 '20 at 08:54
https://github.com/google/guava/issues/135 has some nice context on why there's no "general purpose concurrent multimap" implementation in Guava. — Grzegorz Rożniecki, Dec 16 '20 at 11:36

spongebob · Answer 1 · 2020-12-17T04:48:11.520

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.

score 4 · Answer 2 · answered Dec 17 '20 at 23:09

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.)

Fast MultiMap in Multi-Thread Environments

2 Answers2