2

I'm trying to make a class which utilizes a set-within-a-map thread-safe. I'm unsure of what particularly needs to be synchronized.

The map is defined as something similar to Map<Class<K>, Set<V>> map;. The following is a reduction of the way the map is being used internally in the implementation:

public void addObject(K key, V object) {
    getSet(key).add(object);
}

public void removeObject(K key, V object) {
    getSet(key).remove(object);
}

public void iterateObjectsInternally(K key, Object... params)
{
    for (V o : getSet(key)) {
        o.doSomething(params);
    }
}

private Set<V> getSet(K key) {
    if (!map.containsKey(key)) {
        map.put(key, new Set<V>());
    }

    return map.get(key);
}

Problems with Map

As far as using the map itself goes, the only concurrency problems I see would be in getSet(K), where thread context may switch between containsKey and put. In this case, the following may happen:

[Thread A] map.containsKey(key)       => returns false
[Thread B] map.containsKey(key)       => returns false
[Thread B] map.put(key, new Set<V>())
[Thread B] map.get(key).add(object)
[Thread A] map.put(key, new Set<V>()) => Thread A ovewrites Thread B's object [!]
[Thread B] map.get(key).add(object)

Now, I'm currently using a regular HashMap for this implementation. And, if I am correctly, using Collection.synchronizedMap() or ConcurrentHashMap will only solves concurrency issues on the method-level. That is, methods will be performed atomically. These say nothing about the way methods interact with each other, so the following could still happen even when using a concurrent solution.

ConcurrentHashMap does, however, have the method putIfAbsent. The downside to this is that the statement map.putIfAbsent(key, new Set<V>()) will create a new set every time the set is requested. This seems like a lot of overhead.

On the other hand, is it enough, however, to simply wrap these two statements in a synchronized block?

synchronized(map) {
    if (!map.containsKey(key)) {
        map.put(key, new Set<V>());
    }
}

Is there a better way than locking the entire map? Is there a way to lock only the key, so that reads on other values of the map aren't locked out?

synchronized(key) {
    if (!map.containsKey(key)) {
        map.put(key, new Set<V>());
    }
}

Keep in mind that the keys are not necessarily the same object (they are specifically Class<?> types), but are equal by hashcode. Synchronizing by key may not work if synchronization requires object-address equality.

Problems with Set

The bigger issue, I think, is knowing if the set is being used properly. There are a few issues: adding objects, removing objects, and iterating objects.

Would wrapping the list in Collections.synchronizedList be enough to avoid concurrency issues in addObject and removeObject? I'm assuming that would be fine, as the synchronized wrapper would make them atomic operations.

However, iterating may be a different story. For iterateObjectsInternally, even if the set is synchronized, it still must be synchronized externally:

Set<V> set = getSet(key);
synchronized(set) {
    for (V value : set) {
        // thread-safe iteration
    }
}

However, this seems like an awful waste. What if, instead, we replace simply use CopyOnWriteArrayList or CopyOnWriteArraySet as the definition. Since iteration would simply use a snapshot of the array contents, there's no way to modify it from another thread. Also, CopyOnWriteArrayList uses a re-entrant lock on the add and remove methods, which means that add/remove would be inherently safe as well (as they are synchronized methods). CopyOnWriteArrayList seems attractive because the number of iterations on the internal structure vastly outweigh the number of modifications on the list. Also, with a copied iterator, there is no need to worry about addObject or removeObject messing up the iteration from iterateObjectInternally (ConcurrentModificationExceptions) in another thread.

Are these concurrency checks on the right track and/or rigorous enough? I'm a newbie with concurrent programming problems, and I may be missing something obvious, or over-thinking. I know there are a few similar questions, but my implementation seemed different enough to warrant asking the questions as specifically as I did.

1

2 Answers 2

1

You are definitely overthinking this. Use a simple ConcurrentHashMap, and ConcurrentSkipListSet/CopyOnWriteArraySet depending on your concurrency characteristics (mainly if iteration needs to take into account on-the-fly modifications of the data). Use something like the following snippet as the getSet method:

private Set<V> getSet(K key) {
    Set<V> rv = map.get(key);
    if (rv != null) {
        return rv;
    }
    map.putIfAbsent(key, new Set<V>());
    return map.get(key);
}

This will ensure proper lockless concurrency when adding/removing objects, for the iteration you will need to determine whether missing updates is an issue in your problem domain. if it's not an issue to miss a new object when it's added during the iteration, use the CopyOnWriteArraySet.

On the third hand, you want to take a deep look into what kind of granularity you can use w.r.t. concurrency, what your requirements are, what the proper behavior is in edge cases, and most of all, what performance and concurrency characteristics your code must cover - if it's something that happens twice on startup, I'd just make all methods synchronized and be done with it.

0

If you are going to be adding to the 'set' often, CopyOnWriteArrayList and CopyOnWriteArraySet are not going to be viable - They use far too many resources for add operations. However, If you are adding rarely, and iterating over the 'set' often, than they are your best bet.

The Java ConcurrentHashMap puts every single map into a bucket per se - your put if absent operation will lock the list when it searches for the key, and then, release the lock and put in the key. Definitely use the ConcurrentHashMap instead of the map.

Your getSet method could will be inherently slow, especially when synchronized - perhaps, you could preload all of the keys and the sets sooner than later.

I suggest you follow in line with what Louis Wasserman says, and see if your performance is decent with the Guava implementation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.