1969 EWD 249
Notes on Structured Programming
Edsger W. Dijkstra.
Testing can show the presence of bugs, never their absence. Build programs from a few structures you can reason about, so correctness is designed in, not tested in.
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.
Edsger W. Dijkstra.
Testing can show the presence of bugs, never their absence. Build programs from a few structures you can reason about, so correctness is designed in, not tested in.
E.F. Codd (IBM).
Data as relations, independent of how it is stored, ordered or indexed. Every SQL database, dataframe and warehouse sits on this idea.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Brian W. Kernighan, P. J. Plauger.
Peter Van Roy, Seif Haridi.
Peter Seibel.
Martin Kleppmann.
Bill Chambers, Matei Zaharia.
Roberto Vitillo.