The foundations of big data
Data becomes “big” at the point where it no longer fits on one machine, or arrives faster than one machine can read it. Everything that follows — the file systems, the engines, the vocabulary — is a consequence of having to spread one job across many computers, some of which will fail while it runs.
Large datasets about people are hard to make anonymous. In a study first circulated in 2006 and published in 2008, Arvind Narayanan and Vitaly Shmatikov re-identified subscribers in a released set of film ratings from which names had been removed, using only a few ratings known from elsewhere. Differential privacy, defined by Dwork, McSherry, Nissim and Smith in 2006, gives a mathematical meaning to “this release reveals almost nothing about any one person”. The European GDPR has applied since 2018.
In 1936 a magazine poll of 2.4 million Americans predicted the wrong president; George Gallup, with some fifty thousand chosen with care, got it right. A biased sample does not improve by growing. The same lesson returned when a flu estimate built from search queries overshot badly, as David Lazer and colleagues documented in 2014.
Counting the distinct visitors in a billion events exactly needs memory in proportion to the answer. A sketch gives the answer to within a per cent or two in a few kilobytes. Burton Bloom’s filter (1970), reservoir sampling (an older method, made fast by Jeffrey Vitter in 1985) and HyperLogLog (Philippe Flajolet and colleagues, 2007) are the classics.
A batch job reads everything collected so far and reports hours later; a stream processor updates its answer with every event. Batch came first, with MapReduce in 2004. Treating the data itself as an append-only log that many readers can replay — the design of Kafka, released in 2011 — made the streaming side practical.
A program is kilobytes; the data are terabytes. So the scheduler sends the code to the machines that already hold the data. MapReduce, described by Jeffrey Dean and Sanjay Ghemawat in 2004, reduced a huge class of jobs to two functions and let the system do the rest. Spark, in 2010, kept intermediate results in memory instead of writing them to disk.
With thousands of ordinary machines, something is always broken. The Google File System paper of 2003 treated failure as the normal case: keep every block on several machines and re-copy when one disappears. Replication has a price, stated by Eric Brewer in 2000 and proved by Seth Gilbert and Nancy Lynch in 2002: when the network splits, a system must give up either consistency or availability.
Buying a bigger computer works until it does not. The alternative is many ordinary machines that share nothing — no memory, no disks — each holding a slice of the data. Michael Stonebraker made the case in 1986. Its limit was stated earlier still: Gene Amdahl observed in 1967 that the part of a job that cannot be split caps the gain from adding processors.
Read from the bottom up. The first three ideas are about machines. The next two are about time and cost. The last two are about whether the answer deserves to be believed, and whether it should have been computed at all.