Una guía para ConcurrentMap

Programación

1. Información general

Los mapas son, naturalmente, uno de los estilos más extendidos de la colección de Java.

Y, lo que es más importante, HashMap no es una implementación segura para subprocesos, mientras que Hashtable proporciona seguridad para subprocesos al sincronizar operaciones.

Aunque Hashtable es seguro para subprocesos, no es muy eficiente. Otro mapa totalmente sincronizado , Collections.synchronizedMap, tampoco muestra una gran eficacia. Si queremos seguridad de subprocesos con alto rendimiento bajo alta concurrencia, estas implementaciones no son el camino a seguir.

Para resolver el problema, Java Collections Framework introdujo ConcurrentMap en Java 1.5 .

Las siguientes discusiones se basan en Java 1.8 .

2. ConcurrentMap

ConcurrentMap es una extensión de la interfaz de Map . Su objetivo es proporcionar una estructura y orientación para resolver el problema de conciliar el rendimiento con la seguridad de los subprocesos.

Al anular varios métodos predeterminados de la interfaz, ConcurrentMap brinda pautas para implementaciones válidas para proporcionar operaciones atómicas de seguridad de subprocesos y coherentes con la memoria.

Varias implementaciones predeterminadas se anulan , deshabilitando el soporte de clave / valor nulo :

  • getOrDefault
  • para cada
  • reemplaza todo
  • computeIfAbsent
  • computeIfPresent
  • calcular
  • unir

Las siguientes API también se anulan para admitir la atomicidad, sin una implementación de interfaz predeterminada:

  • putIfAbsent
  • eliminar
  • reemplazar (clave, oldValue, newValue)
  • reemplazar (clave, valor)

El resto de acciones se heredan directamente con básicamente coherencia con Map .

3. ConcurrentHashMap

ConcurrentHashMap es la implementación de ConcurrentMap lista para usar .

Para un mejor rendimiento, consiste en una matriz de nodos como cubos de tabla (solían ser segmentos de tabla antes de Java 8 ) bajo el capó, y utiliza principalmente operaciones CAS durante la actualización.

Los cubos de la tabla se inicializan de forma perezosa, en la primera inserción. Cada cubo se puede bloquear de forma independiente bloqueando el primer nodo del cubo. Las operaciones de lectura no se bloquean y las disputas de actualización se minimizan.

El número de segmentos necesarios es relativo al número de subprocesos que acceden a la tabla, de modo que la actualización en curso por segmento no sea más de una la mayor parte del tiempo.

Antes de Java 8 , el número de "segmentos" necesarios era relativo al número de subprocesos que acceden a la tabla, de modo que la actualización en curso por segmento no sería más de una la mayor parte del tiempo.

Es por eso que los constructores, en comparación con HashMap , proporcionan el argumento concurrencyLevel adicional para controlar la cantidad de subprocesos estimados para usar:

public ConcurrentHashMap(
public ConcurrentHashMap( int initialCapacity, float loadFactor, int concurrencyLevel)

Los otros dos argumentos: initialCapacity y loadFactor funcionaron de la misma manera que HashMap .

Sin embargo, desde Java 8 , los constructores solo están presentes por compatibilidad con versiones anteriores: los parámetros solo pueden afectar el tamaño inicial del mapa .

3.1. Seguridad del hilo

ConcurrentMap garantiza la coherencia de la memoria en las operaciones clave / valor en un entorno de subprocesos múltiples.

Las acciones en un hilo antes de colocar un objeto en un ConcurrentMap como clave o valor suceden antes de las acciones posteriores al acceso o eliminación de ese objeto en otro hilo.

Para confirmar, echemos un vistazo a un caso de inconsistencia de memoria:

@Test public void givenHashMap_whenSumParallel_thenError() throws Exception { Map map = new HashMap(); List sumList = parallelSum100(map, 100); assertNotEquals(1, sumList .stream() .distinct() .count()); long wrongResultCount = sumList .stream() .filter(num -> num != 100) .count(); assertTrue(wrongResultCount > 0); } private List parallelSum100(Map map, int executionTimes) throws InterruptedException { List sumList = new ArrayList(1000); for (int i = 0; i < executionTimes; i++) { map.put("test", 0); ExecutorService executorService = Executors.newFixedThreadPool(4); for (int j = 0; j  { for (int k = 0; k  value + 1 ); }); } executorService.shutdown(); executorService.awaitTermination(5, TimeUnit.SECONDS); sumList.add(map.get("test")); } return sumList; }

Para cada acción map.computeIfPresent en paralelo, HashMap no proporciona una vista coherente de lo que debería ser el valor entero actual, lo que genera resultados inconsistentes e indeseables.

