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

Thanks for any pointers.

---

P.S.
There is a related question on SO (Most efficient way to increment a Map value in Java) but focused on performance and not multi-threading

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

Solution 1

In Java 8:

ConcurrentHashMap<String, LongAdder> map = new ConcurrentHashMap<>();

map.computeIfAbsent("key", k -> new LongAdder()).increment();

Solution 2

Guava's new AtomicLongMap (in release 11) might address this need.

Solution 3

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.

Solution 4

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.

Solution 5

Got a necessity to do the same. I'm using ConcurrentHashMap + AtomicInteger. Also, ReentrantRW Lock was introduced for atomic flush(very similar behavior).

Tested with 10 Keys and 10 Threads per each Key. Nothing was lost. I just haven't tried several flushing threads yet, but hope it will work.

Massive singleusermode flush is torturing me... I want to remove RWLock and break down flushing into small pieces. Tomorrow.

private ConcurrentHashMap<String,AtomicInteger> counters = new ConcurrentHashMap<String, AtomicInteger>();
private ReadWriteLock rwLock = new ReentrantReadWriteLock();

public void count(String invoker) {

    rwLock.readLock().lock();

    try{
        AtomicInteger currentValue = counters.get(invoker);
        // if entry is absent - initialize it. If other thread has added value before - we will yield and not replace existing value
        if(currentValue == null){
            // value we want to init with
            AtomicInteger newValue = new AtomicInteger(0);
            // try to put and get old
            AtomicInteger oldValue = counters.putIfAbsent(invoker, newValue);
            // if old value not null - our insertion failed, lets use old value as it's in the map
            // if old value is null - our value was inserted - lets use it
            currentValue = oldValue != null ? oldValue : newValue;
        }

        // counter +1
        currentValue.incrementAndGet();
    }finally {
        rwLock.readLock().unlock();
    }

}

/**
 * @return Map with counting results
 */
public Map<String, Integer> getCount() {
    // stop all updates (readlocks)
    rwLock.writeLock().lock();
    try{
        HashMap<String, Integer> resultMap = new HashMap<String, Integer>();
        // read all Integers to a new map
        for(Map.Entry<String,AtomicInteger> entry: counters.entrySet()){
            resultMap.put(entry.getKey(), entry.getValue().intValue());
        }
        // reset ConcurrentMap
        counters.clear();
        return resultMap;

    }finally {
        rwLock.writeLock().unlock();
    }

}

View more solutions

Comments

[Enno Shioji]

Just don't forget to store the HashMap in a final member. And better wrap the map in a unmodifiable wrapper. Better yet, you can use ImmutableMap from Guava (superset of google collection) and it should be really really fast.

[Brett]

I think that's right. Apologies to anyone looking at the previous broken code. (You could rearrange it so that it starts off with a get, a compare to null and only then try putIfAbsent, continuing with a normal while loop.)

[Steven Schlansker]

@Zwei: good point, edited the answer to include that advice :)

[wishihadabettername]

The list of metrics is built as they supply data (i.e. the map's keys will be added as the system runs and various collection points are hit; building the list a priori would be error-prone). I forgot about AtomicLong's incrementAndGet(), it's just what I need. If it didn't exist, I was thinking that another approach would have been for the metrics collectors not to increase the counters, but simply to add the request to do so in a queue maintained by the singleton. Thus, the callers only add() to a list, which periodically is read and processed. Not as simple, though.

[snowindy]

This is a perfect answer! Compare probability of concurrency mistake between Guava vs listed here custom code samples.

[pacman]

in short form with link on method: LongAdder::increment

[pacman]

I meant java 8 method on link: AtomicInteger atomicInt = new AtomicInteger(0); atomicInt::incrementAndGet

[pacman]

You can use "more functional" approach in the code above

[ZhekaKozlov]

@pacman Can you provide exact code? I don't think my answer can be more functional.

[pacman]

Map<String, LongAdder> map = new ConcurrentHashMap<>(); Consumer<LongAdder> function = LongAdder::increment; function.accept(map.get("key"));

[pacman]

I implied that Consumer is a reference on the method that invokes incrementing, it's a controversial question is link on function a part of FP

[rebeliagamer]

+1 This solution is suggested in docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomi‌​c/…

[Sudhakar]

For every time getCount is called its going to prevent the writes. This will guarantee value consistency.But will impacts performance.