MapReduce: Simplified Data Processing on Large Clusters (paper)

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Big Data and Cloud Data Platforms · 11 minHow big data evolved, and the papers behind itFrom single databases to Hadoop, Spark, streaming and lakehouses: a timeline of ideas and the research papers that started each one.Read hereClose

  Why a new wave kept appearing

  Each generation of data tools answered a limit of the previous one. Understanding the problem behind each wave makes the tools easier to place.

  Image: Trower, NASA · Public domain · Source · Wikimedia Commons: Columbia Supercomputer - NASA Advanced Supercomputing Facility

  A timeline

  100%

  Figure SDA-BDP-01-1 · A timeline · © forcsguy.com

  1. Before: relational databases and data warehouses

  Data fit on one big server. SQL and data warehouses served reports. Limits: scaling up got very expensive, and unstructured data (web logs, clicks) did not fit neatly.

  2. Web scale (around 2003 to 2006)

  Search companies had far more data than any single machine could hold. Google described how it coped, and open-source projects copied the ideas.

  • GFS (Google File System): a distributed file system on commodity machines that expects failures.
  • MapReduce: a model to process huge datasets in parallel.
  • Hadoop (HDFS plus MapReduce) brought both to everyone.

  3. NoSQL (about 2006 to 2010)

  Web applications needed massive scale and high availability that relational systems struggled to give.

  • Bigtable: a sparse, sorted, wide-column store; inspired HBase and Cassandra's data model.
  • Dynamo: an always-writable key-value store with consistent hashing and eventual consistency; inspired Cassandra, Riak and DynamoDB.

  4. Faster and friendlier processing (2010 onward)

  • Dremel: interactive SQL over huge datasets using columnar storage and tree-shaped execution; the idea behind BigQuery and later engines, and the Parquet format.
  • Spark (resilient distributed datasets): keeps data in memory between steps, much faster than disk-based MapReduce for iterative work, with friendly APIs.

  5. Streaming

  Waiting for nightly batches was too slow. Kafka made a durable, replayable log the backbone of event pipelines, and engines such as Flink and the Dataflow model handled continuous computation with proper treatment of event time, windows and late data.

  6. The cloud

  Cloud providers separated storage (cheap object storage) from compute (elastic clusters or serverless queries). Managed warehouses (BigQuery, Redshift, Snowflake and others) removed cluster management.

  7. The lakehouse

  Data lakes were cheap but unreliable (no transactions, messy files). Table formats (Delta Lake, Apache Iceberg, Apache Hudi) add ACID transactions, schema evolution and time travel on top of files in object storage, so one copy of data can serve both analytics and machine learning.

  100%

  Figure SDA-BDP-01-2 · Key dates, in order · © forcsguy.com

  The classic papers

  These are the research papers most often cited. Search the title to find each; most are freely available.

  Paper	Authors (and year)	The idea
  The Google File System	Ghemawat, Gobioff, Leung (2003)	Large-file storage across commodity machines, built to tolerate failures
  MapReduce: Simplified Data Processing on Large Clusters	Dean, Ghemawat (2004)	A simple map and reduce model with automatic parallelism and fault tolerance
  Bigtable: A Distributed Storage System for Structured Data	Chang and others (2006)	A sorted, sparse, multi-dimensional map for structured data at scale
  Dynamo: Amazon's Highly Available Key-value Store	DeCandia and others (2007)	Consistent hashing, quorums, vector clocks and eventual consistency
  Dremel: Interactive Analysis of Web-Scale Datasets	Melnik and others (2010)	Columnar nested data and tree execution for fast SQL
  Kafka: a Distributed Messaging System for Log Processing	Kreps, Narkhede, Rao (2011)	A partitioned, replicated log as the backbone for event data
  Resilient Distributed Datasets (Spark)	Zaharia and others (2012)	In-memory, fault-tolerant parallel computing
  Spanner: Google's Globally-Distributed Database	Corbett and others (2012)	Strongly consistent, globally distributed SQL using synchronised clocks
  The Dataflow Model	Akidau and others (2015)	A unified model for batch and streaming with event time and windows
  Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	Armbrust and others (2020)	Transactional tables on object storage: the lakehouse idea

  A good companion is Jay Kreps's essay "The Log: What every software engineer should know about real-time data's unifying abstraction" (2013).

  What to take away

  • Scale-out on cheap machines (GFS, MapReduce) made big data practical.
  • Availability versus consistency choices (Dynamo, Bigtable, Spanner) shaped databases.
  • Columnar storage (Dremel, Parquet) made analytics fast.
  • Logs and streams (Kafka, dataflow) made data continuous.
  • Separating storage from compute and open table formats define today's platforms.

  Real-world reading

  Related reading

  • Dremel: Interactive Analysis of Web-Scale Datasets (paper)Melnik et al. · GooglePapers
  • Cassandra architecture overviewApache Cassandra · Apache Software FoundationDocumentation
  • Fast Order Search using Data Pipeline and Elasticsearch at YelpYelp engineers · YelpCase Studies
  • Apache CassandraApache Software Foundation · GitHubGitHub

  Show 6 moreShow fewer

  • Amazon S3 strong consistencyAmazon Web ServicesDocumentation
  • Sherpa: Distributed NoSQL Key-Value Store at YahooYahoo engineers · YahooCase Studies
  • Elasticsearch GuideElasticDocumentation
  • MapReduce: Simplified Data Processing on Large Clusters (paper)Dean and Ghemawat · GooglePapers
  • HBase at SalesforceSalesforce engineers · SalesforceCase Studies
  • Columnar DatabasesAmazon Web Services engineers · Amazon Web ServicesCase Studies

  Open this lesson with its quiz and exercise

