Implementación de un Ring Buffer en Java

1. Resumen

En este tutorial, aprenderemos a implementar un Ring Buffer en Java.

Ring Buffer

El Ring Buffer (o Buffer Circular) es una estructura de datos circular delimitada que se utiliza para almacenar datos en el buffer entre dos o más hilos. A medida que vamos escribiendo en un ring buffer, éste se va envolviendo a medida que llega al final.

2.1. Cómo funciona

Un Ring Buffer se implementa utilizando un array de tamaño fijo que se envuelve en los límites.

Además de la matriz, lleva la cuenta de tres cosas:

• la siguiente ranura disponible en el buffer para insertar un elemento,
• el siguiente elemento no leído en el buffer,
• y el final del array – el punto en el que el buffer se envuelve alrededor del inicio del array

La mecánica de cómo un buffer en anillo maneja estos requisitos varía con la implementación. Por ejemplo, la entrada de Wikipedia sobre el tema muestra un método que utiliza cuatro punteros.

Tomaremos prestado el enfoque de la implementación de Disruptor del buffer de anillo utilizando secuencias.

Lo primero que necesitamos saber es la capacidad – el tamaño máximo fijo del buffer. A continuación, utilizaremos dos secuencias monótonamente crecientes:

• Secuencia de escritura: comienza en -1, se incrementa en 1 a medida que insertamos un elemento
• Secuencia de lectura: comienza en 0, se incrementa en 1 a medida que consumimos un elemento

Podemos asignar una secuencia a un índice en el array utilizando una operación mod:

arrayIndex = sequence % capacity

La operación mod envuelve la secuencia alrededor de los límites para derivar un slot en el buffer:

Veamos cómo insertaríamos un elemento:

buffer = element

Estamos preincrementando la secuencia antes de insertar un elemento.

Para consumir un elemento hacemos un post-incremento:

element = buffer

En este caso, realizamos un post-incremento en la secuencia. Consumir un elemento no lo elimina del buffer – simplemente se queda en el array hasta que se sobrescribe.

2.2. Bufferes vacíos y llenos

A medida que vamos envolviendo el array, empezaremos a sobrescribir los datos del buffer. Si el buffer está lleno, podemos elegir entre sobrescribir los datos más antiguos independientemente de que el lector los haya consumido o impedir que se sobrescriban los datos que no han sido leídos.

Si el lector puede permitirse el lujo de perder los valores intermedios o antiguos (por ejemplo, un ticker de cotización), podemos sobrescribir los datos sin esperar a que se consuman. En cambio, si el lector debe consumir todos los valores (como en las transacciones de comercio electrónico), debemos esperar (block/busy-wait) hasta que el buffer tenga un slot disponible.

El buffer está lleno si el tamaño del buffer es igual a su capacidad, donde su tamaño es igual al número de elementos no leídos:

size = (writeSequence - readSequence) + 1isFull = (size == capacity)

Si la secuencia de escritura va por detrás de la secuencia de lectura, el buffer está vacío:

isEmpty = writeSequence < readSequence

El buffer devuelve un valor nulo si está vacío.

2.2. Ventajas y desventajas

Un buffer en anillo es un eficiente buffer FIFO. Utiliza un array de tamaño fijo que puede ser preasignado por adelantado y permite un patrón de acceso a memoria eficiente. Todas las operaciones del buffer son de tiempo constante O(1), incluyendo el consumo de un elemento, ya que no requiere un desplazamiento de elementos.

Por otro lado, determinar el tamaño correcto del buffer en anillo es crítico. Por ejemplo, las operaciones de escritura pueden bloquearse durante mucho tiempo si el buffer es de tamaño insuficiente y las lecturas son lentas. Podemos utilizar un dimensionamiento dinámico, pero requeriría mover los datos de un lado a otro y perderíamos la mayoría de las ventajas comentadas anteriormente.

Implementación en Java

Ahora que entendemos cómo funciona un buffer en anillo, procedamos a implementarlo en Java.

3.1. Inicialización

Primero, definamos un constructor que inicialice el buffer con una capacidad predefinida:

public CircularBuffer(int capacity) { this.capacity = (capacity < 1) ? DEFAULT_CAPACITY : capacity; this.data = (E) new Object; this.readSequence = 0; this.writeSequence = -1;}

Esto creará un buffer vacío e inicializará los campos de la secuencia como se comentó en la sección anterior.

3.2. Oferta

