ring buffers #

A ring buffer stores a bounded sequence in a fixed array while treating the end of the array as adjacent to the beginning. Logical movement is monotonic; physical positions wrap modulo the capacity.

It is also called a circular buffer. The structure is simple, but its contract is not: a full producer may reject, block, or overwrite; readers may consume items or inspect retained history; and concurrent versions depend on a precise publication protocol.

logical order over physical wraparound #

An eight-slot array contains four logical items in slots six, seven, zero, and one. The read cursor points to slot six and the write cursor points to slot two. Logical order wraps from slot seven to slot zero. physical array CD····AB 01234567 logical order: A → B → C → D read = 6 write = 2 capacity = 8 · length = 4 · next push writes slot 2 · next pop reads slot 6

With capacity C, a logical position maps to storage as

slot(position) = position mod C

When C is a power of two, unsigned positions can use

slot(position) = position & (C - 1)

The mask is an implementation optimization, not a different structure. Monotonically increasing counters are often easier to reason about than cursors that themselves wrap at C: occupancy is write - read, while only array access applies the mask or modulo.

distinguishing empty from full #

If only reduced read and write indices are stored, read == write is ambiguous: it can mean empty or full. Three common representations resolve it:

1. reserve one slot, so usable capacity is C - 1 and equality always means empty;
2. store an explicit length in [0, C];
3. keep monotonic read and write counters, so equality means empty and write - read == C means full.

The third form composes especially well with sequence numbers and concurrency, but counter wrap must still be defined. Unsigned subtraction is safe only while the live distance stays within the chosen half-range assumptions.

queue versus rolling history #

A bounded FIFO and a rolling history can use the same representation but have different full-buffer semantics.

bounded queue #

A push into a full queue can:

• fail immediately, applying backpressure to the caller;
• block until a consumer advances read;
• drop the new item.

Existing unread data remains intact.

rolling history #

A push into a full history overwrites the oldest item and advances both ends:

storage[write mod C] = item
write += 1
if write - read > C:
    read = write - C

This keeps the newest C items. It is appropriate for telemetry, replay windows, recent events, and diagnostic context—not for work that must be processed exactly once.

Naming the policy is part of the type. A generic push whose overflow behavior is implicit invites data loss.

operations and complexity #

operation	cost
push one item	O(1)
pop one item	O(1)
peek oldest/newest	O(1)
iterate n live items	O(n)
storage	O(C) fixed

The fixed bound prevents allocator growth and makes memory use predictable. Contiguous storage gives good locality, though one logical range may require two physical slices:

[first physical run: read .. end]
[second physical run: 0 .. write]

APIs that expose these two slices can perform batched I/O without copying the wrapped sequence into a temporary contiguous buffer.

ownership and overwrite #

For inline values, overwrite is an assignment. For pointers, strings, or other owned resources, replacing the oldest slot must first destroy or transfer the old value. Likewise, pop must define whether ownership moves to the caller or the element is borrowed until the next mutation.

Useful slot states are therefore not always just “occupied.” A concurrent or fallible producer may need empty, being written, and published states so a consumer never observes half-initialized data.

replay by sequence number #

A history ring often stores a monotonic sequence number with each item. This separates identity from physical slot reuse:

slot = sequence mod C

A reader asking for everything after cursor s must compare s with the oldest retained sequence. If the cursor precedes the retained window, replay is incomplete and the API should report a gap rather than silently returning a suffix that looks complete.

Sequence tags also detect stale reads: slot i may exist, but if its stored sequence is not the requested one, that slot has already been reused.

concurrency is a protocol #

A mutex around push and pop is correct and often sufficient. Lock-free rings need stronger assumptions and are not interchangeable.

single producer, single consumer #

An SPSC ring can give each cursor one writer:

1. producer writes the item into its slot;
2. producer release-stores the new write position;
3. consumer acquire-loads that position before reading the item;
4. consumer release-stores the new read position after consuming it.

The acquire/release pair publishes slot contents. Relaxing it without a proof can expose a cursor before the corresponding bytes are visible.

multiple producers or consumers #

A shared fetchAdd cursor alone is insufficient: it reserves positions but can publish position n + 1 before producer n has finished writing. Bounded MPMC rings commonly attach a sequence number to every slot. Producers and consumers claim a slot only when its sequence denotes the expected generation, then publish the next generation after writing or reading.

This solves slot reuse and publication ordering together, at the cost of more metadata and atomic traffic. False sharing also matters: heavily written producer and consumer cursors should not occupy the same cache line.

failure and shutdown #

A production ring needs behavior for more than full and empty:

• Can a blocked operation be cancelled?
• Does shutdown drain existing items or discard them?
• How is a producer failure after reservation represented?
• Are dropped items counted and observable?
• Does a snapshot hold the lock, copy items, or tolerate concurrent overwrite?

A bounded structure turns overload into a decision. That decision should be visible in metrics and in the API contract.

when it fits #

Ring buffers are a strong fit when order matters, capacity is naturally bounded, and old storage can be reused:

• producer/consumer handoff;
• network and audio buffers;
• rolling logs and telemetry;
• cursor replay windows;
• scheduler ready queues;
• fixed-window batching.

They are a poor fit when capacity must grow without a hard policy, arbitrary middle insertion or removal is common, stable addresses are required, or every item must survive overload without external backpressure.

sources #

• Leslie Lamport, “Specifying Concurrent Program Modules,” ACM Transactions on Programming Languages and Systems 5(2), 1983, doi:10.1145/69624.357207.
• Linux kernel documentation, Circular Buffers.
• Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?, Circular Buffers.

in these projects #

• pub-search's pending-search buffer is a mutex-protected rolling queue: when full, it frees and drops the oldest search before inserting the newest, then drains ownership into a local batch before performing network I/O.
• Coral's pulse history uses a monotonic pulse sequence and sequence mod capacity to retain a fixed recent window for frontend replay.