Mapa concurrente de Java

El Java Collections Framework versión 1.5 y posteriores del lenguaje de programación Java define e implementa los mapas originales regulares de un solo hilo, y también nuevos mapas seguros para hilos que implementan la interfaz entre otras interfaces concurrentes. ^{[ 1 ]} En Java 1.6, se agregó la interfaz, extendiendo , y la interfaz se agregó como una combinación de subinterfaz.java.util.concurrent.ConcurrentMapjava.util.NavigableMapjava.util.SortedMapjava.util.concurrent.ConcurrentNavigableMap

El diagrama de interfaz de la versión 1.8 java.util.Map<K, V>tiene la forma que se muestra a continuación. Los conjuntos pueden considerarse subcasos de mapas correspondientes en los que los valores son siempre una constante particular que puede ignorarse, aunque la java.util.Set<E>API utiliza métodos correspondientes pero con nombres diferentes. En la parte inferior se encuentra java.util.concurrent.ConcurrentNavigableMap<K, V>, que es una herencia múltiple.

• java.util.Collection
  • java.util.Map
    • java.util.SortedMap
      • java.util.NavigableMap
        • java.util.concurrent.ConcurrentNavigableMap
    • java.util.concurrent.ConcurrentMap
      • java.util.concurrent.ConcurrentNavigableMap

Uno de los problemas resueltos por el java.util.concurrent<K, V>paquete Java 1.5 es el de la modificación concurrente. Las clases de colección que proporciona pueden ser utilizadas de forma fiable por múltiples java.lang.Threads.

Todos los mapas y otras colecciones compartidas por subprocesos que no son concurrentes necesitan usar alguna forma de bloqueo explícito, como la sincronización nativa, para evitar la modificación concurrente, o bien debe haber una forma de demostrar desde la lógica del programa que la modificación concurrente no puede ocurrir. La modificación concurrente de un mapa java.lang.Map<K, V>por múltiples subprocesos a veces destruirá la consistencia interna de las estructuras de datos dentro del mapa java.lang.Map<K, V>, lo que lleva a errores que se manifiestan raramente o de forma impredecible, y que son difíciles de detectar y corregir. Además, la modificación concurrente por un subproceso con acceso de lectura por otro u otros subprocesos a veces dará resultados impredecibles al lector, aunque la consistencia interna del mapa no se destruirá. Usar lógica de programa externa para evitar la modificación concurrente aumenta la complejidad del código y crea un riesgo impredecible de errores en el código existente y futuro, aunque permite el uso de colecciones no concurrentes. Sin embargo, ni los bloqueos ni la lógica del programa pueden coordinar subprocesos externos que puedan entrar en contacto con el mapa java.util.Collection<E>.

public V put ( K key , V value ) { synchronized ( mutex ) { return m . put ( key , value ); } }

