Una guida a ConcurrentMap

1. Panoramica

Le mappe sono naturalmente uno degli stili più diffusi nella raccolta Java.

E, soprattutto, HashMap non è un'implementazione thread-safe, mentre Hashtable fornisce thread-safety sincronizzando le operazioni.

Anche se Hashtable è thread-safe, non è molto efficiente. Anche un'altra mappa completamente sincronizzata , Collections.synchronizedMap, non mostra una grande efficienza. Se vogliamo la sicurezza dei thread con un throughput elevato in condizioni di concorrenza elevata, queste implementazioni non sono la strada da percorrere.

Per risolvere il problema, Java Collections Framework ha introdotto ConcurrentMap in Java 1.5 .

Le discussioni seguenti sono basate su Java 1.8 .

2. ConcurrentMap

ConcurrentMap è un'estensione dell'interfaccia Map . Ha lo scopo di fornire una struttura e una guida per risolvere il problema della riconciliazione del throughput con la sicurezza dei thread.

Ignorando diversi metodi predefiniti dell'interfaccia, ConcurrentMap fornisce linee guida per implementazioni valide per fornire operazioni atomiche coerenti con la memoria e thread-safety.

Diverse implementazioni predefinite vengono sovrascritte, disabilitando il supporto chiave / valore null :

  • getOrDefault
  • per ciascuno
  • sostituisci tutto
  • computeIfAbsent
  • computeIfPresent
  • calcolare
  • unire

Anche le seguenti API vengono sovrascritte per supportare l'atomicità, senza un'implementazione dell'interfaccia predefinita:

  • putIfAbsent
  • rimuovere
  • sostituire (chiave, vecchioValore, nuovoValore)
  • sostituire (chiave, valore)

Il resto delle azioni vengono ereditate direttamente con sostanzialmente coerente con Map .

3. ConcurrentHashMap

ConcurrentHashMap è l' implementazione di ConcurrentMap pronta per l'uso .

Per prestazioni migliori, consiste in un array di nodi come bucket di tabella (utilizzati per essere segmenti di tabella prima di Java 8 ) sotto il cofano e utilizza principalmente operazioni CAS durante l'aggiornamento.

I bucket di tabella vengono inizializzati pigramente, al primo inserimento. Ogni bucket può essere bloccato in modo indipendente bloccando il primo nodo nel bucket. Le operazioni di lettura non si bloccano e le controversie di aggiornamento sono ridotte al minimo.

Il numero di segmenti richiesti è relativo al numero di thread che accedono alla tabella in modo che l'aggiornamento in corso per segmento non sia più di uno per la maggior parte del tempo.

Prima di Java 8 , il numero di "segmenti" richiesti era relativo al numero di thread che accedevano alla tabella in modo che l'aggiornamento in corso per segmento non fosse più di uno per la maggior parte del tempo.

Ecco perché i costruttori, rispetto a HashMap , forniscono l' argomento concurrencyLevel aggiuntivo per controllare il numero di thread stimati da utilizzare:

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

Gli altri due argomenti: initialCapacity e loadFactor hanno funzionato allo stesso modo di HashMap .

Tuttavia, a partire da Java 8 , i costruttori sono presenti solo per compatibilità con le versioni precedenti: i parametri possono influenzare solo la dimensione iniziale della mappa .

3.1. Thread-Safety

ConcurrentMap garantisce la consistenza della memoria sulle operazioni chiave / valore in un ambiente multi-threading.

Le azioni in un thread prima di posizionare un oggetto in una ConcurrentMap come chiave o valore si verificano prima delle azioni successive all'accesso o alla rimozione di quell'oggetto in un altro thread.

Per confermare, diamo un'occhiata a un caso di memoria inconsistente:

@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; }

Per ogni azione map.computeIfPresent in parallelo, HashMap non fornisce una visione coerente di quello che dovrebbe essere il valore intero attuale, portando a risultati incoerenti e indesiderabili.

Per quanto riguarda ConcurrentHashMap , possiamo ottenere un risultato coerente e corretto:

@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. Valore / chiave null

La maggior parte delle API fornite da ConcurrentMap non consente una chiave o un valore nulli , ad esempio:

@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); }

Tuttavia, per le azioni di calcolo * e unione , il valore calcolato può essere nullo , il che indica che la mappatura valore-chiave viene rimossa se presente o rimane assente se precedentemente assente .

@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. Supporto streaming

Java 8 fornisce anche il supporto Stream in ConcurrentHashMap .

A differenza della maggior parte dei metodi di flusso, le operazioni di massa (sequenziali e parallele) consentono la modifica simultanea in modo sicuro. ConcurrentModificationException non verrà generata, il che si applica anche ai suoi iteratori. Rilevanti per i flussi, vengono aggiunti anche diversi metodi forEach * , search e reduce * per supportare operazioni di attraversamento più ricche e di riduzione della mappa.

3.4. Prestazione

Sotto il cofano, ConcurrentHashMap è in qualche modo simile a HashMap , con accesso ai dati e aggiornamento basato su una tabella hash (anche se più complessa).

E, naturalmente, ConcurrentHashMap dovrebbe fornire prestazioni molto migliori nella maggior parte dei casi simultanei per il recupero e l'aggiornamento dei dati.

Scriviamo un rapido micro-benchmark per ottenere e mettere le prestazioni e confrontarlo con Hashtable e Collections.synchronizedMap , eseguendo entrambe le operazioni per 500.000 volte in 4 thread.

@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; }

Tieni presente che i micro-benchmark guardano solo a un singolo scenario e non sono sempre un buon riflesso delle prestazioni del mondo reale.

Detto questo, su un sistema OS X con un sistema di sviluppo medio, stiamo vedendo un risultato campione medio per 100 esecuzioni consecutive (in nanosecondi):

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 spiegazione completa delle preoccupazioni legate alla performance dietro le quinte va oltre lo scopo di questo articolo. I dettagli possono essere trovati in Javadoc di ConcurrentSkipListMap , che si trova in java / util / concurrent nel file src.zip .

6. Conclusione

In questo articolo, abbiamo introdotto principalmente l' interfaccia ConcurrentMap e le funzionalità di ConcurrentHashMap e abbiamo trattato ConcurrentNavigableMap che richiede l'ordinamento delle chiavi.

Il codice sorgente completo per tutti gli esempi utilizzati in questo articolo può essere trovato nel progetto GitHub.