En cuanto a ConcurrentHashMap , podemos obtener un resultado consistente y correcto:

@Test public void givenConcurrentMap_whenSumParallel_thenCorrect() throws Exception { Map map = new ConcurrentHashMap(); List sumList = parallelSum100(map, 1000); assertEquals(1, sumList .stream() .distinct() .count()); long wrongResultCount = sumList .stream() .filter(num -> num != 100) .count(); assertEquals(0, wrongResultCount); }

3.2. Clave / valor nulo

La mayoría de las API proporcionadas por ConcurrentMap no permiten claves o valores nulos , por ejemplo:

@Test(expected = NullPointerException.class) public void givenConcurrentHashMap_whenPutWithNullKey_thenThrowsNPE() { concurrentMap.put(null, new Object()); } @Test(expected = NullPointerException.class) public void givenConcurrentHashMap_whenPutNullValue_thenThrowsNPE() { concurrentMap.put("test", null); }

Sin embargo, para las acciones de cálculo * y combinación , el valor calculado puede ser nulo , lo que indica que la asignación de clave-valor se elimina si está presente o permanece ausente si no existía anteriormente .

@Test public void givenKeyPresent_whenComputeRemappingNull_thenMappingRemoved() { Object oldValue = new Object(); concurrentMap.put("test", oldValue); concurrentMap.compute("test", (s, o) -> null); assertNull(concurrentMap.get("test")); }

3.3. Soporte de transmisión

Java 8 también proporciona compatibilidad con Stream en ConcurrentHashMap .

A diferencia de la mayoría de los métodos de flujo, las operaciones masivas (secuenciales y paralelas) permiten la modificación simultánea de forma segura. No se lanzará ConcurrentModificationException , lo que también se aplica a sus iteradores. Relevante para las transmisiones, también se agregan varios métodos forEach * , buscar y reducir * para admitir operaciones de reducción de mapas y recorridos más ricos.

3.4. Actuación

Bajo el capó, ConcurrentHashMap es algo similar a HashMap , con acceso a datos y actualización basada en una tabla hash (aunque más compleja).

Y, por supuesto, ConcurrentHashMap debería producir un rendimiento mucho mejor en la mayoría de los casos simultáneos para la recuperación y actualización de datos.

Escribamos un micro-benchmark rápido para obtener y poner rendimiento y compararlo con Hashtable y Collections.synchronizedMap , ejecutando ambas operaciones 500,000 veces en 4 subprocesos.

@Test public void givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster() throws Exception { Map hashtable = new Hashtable(); Map synchronizedHashMap = Collections.synchronizedMap(new HashMap()); Map concurrentHashMap = new ConcurrentHashMap(); long hashtableAvgRuntime = timeElapseForGetPut(hashtable); long syncHashMapAvgRuntime = timeElapseForGetPut(synchronizedHashMap); long concurrentHashMapAvgRuntime = timeElapseForGetPut(concurrentHashMap); assertTrue(hashtableAvgRuntime > concurrentHashMapAvgRuntime); assertTrue(syncHashMapAvgRuntime > concurrentHashMapAvgRuntime); } private long timeElapseForGetPut(Map map) throws InterruptedException { ExecutorService executorService = Executors.newFixedThreadPool(4); long startTime = System.nanoTime(); for (int i = 0; i  { for (int j = 0; j < 500_000; j++) { int value = ThreadLocalRandom .current() .nextInt(10000); String key = String.valueOf(value); map.put(key, value); map.get(key); } }); } executorService.shutdown(); executorService.awaitTermination(1, TimeUnit.MINUTES); return (System.nanoTime() - startTime) / 500_000; }

Tenga en cuenta que los micro-benchmarks solo miran un escenario y no siempre son un buen reflejo del desempeño en el mundo real.

Dicho esto, en un sistema OS X con un sistema de desarrollo promedio, estamos viendo un resultado de muestra promedio para 100 ejecuciones consecutivas (en nanosegundos):

Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2

In a multi-threading environment, where multiple threads are expected to access a common Map, the ConcurrentHashMap is clearly preferable.

However, when the Map is only accessible to a single thread, HashMap can be a better choice for its simplicity and solid performance.

3.5. Pitfalls

Retrieval operations generally do not block in ConcurrentHashMap and could overlap with update operations. So for better performance, they only reflect the results of the most recently completed update operations, as stated in the official Javadoc.

There are several other facts to bear in mind:

  • results of aggregate status methods including size, isEmpty, and containsValue are typically useful only when a map is not undergoing concurrent updates in other threads:
