Section 5: One Byte per Pair - Data Modeling
Executive Summary: MapReduce has no database, but its data model still sets the framework's limits. A job lives in three representations. First, the master's in-memory state: task, worker and region tables, where the region table is the M × R term, 156,000 × 4,000 ≈ 624 M pairs at about one byte each, or 624 MB of RAM. Second, intermediate files: each map task writes R = 4,000 regions of 1.6 KB to its own local disk, partitioned by hash(key) mod R. Third, the output: 4,000 files in GFS, sorted by key within each file, written under a temporary name and then renamed. We trace Riya's (target, source) record through all three and draw the task state machine, including the transition Section 8 relies on: a completed map going back to idle.
Interviewer: "There's no database in this design. So what's your data model?"
You: "Three things, and only one of them is durable. The master holds the job's live state in RAM. Map workers write intermediate data to their local disks. Reducers write the final output to GFS. The input is already in GFS as 64 MB chunks. I'll start with the master, because its size breaks first if the job grows."
The Master's State: Four Tables in RAM
Everything the master knows fits in four in-memory structures, none persisted (Decision 9: one master per job, no HA; if it dies, the job aborts and is resubmitted).
| Structure | Rows | Fields | Why it exists |
|---|---|---|---|
| Job record | 1 | job id, user binary, input pattern, output dir, M, R, counters, phase | What Riya submitted, plus progress for the status page |
| Task table | M + R ≈ 160,000 | task id, type (map/reduce), state, assigned worker, attempt number; map tasks also hold their split and its 3 GFS replica locations | Scheduling and failure handling, about 160,000 decisions per job |
| Worker table | 2,000 | worker id, rack, free map slots (of 2) and reduce slots (of 2), last heartbeat | Liveness (heartbeat every 5 s, dead after 15 s) and placement |
| Region table | M × R ≈ 624 M | for each completed map task, the size of each of its R regions; the location is that task's worker | What tells every reducer where its input is |
The first three are small, even with 400 heartbeats per second arriving. The region table is the one that grows.
Following the 2004 paper, when a map task completes it reports the locations and sizes of its R intermediate regions, and the master pushes those entries incrementally to the in-progress reduce workers. Because R = 4,000 equals our reduce slots, every reducer runs from the start and each of the peak 500 completions per second fans out to all of them. A reducer fetches its region from map 88,213 the moment map 88,213 reports.
Why about one byte per pair? All R regions of one map task live on the same worker, so the location is stored once per task, not per region. What remains per pair is little more than a compact size. The 2004 paper estimates about one byte per map/reduce pair, and we adopt that: 156,000 × 4,000 × 1 B ≈ 624 MB.
Key Insight: The master's scheduling work is O(M + R) ≈ 160,000 decisions, but its memory is O(M × R). That product, not CPU, caps task granularity. Halving the split size to 32 MB doubles M, and with it the region table. Doubling R does the same. Decision 5's fine-grained tasks are bounded by this table, and its flip trigger is exactly this: when master RAM or the M × R fetch count becomes the bottleneck, use bigger splits or merge map output per machine.
None of this 624 MB is persisted: a master crash costs one resubmit, and Section 10 prices that trade and names when checkpointing would win.
Quick check before moving on:
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson