Lambdas for concurrent maps

April 16, 2020

The package java.util.concurrent contains two concurrent maps, the class ConcurrentHashMap, and the class ConcurrentSkipListMap. Both classes are thread-safe and high performant. But using them is error-prone because of read modify write race conditions. Here come lambda expressions into the play. Lambda expressions help us to avoid these race conditions elegantly.

Let us see how.

Read modify write race condition

The race condition happens when we read an element from the map, modify this element and write the element back into the map. Like in the following example:

import com.vmlens.api.AllInterleavings;
public class TestUpdateWrong {
	public void update(ConcurrentHashMap<Integer, Integer> map) {
		Integer result = map.get(1);
		if (result == null) {
			map.put(1, 1);
		} else {
			map.put(1, result + 1);
		}
	}
	@Test
	public void testUpdate() throws InterruptedException {
		try (AllInterleavings allInterleavings = 
			new AllInterleavings("TestUpdateWrong");) {
			while (allInterleavings.hasNext()) {
				final ConcurrentHashMap<Integer, Integer> map = 
						new ConcurrentHashMap<Integer, Integer>();
				Thread first = new Thread(() -> {
					update(map);
				});
				Thread second = new Thread(() -> {
					update(map);
				});
				first.start();
				second.start();
				first.join();
				second.join();
				assertEquals(2, map.get(1).intValue());
			}
		}
	}

}

You can download the source code of the example from Github here.

Here we implement a per-key counter. In the update method, we initialize the count to 1 if no mapping exists otherwise we increment the count by one. To reproduce the race condition we update the map from two different threads. After both threads are stopped we check if the value is indeed two.

To test all thread interleavings we put the complete test in a while loop iterating over all thread interleavings using the class AllInterleavings from vmlens, line 15. Running the test we see the following error:

java.lang.AssertionError: expected:<2> but was:<1>

To see why the result is one and not two as expected we can look at the report vmlens generated:

The problem is that the update method is not atomic. Both threads can read the same. This lets the last thread override the result of the first thread.

Avoiding read modify write race condition with lambda expressions

To avoid this race condition we need a way to execute all three operations, the read, the modification and the write in one atomic method call. The method compute does exactly this using a lambda expression:

public void update(
	ConcurrentHashMap<Integer,Integer>  map ) {
	map.compute(1, (key, value) -> {
		if (value == null) {
			return 1;
		 } 
			return value + 1;
	});
}

Now the read modify write operations happen in one atomic method and the race disappears.

Lambdas should be pure

What properties should a lambda function have?

The lambda expressions in the ConcurrentHashMap get executed under a synchronized block on a bin entry of the hash map. Therefore you must not call another writing operation of this ConcurrentHashMap instance. Otherwise, this can lead to deadlocks, as shown in this blog post.

When we use a ConcurrentSkipListMap on the other side our lambda expressions might be called multiple times, since this map uses an optimistic concurrency scheme. To not depend on implementation details the general advice is to make lambda expression pure. This means they should have no side effects and simply calculate a new immutable value from a given immutable value.

Conclusion

Lambda expressions help to avoid read modify write race conditions elegantly. When using lambda expressions the elements in the collection should be immutable. And the lambda function itself should be pure.

© 2020 vmlens Legal Notice Privacy Policy