How do pipelines limit memory usage?
The data doesn’t need to be stored in RAM. Pipes block their writers if the readers aren’t there or can’t keep up; under Linux (and most other implementations, I imagine) there’s some buffering but that’s not required. As mentioned by mtraceur and JdeBP (see the latter’s answer), early versions of Unix buffered pipes to disk, and this is how they helped limit memory usage: a processing pipeline could be split up into small programs, each of which would process some data, within the limits of the disk buffers. Small programs take less memory, and the use of pipes meant that processing could be serialised: the first program would run, fill its output buffer, be suspended, then the second program would be scheduled, process the buffer, etc. Modern systems are orders of magnitude larger than the early Unix systems, and can run many pipes in parallel; but for huge amounts of data you’d still see a similar effect (and variants of this kind of technique are used for “big data” processing).
In your example,
sed 'simplesubstitution' file | sort | uniq > file2
sed reads data from file as necessary, then writes it as long as sort is ready to read it; if sort isn’t ready, the write blocks. The data does indeed live in memory eventually, but that’s specific to sort, and sort is prepared to deal with any issues (it will use temporary files it the amount of data to sort is too large).
You can see the blocking behaviour by running
strace seq 1000000 -1 1 | (sleep 120; sort -n)
This produces a fair amount of data and pipes it to a process which isn’t ready to read anything for the first two minutes. You’ll see a number of write operations go through, but very quickly seq will stop and wait for the two minutes to elapse, blocked by the kernel (the write system call waits).
But I don't understand how this could limit memory usage considering the fact that the data has to be stored in RAM to transmit between programs.
This is your fundamental error. Early versions of Unix didn't hold pipe data in RAM. They stored them on disc. Pipes had i-nodes; on a disc device that was denoted the pipe device. The system administrator ran a program named /etc/config to specify (amongst other things) which volume on which disc was the pipe device, which volume was the root device, and which the dump device.
The amount of pending data was constrained by the fact that only the direct blocks of the i-node on disc were used for storage. This mechanism made the code simpler, because much the same algorithm was employed for reading from a pipe as was employed for reading for a regular file, with some tweaks caused by the fact that pipes are non-seekable and the buffer is circular.
This mechanism was replaced by others in the middle to late 1980s. SCO XENIX gained the "High Performance Pipe System", which replaced i-nodes with in-core buffers. 4BSD made unnamed pipes into socketpairs. AT&T reimplemented pipes using the STREAMS mechanism.
And of course the sort program performed a limited internal sort of 32KiB chunks of input (or whatever smaller amount of memory it could allocate if 32KiB was not available), writing the sorted results to intermediate stmX?? files in /usr/tmp/ which it then externally merge sorted to provide the final output.
Further reading
- Steve D. Pate (1996). "Inter-process communication". UNIX Internals: A Practical Approach. Addison-Wesley. ISBN 9780201877212.
- Maurice J. Bach (1987). "System Calls for the File System". The Design of The Unix Operating System. Prentice-Hall. ISBN 0132017571.
- Steven V. Earhart (1986). "
config(1M)". Unix Programmer's Manual: 3. System Administration Facilities. Holt, Rinehart, and Winston. ISBN 0030093139. pp. 23–28. - Abhijit Menon-Sen (2020-03-23). How are Unix pipes implemented?. toroid.org.