java - ConcurrentHashMap pegado en bucle-¿Por qué?
deadlock (4)
Como otros ya han dicho: no es un punto muerto, sino un bucle infinito. Independientemente de eso, el núcleo (y el título) de la pregunta es: ¿Por qué sucede esto?
Las otras respuestas no entran en mucho detalle aquí, pero tenía curiosidad por entender mejor esto también. Por ejemplo, cuando cambias la línea.
map.put((1L << 32) + 1, 0L);
a
map.put(1L, 0L);
entonces no se atasca. Y de nuevo, la pregunta es por qué .
La respuesta es: es complicado.
El
ConcurrentHashMap
es una de las clases más complejas del marco de las colecciones / concurrentes, con 6300 líneas de código, con 230 líneas de comentarios que solo explican el
concepto
básico de la implementación, y por qué el código mágico e ilegible realmente
funciona
.
Lo siguiente está bastante simplificado, pero al menos debería explicar el problema
básico
.
En primer lugar: el conjunto que devuelve
Map::keySet
es una
vista
del estado interno.
Y el JavaDoc dice:
Devuelve una vista de conjunto de las claves contenidas en este mapa. El conjunto está respaldado por el mapa, por lo que los cambios en el mapa se reflejan en el conjunto y viceversa. Si el mapa se modifica mientras se está ejecutando una iteración sobre el conjunto (excepto a través de la propia operación de eliminación del iterador), los resultados de la iteración no están definidos. El conjunto soporta la eliminación de elementos, [...]
(Énfasis por mi)
Sin embargo, el JavaDoc de
ConcurrentHashMap::keySet
dice:
Devuelve una vista de conjunto de las claves contenidas en este mapa. El conjunto está respaldado por el mapa, por lo que los cambios en el mapa se reflejan en el conjunto y viceversa. El conjunto soporta la eliminación de elementos, [...]
(Tenga en cuenta que no menciona el comportamiento indefinido!)
Por lo general, modificar el mapa mientras se itera sobre
keySet
generaría una
keySet
ConcurrentModificationException
.
Pero el
ConcurrentHashMap
es capaz de hacer frente a esto.
Sigue siendo consistente y aún puede repetirse, aunque los resultados pueden ser inesperados, como en su caso.
Llegando a la razón del comportamiento que observaste:
Una
tabla hash (o mapa hash)
básicamente funciona calculando un valor hash de la clave y utilizando esta clave como un indicador del "depósito" al que se debe agregar la entrada.
Cuando se asignan varias claves al mismo grupo, las entradas en el grupo generalmente se administran como una
lista enlazada
.
Lo mismo es el caso para el
ConcurrentHashMap
.
El siguiente programa utiliza algunos hacks de reflexión desagradables para imprimir el estado interno de la tabla, especialmente los "grupos" de la tabla, que consta de nodos, durante la iteración y modificación:
import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class MapLoop
{
public static void main(String[] args) throws Exception
{
runTestInfinite();
runTestFinite();
}
private static void runTestInfinite() throws Exception
{
System.out.println("Running test with inifinite loop");
Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put((1L << 32) + 1, 0L);
int counter = 0;
for (long key : map.keySet())
{
map.put(key, map.remove(key));
System.out.println("Infinite, counter is "+counter);
printTable(map);
counter++;
if (counter == 10)
{
System.out.println("Bailing out...");
break;
}
}
System.out.println("Running test with inifinite loop DONE");
}
private static void runTestFinite() throws Exception
{
System.out.println("Running test with finite loop");
Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put(1L, 0L);
int counter = 0;
for (long key : map.keySet())
{
map.put(key, map.remove(key));
System.out.println("Finite, counter is "+counter);
printTable(map);
counter++;
}
System.out.println("Running test with finite loop DONE");
}
private static void printTable(Map<Long, Long> map) throws Exception
{
// Hack, to illustrate the issue here:
System.out.println("Table now: ");
Field fTable = ConcurrentHashMap.class.getDeclaredField("table");
fTable.setAccessible(true);
Object t = fTable.get(map);
int n = Array.getLength(t);
for (int i = 0; i < n; i++)
{
Object node = Array.get(t, i);
printNode(i, node);
}
}
private static void printNode(int index, Object node) throws Exception
{
if (node == null)
{
System.out.println("at " + index + ": null");
return;
}
// Hack, to illustrate the issue here:
Class<?> c =
Class.forName("java.util.concurrent.ConcurrentHashMap$Node");
Field fHash = c.getDeclaredField("hash");
fHash.setAccessible(true);
Field fKey = c.getDeclaredField("key");
fKey.setAccessible(true);
Field fVal = c.getDeclaredField("val");
fVal.setAccessible(true);
Field fNext = c.getDeclaredField("next");
fNext.setAccessible(true);
System.out.println(" at " + index + ":");
System.out.println(" hash " + fHash.getInt(node));
System.out.println(" key " + fKey.get(node));
System.out.println(" val " + fVal.get(node));
System.out.println(" next " + fNext.get(node));
}
}
La salida para el caso
runTestInfinite
es la siguiente (se omiten las partes redundantes):
Running test with infinite loop
Infinite, counter is 0
Table now:
at 0:
hash 0
key 4294967297
val 0
next 0=0
at 1: null
at 2: null
...
at 14: null
at 15: null
Infinite, counter is 1
Table now:
at 0:
hash 0
key 0
val 0
next 4294967297=0
at 1: null
at 2: null
...
at 14: null
at 15: null
Infinite, counter is 2
Table now:
at 0:
hash 0
key 4294967297
val 0
next 0=0
at 1: null
at 2: null
...
at 14: null
at 15: null
Infinite, counter is 3
...
Infinite, counter is 9
...
Bailing out...
Running test with infinite loop DONE
Se puede ver que las entradas para la clave
0
y la clave
4294967297
(que es su
(1L << 32) + 1
) siempre terminan en el cubo 0, y se mantienen como una lista enlazada.
Así que la iteración sobre el conjunto de
keySet
comienza con esta tabla:
Bucket : Contents
0 : 0 --> 4294967297
1 : null
... : ...
15 : null
En la primera iteración, elimina la clave
0
, básicamente convirtiendo la tabla en esta:
Bucket : Contents
0 : 4294967297
1 : null
... : ...
15 : null
Pero la clave
0
se agrega inmediatamente después, y termina en el mismo cubo que el
4294967297
, por lo que se agrega al final de la lista:
Bucket : Contents
0 : 4294967297 -> 0
1 : null
... : ...
15 : null
(Esto se indica mediante la
next 0=0
de la salida).
En la siguiente iteración, el
4294967297
se quita y se vuelve a insertar, colocando la tabla en el mismo estado que tenía inicialmente.
Y de ahí viene tu bucle infinito.
En contraste con eso, la salida para el caso
runTestFinite
es la siguiente:
Running test with finite loop
Finite, counter is 0
Table now:
at 0:
hash 0
key 0
val 0
next null
at 1:
hash 1
key 1
val 0
next null
at 2: null
...
at 14: null
at 15: null
Finite, counter is 1
Table now:
at 0:
hash 0
key 0
val 0
next null
at 1:
hash 1
key 1
val 0
next null
at 2: null
...
at 14: null
at 15: null
Running test with finite loop DONE
Uno puede ver que las teclas
0
y
1
terminan en
diferentes
cubos.
Por lo tanto, no hay una lista enlazada a la que se puedan agregar los elementos eliminados (y agregados), y el bucle termina después de iterar a través de los elementos relevantes (es decir, los dos primeros grupos)
una vez
.
Mientras realizaba un análisis en profundidad de
ConcurrentHashMap
, encontré una publicación de blog en Internet que dice que incluso
ConcurrentHashMap
puede quedar atrapado en un bucle infinito.
Da este ejemplo. Cuando ejecuté este código, se atascó:
public class Test {
public static void main(String[] args) throws Exception {
Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put((1L << 32) + 1, 0L);
for (long key : map.keySet()) {
map.put(key, map.remove(key));
}
}
}
No puedo entender la causa raíz. Por favor explique por qué sucede este punto muerto.
No creo que esto tenga nada que ver con la seguridad de subprocesos que ofrece
ConcurrentHashMap
.
Ni siquiera parece un punto muerto en absoluto, sino un bucle infinito.
Y esto se debe a que el mapa se modificó al iterar sobre el conjunto de teclas, que está respaldado por el mismo mapa.
Aquí hay un extracto de la documentación de Map::keySet :
El conjunto está respaldado por el mapa, por lo que los cambios en el mapa se reflejan en el conjunto y viceversa. Si el mapa se modifica mientras se está ejecutando una iteración sobre el conjunto (excepto a través de la propia operación de eliminación del iterador), los resultados de la iteración no están definidos.
No hay ningún interbloqueo. Un interbloqueo se produce cuando dos (o más) subprocesos se bloquean entre sí. Obvio: solo tiene un subproceso principal aquí.
No hay punto muerto.
Sólo estás corriendo en un bucle infinito.
Cuando ejecuto este código (e imprimo la
key
en el bucle), la consola lo muestra repetidamente:
0
4294967297
0
4294967297
0
...
Si hiciera un
map
una instancia de
HashMap
, vería que el código genera una
ConcurrentModificationException
.
Así que solo está modificando el mapa mientras está iterando a través de sus claves, y
ConcurrentHashMap
no lanza una excepción de modificación concurrente, lo que hace que su bucle sea infinito.