Tuesday 21 November 2023

Ring Buffers: A Comprehensive Guide to Ring Buffers for High-Performance Data Management

A ring buffer, also known as a circular buffer or cyclic buffer, that stores elements in a fixed-size, circular arrangement. Following image depicts a ring buffer of capacity to store 11 elements.


Key characteristics of ring buffer

1. Fixed Size

Ring buffer is fixed in size. Once the buffer is full, either you can replace the old elements or you can wait until the elements in buffer are consumed.

 

2. Circular in nature

Buffer is organized in a circular ring like fashion.

 

3. FIFO behaviour

Elements are consumed in First-In, First-Out order. Elements which are added first are consumed first.

 

4. Efficient for sequential access applications

RingBuffers are used to sequential access applications. In video streaming applications, where data is continuously arriving and being processed, a ring buffer can be more efficient than other data structures.

 

5. Efficient space usage

Unlike conventional arrays or buffers that can experience wasted space as elements are added or removed, ring buffers seamlessly employ their fixed-size storage without any gaps.

 

6. Easy to implement

Simple to implement.

 

When is the ring-buffer empty?

A ring buffer is considered empty when the read_pointer is equal to the write_pointer. This can be expressed mathematically as:

 

read_pointer == write_pointer

 


 

When the producer add elements to the buffer, the write_pointer will move ahead. After adding four elements a, b, c and d, ring buffer looks like below.

 


 

Assume consumer processed 2 elements from the buffer, then the ring buffer looks like below.




When is the buffer full?

A ring buffer is considered full when the write_pointer is one position behind the read_pointer. This can be expressed mathematically as:

 

(write_pointer + 1) % buffer_size == read_pointer

 

Find the below working application.

 

RingBuffer.java

package com.sample.app.collections;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class RingBuffer<T> {
	private int bufferSize;
	private Object[] buffer;
	private int writePointer = 0;
	private int readPointer = 0;
	private final Lock LOCK = new ReentrantLock();

	public RingBuffer(int capacity) {
		this.bufferSize = capacity;
		this.buffer = new Object[capacity];
	}

	public boolean publish(T item) {
		LOCK.lock();
		try {
			// Check if the buffer is full
			if ((writePointer + 1) % bufferSize == readPointer) {
				return false;
			}

			// Add item to the buffer
			buffer[writePointer] = item;
			writePointer = (writePointer + 1) % bufferSize;

			System.out.println("Published: " + item);
			return true;

		} finally {
			LOCK.unlock();
		}
	}

	public T consume() {
		LOCK.lock();
		try {
			// Check if the buffer is empty
			if (readPointer == writePointer) {
				return null;
			}

			// Retrieve item from the buffer
			T item = (T) buffer[readPointer];
			readPointer = (readPointer + 1) % bufferSize;
			return item;

		} finally {
			LOCK.unlock();
		}
	}
}

Producer.java

package com.sample.app.tasks;

import com.sample.app.collections.RingBuffer;
import com.sample.app.util.TimerUtil;

public class Producer implements Runnable {
	private RingBuffer<String> buffer;

	public Producer(RingBuffer<String> buffer) {
		this.buffer = buffer;
	}

	@Override
	public void run() {
		for (int i = 0; i < 10; i++) {
			boolean ispublished = buffer.publish("Event " + i);
			if(!ispublished) {
				System.out.println("Buffer is full. Producer waiting...");
				TimerUtil.sleepNMilliseconds(100);
				i--;
				continue;
			}
		}
	}
}

Consumer.java

package com.sample.app.tasks;

import com.sample.app.collections.*;
import com.sample.app.util.TimerUtil;

public class Consumer implements Runnable {
	private RingBuffer<String> buffer;

	public Consumer(RingBuffer<String> buffer) {
		this.buffer = buffer;
	}

	@Override
	public void run() {
		for (int i = 0; i < 10; i++) {
			String itemRead = buffer.consume();
			if (itemRead == null) {
				TimerUtil.sleepNMilliseconds(100);
				i--;
				System.out.println("Buffer is empty. Consumer waiting...");
				continue;
			}
			System.out.println("Consumed: " + itemRead);
		}
	}
}

App.java

package com.sample.app;

import com.sample.app.collections.RingBuffer;
import com.sample.app.tasks.Consumer;
import com.sample.app.tasks.Producer;

public class App {
	public static void main(String[] args) {
		RingBuffer<String> buffer = new RingBuffer<>(5);

		// Create and start producer and consumer threads
		Thread producerThread = new Thread(new Producer(buffer));
		Thread consumerThread = new Thread(new Consumer(buffer));

		producerThread.start();
		consumerThread.start();

		try {
			producerThread.join();
			consumerThread.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
}

Sample Output

Published: Event 0
Published: Event 1
Published: Event 2
Published: Event 3
Buffer is full. Producer waiting...
Consumed: Event 0
Consumed: Event 1
Consumed: Event 2
Consumed: Event 3
Buffer is empty. Consumer waiting...
Published: Event 4
Published: Event 5
Published: Event 6
Published: Event 7
Buffer is full. Producer waiting...
Consumed: Event 4
Consumed: Event 5
Consumed: Event 6
Consumed: Event 7
Buffer is empty. Consumer waiting...
Published: Event 8
Published: Event 9
Buffer is empty. Consumer waiting...
Consumed: Event 8
Consumed: Event 9

You can download this example from this link.



                                                             System Design Questions

No comments:

Post a Comment