java - ConcurrentHashMap pegado en bucle-¿Por qué?

deadlock

Question

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.

Answer 1

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 .

Answer 2

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.

Answer 3

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í.

Answer 4

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.