Explicación al reto de concurrencia. Solución con StampedLock

Éste artículo es una traducción al castellano de la entrada original publicada, en inglés, por Dr. Heinz Kabutz en su número 242 de The Java^tm Specialists’ Newsletter. Puedes consultar el texto original en Javaspecialists’ Newsletter #242: Concurrency Puzzle Explained, Solved With StampedLock

Este artículo se publica traducido en adictos, con permiso del autor, por David Gómez García, (@dgomezg) consultor tecnológico en Autentia, colaborador de JavaSpecialists e instructor certificado para impartir los cursos de JavaSpecialists en español.
[/box]

El canal de Slack de Java Specialists (en inglés) está que se sale. Casi 2.000 miembros ya, intercambiando grandes ideas, aprendiendo cosas nuevas. Tenemos miembros en 22 husos horarios. Lo que significa que puedes encontrar a alguien para hablar de Java en tiempo real a cualquier hora del día o de la noche. Para unirte, rellena este formulario con tus datos y automágicamente recibirás una invitación de Slack (pero por favor, comprueba tu carpeta de SPAM).

NOVEDAD Hemos actualizado nuestro curso de «Advanced Topics» que cubre Reflection, Java NIO, Estructuras de datos, Gestión de memoria y algunos otros temas útiles para dominar si eres un experto en Java. Dos días de diversión y aprendizaje extremos: «Extreme Java – Advanced Topics». Este curso también lo impartimos en castellano.

El problema de concurrencia explicado, solucionado con StampedLock

Nos hemos divertido este último mes. Propuse un reto de concurrencia que ha tenido a expertos en Java de todo el mundo rascándose la cabeza. Tanto es así, que también publiqué algunas pistas útiles.

Lo que más me sorprendió de las respuestas es la cantidad que no se había molestado en ejecutar el código. En vez de ello, lo revisaron y pulsaron en «Responder». Ninguna de estas respuestas capturó el bug que lo hacía fallar de forma consistente. Lo peor es que perdieron una oportunidad fantástica de aprender algo nuevo.

Cuando se buscan errores de concurrencia, el primer paso es tratar de reproducirlo. Esto puede resultar bastante difícil. Por ejemplo, el código que me envió Jack no fallaba en mi MacBook Pro. Lo tuve que ejecutar en mi servidor 2-4-1 con una CPU más antigua para conseguir que el bug se reprodujese. Aquí tenéis una versión con un probabilidad mayor de hacer aparecer el fallo, adaptado para mi amigo Stuart Marks:

import java.util.*;

public class MyArrayListStuart {
  private final Object READ_LOCK = new Object();
  private final Object WRITE_LOCK = new Object();
  private int[] arr = new int[10];
  private int size = 0;

  public int size() {
    synchronized (READ_LOCK) {
      return size;
    }
  }

  public int get(int index) {
    synchronized (READ_LOCK) {
      rangeCheck(index);
      return arr[index];
    }
  }

  public boolean add(int e) {
    synchronized (WRITE_LOCK) {
      if (size + 1 > arr.length)
        arr = Arrays.copyOf(arr, size + 10);

      arr[size++] = e;
      return true;
    }
  }

  public int remove(int index) {
    synchronized (WRITE_LOCK) {
      rangeCheck(index);

      int oldValue = arr[index];

      int numMoved = size - index - 1;
      if (numMoved > 0)
        System.arraycopy(arr, index + 1,
            arr, index, numMoved);
      arr[--size] = 0;

      return oldValue;
    }
  }

  private void rangeCheck(int index) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index: " + index + ", Size: " + size);
  }

  private static volatile boolean goAdd;

  public static void main(String[] args) {
    for (int i = 0; i < 100000; i++) {
      goAdd = false;
      MyArrayListStuart list = new MyArrayListStuart();
      new Thread(new Main(list, true)).start();
      new Thread(new Main(list, false)).start();
      new Thread(new Main(list, false)).start();
      new Thread(new Main(list, false)).start();
    }
  }

  static class Main implements Runnable {
    MyArrayListStuart list;
    boolean update;

    public Main(MyArrayListStuart list,
                boolean update) {
      this.list = list;
      this.update = update;
    }

    @Override
    public void run() {
      if (update) {
        while(!goAdd);
        goAdd = false;
        for (int i = 1; i < 1000; i++) {
          list.add(i);
        }
        for (int i = 1; i < 250; i++) {
          list.remove(7);
        }
      } else {
        // wait until we're certain
        // index 6 has a value
        while (list.size() < 7) {goAdd = true;}
        for (int i = 1; i < 1000; i++) {
          int x;
          if ((x = list.get(6)) != 7) {
            System.out.println(x +
                " and " + list.size());
          }
        }
      }
    }
  }
}

