LetItCrash

Backpressure: the queue that says no before it overflows

LLM-authored, human-reviewed

Algorithms & theory

The bounded-job-queue project ends with a strange little return value: enqueue gives you back :ok when there is room, and :full when there is not. The :full is not a failure mode. It is the whole point. It is the mechanism that keeps a fast producer from drowning a slow consumer, and it has a name: backpressure. This article names it, shows why an unbounded queue is the alternative, and explains why the rejection has to travel back upstream.

Why the queue grows

A producer and a consumer almost never run at the same speed. The producer writes work into a queue; the consumer drains it. If the producer is faster, the queue grows. Paul Butcher puts the stakes plainly, writing about a parser feeding a word counter:

The issue is that the producer and consumer may not (almost certainly will not) run at the same speed. In particular, if the producer runs faster than the consumer, the queue will get larger and larger. Given that the Wikipedia dump we’re parsing is around 40 GiB, that could easily result in the queue becoming too large to fit in memory.

That last clause is the failure. An unbounded queue does not fail loudly; it fails by holding everything you gave it until the machine runs out of memory. The producer is happy, the consumer is busy, and the system dies of storage. The queue that “always accepts” is the queue that eventually accepts the system’s own life.

The three responses

When the queue is full, there are three choices. The first is to do nothing - let it grow. That is the unbounded queue above, and its end is memory exhaustion. The second is to make the producer wait. Butcher names the tool for that: “Using a blocking queue, by contrast, will allow the producer to get ahead of the consumer, but not too far.” A blocking put sleeps until there is space, so the producer cannot run away, but it also stops doing anything else while it waits.

The third is to refuse. Return :full and let the producer decide what to do next - retry, drop the work, slow down, or shed load elsewhere. That refusal is backpressure, and it is what the bounded-job-queue project builds:

defmodule BoundedQueue do
  def new(max), do: %{max: max, items: :queue.new()}

  def enqueue(%{max: max, items: items} = q, job) do
    if :queue.len(items) >= max do
      {:full, q}
    else
      {:ok, %{q | items: :queue.in(job, items)}}
    end
  end

  def dequeue(%{items: items} = q) do
    case :queue.out(items) do
      {{:value, job}, rest} -> {{:ok, job}, %{q | items: rest}}
      {:empty, _} -> {:empty, q}
    end
  end
end

The queue never holds more than max jobs. The decision is explicit: len(items) >= max means no room, and the answer is :full, not a silent grow.

The bound is a proof obligation

A bounded queue is more than a queue with an if in it. The bound is a property the program states about itself and must preserve through every step. Leslie Lamport, analyzing the producer-consumer problem, writes the invariant of an N-element bounded queue as two conditions that must hold in every state of every execution: the buffer’s length never exceeds N, and the concatenation of what has already been output, what is in the buffer, and what is waiting to come in always equals the full input sequence.

The first condition is the backpressure - nothing is ever held that the bound does not allow. The second is the correctness - nothing is ever lost. Both are the same idea the queue enforces at runtime: a producer can get ahead, but only to the edge of the buffer, and every item either sits in the buffer or has already come out the other side. The :full return is how the program keeps the first condition true, one enqueue at a time.

The rejection is a signal

The reason the third response matters is that :full does not stay where it is. It travels. In a pipeline of stages - read, parse, count, store - the queue at each boundary carries the signal from the slow stage back to the fast one. When the counter falls behind, its input queue fills, its :full tells the parser to slow down, the parser’s queue fills in turn, and the reader slows with it. The slowest stage sets the pace for every stage ahead of it.

This is why backpressure is not a local detail. It is the difference between a system that degrades gracefully and one that collapses. A system with no backpressure hides its overload until the memory runs out; a system with backpressure turns overload into a signal that propagates to the place that can actually do something about it. The same pattern appears under different names everywhere: TCP’s receive window, a reactive stream’s demand, a message queue’s prefetch limit. All of them are one producer saying to another, “I am full; send less.”

On the BEAM

The BEAM gives every process a mailbox, and a mailbox is a queue. The default is unbounded: a process that cannot keep up with its messages accumulates them forever. The bounded-job-queue project wraps that default in a decision - a GenServer that keeps a count, accepts while the count is under the limit, and replies :full when it is not.

This is the let-it-crash idea, pointed at a queue. Letting a process fail loudly and restarting it under a supervisor is better than letting it silently corrupt itself; refusing a job with :full is the queue’s version of the same preference. A loud :full is recoverable - the producer can retry later, or drop, or slow. An unbounded queue is a slow crash that takes the whole node with it.

Choosing a response

Response What the producer does The cost When to use it
Grow keeps sending unbounded memory never in production
Block sleeps until there is room the producer stalls when the producer has nothing else to do
Reject decides: retry, drop, or slow the producer needs a policy when the producer can do useful work while waiting

The block and the reject are both bounded, and both are valid. The choice is about whether the producer has a better use for its time than waiting. A web request handler has a user waiting, so it should reject fast and let the client retry. A background reader has nothing to do but read, so it can block. Backpressure is the reject, but the point is the bound, not the mechanism.

The same “no” as rate limiting

Backpressure and rate limiting are the same idea wearing two costumes. A rate limiter says no because the client has already had its share of time; a bounded queue says no because the buffer has already used its share of space. One is admission control at the door, the other is admission control at the inbox. The rate limiting article walks the time-bound version; this one walks the space-bound version. Both answer the same question - will accepting this one more thing make the system fail - and both answer it with a no that arrives early enough to matter.

Where to go next

A queue is a promise about order. A bounded queue adds a second promise, about size. The :full return is how the queue keeps that second promise, and it is the difference between a system that knows when it is drowning and one that discovers it only after the memory is gone.

← Back to articles

Exercises