Ring Buffers in Go #go #golang #ring #circular #buffers #queues

Ring Buffers in Go.md

What's a ring buffer?

Ring buffers are known by a few names, such as circular queues and circular buffers.

A ring buffer is a fixed-size, circular data structure that overwrites the oldest data when the buffer is full. It’s particularly useful for scenarios where you want to store and retrieve data in a FIFO (First-In-First-Out) manner but with limited memory. When the buffer reaches its size limit, new data will overwrite the oldest data.

Instead of adding on the end and popping from the end, like a stack, you can add to one end and remove from the start, like a queue. And as you add or remove things, the start and end pointers move around. By managing these pointers, a ring buffer naturally enforces the FIFO order.

What's the benefit?

A ring buffer lets us keep a fixed number of elements in the buffer without running into reallocation.

In a regular old buffer, if you use it as a queue—add to the end, remove from the front—then you'll eventually need to either reallocate the entire thing or shift all the elements over.

Instead, a ring buffer lets you just keep adding from either end and removing from either end and you never have to reallocate!

Algorithm

• We start with an empty buffer.
• The start and end markers both point at the first element.

  START
  ▿
| _ | _ | _ | _ | _ |
  ▵
  END

• When start == end, we know the buffer is empty.
• If we insert an element, we move end forward.

  START
  ▿
| A | _ | _ | _ | _ |
      ▵
      END
      

  START
  ▿
| A | B | C | _ | _ |
              ▵
              END

• If we remove an element (<X>), we move start forward.

        START
        ▿
| <X> | B | C | _ | _ |
                ▵
                END

• We can also have start point at any part of the buffer, and it crosses over the end gracefully.

              START
              ▿
| A | B | C | D | E |
      ▵
      END

Implementations

Here are some Go packages that implement a ring buffer:
https://github.com/search?q=lang%3AGo+ring+buffer&type=repositories&s=stars&o=desc

When I last checked https://github.com/smallnest/ringbuffer seemed like a good option.

Here's a custom option written by:
https://medium.com/checker-engineering/a-practical-guide-to-implementing-a-generic-ring-buffer-in-go-866d27ec1a05

package main

import (
	"fmt"
	"log"
	"reflect"
	"sync"
)

func main() {
	ringBuffer := NewRingBuffer[int](5)
	ringBuffer.Add(1)
	ringBuffer.Add(2)
	ringBuffer.Add(3)

	expected := []int{1, 2, 3}
	actual := ringBuffer.Get()
	if !reflect.DeepEqual(actual, expected) {
		log.Fatalf("Expected %v, but got %v", expected, actual)
	}

	ringBuffer.Add(4)
	ringBuffer.Add(5)
	ringBuffer.Add(6)

	expected = []int{2, 3, 4, 5, 6}
	actual = ringBuffer.Get()
	if !reflect.DeepEqual(actual, expected) {
		log.Fatalf("Expected %v, but got %v", expected, actual)
	}

	ringBuffer.Add(7)
	ringBuffer.Add(8)

	expected = []int{4, 5, 6, 7, 8}
	actual = ringBuffer.Get()
	if !reflect.DeepEqual(actual, expected) {
		log.Fatalf("Expected %v, but got %v", expected, actual)
	}

	fmt.Printf("ring buffer: %#v\n", ringBuffer)
}

type RingBuffer[T any] struct {
	buffer []T
	size   int
	mu     sync.Mutex
	write  int
	count  int
}

// NewRingBuffer creates a new ring buffer with a fixed size.
func NewRingBuffer[T any](size int) *RingBuffer[T] {
	return &RingBuffer[T]{
		buffer: make([]T, size),
		size:   size,
	}
}

// Add inserts a new element into the buffer, overwriting the oldest if full.
func (rb *RingBuffer[T]) Add(value T) {
	rb.mu.Lock()
	defer rb.mu.Unlock()

	rb.buffer[rb.write] = value
	rb.write = (rb.write + 1) % rb.size

	if rb.count < rb.size {
		rb.count++
	}
}

// Get returns the contents of the buffer in FIFO order.
func (rb *RingBuffer[T]) Get() []T {
	rb.mu.Lock()
	defer rb.mu.Unlock()

	result := make([]T, 0, rb.count)

	for i := 0; i < rb.count; i++ {
		index := (rb.write + rb.size - rb.count + i) % rb.size
		result = append(result, rb.buffer[index])
	}

	return result
}

// Len returns the current number of elements in the buffer.
func (rb *RingBuffer[T]) Len() int {
	rb.mu.Lock()
	defer rb.mu.Unlock()
	return rb.count
}