@Test public void givenConcurrentMap_whenUpdatingAndGetSize_thenError() throws InterruptedException { Runnable collectMapSizes = () -> { for (int i = 0; i  { for (int i = 0; i < MAX_SIZE; i++) { concurrentMap.put(String.valueOf(i), i); } }; executorService.execute(updateMapData); executorService.execute(collectMapSizes); executorService.shutdown(); executorService.awaitTermination(1, TimeUnit.MINUTES); assertNotEquals(MAX_SIZE, mapSizes.get(MAX_SIZE - 1).intValue()); assertEquals(MAX_SIZE, concurrentMap.size()); }

If concurrent updates are under strict control, aggregate status would still be reliable.

Although these aggregate status methods do not guarantee the real-time accuracy, they may be adequate for monitoring or estimation purposes.

Note that usage of size() of ConcurrentHashMap should be replaced by mappingCount(), for the latter method returns a long count, although deep down they are based on the same estimation.

  • hashCode matters: note that using many keys with exactly the same hashCode() is a sure way to slow down a performance of any hash table.

To ameliorate impact when keys are Comparable, ConcurrentHashMap may use comparison order among keys to help break ties. Still, we should avoid using the same hashCode() as much as we can.

  • iterators are only designed to use in a single thread as they provide weak consistency rather than fast-fail traversal, and they will never throw ConcurrentModificationException.
  • the default initial table capacity is 16, and it's adjusted by the specified concurrency level:
public ConcurrentHashMap( int initialCapacity, float loadFactor, int concurrencyLevel) { //... if (initialCapacity < concurrencyLevel) { initialCapacity = concurrencyLevel; } //... }
  • caution on remapping functions: though we can do remapping operations with provided compute and merge* methods, we should keep them fast, short and simple, and focus on the current mapping to avoid unexpected blocking.
  • keys in ConcurrentHashMap are not in sorted order, so for cases when ordering is required, ConcurrentSkipListMap is a suitable choice.

4. ConcurrentNavigableMap

For cases when ordering of keys is required, we can use ConcurrentSkipListMap, a concurrent version of TreeMap.

As a supplement for ConcurrentMap, ConcurrentNavigableMap supports total ordering of its keys (in ascending order by default) and is concurrently navigable. Methods that return views of the map are overridden for concurrency compatibility:

  • subMap
  • headMap
  • tailMap
  • subMap
  • headMap
  • tailMap
  • descendingMap

keySet() views' iterators and spliterators are enhanced with weak-memory-consistency:

  • navigableKeySet
  • keySet
  • descendingKeySet

5. ConcurrentSkipListMap

Previously, we have covered NavigableMap interface and its implementation TreeMap. ConcurrentSkipListMap can be seen a scalable concurrent version of TreeMap.

In practice, there's no concurrent implementation of the red-black tree in Java. A concurrent variant of SkipLists is implemented in ConcurrentSkipListMap, providing an expected average log(n) time cost for the containsKey, get, put and remove operations and their variants.

In addition to TreeMap‘s features, key insertion, removal, update and access operations are guaranteed with thread-safety. Here's a comparison to TreeMap when navigating concurrently:

@Test public void givenSkipListMap_whenNavConcurrently_thenCountCorrect() throws InterruptedException { NavigableMap skipListMap = new ConcurrentSkipListMap(); int count = countMapElementByPollingFirstEntry(skipListMap, 10000, 4); assertEquals(10000 * 4, count); } @Test public void givenTreeMap_whenNavConcurrently_thenCountError() throws InterruptedException { NavigableMap treeMap = new TreeMap(); int count = countMapElementByPollingFirstEntry(treeMap, 10000, 4); assertNotEquals(10000 * 4, count); } private int countMapElementByPollingFirstEntry( NavigableMap navigableMap, int elementCount, int concurrencyLevel) throws InterruptedException { for (int i = 0; i < elementCount * concurrencyLevel; i++) { navigableMap.put(i, i); } AtomicInteger counter = new AtomicInteger(0); ExecutorService executorService = Executors.newFixedThreadPool(concurrencyLevel); for (int j = 0; j  { for (int i = 0; i < elementCount; i++) { if (navigableMap.pollFirstEntry() != null) { counter.incrementAndGet(); } } }); } executorService.shutdown(); executorService.awaitTermination(1, TimeUnit.MINUTES); return counter.get(); }

Una explicación completa de las preocupaciones sobre el desempeño detrás de escena está más allá del alcance de este artículo. Los detalles se pueden encontrar en el Javadoc de ConcurrentSkipListMap , que se encuentra en java / util / concurrent en el archivo src.zip .

6. Conclusión

En este artículo, presentamos principalmente la interfaz ConcurrentMap y las características de ConcurrentHashMap y cubrimos que ConcurrentNavigableMap requiere el pedido de claves.

El código fuente completo de todos los ejemplos utilizados en este artículo se puede encontrar en el proyecto GitHub.