// readings

Papers and books.

Papers and books behind today's tools, in order of publication. Each paper with its idea in one line and the paper it builds on; each book with its notes on the blog.

2023-06-25
1971 EWD 316

A Short Introduction to the Art of Programming

Edsger W. Dijkstra.

Programming is designing a class of computations, not writing a program: actions, states, and reasoning about them one step at a time.

Builds on: Structured Programming (1969). Two years later, the same discipline written for newcomers: reason about actions and states before writing code.

blog post (1)
2023-04-11
1972 CACM

The Humble Programmer

Edsger W. Dijkstra (ACM Turing Award lecture).

Software outgrew our heads. A competent programmer knows the limits of their own skull and keeps programs small enough to reason about, instead of testing them into shape.

Builds on: Structured Programming (1969). The Turing lecture takes the argument of the Notes to the whole field: only programs we can reason about can grow.

blog post (1)
2023-03-04
1988 EWD 1036

On the Cruelty of Really Teaching Computing Science

Edsger W. Dijkstra.

Computing is a radical novelty that analogies hide. Teach it as the formal manipulation of symbols, with proofs, from the first day.

Builds on: Humble Programmer (1972). Sixteen years later, aimed at teaching: if programs must be reasoned about, students should learn to reason formally before they touch a machine.

blog post (1)
2026-10-23
1993 Codd & Associates

Providing OLAP to User-Analysts: An IT Mandate

E.F. Codd, S.B. Codd, C.T. Salley.

Analysts need a multidimensional view (dimensions, hierarchies, totals) that transactional SQL doesn’t give. Vendor-sponsored, so read it critically.

Builds on: Relational model (1970). Same author, 23 years later. Relations and SQL ran the transactions (OLTP), but analysts needed dimensions, hierarchies and totals across them, so Codd named OLAP as a separate job.

blog posts (3)
2026-10-23
2003 SOSP

The Google File System

Ghemawat, Gobioff, Leung (Google).

A file system for huge, append-only files on cheap machines that fail: one master for metadata, 64 MB chunks replicated three times.

Next problem after: OLAP (1993). Warehouses ran on one big, expensive server. A web crawl of hundreds of terabytes fits on no single machine, so Google spread storage over thousands of cheap ones that fail all the time.

blog post (1)
2026-10-23
2004 OSDI

MapReduce: Simplified Data Processing on Large Clusters

Dean, Ghemawat (Google).

You write map and reduce; the library handles partitioning, the shuffle and failed machines. Every batch engine still uses its vocabulary.

Builds on: GFS (2003). Storage first, then computation next to it: map tasks run on the machines that hold their GFS chunks, and the output goes back to GFS.

blog posts (3)
2026-10-23
2006 OSDI

Bigtable: A Distributed Storage System for Structured Data

Chang, Dean, Ghemawat, Hsieh, Wallach, Burrows, Chandra, Fikes, Gruber (Google).

A sorted map by row, column and timestamp, written to memory and flushed to immutable SSTables: the LSM tree behind HBase, Cassandra and RocksDB.

Builds on: GFS (2003). Bigtable keeps its commit log and SSTables as files in GFS, and adds what a file system lacks: rows, columns and fast lookups by key.

blog posts (2)
2023-10-09
2007 Foundations and Trends in Databases

Architecture of a Database System

Hellerstein, Stonebraker, Hamilton.

How a relational database is built inside: process models, parallelism, the query optimizer and executor, storage, and transactions.

Builds on: Relational model (1970). Codd said what a relational database is; this one shows how the systems that implement it are put together, decades of engineering later.

blog posts (2)
2026-10-23
2009 VLDB

Hive: A Warehousing Solution Over a Map-Reduce Framework

Thusoo, Sarma, Jain, Shao, Chakka, Anthony, Liu, Wyckoff, Murthy (Facebook).

SQL on Hadoop: queries compile to MapReduce jobs, tables are HDFS directories, and schemas live in a metastore that outlived Hive itself.

Next problem after: MapReduce (2004). Every question had to be written as Java map and reduce functions. Facebook’s analysts knew SQL, so Hive compiles SQL into MapReduce jobs.

blog posts (3)
2026-10-19
2010 MSST

The Hadoop Distributed File System

Shvachko, Kuang, Radia, Chansler (Yahoo!).

GFS rebuilt in open source: one NameNode keeps metadata in memory, DataNodes hold 128 MB blocks replicated three times.

Builds on: GFS (2003). The open-source copy of GFS, built for Hadoop at Yahoo!: the NameNode plays the master, DataNodes play the chunkservers.

blog posts (5)
2026-10-23
2024 SIGMOD Record

What Goes Around Comes Around... And Around...

Stonebraker, Pavlo.

Twenty years of “SQL killers” (MapReduce, key-value, document, vector, graph) reviewed: each one was absorbed by relational systems or stayed a niche.

Builds on: Relational model (1970). Fifty-four years on, it checks every challenger to Codd’s model and finds that SQL absorbed the useful parts.

Next problem after: MapReduce (2004). MapReduce is one of those challengers: the systems built on it, like Hive, ended up putting SQL back on top.

blog post (1)
2023-05-19
1978 McGraw-Hill, 2nd ed.

The Elements of Programming Style

Brian W. Kernighan, P. J. Plauger.

blog posts (11)
2023-01-05
2009 Apress

Coders at Work: Reflections on the Craft of Programming

Peter Seibel.

blog posts (33)