Section 4: Less Power, More Guarantees - API Design (with Pushback)

Executive Summary: The user writes two functions, map(k1, v1) → list(k2, v2) and reduce(k2, iterator<v2>) → list(v3), and optionally a combine and a partition(k2, R). Add a job spec (input, output, R, reader and writer types, a skip budget) and that's the entire surface. Riya's inlinks job fits in about 40 lines and never mentions a machine, a retry or a byte on the wire. Six pushbacks defend the narrowness. Values come as an iterator because one hot key can carry 10 GB. There are no DAGs because one restricted stage is what buys automatic fault tolerance (Decision 1). Map must be deterministic because recovery is re-execution. R is the user's because it's the number of output files. Side effects are the user's to make atomic. Global sort costs a custom partitioner.

Section 3 left a sentence on the board: the network is the budget. The interviewer underlines it and turns around.

Interviewer: "Fine, the cluster can do it. Now show me what Riya actually types. If the answer is more than a page, you've lost the prompt."

You: "Less than a page, on purpose. Every capability I hand the user is one the framework can no longer manage for them."

The Two Functions and Two Hooks

map(k1, v1)                  -> list(k2, v2)   # one input record at a time
reduce(k2, iterator<v2>)     -> list(v3)       # one key and all of its values
combine(k2, iterator<v2>)    -> list(v2)       # optional; runs on the map worker
partition(k2, R)             -> [0, R)         # optional; default hash(k2) mod R

The 2004 paper writes the types as reduce(k2, list(v2)) → list(v2), and then says the values actually reach reduce through an iterator, so a key's values can exceed memory. We keep that iterator, and we let reduce's output type differ. combine usually is the reduce code: it partially merges a map task's output before it's written to local disk. In our contract it must be safe to run zero, one or many times, because the framework decides when to apply it. partition decides which of the R reduce tasks receives a key. The default spreads keys evenly; Section 5 traces Riya's record to partition 1,729.

Quick check before moving on: