--- title: "MapReduce data flow technique" subject: "Big Data Technologies" chapter: 3 key: "semester_8/big_data_technologies:mapreduce-data-flow" source: https://www.bctengineer.com/q/semester_8/big_data_technologies/mapreduce-data-flow site: BCT Engineering --- # MapReduce data flow technique Big Data Technologies · Chapter 3: Map-Reduce Framework - Asked in: 2074 Bhadra, 8 marks - Video: [Map Reduce explained with example | System Design](https://www.youtube.com/watch?v=neoXVthw22Q) — Hayk Simonyan - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/big_data_technologies/mapreduce-data-flow - Whole chapter: https://www.bctengineer.com/md/semester_8/big_data_technologies/chapter-3 ## Question Explain in brief Data Flow technique of Map-Reduce Framework. ## Short answer Data flows from HDFS input splits to mappers that write sorted, partitioned output on local disk. Reducers fetch their partitions, merge and sort, then reduce to final output written to HDFS. An optional combiner reduces shuffle data. ## Answer **Data flow in MapReduce** describes how data moves from the input in HDFS, through map, shuffle/sort and reduce, to the final output. The input is split, processed in parallel, and the intermediate results are redistributed by key. ```text HDFS input | [Split 1][Split 2][Split 3] | | | Mapper1 Mapper2 Mapper3 (local disk output) | | | Combiner Combiner Combiner (optional) +---- Partition / Shuffle ----+ | | sort+merge sort+merge Reducer1 Reducer2 | | part-r-00000 part-r-00001 (HDFS) ``` #### Steps 1. **Input splits:** the job's input is divided into fixed-size splits (about one HDFS block). One map task is created per split. The `InputFormat` and `RecordReader` convert records into (key, value) pairs. 2. **Map:** each mapper processes its split, ideally on the node that holds the block (data locality), and emits intermediate pairs. Output is buffered in memory (circular buffer), partitioned by reducer, sorted by key, and spilled to **local disk**. Spill files are merged into one partitioned, sorted file. 3. **Combiner (optional):** it runs on map output before it is sent, to reduce the volume (e.g. local sum). 4. **Shuffle:** each reducer fetches its partition from every mapper's output over the network (HTTP). Partitioning is `hash(key) mod R`, which ensures all values of one key go to the same reducer. 5. **Sort/merge:** the reducer merges the fetched pieces, sorting them by key and grouping values with the same key. 6. **Reduce:** `reduce(key, values)` is called once per key group. 7. **Output:** results are written by `OutputFormat` to HDFS, one file per reducer, and replicated. #### Notes - Intermediate data lives on local disks, not HDFS, to avoid replication cost. - With zero reducers (map-only job), map output goes directly to HDFS. - Failed tasks are re-run on another node using the same input split. #### Small example (word count) Two splits: "to be or" and "not to be". - Mapper 1 emits (to,1) (be,1) (or,1); mapper 2 emits (not,1) (to,1) (be,1). - Partitioner with two reducers sends to,be to one reducer and or,not to another (by hash). - Reducer groups: be -> [1,1], to -> [1,1], or -> [1], not -> [1]. - Output: (be,2) (to,2) (or,1) (not,1). #### Fault tolerance and locality in the flow - The master schedules map tasks close to input blocks and re-runs failed map or reduce tasks. - Completed map output on a failed node must be recomputed, because it is only on local disk. - Reducers start copying map outputs as soon as maps complete, but the reduce function itself starts only after all maps finish. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How many map tasks are created for a job? A. One per reducer B. One per input split (about one HDFS block) C. One per cluster node D. Exactly one Answer: B. One map task is created per input split, which is about one HDFS block. (Key point: Splits and map tasks) 2. What does partitioning by hash(key) mod R guarantee? A. Equal data on every reducer B. Sorted global output C. All values of one key go to the same reducer D. Mappers run on data-local nodes Answer: C. The same key always hashes to the same reducer, so it sees all values of that key. (Key point: Shuffle guarantee) 3. Why must completed map output on a failed node be recomputed? A. It is stored only on that node's local disk B. It was never written C. HDFS deleted it D. Reducers do not need it Answer: A. Intermediate data is on local disk, not replicated, so it is lost with the node. (Key point: Failed node recomputation) 4. When does the reduce function itself start? A. Before any map begins B. As soon as the first map finishes C. Only after all maps finish, although copying can start earlier D. After the output is written Answer: C. Reducers may copy outputs early, but the reduce function begins only after all maps complete. (Key point: Reduce start timing) ## Related in Big Data Technologies - [Optimization and data locality in MapReduce](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-optimization-data-locality) — Big Data Technologies, chapter 3 - [MapReduce worker failure tolerance](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-fault-tolerance) — Big Data Technologies, chapter 3 - [MapReduce workflow with example](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-workflow-example) — Big Data Technologies, chapter 3, asked 2× - [MapReduce max marks per college](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-max-marks-college) — Big Data Technologies, chapter 3 - [Combiner function in MapReduce](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-combiner-function) — Big Data Technologies, chapter 3 - [Max and min word occurrence with MapReduce](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-max-min-word-occurrence) — Big Data Technologies, chapter 3 ## Related in other subjects - [MapReduce with GFS and HDFS](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Amapreduce-gfs-hdfs) — Information System, chapter 8 - [MapReduce working with example](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Amapreduce-working-big-data) — Information System, chapter 8 - [Application framework versus component reuse](https://www.bctengineer.com/question.md?key=semester_5%2Fsoftware_engineering%3Aframework-vs-component-reuse) — Software Engineering, chapter 5 - [Stream flow from current meter data](https://www.bctengineer.com/question.md?key=semester_5%2Fengineering_hydrology%3Acurrent-meter-0-035-0-74n) — Engineering Hydrology, chapter 4, asked 2×