The bounded buffer

The problem it solves

Producers make work. Consumers do work. They run at different speeds, and neither can be told to slow down by the other.

If the buffer between them is unbounded, the fast side wins and the slow side falls behind forever — which is not “handling the load”, it is converting a visible failure into an invisible one. Memory grows, the queue’s contents age, and the first symptom is an out-of-memory kill or a latency measured in minutes. If the buffer is bounded, something has to happen when it fills, and that something is the actual design decision.

A bounded buffer is where backpressure stops being a word and becomes a mechanism. When the buffer is full, the producer does not consult a flag and decide to be polite. It calls acquire on a semaphore with no permits, and it cannot proceed. Being unable to continue is the flow control — there is no cooperation required, and no way to opt out by forgetting.

The mechanism

Two counting semaphores facing opposite directions, plus a mutex for the buffer itself:

• slots starts at the capacity and counts the space available to producers.
• items starts at zero and counts the work available to consumers.

Produce: acquire a slot, insert under the mutex, release an item. Consume: acquire an item, remove under the mutex, release a slot.

The elegance is that the invariant maintains itself and neither side counts the other. A producer cannot insert into a full buffer because there is no slot to take; a consumer cannot take from an empty one because there is no item. Nobody checks size and nobody compares against a limit — the permits are the limit, and the arithmetic is enforced by the primitive rather than by everyone remembering.

The mutex is still needed: the semaphores control how many threads may be inside, and the mutex controls the buffer’s internal structure while they are. Two producers who both hold slots may still not modify the list simultaneously.

What the enumeration shows

Three producers, one consumer, a buffer of two. No interleaving ever holds three items — the bound is not merely usually respected, it is unreachable. Step through and watch a producer’s badge read blocked · semaphore slots: it is waiting because there is nothing to take, and it will resume when the consumer releases one.

That badge is the picture of backpressure worth carrying. The fast side is running at the slow side’s pace, and no code anywhere says so.

Then switch to bounded-buffer-unbounded, which removes the slot semaphore while leaving the mutex and the capacity in place. The capacity is now a comment. 844 of 2,500 interleavings hold more than the buffer was designed for, because producers run whenever they are scheduled to and nothing stops them. This is exactly the shape of an unbounded queue in production: the limit exists in the design document and in nobody’s code path.

The numbers worth carrying

• With the slot semaphore: 0 overflows. Without: 844 of 2,500 interleavings overflow.
• Buffer sizing is a latency decision, not a memory one. Depth divided by drain rate is the age of the oldest item: a buffer of 10,000 draining at 1,000/s means the head is ten seconds old. Size from the staleness you can tolerate, then check the memory fits — not the other way round.
• A buffer only absorbs variance. If the producer’s mean rate exceeds the consumer’s, no capacity is sufficient; you have a deficit, and the buffer only sets how long until you notice.

Where it breaks down

Blocking the producer may be the wrong answer. For a metrics pipeline, telemetry or a live feed where only the latest value matters, dropping is correct and blocking is a bug — you have coupled a non-critical path to a critical one. The three options are grow, drop and push back, and the backpressure page walks through choosing between them.

Backpressure must have somewhere to go. Blocking an internal producer works. Blocking a thread that is servicing a network request just moves the queue into the network, where it is invisible and where clients time out and retry — see retry storms. At the true edge the only options are drop and shed.

Blocking while holding a lock deadlocks. A producer that acquires the mutex before the slot semaphore will block on the semaphore while holding the mutex the consumer needs to free a slot. The acquisition order in this program — semaphore first, then mutex — is load-bearing, and reversing it is a textbook deadlock.

Multiple consumers reorder. Competing consumers give you throughput and no ordering guarantee across them; if messages about the same entity must be applied in order, one queue is not enough. That is the queues and ordering problem.

What people get wrong

“Add a queue so nothing is lost.” An unbounded queue loses things too — to timeouts, after paying the full cost of processing work whose requester left.

“The queue is our buffer for spikes.” Only if the average is sustainable. Buffers absorb variance, not deficits.

“We set the capacity to 100,000 because we had the memory.” That is a promise to answer very late. Compute the age of the head at your drain rate and see whether you meant it.

“size() < capacity then insert.” Check-then-act. Two producers both pass the check. The permit exists so that the check and the reservation are one operation.

In production

ArrayBlockingQueue and LinkedBlockingQueue in Java, and note that LinkedBlockingQueue is unbounded by default — a genuinely dangerous default, and the direct cause of a great many heap exhaustions, because a ThreadPoolExecutor configured with one will queue without limit rather than rejecting. Go’s buffered channels are bounded by construction and block on send when full, which is the same design with the semaphores hidden. asyncio.Queue in Python takes a maxsize. Disruptor and other ring buffers are the high-performance variant, using a pre-allocated array and sequence numbers instead of locks.

The operational metric that matters is not depth but age of the head, or equivalently depth divided by drain rate, because depth without a rate has no units anyone feels. A dashboard showing “queue depth 40,000” tells you nothing; “oldest item 38 seconds” tells you the system is broken.

And the design rule the whole page reduces to: every queue has a bound, and every bound has a documented behaviour when reached. A queue whose bound is “whatever the heap allows” has both — neither was chosen.

The follow-up questions

“What happens when the queue is full?” — Block, drop, or reject. Have an answer per queue, and say which you chose and why.

“How big should the buffer be?” — From the latency you can tolerate: depth over drain rate. Answering in megabytes is answering a different question.

“Your producer is faster than your consumer. How long until you have a problem?” — Deficit rate times time against the bound. If unbounded, until the heap dies.

“Which do you acquire first, the semaphore or the mutex?” — The semaphore. Reversing it deadlocks, and being able to say why is the point of the question.