Source-linked AI summary
Hadoop Performance Models
Herodotos Herodotou
TL;DR
Hadoop MapReduce needs detailed performance estimates for large-scale analytics. This report models dataflow and costs at map and reduce phase granularity, supporting job-cost estimation and configuration selection. The models can be evaluated analytically or through task-scheduler simulation.
Problem
Large-scale MapReduce analytics requires performance models that describe job execution and costs at sufficiently fine phase granularity.
Method
The report builds mathematical models for map and reduce phases, including data movement, buffering, merging, compression, and resource costs.
Results
The models estimate MapReduce job costs and support finding configuration settings for running jobs.
Takeaways & Limitations
Users can analyze jobs either analytically or by simulating task execution with a task scheduler.
Takeaways & Limitations
The map-merge formulas assume numSpils ≤pSortFactor2; otherwise, simulation is required to calculate intermediate merges and total merge passes.
Abstract
from arXiv · showhide
Hadoop MapReduce is now a popular choice for performing large-scale data analytics. This technical report describes a detailed set of mathematical performance models for describing the execution of a MapReduce job on Hadoop. The models describe dataflow and cost information at the fine granularity of phases within the map and reduce tasks of a job execution. The models can be used to estimate the performance of MapReduce jobs as well as to find the optimal configuration settings to use when running the jobs.
1 Model Parameters
The models organize inputs into Hadoop configuration parameters, job-specific profile statistics, and system cost factors for estimating I/O, CPU, and network costs.
- The model parameters comprise Hadoop-defined configuration settings, profile statistics for input data and user functions, and profile cost factors for I/O, CPU, and network execution costs.
- Tables 1–3 define the variables for Hadoop parameters, profile statistics, and profile cost factors, respectively.
- Compression costs are expressed per byte, other CPU costs per key-value pair, and network cost per transferred byte.
- The identity function returns 1 when x exists or equals true, and 0 otherwise.
2 Performance Models for the Map Task Phases
Map-task models decompose execution into Read, Map, Collect, Spill, and Merge phases, then estimate their resource costs from buffering, spilling, combining, compression, and merge behavior.
- Map-task execution has five phases: Read, Map, Collect, Spill, and Merge.Read creates key-value pairs; Map applies the user function; Collect buffers and partitions output; Spill creates sorted spill files; Merge combines them.
- For a map-only job, spilling and merging are skipped; otherwise, total map I/O and CPU costs combine Read with Spill and Merge costs.
- Collect and Spill: Spills occur when the serialization or accounting buffer reaches its threshold, with spillBufferPairs limited by the smaller buffer capacity and total map-output pairs.
- Collect and Spill: The number and size of spills depend on key-value width, combining, and intermediate compression, whose disabled-compression defaults set the corresponding ratios to 1.
- Merge: Merge combines spill files through passes of at most pSortFactor files, potentially across multiple rounds, with a distinct final pass that may reuse the combiner.
- Merge: If numSpills exceeds the stated pSortFactor-based assumption, a simulation-based approach is required to calculate intermediate merges and total merge passes.
3 Performance Models for the Reduce Task Phases
Reduce-task models cover Shuffle, Merge, Reduce, and Write, tracking map-output transfer, buffering, multi-stage merging, reduce processing, and HDFS output costs.
- Reduce-task execution consists of Shuffle, Merge, Reduce, and Write phases.Shuffle copies and decompresses map output; Merge forms the reducer input; Reduce applies the user function; Write sends output to HDFS.
- Shuffle: During Shuffle, each reducer fetches its map-output segment, decompresses it when necessary, and places it in memory or on disk.
- Shuffle: Segments larger than 25% of shuffleBufferSize bypass memory and go directly to disk, avoiding in-memory merging.
- Shuffle: Shuffle files are merged when their count exceeds 2 × pSortFactor −1, using pSortFactor files per merge and no Combiner during disk merging.
- Merge: Reduce-side sorting and merging proceeds in three steps: evicting memory segments, merging disk files across rounds, and merging all remaining files and segments into the reducer stream.
- Overall reduce-task I/O and CPU costs are sums of Shuffle, Sort, and Write costs, excluding network transfers.
4 Performance Models for the Network Transfer
The shuffle phase copies mapper-produced data to reducer nodes, excluding data that is already local, and models the resulting network transfer and its cost.
- Shuffle copies map-task output to reduce-task nodes, except for data that remains local.
- finalOutMapSize denotes the output size produced by a single map task.
- The model separately defines the overall network data transferred and the cost of transferring it.
5 Performance Models for the Map-Reduce Job
The report estimates total MapReduce job cost either by simulating parallel task execution in waves or by analytically combining map and reduce costs.
- The job executes map and reduce tasks in parallel and in waves, enabling simulation or analytical cost estimation.
- Simulation schedules individual tasks on a virtual cluster and computes each task's cost using the performance models.
- Total job cost is the sum of costs from all map and reduce tasks.
- Analytical estimation uses separate I/O and CPU costs for maps alone when pNumReducers = 0, and for maps plus reducers otherwise.
- With system parameters that equalize I/O, CPU, and network costs, the overall cost combines these cost dimensions.