What is a ring buffer?
Most people have a general idea of the term "buffer" in computing: a region in memory used for temporarily storing data before transferring it to another location. For example, you may see the message "buffering" when watching an Internet video, which indicates that the computer is waiting for the buffer to be filled before continuing playback.
A ring buffer is a special type of buffer with a distinct structure that changes its use case in practice. But what is a ring buffer exactly, and how do ring buffers work?
What are ring buffers?
A ring buffer (also known as a circular buffer or a circular queue) is a buffer data structure that behaves as if it had a circular shape, in which the last element in the buffer is connected to the first element. Like standard buffers, ring buffers typically have a fixed size.
There are several benefits of using a ring buffer over a standard buffer. For example, suppose that your buffer has 1000 elements in it, and you consume the first element at the start of the buffer. With a standard linear buffer, you would then need to shift all the other 999 elements one position to the left, so that you can keep inserting new elements at the end of the buffer. This can easily become very inefficient as the size of the buffer grows.
Ring buffers fix this issue by maintaining a circular structure. If you consume the first element from a ring buffer, you can simply point to the next element in the buffer as the new head of the buffer, and then insert a new element in the empty space. This pointer to the first element will rotate around the ring buffer as you continue to consume elements.
This single change dramatically affects how standard buffers and ring buffers are typically used. Standard buffers are best used for LIFO (last in, first out) use cases: for example, undoing commands in a program, or hitting the "back" button in a web browser. Ring buffers, meanwhile, are best used for FIFO (first in, first out) use cases: for example, serving customers in a queue in the order they arrived.
How do ring buffers work?
To implement a ring buffer, you need a designated fixed space in memory, as well as four pointers:
- A pointer to the start of the ring buffer in memory.
- A pointer to the end of the ring buffer in memory.
- A pointer to the start of the data in the ring buffer.
- A pointer to the end of the data in the ring buffer.
These last two pointers are necessary because the data in the ring buffer may not start or end where the memory itself starts or ends, due to the buffer's circular structure. Whenever we consume another element in the buffer, we need to update the pointers to the start and end of the data.
For example, suppose we have a ring buffer of size 10 (i.e. with indices 0-9), and we insert 5 elements into the buffer at positions 0-4. We then consume the first element in the buffer, which means there will be 4 elements remaining at positions 1-4. Now the data in the buffer no longer begins at the start of the buffer, nor does it end at the buffer's end.
There are several existing implementations of ring buffers: for example, the CircularFifoBuffer in Java from Apache's Common Collections package.
Ring buffers in Redis
Redis is an open-source, in-memory data structure store that is a popular choice for building key-value NoSQL databases, caches, and message brokers. Because Redis is often used as a messaging server, it's no surprise that ring buffers are a popular data structure in Redis for storing and consuming messages.
One complication for Redis developers is that Redis isn't automatically compatible with programming languages such as Java. To gain access to Java objects and collections, developers often use a third-party Redis Java client such as Redisson.
Redisson includes a pre-built implementation of the ring buffer data structure with its RRingBuffer interface, which inherits from the standard java.util.Queue interface. Below is an example of how to use RRingBuffer in Redisson:
RRingBuffer<Integer> buffer = redisson.getRingBuffer("test");
// buffer capacity is 4 elements
buffer.trySetCapacity(4);
buffer.add(1);
buffer.add(2);
buffer.add(3);
buffer.add(4);
// buffer state is 1, 2, 3, 4
buffer.add(5);
buffer.add(6);
// buffer state is 3, 4, 5, 6