The Ring Buffer: Why a Queue With No Limit Is a Memory Leak (and What Happens When It Fills)
An unbounded queue has no bound in the code — the only bound is the OOM killer. Measured: 9.9 MB to 617 MB over three million events, perfectly linear at 202.5 MB per million. A ring buffer replaces that with a fixed number of slots decided once at startup, and forces the one question the unbounded version never asked: what happens when it's full? Overwrite the oldest, or refuse the write. Same structure, opposite guarantee, one branch of code apart.
Here is a system small enough to hold in your head. One Python process. No broker, no network, no database. A request handler measures how long each request took and writes the sample into a queue. A background thread reads samples back out and appends them to a file on disk.
# one CPython process. no broker, no network, no database.
# the request handler writes a sample; a background thread drains it to disk.
from collections import deque
q = deque() # no maxlen
sample = {"path": "/checkout", "ms": 41.2} # one sample, made by the request
This works perfectly, right up until the writer is faster than the reader. And then it does something worse than break: it keeps working.
The queue never complains. It never returns an error, never logs a warning, never blocks. It just gets longer.
The failure that never looks like a failure
I ran it. A producer pushing 4× faster than the consumer drains, three million samples produced, 750,000 consumed, 2.25 million left as backlog:
=== collections.deque() (NO maxlen) ===
start RSS : 9.9 MB
after 250,000 events : RSS 60.6 MB grew 50.7 MB 202.8 MB/M events
after 1,000,000 events : RSS 212.4 MB grew 202.5 MB 202.5 MB/M events
after 2,000,000 events : RSS 414.8 MB grew 404.9 MB 202.5 MB/M events
after 3,000,000 events : RSS 617.2 MB grew 607.3 MB 202.4 MB/M events
9.9 MB to 617.4 MB. And look at the last column — 202.8 at the first checkpoint, 202.4 at the twelfth. The growth is not "roughly linear", it is linear to within a rounding error: 202.5 MB per million backlogged events, forever.
The accounting closes exactly, which is what makes it so mundane: 2.25 million dicts at 232 bytes each is 522 MB of dict objects, and the measured growth is 607 MB — the extra ~85 MB is the deque's own block storage plus the float objects inside each sample. Nothing is leaking in the C sense. Every byte is reachable, correct, and doing its job. There is simply no line of code anywhere that says stop.
This is why it is so hard to catch. A classic memory leak has a smoking gun — an object nobody freed. Here, every object has a legitimate owner. The queue is supposed to hold things. It is holding things. The bug is that nobody ever said how many.
Swap in queue.Queue() with no maxsize and you get the same curve — 617.4 MB peak, 196.4 MB per million — plus a lock on every operation that makes it 4.3× slower (4.60 s vs 1.08 s for the same work).
There is no bound in the code. The only bound is the OOM killer — and it doesn't run at a convenient time, it doesn't pick the process you'd have picked, and it leaves you a
Killedin dmesg and nothing else.
The fix is a decision, not a data structure
A ring buffer is a fixed-length array plus two integers. That's genuinely all it is:
CAPACITY = 8 # decided once, at startup, and never again
buf = [None] * CAPACITY # the entire memory footprint is this line
head = 0 # how many samples have ever been written
tail = 0 # how many samples have ever been read
The trick is that head and tail never wrap. They count forever. Only the index wraps, at the moment you touch the array:
class Ring:
def __init__(self, n):
self.buf = [None] * n # allocated once, never again
self.n = n
self.head = 0 # total writes, ever
self.tail = 0 # total reads, ever
def push(self, x):
self.buf[self.head % self.n] = x
self.head += 1
def pop(self):
x = self.buf[self.tail % self.n]
self.tail += 1
return x
Because the counters are monotonic, the three questions you actually want to ask become plain arithmetic, with no special cases:
- how many are in there?
head - tail - is it empty?
head == tail - is it full?
head - tail == n
Here is the same run against a 1,024-slot ring — identical producer, identical three million events:
start RSS : 10.4 MB
sys.getsizeof(buf) BEFORE : 8,248 bytes
after 1,000,000 events : RSS 11.0 MB grew +0.64 MB getsizeof(buf) 8,248
after 3,000,000 events : RSS 11.0 MB grew +0.64 MB getsizeof(buf) 8,248
After three million writes the container is byte-for-byte the same size it was before the first one. RSS growth: +0.64 MB against +607.4 MB — 949× less. Measured with tracemalloc on a smaller run, peak traced memory is 79.28 MB unbounded versus 0.27 MB for the ring, a ratio of 293:1.
One honest correction, because it's the kind of thing that gets repeated wrongly: in Python, "nothing is allocated after startup" is true of the buffer and false of the events. Half a million dicts really were created in that loop — I counted them. What the ring changes is that at most n of them are ever reachable, so CPython recycles the same freed memory instead of asking the OS for more. Memory goes flat, not to zero. In C, where the ring holds raw structs rather than pointers to heap objects, the stronger claim does hold — you malloc once at startup and push/pop are index arithmetic and a store, with no allocator on the hot path at all. That is precisely why kernels, audio callbacks and embedded firmware use this structure: not because it's fast, but because it's predictable.
The part everybody gets wrong: full and empty look identical
If head and tail are stored wrapped — the way most tutorials write it — the structure has a genuine ambiguity, and it is not a subtle one.
EMPTY ring : pushed 0, popped 0 -> (head, tail) = (0, 0)
FULL ring : pushed 8, popped 0 -> (head, tail) = (0, 0)
contents of the FULL ring's storage : [1, 2, 3, 4, 5, 6, 7, 8]
contents of the EMPTY ring's storage : [None, None, None, None, None, None, None, None]
(head, tail) pairs IDENTICAL? : True <-- BYTE-IDENTICAL
A buffer holding eight unread events and a buffer holding nothing produce the byte-identical pair (0, 0). And it isn't an artifact of starting at zero — do three push/pop cycles first and you get (3, 3) for empty and (3, 3) for full. head == tail cheerfully reports EMPTY while eight events sit there unread.
The reason is a counting argument, and once you see it the whole family of fixes falls out:
A ring of
nslots hasn + 1possible occupancies — 0 through n — but a pair of wrapped indices can only encodendistinct differences. One state doesn't fit.
So you either add one bit of information, or you delete a state. Every real implementation is one of those two moves:
| Technique | The move | Usable capacity | Cost |
|---|---|---|---|
Separate count field | add information | n of n | every push and pop must update a third variable |
| Waste one slot | delete a state | n − 1 of n | declare 8 slots, actually get 7 |
| Monotonic counters (never wrap) | add information | n of n | counters grow unboundedly (a non-issue at 64 bits) |
A single full boolean | add information | n of n | one bit, plus remembering to maintain it |
You'll often read that there are only two options — a count or a wasted slot. There are at least four, and the third one is the formulation used above and the one the Linux kernel's kfifo uses. It costs nothing and wastes nothing.
The real question: what happens when it's full?
Here's the part that makes this a system-design topic rather than a data-structures exercise.
Bounding the queue doesn't make the overflow problem go away. It forces you to answer it, at the moment you write the code, instead of discovering the answer at 3am when the OOM killer picks a process. And there are exactly two answers:
def push_overwrite(self, x): # a log buffer, a metrics window
if self.head - self.tail == self.n:
self.tail += 1 # give up the oldest sample
self.dropped += 1 # and COUNT what you gave up
self.buf[self.head % self.n] = x
self.head += 1
return True
def push_or_refuse(self, x): # a job queue: never lose work
if self.head - self.tail == self.n:
self.refused += 1
return False # the producer has to handle this
self.buf[self.head % self.n] = x
self.head += 1
return True
Same structure. Opposite guarantee. One branch of code apart.
Overwrite says: the newest data matters most, and I would rather lose history than lose the present. That's a metrics window, a log ring, an audio buffer, a flight recorder — you want the last N seconds before the crash, and the seconds before those are worthless.
Refuse says: every item is work that must not vanish, so if I can't take it, the producer needs to know. That's a job queue. Refusing is how backpressure gets created — the pain travels back up to whoever is producing too fast, which is the only place it can actually be fixed.
Choosing wrong is a data-loss bug wearing a performance costume. Silently overwriting a job queue loses paid work. Refusing writes to a metrics buffer takes down the request path to protect telemetry that nobody was going to read.
Python hands you both — but only one for free
from collections import deque
from queue import Queue
# POLICY ONE, handed to you: a bounded deque OVERWRITES, silently
d = deque([1, 2, 3], maxlen=3)
d.append(4) # d is now deque([2, 3, 4]) - the 1 is gone
# nothing raised, nothing logged, no return value
# POLICY TWO, and you have to ask for it by name
q = Queue(maxsize=3)
for i in (1, 2, 3): q.put_nowait(i)
q.put_nowait(4) # raises queue.Full
Just how silent is the overwrite? I went looking for anything at all that signals the loss:
append()returnsNone— exactly as it does on a non-full deque.- No exception, no warning, no log line.
len()is 8 before and 8 after, so length can't tell you either.- There is no attribute anywhere on the object that counts discards. I checked
dir().
The only way to know is to ask before you append: if len(d) == d.maxlen: dropped += 1. If you take one practical thing from this article, take that line.
The refusing side is loud but oddly terse: the exception is queue.Full, and str(e) is the empty string — the type is the message. After the refusal qsize() is still 8 and the contents are unchanged. Note which item died in each case: deque(maxlen) sacrifices the oldest data silently; Queue(maxsize) sacrifices the newest, loudly. Same bounded capacity, opposite victim.
One more distinction worth keeping straight: a deque without maxlen grows. A ring buffer refuses to — and refusing to grow is the entire feature, not a limitation you work around.
The loss isn't just bounded, it's predictable
"You'll drop data" sounds like a concession. It's actually the strongest thing about the design, because the drops obey a closed form:
ring n=1,024 burst= 900 events DROPPED 0 ( 0.00 %)
ring n=1,024 burst=1,200 events DROPPED 35,200 (14.67 %)
ring n=1,024 burst=4,096 events DROPPED 614,400 (75.00 %)
ring n=4,096 burst=4,096 events DROPPED 0 ( 0.00 %)
predicted drops = bursts x max(0, burst - n) -> EXACT MATCH, all four rows
drops = bursts × max(0, burst_size − n), and the measured count matched the prediction exactly in every configuration. Size the ring at or above the burst — the last row — and the drop count is exactly zero.
Meanwhile peak RSS stayed at ~11 MB across all of it. Push the overrun to its worst and peak memory does not move, because peak memory tracks the ring you chose, not the burst you got. That is the whole trade: you convert an unbounded, invisible, unpredictable memory risk into a bounded, counted, predictable data loss. One of those you can put on a dashboard and alert on. The other one pages you at 3am.
Where it's already running on your machine
You don't have to adopt this pattern; you're already surrounded by it. All of these are readable without root:
| Ring | Size on my box | Policy |
|---|---|---|
Kernel log ring (printk) | 256 KiB (CONFIG_LOG_BUF_SHIFT=18, fixed at kernel build) | overwrite the oldest |
| A pipe | 65,536 bytes = 16 pages of 4 KiB | refuse — blocks the writer |
perf event ring | 516 KiB per user | overwrite, and increments a lost-event counter |
| ALSA PCM preallocation | 32,768 KiB max per substream | overwrite (audio can't wait) |
The pipe is the best one, because you can watch it happen with no privileges at all. F_GETPIPE_SZ on a fresh pipe reports 65,536 bytes. Fill it non-blocking and it accepts exactly 65,536 and then the write refuses with EAGAIN. Read 8,192 bytes back out and the writer immediately accepts 4,096 more — the ring wrapped and reused the freed slots.
So the deque(maxlen)-versus-Queue(maxsize) decision isn't a Python quirk. It's the same fork, made inside the kernel: the log ring overwrites you, the pipe blocks you. Same structure, the other policy.
And note what perf does, because it's the design worth copying: it overwrites and counts what it lost. Overwriting is defensible. Overwriting silently is not.
The bit-trick that isn't (in Python)
While measuring, one piece of folklore fell over, and it's worth flagging because it's repeated everywhere: "use & (n - 1) instead of % n, it's much faster."
bare arithmetic head % N : 24.66 ns
bare arithmetic head & MASK : 34.27 ns <- the mask is 39 % SLOWER
inside a method RingMod.push : 285.14 ns
inside a method RingMask.push: 283.00 ns <- indistinguishable, it's noise
In CPython the mask is 39% slower on the bare arithmetic, and inside a real method call the difference vanishes into noise. Both are a single bytecode op, so it's a fair fight — CPython's long_mod has a fast path for single-digit ints while & goes through a more general path.
The trick is real in C, Rust and assembly, where % compiles to a hardware divide costing tens of cycles and & is one. Say it about compiled languages; don't claim it about the Python on your screen. Use whichever is clearer, and save the trick for the language where it pays.
While we're at it, here's what the operations actually cost:
| Operation | ns/op |
|---|---|
| hand-written ring push (Python method) | ~285 |
| hand-written ring pop | ~109 |
deque(maxlen=n).append on a full deque | ~37 |
Queue.put_nowait + get_nowait pair | ~1,867 |
The stdlib deque beats the hand-rolled ring by 7.8×, because deque is C and your ring pays a ~250 ns Python method call. Queue is 4.7× slower than the hand-written ring and 32.7× slower than deque — that gap is the lock, and it's the honest number for what thread-safety costs you.
So: write the ring by hand to understand it. In production Python, reach for deque(maxlen=n) — and add the drop counter yourself.
The reframe: this is the shape of LLM serving
If you work on model serving rather than web backends, you've met all of this under different names — and the failure mode is more expensive, because the memory in question is GPU memory.
The request queue in front of a model server is the exact push_or_refuse branch. An inference server can only hold so many concurrent sequences; the KV cache for each one is real, reserved VRAM. If the arrival rate exceeds the completion rate and the admission queue is unbounded, you don't get slow — you get a CUDA OOM that kills in-flight requests that were already 80% generated. This is why serving stacks admit a bounded number of sequences and reject the overflow with a 429 rather than buffering it. Refusing the write is the backpressure, and it's the difference between a degraded service and a dead one.
Sliding-window attention is push_overwrite, applied to context. A model with a fixed window keeps the last n tokens of KV cache and evicts the oldest as new ones arrive — a ring buffer over tokens, with the overwrite policy chosen deliberately because recent context is worth more than distant context. The fixed window is what makes memory per sequence a constant you chose at config time rather than a function of conversation length. Exactly the 617 MB → 11 MB trade, in VRAM.
Streaming token buffers are rings too. The generation loop produces tokens faster than a network client consumes them; a bounded buffer between them keeps a slow client from making the GPU-side loop hold unbounded state.
And the metrics case is the original one: every inference server tracks rolling TTFT and inter-token latency over a fixed window of recent requests. Not because old measurements are wrong, but because a p99 over "all of time" is useless and an unbounded list of samples is the 202.5 MB/million curve waiting to happen on your serving box.
The question is identical in every one of these, and it's the question the unbounded version never made anyone ask: when this fills up, does the oldest thing die quietly, or does the newest thing get refused loudly? In a token window, the oldest should die. In an admission queue, the newest must be refused. Getting that backwards costs you either a truncated context or a dropped payment.
The verdict
An unbounded queue is not a queue. It's an unbounded memory allocation with a friendly API, and it will happily grow at 202.5 MB per million events until the kernel picks a process and kills it. It never returns an error, because from its point of view nothing has gone wrong.
A ring buffer is a fixed number of slots decided once, at startup. That single constraint buys you three things: memory that is flat and known before you deploy (+0.64 MB versus +607.4 MB over the same three million events), loss that is predictable in closed form rather than catastrophic, and — most valuable of all — it forces the overflow decision into your source code, where you can read it, instead of leaving it to the OOM killer.
So the real content of this data structure isn't the modulo. It's the branch:
What a buffer does when it is full is a product decision wearing a data-structure costume. Overwrite the oldest and count what you dropped, or refuse the write and push back on the producer. Pick deliberately, write down why, and expose the counter.
In Python, reach for deque(maxlen=n) when overwriting is right and Queue(maxsize=n) when refusing is right. Then add the one line the stdlib doesn't give you — the counter that tells you it's happening.
References and further reading
The structure itself, and the wrap arithmetic
- Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed. (Addison-Wesley, 1997) — §2.2.2 "Sequential Allocation" is the classical treatment of a queue in a circular array, including the full-versus-empty problem and the wasted-slot fix.
- Linux kernel documentation, FIFO Buffer (
kfifo) — the monotonic-counter formulation used throughout this article, in production C.
Choosing the policy: overwrite or refuse
- Python documentation,
collections.deque— themaxlenparagraph, which is where the silent-discard behaviour is specified rather than implied. - Python documentation,
queue.Queue—maxsize,put_nowait, and thequeue.Fullexception. - Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017) — chapter 11 on message brokers frames "what happens when the queue fills" (drop, buffer, or apply backpressure) as a design decision with consequences, which is the argument this article makes at process scale.
Cost, locks, and lock-free rings
- Martin Thompson, Dave Farley, Michael Barker, Patricia Gee & Andrew Stewart, Disruptor: High Performance Alternative to Bounded Queues for Exchanging Data Between Concurrent Threads (LMAX, 2011) — a production ring buffer built specifically to avoid the lock that costs
queue.Queueits 32.7× penalty here. - Ross Bencina, Real-time audio programming 101: time waits for nothing — why "no allocator on the hot path" is a correctness requirement and not an optimisation, which is the strongest case for the fixed-at-startup array.
Where the rings already are
man 7 pipe— pipe capacity andF_GETPIPE_SZ; the 65,536-byte figure measured above, and the blocking semantics that make a pipe the refusing variant.- Brendan Gregg, Systems Performance: Enterprise and the Cloud, 2nd ed. (Addison-Wesley, 2020) — the
perfand BPF ring buffers, including the lost-event counters that make overwriting observable rather than silent.
If a reference you'd expect is missing, say so in the comments and I'll add it.
Watch the reel: the 2-minute version frames the failure, and the full episode builds the ring from scratch and runs every measurement on screen.