• Big Data and Cloud Data Platforms · 12 minBatch and stream processingMapReduce and Spark for large batch jobs, and streaming concepts: event time, windows, watermarks and exactly-once results.Read hereClose

  Two ways to process data

  • Batch: process a bounded dataset (yesterday's logs) as a job that starts, runs and finishes. High throughput, results later.
  • Stream: process an unbounded flow of events continuously as they arrive. Low latency, harder to get right.

  Most platforms need both: stream for fresh insight, batch for heavy recomputation and history.

  Before: batch: a big job on a schedule

  100%

  After: stream: process each event

  100%

  What changed

  • Results arrive in seconds instead of hours
  • Late and duplicate events must be handled
  • Batch stays useful for reprocessing history

  Batch: the MapReduce idea

  Word count is the classic example.

  100%

  Figure SDA-BDP-02-1 · MapReduce word count flow · © forcsguy.com

  1. Map: each worker reads a slice and emits key-value pairs (("system", 1)).
  2. Shuffle: the framework groups all pairs with the same key and sends them to the same reducer. This is the expensive step (network and sorting).
  3. Reduce: each reducer combines the values for its keys (("system", 4812)).

  Failures are handled by re-running tasks, which is possible because inputs are immutable and tasks have no side effects.

  Spark improved this model: it keeps intermediate data in memory, expresses jobs as chains of transformations on DataFrames (with a query optimiser), and offers SQL, machine learning and streaming APIs on one engine. Today you usually write Spark or SQL, not raw MapReduce.

  Image: Unknown authorUnknown author · Public domain · Source · Wikimedia Commons: Ford assembly line - 1913

  Stream processing

  A stream processor reads events from a log (such as Kafka), transforms them, and writes results to another log, a database or a dashboard.

  Common operations: filter and enrich, aggregate, join streams, and detect patterns.

  Time is the hard part

  • Processing time: when the system sees the event.
  • Event time: when it actually happened.

  Phones go offline, networks lag, and events arrive late and out of order. Computing "clicks per minute" by arrival time gives wrong answers. Use event time.

  Windows

  Aggregations need boundaries:

  Window	Meaning
  Tumbling	Fixed, non-overlapping (every minute)
  Sliding	Overlapping (last 5 minutes, updated each minute)
  Session	Grouped by activity, closed by a gap of inactivity

  Watermarks and late data

  A watermark is the system's estimate of "we have seen everything up to event time T". When it passes the end of a window, the window can close and emit a result. Choosing the delay trades latency against completeness. Events arriving after the watermark are late: drop them, send them to a side output, or update the earlier result.

  State and failures

  Windows and joins need state. Engines such as Flink keep state locally and checkpoint it periodically to durable storage, together with the position in the input log. After a failure they restore the checkpoint and replay from that position.

  Delivery guarantees

  • At-most-once: may lose events.
  • At-least-once: may duplicate on replay.
  • Exactly-once effect: achieved by replayable sources, checkpointed state and idempotent or transactional sinks, so a replay does not change results.

  Architectures that combine both

  • Lambda architecture: a batch layer computes accurate views from all data, a speed layer gives fast approximations; the two are merged. Powerful but means writing logic twice.
  • Kappa architecture: treat everything as a stream. Keep the log long enough to replay history through the same code when logic changes. Simpler, if your log and engine can handle it.
  • Modern engines and the dataflow model increasingly unify batch and streaming under one API.

  100%

  Figure SDA-BDP-02-2 · Lambda and Kappa architectures · © forcsguy.com

  Choosing

  Need	Choice
  Nightly reports, big joins, model training on history	Batch (Spark, SQL warehouse)
  Fraud detection, live dashboards, alerting, real-time features	Streaming (Flink, Kafka Streams, Spark Structured Streaming)
  Both with minimal duplication	Streaming core with replayable log, or a unified engine

  Real-world reading

  Related reading

  • MapReduce: Simplified Data Processing on Large Clusters (paper)Dean and Ghemawat · GooglePapers
  • Cape: Event Stream Processing Framework at DropboxDropbox engineers · DropboxCase Studies
  • Pagelets Parallelize Server-side Processing at YelpYelp engineers · YelpCase Studies
  • Optimizing CAL Report Hadoop MapReduce Jobs at eBayeBay engineers · eBayCase Studies

  Show 6 moreShow fewer

  • Bullet: Forward-Looking Query Engine for Streaming Data at YahooYahoo engineers · YahooCase Studies
  • Samza: Stream Processing System for Latency Insighs at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Netflix: What Happens When You Press Play?High Scalability engineers · High ScalabilityBlogs
  • CMU Database GroupCarnegie Mellon UniversityYouTube
  • Omid: Transaction Processing Platform at YahooYahoo engineers · YahooCase Studies
  • Big Data Processing at UberUberPapers

  Open this lesson with its quiz and exercise