El fallo de concurrencia se manifiesta más fácilmente con el código modificado. Lo podemos reproducir de forma consistente. Es casi imposible hacer esto con errores de tipo happens-before. Esos suelen mostrar su fea cara en producción, no en un pequeño test como el nuestro. Los errores de visibilidad suelen aparecer y no se recupera uno de ellos, por ejemplo, si tenemos un bucle cerrado en el que leemos un campo desprotegido. En nuestro caso, el error es mucho más básico.

La segunda pista estaba en que ocurría incluso sin el remove(). Así que podiamos ignorar tranquilamente el método remove() y centrarnos en el método add().

Una tercera pista estaba en que el redimensionado no tenía nada que ver con el error. Incluso si dimensionamos desde el principio el array con un tamaño de 1.000, también podía fallar.

La primera respuesta correcta la dió Andreas Senft. Reconoció que se trataba simplemente de un error de concurrencia común que no tenía nada que ver con cachés, happens-before, visibilidad, etc… Simple y llanamente una condición de carrera en el método add(). Si miramos dentro de add(), veremos la sentencia arr[size++] = e;. La mayoría de programadores leen esto como «Asigna e en el elemento del array y actualiza el tamaño». En sus cabezas, esto es lo que ocurre:

	arr[size] = e;
	size = size + 1;

Aunque sería más acertado verlo de la siguiente forma:

  int temp = size;
  size = size + 1;
  arr[temp] = e;

Ahora es obvio que size se actualiza primero y después se asigna el elemento en el array. Si, entre la llamada a size = size + 1; y arr[temp] = e; el hilo deja su tiempo de ejecución de CPU, el hilo de lectura podría tratar de leer un elemento que no existe todavía, dado que está bloqueado en un monitor diferente. Si reemplazamos el código por el siguiente, entonces los errores se producirán con menos frecuencia (pero todavía es incorrecto):

	arr[size] = e;
	size++;

Demostrar que es también incorrecto será más complicado. El test que teníamos en el artículo anterior no será suficiente.

El problema con el código estaba en que tenemos distintos locks guardando campos que mantienen una invariante entre ellos. La motivación detrás de esto era tratar de evitar que los bloqueos de escritura bloqueen los hilos que sólo quieren leer. Pensé que éste sería un buen caso de uso para el StampedLock de Java 8. Si todo esto te resulta nuevo, ¿puedo sugerirte apuntarte a mi curso Extreme Java – Concurrency and performance for Java 8? (que también impartimos en español). ¡Aprenderás en tres días más de lo que crees que es posible!

IntList con StampedLock

StampedLock se añadió con Java 8 para darnos la posibilidad de realizar lecturas optimistas sobre campos. Esto es útil cuando tenemos varios campos con una invariante entre todos ellos. En nuestro ejemplo, esos son los campos arr y size.

IntList es el resultado de un trabajo en colaboración entre Peter Levart, Henri Tremblay, Hanko Gergely, Alex Snaps y yo mismo. Cada uno de nosotros ha ayudado a refinar un poquito la solución final. Es un trabajo en curso así que, por favor, decidme si encontráis una forma de mejorarlo todavía más. Casi seguro que tiene jugosos bugs aún por descubrir.

Para empezar tenemos size(). Dado que lo que nos preocupa es la visibilidad del campo size, lo único que necesitamos es llamar al método tryOptimisticRead(). Éste método realiza una lectura volatile sobre el campo dentro de un StampedLock, que tiene el mismo efecto que entrar en un bloque synchronized, y por tanto garantiza que veremos el valor correcto del campo size.

El método get() es el más complejo. Intentamos leer el elemento del array en una variable local entre las llamadas a tryOptimisticRead() y validate(), asegurándonos que no causamos un ArrayIndexOutOfBoundsException en el proceso. Si somos lo suficientemente rápidos, podemos hacerlo antes de que otro hilo obtenga el lock de escritura. Verás que intentamos la lectura optimista tres veces y, si no lo conseguimos, cambiamos a usar un lock de lectura pesimista. Este cambio puede ser bueno, pero también puede penalizarnos si lo hacemos demasiado.

La función trimToSize() se supone que nos muestra como podemos utilizar tryOptimisticRead() para evitar obtener un lock de escritura si no lo necesitamos.

El método add() es sencillo, casi como utilizar un ReentrantLock.

Tenemos dos funciones de borrado. El método remove() simple es análogo a add(), utilizando un lock pesimista para la lectura exclusiva. El método removeWithUpgrade() obtiene un lock de lectura y, si el índice no está fuera de rango, intentamos convertirlo en un lock de escritura. Un ReentrantReadWriteLock produciría un deadlock, pero con StampedLock lo conseguiremos. Este lock condicional de escritura es útil cuando tenemos una alta probabilidad de no necesitar el lock de escritura. De todas formas, en nuestro caso esperamos que la mayor parte de las veces el índice estará dentro del rango. Por eso, el método remove() sería probablemente una solución mejor. Más rápido y más fácil de comprender y de mantener.

