JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Request-Level Parallelism and MapReduce

Inside the warehouse-scale computer, a different kind of parallelism rules: millions of independent requests, and giant batch jobs sliced across thousands of machines. This guide shows how request-level parallelism and the map-then-reduce idea turn a building full of commodity boxes into one machine — and why the network, not the ALU, is now the thing you fight.

A third kind of parallelism

The previous guide reframed the datacenter as a single warehouse-scale computer — one machine whose chassis happens to be a building. Now we ask the question that machine exists to answer: what work does it run, and how is that work parallel? On the earlier rungs we met two flavours of parallelism inside one chip. Instruction-level parallelism overlapped instructions in a pipeline; data-level parallelism (SIMD and the GPU) ran one operation over many data elements at once. The warehouse adds a third, coarser flavour that lives between machines, and it is the one that pays the building's electricity bill.

Call it request-level parallelism (RLP). When you type a search, load a feed, or send a message, you generate a request that is almost entirely independent of everyone else's request at that instant. A billion users hitting a service produce a billion mostly-unrelated units of work, and the warehouse simply hands each one to whatever machine is free. There are no instructions to overlap and no vector to widen — the parallelism is sitting right there in the workload, already chopped into pieces by the users themselves. That independence is the gift that makes warehouse-scale computing tractable.

When the data is too big for one box

Serving live requests is only half the warehouse's job. The other half is batch work: chewing through a dataset so large that no single machine could hold it, let alone process it in reasonable time — building a search index over the whole web, counting words across billions of documents, training on a mountain of logs. This is data-level parallelism again, but at building scale: the same operation applied across an enormous dataset, except the data is now spread over thousands of disks instead of sitting in one core's vector registers.

The naive plan — copy all the data to one powerful computer — fails twice over. The data does not fit, and moving petabytes across the network would take days. The winning move flips the geometry: instead of bringing data to the code, you ship the code to wherever the data already lives. Each machine reads the slice of data sitting on its own local disks, runs your computation on just that slice, and only the small results travel across the datacenter network. This 'move the computation, not the data' principle is the seed of the whole programming model we are about to meet.

MapReduce: two functions and a shuffle

MapReduce is a beautifully small idea that made batch work across thousands of machines writable by ordinary programmers. You supply just two functions. Map takes one input record and emits some number of (key, value) pairs — it is applied in parallel to every slice of the data, on the machines that already hold those slices. Reduce takes one key together with all the values that any map produced for that key, and folds them into a final answer. Between the two, the system performs a shuffle: it carries every value to the machine responsible for its key, so each reducer sees a complete group. Map and reduce are the parts you write; the shuffle, scheduling, and failure handling are what the framework gives you for free.

The canonical example is counting words across billions of documents, and it fits on a napkin. The map function reads a document and, for every word it sees, emits the pair (word, 1). The shuffle gathers all the 1s for, say, the word 'cat' onto one reducer. The reduce function for 'cat' just adds up its list of 1s and emits (cat, total). Run map on a thousand machines at once, each on its own local documents, and the only network traffic is the compact stream of partial counts — exactly the 'move the code, not the data' geometry from the last section.

WORD COUNT in MapReduce (pseudocode + tiny trace)

  map(docID, text):
      for each word w in text:
          emit(w, 1)

  reduce(word, list_of_counts):
      emit(word, sum(list_of_counts))

Trace on 2 input slices (run on 2 machines in parallel):

  slice A = "the cat sat"      slice B = "the cat ran"
  map A -> (the,1)(cat,1)(sat,1)
  map B -> (the,1)(cat,1)(ran,1)

  --- shuffle: group every value by its key ---
  the -> [1, 1]     cat -> [1, 1]
  sat -> [1]        ran -> [1]

  reduce -> (the,2) (cat,2) (sat,1) (ran,1)

Only the small (key,partial) pairs cross the network --
not the documents themselves.
The whole of distributed word counting: a two-line map, a two-line reduce, and a shuffle the framework runs for you. The programmer never writes a line about which machine does what, or what to do when one dies.
  1. Split: the framework carves the input dataset into many slices, each sized to sit on one machine's local disk.
  2. Map in parallel: it ships your map function to the machines holding each slice and runs them all at once, emitting (key, value) pairs locally.
  3. Shuffle: it sorts and routes those pairs across the network so that every value for a given key lands on the same reducer machine.
  4. Reduce in parallel: each reducer folds its key's value list into a final result, and the framework writes the outputs back out.

From MapReduce to Spark, and what stays true

MapReduce was the first widely-used model, but it has a real cost: between every map and reduce stage it writes intermediate results all the way to disk, which is safe but slow when a computation has many stages — think an iterative algorithm that loops dozens of times. Newer systems like Spark keep the same map-then-shuffle-then-reduce skeleton but try to hold intermediate data in memory across stages, and let you chain operations into a richer pipeline rather than forcing everything into exactly one map and one reduce. The orientation-level takeaway is not the API differences but the shared shape: partition the data, compute locally, shuffle by key, combine.

Notice how cleanly this echoes ideas from lower rungs, just at a new scale. The shuffle is a memory-wall problem wearing a network jersey: moving data is expensive, so you design to move as little as possible and keep computation near its data — the same instinct behind caches and locality, now measured in racks and switches instead of nanometres. And the (key, value) grouping is just a giant, distributed version of building a table indexed by key. The warehouse does not invent new principles; it stretches the ones you already know across a building.

The honest limits: Amdahl, the shuffle, and the straggler

It is tempting to believe that with a thousand machines a job runs a thousand times faster. It does not, and the reason is an old friend: Amdahl's law, which we first met for multicore chips and which scales up unchanged. Any part of the job that cannot be parallelised — reading the very first input, the final reduce that must see all the data, the framework's own coordination — sets a floor on the runtime no number of machines can break through. If even 1% of the work is inherently serial, your speedup is capped near 100x no matter how many thousands of nodes you throw at it.

The shuffle is the other hard limit, and it is specific to this scale. Mapping and reducing are gloriously parallel, but between them sits a step that may move a large fraction of the intermediate data across the network — and the network has finite bandwidth shared by everyone. On many real jobs the shuffle, not the computation, is the slowest stage, which is exactly why the next guide makes the network and its latency the main character. The lesson rhymes with the roofline idea from the accelerator rung: past a point you are not compute-bound, you are communication-bound.