Atomically incrementing counters stored in ConcurrentHashMap

Question

I would like to collect some metrics from various places in a web app. To keep it simple, all these will be counters and therefore the only modifier operation is to increment them by 1.

The increments will be concurrent and often. The reads (dumping the stats) is a rare operation.

I was thinking to use a ConcurrentHashMap. The issue is how to increment the counters correctly. Since the map doesn't have an "increment" operation, I need to read the current value first, increment it than put the new value in the map. Without more code, this is not an atomic operation.

Is it possible to achieve this without synchronization (which would defeat the purpose of the ConcurrentHashMap)? Do I need to look at Google Collections ?

Thanks for any pointers.

PS There is a related question on SO (http://stackoverflow.com/questions/81346/most-efficient-way-to-increment-a-map-value-in-java) but focused on performance and not multi-threading

EDIT: For those arriving here through searches on the same topic: besides the answers below, there's a useful presentation which incidentally covers the same topic. See slides 24-33.

Answer 1

Please take a look at this thread http://stackoverflow.com/questions/2539654/java-concurrency-many-writers-one-reader/2539761#2539761

The answer I gave would probably be the most efficient way to increment a value pulled from a ConcurrentHashMap

Answer 2

You're pretty close. Why don't you try something like a ConcurrentHashMap<Key, AtomicLong>? If your Keys (metrics) are unchanging, you could even just use a standard HashMap (they are threadsafe if readonly, but you'd be well advised to make this explicit with an ImmutableMap from Google Collections or Collections.unmodifiableMap, etc.).

This way, you can use map.get(myKey).incrementAndGet() to bump statistics.

Answer 3

Other than going with AtomicLong, you can do the usual cas-loop thing:

private final ConcurrentMap<Key,Long> counts =
    new ConcurrentHashMap<Key,Long>();

public void increment(Key key) {
    if (counts.putIfAbsent(key, 1)) == null) {
        return;
    }

    Long old;
    do {
       old = counts.get(key);
    } while (!counts.replace(key, old, old+1)); // Assumes no removal.
}

(I've not written a do-while loop for ages.)

For small values the Long will probably be "cached". For longer values, it may require allocation. But the allocations are actually extremely fast (and you can cache further) - depends upon what you expect, in the worst case.