Backpressure and Deadlock in Long-Running Pipelines

A pipeline of stages connected by pipes has exactly one flow-control mechanism: when a pipe is full, the writer blocks. There is no acknowledgement, no window negotiation, and no way for a consumer to say “slower” other than by not reading. That single mechanism is sufficient for correctness and insufficient for many of the pipelines people build, and the failures it produces look like hangs rather than like errors.

Blocking is the protocol

The buffer in a pipe is finite: 65,536 bytes by default on Linux, as described in pipe buffering. When a writer fills it, the next write sleeps until the reader drains space. When a reader finds it empty, the read sleeps until a writer adds data.

This is a rendezvous, and it enforces an invariant that is worth stating precisely: at any instant, the amount of data in flight between two consecutive stages is at most one buffer. The producer can be ahead of the consumer by that amount and no more. Neither side can run arbitrarily far ahead, and neither can be starved while the other makes progress, because the kernel schedules both.

That property is what makes a pipeline safe for unbounded input. A command that generates a terabyte of output into a consumer that reads slowly will run at the consumer’s rate, with bounded memory, without either program implementing a rate limit. The rate limit is imposed by the kernel’s willingness to accept bytes.

Barriers break the streaming property

The problem is that not every stage can produce output before consuming all of its input. A stage that sorts, groups, or aggregates has to see the final record before it can emit the first one. Such a stage is a barrier, and while it is absorbing input the upstream portion of the pipeline runs at full speed until it fills the pipe and blocks.

A pipeline like generate | sort | head -n 10 is the canonical case. The generator cannot be stopped early by the fact that only ten lines are needed, because sort requires all of them. Total memory is bounded by sort’s decision to spill to temporary files, and total disk usage is proportional to input size. The pipeline still terminates, but head provided no benefit at all: the entire input was consumed before the first line of output existed.

# barrier: the whole input is consumed before any output
generate | sort | head -n 10

# streaming: head exits, the producer dies on SIGPIPE
generate | head -n 10

In the second form, head exits after its tenth line, the pipe’s read end closes, and the generator dies on SIGPIPE. The difference between the two command lines is one stage, and the resource profile differs by orders of magnitude. Recognising which stages are barriers and which are streaming is the main design skill in composing long pipelines.

Aggregation is the other common barrier shape. Summing, counting, computing a maximum, and building a histogram all require the complete input. The streaming alternative is to compute the aggregate incrementally and never materialise the input, which turns a barrier into a running fold with constant memory. When the aggregate cannot be expressed that way, the barrier is unavoidable and the only remaining choices are where the intermediate data lives and how much of it is spilled.

Deadlock needs a cycle

A single linear pipeline cannot deadlock. Data flows one way, and the kernel’s blocking provides flow control without any possibility of a wait cycle: a blocked writer is waiting on a reader that is always capable of eventually running.

Deadlock requires a cycle in the wait graph, which appears as soon as two pipes are used in opposite directions. Two processes, each writing to the other before reading, will each fill its outgoing pipe and then block. Each is waiting for the other to drain, and neither will. The buffer size determines how much is written before the deadlock becomes visible, which is a few kilobytes for small buffers and more for large ones, but not whether it happens.

The same cycle appears with a single pipe when a stage’s input and output are the same descriptor, which happens with careless redirection. cmd < file > file is not a cycle in the wait graph, but it destroys the file: the shell truncates the file when it sets up the redirection, and the program then reads an empty file. Using >> avoids the truncation but still writes into the data being read.

A subtler cycle exists between a process and itself. A program that writes enough to a pipe that it also reads from will block on the write with a full buffer and never reach the read. The cycle is in one process, and the fix is either a separate thread or a buffer large enough to hold the whole payload, which converts the design into one that requires bounded input.

Co-processes and the general two-way pattern

Shells provide a construct for genuine two-way communication: bash’s coproc, ksh’s |&, and the older named-pipe arrangement. All of them create two pipes and expose both ends to the parent, which is then responsible for the protocol. Because the parent holds both ends, it must never do a blocking write while the child is blocked on a write of its own; the negotiation has to be request-response with the parent reading first, or the cycle reappears.

The general rule for any two-way arrangement is to designate one side as the driver and have it always read before writing. That is a protocol constraint, not a kernel constraint, and no amount of buffer tuning substitutes for it. A protocol that requires both sides to speak first is deadlocked by construction.

Buffering upstream of the pipe

Backpressure works because the pipe is the only place data can accumulate. Anything that adds buffering between the producer and the pipe removes the guarantee.

The common additions are the C library’s output buffer, a program’s own internal queue, and an intermediary that reads everything and then writes. The first is bounded and small, and its effect is only to add latency. The second is bounded by the program’s design and is often the actual limit. A producer that batches ten thousand records in memory before writing is holding that many records regardless of what the pipe does. The third is unbounded in the worst case and converts a pipeline into a two-phase job with a materialised intermediate result.

Any of them means the consumer’s slowness no longer propagates to the producer within one buffer’s worth of data. A producer with an internal queue of a million records will keep generating for a million records after the consumer stops, and the memory it holds is the price of that decoupling. Explicit and bounded is the alternative: a fixed-capacity queue that blocks the producer when full gives the same decoupling without the unbounded growth, at the cost of having to choose a capacity.

Choosing the shape

Three shapes cover most cases, and the choice follows from whether the stages stream and whether any stage needs the whole input.

A linear chain of streaming stages needs no design work. The pipe’s buffer is the only queue, memory is bounded, and termination is immediate on either side failing. This is the shape a filter should be written for, and the requirements are modest: read in blocks, write what can be written, do not accumulate.

A chain with a barrier needs a decision about intermediate storage. If the barrier is a sort, the cost is spilling to disk and the pipeline’s peak disk usage is proportional to input. If the barrier is an aggregate, the cost can often be reduced to a running fold with memory proportional to the number of distinct keys rather than the number of records.

A job that must not block its producer needs an explicit queue with a chosen capacity, and the queue’s capacity is a policy decision about how far ahead the producer may run. Beyond that point, the producer waits. Anything else, such as an unbounded queue, a retry loop, or a thread pool that grows, removes the limit without replacing it, and the failure mode moves from a visible stall to a memory exhaustion that arrives later and with less context.

Where the shell stops helping

The shell can express the wiring but not the policy. It can create pipes, start stages, and report statuses, but it has no way to say “this stage may buffer up to N items” or “this stage may be skipped when the consumer is saturated”. Those decisions belong to the programs, and a program that is not written to honour backpressure cannot be made to honour it from outside.

The visible symptom of a pipeline that has lost its backpressure is a hang in the producer with a consumer that is idle, or memory growth in a process whose output is supposedly being consumed. In the first case the block is somewhere other than the pipe; in the second, the queue is. Both are diagnosed by looking at where the data accumulates rather than at the shell command that started the process, and both are fixed in the program rather than in the invocation.