MapReduce: Simplified Data Processing on Large Clusters
Take away almost everything a program can say, and what is left can be parallelised, scheduled and re-run by a library nobody has to write twice.
Read the original ↗MapReduce is remembered as a way to process a lot of data. That undersells it: the contribution is that it let engineers who could not write a distributed system write one anyway, by taking away almost everything they could say.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardBatch Processingthe chapter this paper started, with the model taken apart
- BoardThe Inverted Indexthe paper's own worked example - building one is the job MapReduce was written for
- BoardStorage & Compute Infrathe fleet underneath, and what replaced this pipeline on it
- BoardSplitting the Ledgerthe partitioning function that decides which reducer a key lands on, and the hot key that stalls one
- BoardConcurrency and the Hardwarewhy 'run it on more machines' stops helping, which is the ceiling on the whole promise
- LabThe parallel ceilingmove the sequential fraction and watch the speedup ceiling refuse to move with it
- LabSplitting the ledgera badly chosen key sends most of the work to one worker - the straggler reducer, run
- LabHow cost growsparallelism moves the constant, never the exponent: a bad algorithm at scale is still bad
- VideoThe data platform: measuring everything, testing anythinga batch pipeline and the faster path beside it, which is the shape this model became
- VideoSharding: splitting the ledgerpartition by key, and the hot shard that does everyone's work
- LessonBatch ProcessingUses the board Batch Processing
- LessonGoogle Search - the case studyUses the board The Inverted Index
- LessonKV: the ringUses the board Splitting the Ledger
- LessonSplitting the ledger (sharding)Uses the board Splitting the Ledger
- LessonConcurrency & the HardwareUses the board Concurrency and the Hardware
- LessonWaiting without spinningUses the board Concurrency and the Hardware
Further reading
Read the original for the full argument and its evidence.
- The paper (PDF) ↗OSDI 2004. Section 3 is the implementation and section 3.6 is backup tasks; section 5's list of what it was used for is more revealing than the benchmarks.
- Resilient Distributed Datasets (PDF) ↗Later work, and the direct reply: Spark's NSDI 2012 paper, whose motivation section is an argument about exactly the between-stages disk round trip above.