import java.util.Collections ; import java.util.Map ;Mapa < Cadena , Cadena > wrappedMap = Collections . synchronizedMap ( mapa );synchronized ( wrappedMap ) { for ( String s : wrappedMap . keySet ()) { // alguna operación posiblemente larga ejecutada posiblemente // muchas veces, retrasando todos los demás accesos } }

import java.util.HashMap ; import java.util.Map ;Mapa < Cadena , Cadena > mapa = nuevo HashMap <> ();// Hilo A // Usa el mapa mismo como bloqueo. En su lugar, se puede usar cualquier objeto acordado. synchronized ( map ) { map . put ( "key" , "value" ); }// Hilo B sincronizado ( mapa ) { String resultado = mapa.obtener ( "clave" ); // ... }// Hilo C sincronizado ( mapa ) { para ( Mapa.Entrada < String , String > s : mapa.EntradaSet ( )) { /* *  Alguna operación posiblemente lenta, que retrasa todas las demás operaciones supuestamente rápidas.  * La sincronización en iteraciones individuales no es posible. *  / // ... } }

import java.util.Map ; import java.util.concurrent.locks.ReadWriteLock ; import java.util.concurrent.locks.ReentrantReadWriteLock ;final ReentrantReadWriteLock lock = new ReentrantReadWriteLock (); final ReadWriteLock readLock = lock . readLock (); final ReadWriteLock writeLock = lock . writeLock ();// Hilo A try { writeLock.lock ( ); map.put ( " key" , "value" ); } finally { writeLock.unlock ( ) ; }// Hilo B intentar { leerLock.bloquear ( ) ; String s = map.obtener ( " clave" ); } finalmente { leerLock.desbloquear ( ) ; }// Hilo C try { readLock.lock ( ); for ( Map.Entry < String , String > s : map.entrySet ( ) ) { /*  * Alguna operación posiblemente lenta, que retrasa todas las demás operaciones supuestamente rápidas. * La  sincronización en iteraciones individuales no es posible.  */ // ... } } finally { readLock.unlock ( ) ; }

La exclusión mutua tiene un problema de convoy de bloqueo , en el que los hilos pueden acumularse en un bloqueo, lo que hace que la JVM necesite mantener costosas colas de espera y "estacionar" los java.lang.Threads en espera. Estacionar y desestacionar un s es costoso , y puede ocurrir un cambio de contextojava.lang.Thread lento . Los cambios de contexto requieren de microsegundos a milisegundos, mientras que las operaciones básicas del mapa normalmente tardan nanosegundos. El rendimiento puede caer a una pequeña fracción del rendimiento de un solo s a medida que aumenta la contención. Cuando no hay contención o hay poca contención por el bloqueo, hay poco impacto en el rendimiento; sin embargo, excepto por la prueba de contención del bloqueo. Las JVM modernas insertarán en línea la mayor parte del código del bloqueo, reduciéndolo a solo unas pocas instrucciones, lo que mantiene el caso sin contención muy rápido. Las técnicas reentrantes como la sincronización nativa o sin embargo tienen un lastre adicional que reduce el rendimiento en el mantenimiento de la profundidad de reentrada, lo que afecta también al caso sin contención. El problema del convoy parece estar disminuyendo con las JVM modernas, pero puede quedar oculto por un cambio de contexto lento: en este caso, la latencia aumentará, pero el rendimiento seguirá siendo aceptable. Con cientos de s, un tiempo de cambio de contexto de 10 ms produce una latencia de segundos.java.lang.Threadjava.util.concurrent.locks.ReentrantReadWriteLockjava.lang.Thread

Las soluciones de exclusión mutua no aprovechan toda la potencia de cálculo de un sistema multinúcleo, ya que solo java.lang.Threadse permite un núcleo dentro del java.util.Map<K, V>código a la vez. Las implementaciones de los mapas concurrentes específicos proporcionados por Java Collections Framework y otros a veces aprovechan los múltiples núcleos mediante técnicas de programación sin bloqueocompareAndSet() . Estas técnicas utilizan operaciones como el método intrínseco disponible en muchas clases de Java para AtomicReferencerealizar actualizaciones condicionales de algunas estructuras internas de Map de forma atómica. La compareAndSet()primitiva se amplía en las clases de JCF con código nativo que puede realizar compareAndSet en partes internas especiales de algunos objetos para ciertos algoritmos (utilizando acceso "inseguro"). Las técnicas son complejas y a menudo dependen de las reglas de comunicación entre hilos proporcionadas por variables volátiles, la relación happen-before y tipos especiales de "bucles de reintento" sin bloqueo (que no son como los spin locks, ya que siempre producen progreso). compareAndSet()Dependen de instrucciones especiales específicas del procesador. Es posible que cualquier código Java utilice para otros fines el compareAndSet()método en varias clases concurrentes para lograr concurrencia sin bloqueo o incluso sin espera, lo que proporciona una latencia finita. Las técnicas sin bloqueo son sencillas en muchos casos comunes y con algunas colecciones simples como las pilas.

El diagrama indica cómo la sincronización mediante Collections.synchronizedMap(java.util.Map)el envoltorio de un regular HashMap(púrpura) puede no escalar tan bien como ConcurrentHashMap(rojo). Los otros son los ordenados java.util.concurrent.ConcurrentNavigableMap<K, V>( java.util.concurrent.AirConcurrentMap<K, V>azul) y java.util.concurrent.ConcurrentSkipListMap<K, V>(CSLM verde). (Los puntos planos pueden ser rehashes que producen tablas más grandes que el nursery y java.util.concurrent.ConcurrentHashMap<K, V>ocupan más espacio. Nótese que el eje y debería decir 'puts K'. El sistema es un i7 de 8 núcleos a 2,5  GHz, con -Xms5000m para evitar el GC). El GC y la expansión del proceso JVM cambian las curvas considerablemente, y algunas técnicas internas sin bloqueo generan basura en la contención.

Otro problema con los enfoques de exclusión mutua es que la suposición de atomicidad completa que hace cierto código de un solo hilo crea retrasos entre hilos esporádicos inaceptablemente largos en un entorno concurrente. En particular, los iteradores y las operaciones masivas como putAll()y otras pueden tomar un tiempo proporcional al java.util.Map<K, V>tamaño, retrasando otros que esperan una latencia predeciblemente baja para operaciones no masivas. Por ejemplo, un servidor webjava.lang.Thread multihilo no puede permitir que algunas respuestas se retrasen por iteraciones de larga duración de otros hilos que ejecutan otras solicitudes que buscan un valor particular. Relacionado con esto está el hecho de que los que bloquean en realidad no tienen ningún requisito de liberar el bloqueo, y un bucle infinito en el propietario puede propagar un bloqueo permanente a otros . Los propietarios lentos a veces pueden ser interrumpidos. Los mapas hash también están sujetos a retrasos espontáneos durante el rehashing.java.lang.Threadjava.util.Map<K, V>Threadjava.lang.Threadjava.lang.Thread

La java.util.concurrentsolución de los paquetes al problema de modificación concurrente, el problema de convoy, el problema de latencia predecible y el problema multinúcleo incluye una elección arquitectónica llamada consistencia débil. Esta elección significa que las lecturas como get(java.lang.Object)no se bloquearán incluso cuando las actualizaciones estén en progreso, y es permisible incluso que las actualizaciones se superpongan entre sí y con las lecturas. La consistencia débil permite, por ejemplo, que el contenido de un java.util.concurrent.ConcurrentMap<K, V>cambie durante una iteración del mismo por un solo java.lang.Thread. ^{[ 7 ]} Los iteradores están diseñados para ser utilizados por uno java.lang.Threada la vez. Así, por ejemplo, un Mapque contiene dos entradas que son interdependientes puede ser visto de manera inconsistente por un lector Threaddurante la modificación por otro java.lang.Thread. Una actualización que se supone que cambia la clave de un Map.Entry(k1, v)a un Map.Entry(k2, v)atómicamente necesitaría hacer un remove(k1)y luego un put(k2, v), mientras que una iteración podría perder la entrada o verla en dos lugares. Las recuperaciones devuelven el valor para una clave dada que refleja la última actualización completada anterior para esa clave. Por lo tanto, hay una relación 'sucede antes'.

No hay forma de que java.util.concurrent.ConcurrentMap<K, V>s bloquee toda la tabla. No hay posibilidad de java.util.ConcurrentModificationExceptionque como ocurre con la modificación concurrente inadvertida de java.util.Map<K, V>s no concurrentes. El size()método puede tardar mucho tiempo, a diferencia de los s no concurrentes correspondientes java.util.Map<K, V>y otras colecciones que normalmente incluyen un campo de tamaño para un acceso rápido, porque pueden necesitar escanear todo java.util.Map<K, V>de alguna manera. Cuando se producen modificaciones concurrentes, los resultados reflejan el estado de java.util.Map<K, V>en algún momento, pero no necesariamente un único estado consistente, por lo tanto size(), isEmpty()y containsValue(java.lang.Object)puede ser mejor usarlo solo para monitorización.

Hay algunas operaciones proporcionadas por java.util.concurrent.ConcurrentMap<K, V>que no están en java.util.Map<K, V>(de la que hereda) para permitir la atomicidad de las modificaciones. replace(K, v1, v2)Comprobará la existencia de v1en el java.util.Map.Entry<K, V>identificado por Ky solo si se encuentra, entonces v1se reemplaza por v2atómicamente. El nuevo replace(k, v)hará un put(k, v)solo si kya está en el java.util.Map<K, V>. Además, putIfAbsent(k, v)hará un put(k, v)solo si kno está ya en el java.util.Map<K, V>, y remove(k, v)eliminará el java.util.Map.Entry<K, V>para vsolo si vestá presente. Esta atomicidad puede ser importante para algunos casos de uso multihilo, pero no está relacionada con la restricción de consistencia débil.

Para java.util.concurrent.ConcurrentMap<K, V>s, los siguientes son atómicos.

m.putIfAbsent(k, v)es atómico pero equivalente a:

if ( k == null || v == null ) { throw new NullPointerException (); }if ( ! m . containsKey ( k )) { return m . put ( k , v ); } else { return m . get ( k ); }

m.replace(k, v) es atómico pero equivalente a:

if ( k == null || v == null ) { throw new NullPointerException (); }if ( m . containsKey ( k )) { return m . put ( k , v ); } else { return null ; }

m.replace(k, v1, v2) es atómico pero equivalente a:

if ( k == null || v1 == null || v2 == null ) { throw new NullPointerException (); }if ( m . containsKey ( k ) && Objects . equals ( m . get ( k ), v1 )) { m . put ( k , v2 ); return true ; } else return false ; }

m.remove(k, v) es atómico pero equivalente a:

// Si Map no admite claves o valores nulos (aparentemente de forma independiente) if ( k == null || v == null ) { throw new NullPointerException (); }if ( m . containsKey ( k ) && Objects . equals ( m . get ( k ), v )) { m . remove ( k ); return true ; } else return false ; }

Debido a que java.util.Map<K, V>y java.util.concurrent.ConcurrentMap<K, V>son interfaces, no se pueden agregar nuevos métodos a ellas sin romper las implementaciones. Sin embargo, Java 1.8 agregó la capacidad para implementaciones de interfaz predeterminadas y agregó a la Mapinterfaz implementaciones predeterminadas de algunos métodos nuevos getOrDefault(Object, V), forEach(BiConsumer), replaceAll(BiFunction), computeIfAbsent(K, Function), computeIfPresent(K, BiFunction), compute(K,BiFunction), y merge(K, V, BiFunction). Las implementaciones predeterminadas en java.util.Map<K, V>no garantizan atomicidad, pero en las java.util.concurrent.ConcurrentMap<K, V>predeterminadas de anulación estas usan técnicas sin bloqueo para lograr atomicidad, y las implementaciones existentes java.util.concurrent.ConcurrentMap<K, V>serán automáticamente atómicas. Las técnicas sin bloqueo pueden ser más lentas que las anulaciones en las clases concretas, por lo que las clases concretas pueden optar por implementarlas atómicamente o no y documentar las propiedades de concurrencia.

Es posible utilizar técnicas sin bloqueojava.util.concurrent.ConcurrentMap<K, V> con s porque incluyen métodos con un número de consenso suficientemente alto, es decir, infinito , lo que significa que cualquier número de java.lang.Threads puede coordinarse. Este ejemplo podría implementarse con Java 8 merge(), pero muestra el patrón general sin bloqueo, que es más general. Este ejemplo no está relacionado con los detalles internos de , java.util.concurrent.ConcurrentMap<K, V>sino con el uso que hace el código cliente de java.util.concurrent.ConcurrentMap<K, V>. Por ejemplo, si queremos multiplicar un valor en el Mapa por una constante Nde forma atómica:

importar java.util.concurrent.ConcurrentMap ;estático final largo N = 10 ;void atomicMultiply ( ConcurrentMap < Long , Long > map , long key ) { while ( true ) { Long oldValue = map.get ( key ); // Suponiendo que oldValue no es nulo. Esta es la operación de 'carga útil' y no debería tener efectos secundarios debido a un posible recálculo en caso de conflicto . Long newValue = oldValue * N ; if ( map.replace ( key , oldValue , newValue ) ) { break ; } } }

También putIfAbsent(k, v)es útil cuando se permite que la entrada para la clave esté ausente. Este ejemplo podría implementarse con Java 8 compute(), pero muestra el patrón general sin bloqueo, que es más general. replace(k, v1, v2)No acepta parámetros nulos, por lo que a veces es necesaria una combinación de ellos. En otras palabras, si v1es nulo, putIfAbsent(k, v2)se invoca, de lo contrario replace(k, v1, v2)se invoca.

importar java.util.concurrent.ConcurrentMap ;void atomicMultiplyNullable ( ConcurrentMap < Long , Long > map , long key ) { while ( true ) { long oldValue = map.get ( key ); // Esta es la operación de 'carga útil' y no debería tener efectos secundarios debido a un posible recálculo en caso de conflicto long newValue = oldValue == null ? INITIAL_VALUE : oldValue * N ; if ( replaceNullable ( map , key , oldValue , newValue ) ) { break ; } } }static boolean replaceNullable ( ConcurrentMap < Long , Long > map , long key , long v1 , long v2 ) { return v1 == null ? map . putIfAbsent ( key , v2 ) == null : map . replace ( key , v1 , v2 ); }

El marco de colecciones de Java fue diseñado y desarrollado principalmente por Joshua Bloch y se introdujo en JDK 1.2 . ^{[ 8 ]} Las clases de concurrencia originales provenían del paquete de colecciones de Doug Lea . ^{[ 9 ]}

• Marco de colecciones de Java
• Contenedor (estructura de datos)
• Concurrencia en Java
• Sin cerradura

• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Java Concurrency in Practice . Addison Wesley. ISBN 0-321-34960-1. OL 25208908M . 
• Lea, Doug (1999). Programación concurrente en Java: principios y patrones de diseño . Addison Wesley. ISBN 0-201-31009-0. OL 55044M . 

• Lecciones de colecciones
• Tutorial de la colección Java 6 - Por Jakob Jenkov, Kadafi Kamphulusa
• Domando al tigre: El marco de las colecciones
• 'El marco de colecciones' (documentación de Oracle Java SE 8)
• 'Los tutoriales de Java - Colecciones' de Josh Bloch
• ¿Qué colección de Java debo usar? — Un práctico diagrama de flujo para simplificar la selección de colecciones.
• ¿Qué colección de Java usar? — por Janeve George