Vamos al código. Divertíos. Discutiremos esto en el canal #newsletter del grupo JavaSpecialists.slack.com. Por favor, rellena tus datos aquí para unirte (sin cuotas, sin obligaciones, excepto «ser agradables»).

import java.util.*;
import java.util.concurrent.locks.*;

public class IntList {
  private static final int OPTIMISTIC_SPIN = 3;
  private final StampedLock sl = new StampedLock();
  private int[] arr = new int[10];
  private int size = 0;

  /**
   * The size() method cannot be used to perform compound
   * operations, such as getting the last element of a list.
   * This code could fail with an IndexOutOfBoundsException:
   *
   * <pre>
   *   Thread1:
   *     while(true) {
   *       list.get(list.size()-1);
   *     }
   *
   *   Thread2:
   *     for (int i = 0; i < 2000; i++) {
   *       for (int j = 0; j < 100; j++) {
   *         list.add(j);
   *       }
   *       for (int j = 0; j < 50; j++) {
   *         list.remove(0);
   *       }
   *     }
   * </pre>
   */
  public int size() {
    // Internally, the tryOptimisticRead() is reading a volatile
    // field.  From a memory visibility perspective, reading a
    // volatile field is like entering a synchronized block.
    // We will thus not have an issue with stale values of size.
    // Note 1: volatile != synchronized.  Volatile does not
    // magically make compound operations on fields mutually
    // exclusive. Race conditions are more probable on volatile
    // fields.
    // Note 2: We could also have made size volatile.  From a
    // visibility perspective the tryOptimisticRead() will work,
    // but not if size was a long or if it could have
    // intermediate values that broke invariants.
    sl.tryOptimisticRead();
    return this.size;
  }

  public int get(int index) {
    for (int i = 0; i < OPTIMISTIC_SPIN; i++) {
      long stamp = sl.tryOptimisticRead();
      int size = this.size;
      int[] arr = this.arr;
      if (index < arr.length) {
        int r = arr[index];
        if (sl.validate(stamp)) {
          rangeCheck(index, size);
          return r;
        }
      }
    }
    long stamp = sl.readLock();
    try {
      rangeCheck(index, this.size);
      return this.arr[index];
    } finally {
      sl.unlockRead(stamp);
    }
  }

  public void trimToSize() {
    long stamp = sl.tryOptimisticRead();
    int currentSize = size;
    int[] currentArr = arr;
    if (sl.validate(stamp)) {
      // fast optimistic read to accelerate trimToSize() when
      // there is no work to do
      if (currentSize == currentArr.length) return;
    }
    stamp = sl.writeLock();
    try {
      if (size  arr.length)
        arr = Arrays.copyOf(arr, size + 10);

      arr[size++] = e;
      return true;
    } finally {
      sl.unlockWrite(stamp);
    }
  }

  // just to illustrate how an upgrade could be coded
  public int removeWithUpgrade(int index) {
    long stamp = sl.readLock();
    try {
      while (true) {
        rangeCheck(index, size);
        long writeStamp = sl.tryConvertToWriteLock(stamp);
        if (writeStamp == 0) {
          sl.unlockRead(stamp);
          stamp = sl.writeLock();
        } else {
          stamp = writeStamp;
          return doActualRemove(index);
        }
      }
    } finally {
      sl.unlock(stamp);
    }
  }

  public int remove(int index) {
    long stamp = sl.writeLock();
    try {
      rangeCheck(index, size);
      return doActualRemove(index);
    } finally {
      sl.unlock(stamp);
    }
  }

  private int doActualRemove(int index) {
    int oldValue = arr[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
      System.arraycopy(arr, index + 1, arr, index, numMoved);
    arr[--size] = 0;

    return oldValue;
  }

  private static void rangeCheck(int index, int size) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index: " + index + ", Size: " + size);
  }
}
  

He ejecutado algunas pruebas de rendimiento comparando éste con una versión correctamente sincronizada del MyArrayList que usamos en el número anterior. El método get() es basicamente el doble de rápido y usa bastante menos CPU de sistema gracias a la reducción del número de cambios de contexto voluntarios. Los métodos add() y remove() son ligeramente más lentos, pero como esperaba, size() es ridículamente rápido. He añadido éste como un ejercicio a mi curso de concurrencia. Veamos cómo de bien se las apañan programadores Java buenos y experimentados cuando vean StampedLock por primera vez 🙂

Saludos

Heinz.