By 2003, Google engineers were writing hundreds of special-purpose programs to process crawled pages and request logs: count word frequencies, build the inverted index, find the most popular queries of the day. The computations themselves were usually simple. What made each one hard was everything around it: splitting the input across hundreds of machines, moving intermediate data between them, rerunning work when a machine died, and noticing when one slow machine held everyone up. Every team solved those problems again, slightly differently, and the simple logic disappeared under them.
Jeff Dean and Sanjay Ghemawat pulled all of that machinery into one library. Engineers wrote two small functions, and the library did the rest on thousands of machines. They described it in "MapReduce: Simplified Data Processing on Large Clusters" (Dean and Ghemawat, OSDI 2004, Google). The first version was written in February 2003, and within a year it was used across Google, from indexing to machine learning.
The batch processing lesson already covered the map, shuffle and reduce shape. This lesson is about the system: how one master runs a job across thousands of unreliable machines, and the design decisions that made it robust.
The programming model
You write two functions:
map(key, value) -> list of (intermediate key, intermediate value)
reduce(intermediate key, list of values) -> list of output values
The classic example counts words across a huge set of documents:
map(document_name, text):
for each word in text:
emit(word, 1)
reduce(word, counts):
emit(word, sum(counts))
That's the whole program. You don't say how many machines to use, where the data is, or what happens when a machine dies. The library guarantees that every value for a given intermediate key arrives at one reduce call, grouped together.
Two optional hooks matter in practice. A partitioning function decides which reduce task gets each key; the default is hash(key) mod R, but you can supply your own, for example to put all URLs from one host into the same output file. And a combiner runs reduce-like logic on each map worker before anything is sent over the network. For word count, a map task that sees "the" ten thousand times sends one ("the", 10000) instead of ten thousand ("the", 1) pairs.