A continuación, implementaremos la operación de oferta que inserta un elemento en el buffer en la siguiente ranura disponible y devuelve true en caso de éxito. Devuelve false si el buffer no encuentra un slot vacío, es decir, no podemos sobrescribir valores no leídos.

Implementemos el método offer en Java:

public boolean offer(E element) { boolean isFull = (writeSequence - readSequence) + 1 == capacity; if (!isFull) { int nextWriteSeq = writeSequence + 1; data = element; writeSequence++; return true; } return false;}

Así, estamos incrementando la secuencia de escritura y calculando el índice en el array para el siguiente slot disponible. Luego, estamos escribiendo los datos en el buffer y almacenando la secuencia de escritura actualizada.

Vamos a probarlo:

@Testpublic void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); assertTrue(buffer.offer("Square")); assertEquals(1, buffer.size());}

3.3. Poll

Por último, implementaremos la operación poll que recupera y elimina el siguiente elemento no leído. La operación de sondeo no elimina el elemento sino que incrementa la secuencia de lectura.

Implementémosla:

public E poll() { boolean isEmpty = writeSequence < readSequence; if (!isEmpty) { E nextValue = data; readSequence++; return nextValue; } return null;}

Aquí, estamos leyendo los datos en la secuencia de lectura actual calculando el índice en el array. Luego, estamos incrementando la secuencia y devolviendo el valor, si el buffer no está vacío.

Vamos a probarlo:

@Testpublic void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); buffer.offer("Triangle"); String shape = buffer.poll(); assertEquals("Triangle", shape);}

Productor-Consumidor Problema

Hemos hablado sobre el uso de un buffer de anillo para el intercambio de datos entre dos o más hilos, que es un ejemplo de un problema de sincronización llamado el Productor-Consumidor problema. En Java, podemos resolver el problema productor-consumidor de varias maneras utilizando semáforos, colas delimitadas, buffers de anillo, etc.

Implementemos una solución basada en un buffer de anillo.

4.1. Campos de secuencia volátiles

Nuestra implementación del buffer de anillo no es segura para hilos. Vamos a hacerla segura para el caso simple de un productor y un consumidor.

El productor escribe datos en el buffer e incrementa la writeSequence, mientras que el consumidor sólo lee del buffer e incrementa la readSequence. Por lo tanto, el array de respaldo está libre de contención y podemos prescindir de cualquier sincronización.

Pero todavía tenemos que asegurarnos de que el consumidor puede ver el último valor del campo writeSequence (visibilidad) y que el writeSequence no se actualiza antes de que los datos estén realmente disponibles en el buffer (ordenación).

Podemos hacer que el buffer de anillo sea concurrente y libre de bloqueos en este caso haciendo que los campos de secuencia sean volátiles:

private volatile int writeSequence = -1, readSequence = 0;

En el método de oferta, una escritura en el campo volátil writeSequence garantiza que las escrituras en el buffer ocurran antes de actualizar la secuencia. Al mismo tiempo, la garantía de visibilidad volátil asegura que el consumidor siempre verá el último valor de writeSequence.

4.2. Productor

Implementemos un Runnable productor sencillo que escriba en el buffer del anillo:

public void run() { for (int i = 0; i < items.length;) { if (buffer.offer(items)) { System.out.println("Produced: " + items); i++; } }}

El hilo productor esperaría un slot vacío en un bucle (busy-waiting).

4.3. Consumidor

Implementaremos un consumidor Callable que lea del buffer:

public T call() { T items = (T) new Object; for (int i = 0; i < items.length;) { T item = buffer.poll(); if (item != null) { items = item; System.out.println("Consumed: " + item); } } return items;}

El hilo consumidor continúa sin imprimir si recibe un valor nulo del buffer.

Escribamos el código de nuestro controlador:

executorService.submit(new Thread(new Producer<String>(buffer)));executorService.submit(new Thread(new Consumer<String>(buffer)));

La ejecución de nuestro programa productor-consumidor produce una salida como la siguiente:

Produced: CircleProduced: Triangle Consumed: CircleProduced: Rectangle Consumed: Triangle Consumed: RectangleProduced: SquareProduced: Rhombus Consumed: SquareProduced: Trapezoid Consumed: Rhombus Consumed: TrapezoidProduced: PentagonProduced: PentagramProduced: Hexagon Consumed: Pentagon Consumed: PentagramProduced: Hexagram Consumed: Hexagon Consumed: Hexagram

Conclusión

En este tutorial, hemos aprendido a implementar un Ring Buffer y hemos explorado cómo se puede utilizar para resolver el problema productor-consumidor.