CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 3 of 7 · 3 min read

Batch with Unix tools

A chain of small programs can analyse gigabytes quickly.

Think of an assembly line in a workshop. One person cuts, the next sands, the next paints. Nobody does everything. Each takes the previous person's output.

The DDIA book starts with a web server that appends a line to a log for every request. A line includes the client address, the time, the requested page, the status code and the size of the reply. Suppose the question is: which five pages are visited most? The book answers with a pipeline of Unix commands:

cat access.log |
  awk '{print $7}' |
  sort |
  uniq -c |
  sort -r -n |
  head -n 5

Each step does one small job:

  1. cat reads the log file.
  2. awk '{print $7}' keeps only the seventh field of each line, which is the page address.
  3. sort puts the addresses in alphabetical order, so identical ones sit next to each other.
  4. uniq -c collapses runs of identical lines and puts a count in front.
  5. sort -r -n sorts by that count, biggest first.
  6. head -n 5 keeps the first five lines.

A worked example. Take six log lines, with only the page shown: /a, /b, /a, /c, /a, /b.

After step Content
awk /a, /b, /a, /c, /a, /b
sort /a, /a, /a, /b, /b, /c
uniq -c 3 /a, 2 /b, 1 /c
sort -r -n 3 /a, 2 /b, 1 /c
head -n 2 3 /a, 2 /b

The same job could be written as a short program with a hash table that counts each page. DDIA compares the two. The hash table needs memory proportional to the number of different pages. For a small or mid-sized website, all the distinct pages and a counter for each fit in about 1 GB. If the working set is larger than memory, the sorting approach wins, because sorting can use the disk well: it sorts chunks in memory, writes them as sorted files, and merges those files, which reads and writes the disk in long sequential runs (the same trick as the SSTables of Level 2). The GNU sort tool spills to disk and uses several cores by itself, so the chain scales to large files, and the main limit becomes how fast the file can be read.

Working set

The working set of a job is the amount of data it needs to keep in memory for random access while it runs.

Example: a page-counting program keeps one counter per distinct page, so its working set is the number of distinct pages times the size of a counter.

Why the pipeline works. DDIA ties it to the Unix philosophy of 1978: make each program do one thing well, expect the output of every program to become the input to another, build and try early, and use tools in preference to unskilled help. The book lists what makes composition possible:

  • A uniform interface. Every program reads and writes a sequence of bytes, usually lines of text, so any output can feed any input.
  • Separation of logic and wiring. Programs read from standard input and write to standard output and do not care where those lead. The user connects them with pipes. That is loose coupling.
  • Immutable input and no side effects. A program leaves its input unchanged and replaces its output, so it can be rerun as often as needed.

A pipe connects two programs with a small in-memory buffer and does not write the whole stream to disk. That detail returns in section 5.

Check yourself:

  • In the pipeline above, why must the first sort come before uniq -c?
  • Why can a sort-based job handle more distinct pages than a hash table job?