Implementing a Ring Buffer in Java

1. Overview

In this tutorial, we’ll learn how to implement a Ring Buffer in Java.

2. Ring Buffer

Ring Buffer (or Circular Buffer) is a bounded circular data structure that is used for buffering data between two or more threads. As we keep writing to a ring buffer, it wraps around as it reaches the end.

2.1. How It Works

A Ring Buffer is implemented using a fixed-size array that wraps around at the boundaries.

Apart from the array, it keeps track of three things:

• the next available slot in the buffer to insert an element,
• the next unread element in the buffer,
• and the end of the array – the point at which the buffer wraps around to the start of the array

The mechanics of how a ring buffer handles these requirements vary with the implementation. For instance, the Wikipedia entry on the subject shows a method using four-pointers.

We’ll borrow the approach from Disruptor‘s implementation of the ring buffer using sequences.

The first thing we need to know is the capacity – the fixed maximum size of the buffer. Next, we’ll use two monotonically increasing sequences:

• Write Sequence: starting at -1, increments by 1 as we insert an element
• Read Sequence: starting at 0, increments by 1 as we consume an element

We can map a sequence to an index in the array by using a mod operation:

arrayIndex = sequence % capacity

The mod operation wraps the sequence around the boundaries to derive a slot in the buffer:

Let’s see how we’d insert an element:

buffer[++writeSequence % capacity] = element

We are pre-incrementing the sequence before inserting an element.

To consume an element we do a post-increment:

element = buffer[readSequence++ % capacity]

In this case, we perform a post-increment on the sequence. Consuming an element doesn’t remove it from the buffer – it just stays in the array until it’s overwritten.

2.2. Empty and Full Buffers

As we wrap around the array, we will start overwriting the data in the buffer. If the buffer is full, we can choose to either overwrite the oldest data regardless of whether the reader has consumed it or prevent overwriting the data that has not been read.

If the reader can afford to miss the intermediate or old values (for example, a stock price ticker), we can overwrite the data without waiting for it to be consumed. On the other hand, if the reader must consume all the values (like with e-commerce transactions), we should wait (block/busy-wait) until the buffer has a slot available.

The buffer is full if the size of the buffer is equal to its capacity, where its size is equal to the number of unread elements:

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

If the write sequence lags behind the read sequence, the buffer is empty:

isEmpty = writeSequence < readSequence

The buffer returns a null value if it’s empty.

2.2. Advantages and Disadvantages

A ring buffer is an efficient FIFO buffer. It uses a fixed-size array that can be pre-allocated upfront and allows an efficient memory access pattern. All the buffer operations are constant time O(1), including consuming an element, as it doesn’t require a shifting of elements.

On the flip side, determining the correct size of the ring buffer is critical. For instance, the write operations may block for a long time if the buffer is under-sized and the reads are slow. We can use dynamic sizing, but it would require moving data around and we’ll miss out on most of the advantages discussed above.

3. Implementation in Java

Now that we understand how a ring buffer works, let’s proceed to implement it in Java.

3.1. Initialization

First, let’s define a constructor that initializes the buffer with a predefined capacity:

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

This will create an empty buffer and initialize the sequence fields as discussed in the previous section.

3.2. Offer

Next, we’ll implement the offer operation that inserts an element into the buffer at the next available slot and returns true on success. It returns false if the buffer can’t find an empty slot, that is, we can’t overwrite unread values.

Let’s implement the offer method in Java:

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

So, we’re incrementing the write sequence and computing the index in the array for the next available slot. Then, we’re writing the data to the buffer and storing the updated write sequence.

Let’s try it out:

@Test
public void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() {
    CircularBuffer buffer = new CircularBuffer<>(defaultCapacity);

    assertTrue(buffer.offer("Square"));
    assertEquals(1, buffer.size());
}

3.3. Poll

Finally, we’ll implement the poll operation that retrieves and removes the next unread element. The poll operation doesn’t remove the element but increments the read sequence.

Let’s implement it:

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

Here, we’re reading the data at the current read sequence by computing the index in the array. Then, we’re incrementing the sequence and returning the value, if the buffer is not empty.

Let’s test it out:

@Test
public void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() {
    CircularBuffer buffer = new CircularBuffer<>(defaultCapacity);
    buffer.offer("Triangle");
    String shape = buffer.poll();

    assertEquals("Triangle", shape);
}

4. Producer-Consumer Problem

We’ve talked about the use of a ring buffer for exchanging data between two or more threads, which is an example of a synchronization problem called the Producer-Consumer problem. In Java, we can solve the producer-consumer problem in various ways using semaphores, bounded queues, ring buffers, etc.

Let’s implement a solution based on a ring buffer.

4.1. volatile Sequence Fields

Our implementation of the ring buffer is not thread-safe. Let’s make it thread-safe for the simple single-producer and single-consumer case.

The producer writes data to the buffer and increments the writeSequence, while the consumer only reads from the buffer and increments the readSequence. So, the backing array is contention-free and we can get away without any synchronization.

But we still need to ensure that the consumer can see the latest value of the writeSequence field (visibility) and that the writeSequence is not updated before the data is actually available in the buffer (ordering).

We can make the ring buffer concurrent and lock-free in this case by making the sequence fields volatile:

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

In the offer method, a write to the volatile field writeSequence guarantees that the writes to the buffer happen before updating the sequence. At the same time, the volatile visibility guarantee ensures that the consumer will always see the latest value of writeSequence.

4.2. Producer

Let’s implement a simple producer Runnable that writes to the ring buffer:

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

The producer thread would wait for an empty slot in a loop (busy-waiting).

4.3. Consumer

We’ll implement a consumer Callable that reads from the buffer:

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

The consumer thread continues without printing if it receives a null value from the buffer.

Let’s write our driver code:

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

Executing our producer-consumer program produces output like below:

Produced: Circle
Produced: Triangle
  Consumed: Circle
Produced: Rectangle
  Consumed: Triangle
  Consumed: Rectangle
Produced: Square
Produced: Rhombus
  Consumed: Square
Produced: Trapezoid
  Consumed: Rhombus
  Consumed: Trapezoid
Produced: Pentagon
Produced: Pentagram
Produced: Hexagon
  Consumed: Pentagon
  Consumed: Pentagram
Produced: Hexagram
  Consumed: Hexagon
  Consumed: Hexagram

5. Conclusion

In this tutorial, we’ve learned how to implement a Ring Buffer and explored how it can be used to solve the producer-consumer problem.