PaperlayerView exact revision on arXiv

Source-linked AI summary

Coded MapReduce

Songze Li, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

arXiv:1512.01625v1cs.DCcs.IT

TL;DR

MapReduce’s data-shuffling phase is a major communication bottleneck. Coded MapReduce repeats Map tasks to create coding opportunities, reducing shuffling communication while increasing Map computation; it achieves communication load within a constant factor of the minimum and offers a tunable computation–communication tradeoff.

  • Problem

    Data shuffling is a key MapReduce runtime bottleneck, accounting for 33% of job execution time in an observed Hadoop cluster.

  • Method

    Coded MapReduce assigns repetitive Map tasks and codes transmitted intermediate values across keys and data blocks to reduce shuffling communication.

  • Results

    Coded MapReduce reduces communication by a factor that grows linearly with the number of servers and achieves the minimum communication load within a constant multiplicative factor.

  • Takeaways & Limitations

    Repetitive mapping creates coding opportunities that substantially reduce shuffling communication, while clients can choose operating points balancing Map computation time and communication load.

Abstract

from arXiv · show

MapReduce is a commonly used framework for executing data-intensive jobs on distributed server clusters. We introduce a variant implementation of MapReduce, namely "Coded MapReduce", to substantially reduce the inter-server communication load for the shuffling phase of MapReduce, and thus accelerating its execution. The proposed Coded MapReduce exploits the repetitive mapping of data blocks at different servers to create coding opportunities in the shuffling phase to exchange (key,value) pairs among servers much more efficiently. We demonstrate that Coded MapReduce can cut down the total inter-server communication load by a multiplicative factor that grows linearly with the number of servers in the system and it achieves the minimum communication load within a constant multiplicative factor. We also analyze the tradeoff between the "computation load" and the "communication load" of Coded MapReduce.

I. INTRODUCTION

MapReduce distributes large-scale data processing across commodity-server clusters, but data shuffling is a major runtime bottleneck. Coded MapReduce uses repetitive mapping to create coding opportunities that reduce communication while trading additional Map computation for lower shuffling load.

  • MapReduce workflow: Each input data block is mapped to intermediate (key,value) pairs before those pairs are transferred to reducers during data shuffling.Each server executes both Map and Reduce tasks in the generic workflow.
  • Motivation: 33% of Hadoop job execution time is spent on data shuffling, motivating methods that reduce communication during this phase.Existing approaches include combining intermediate pairs, flow scheduling, and distributed cache memories.
  • Contribution: Coded MapReduce reduces inter-server communication by a multiplicative factor that grows linearly with the number of servers.The framework exploits repetitive mapping of data blocks to create coding opportunities during shuffling.
  • Results: Coded MapReduce achieves the minimum shuffling load within a constant multiplicative factor regardless of system parameters.The paper also analyzes the tradeoff between Map processing time and inter-server communication load.
  • Mechanism: A coded multicast opportunity lets a group of approximately rK > 1 servers satisfy its data demand with one coded transmission, providing coding gain rK.Even when rK = 2, the framework can reduce communication by more than 50%.

Step 3: Reduce Tasks

Reduce tasks require servers to obtain missing intermediate values for their assigned keys through data shuffling. The communication load is minimized by exploiting repeated Map results and coding transmissions across servers, rather than sending every requested value separately.

  • Reduce requirements: Each reducer must obtain the values of its assigned key from all N subfiles before executing the Reduce function.Reducer assignments partition the Q keys across K servers.
  • Communication load: The communication load L is the expected number of inter-server communication time slots required for all servers to construct their reducer inputs.The expectation averages over possible Map task executions for each subfile.
  • Optimization target: Coded MapReduce targets the minimum communication load over Map-task assignments and shuffling schemes when each subfile is mapped at rK servers.The framework is analyzed on a multicast LAN where each transmitted message is sent to all other servers.
  • Conventional baseline: 36 communication slots are required for the conventional word-counting example with N = 12 and Q = K = 4.This baseline maps each subfile at only one server.
  • Repetition gain: Repeated mapping produces a repetition gain because each server knows values from more subfiles locally and therefore requests fewer values during shuffling.With a simple uncoded scheme, the improvement factor is 1−1/(rK) as represented in the cited expression.
  • Coded shuffling: Careful Map-task assignment combined with coded shuffling can reduce communication beyond the repetition gain from repeated mapping alone.The motivating example forms the basis of the general Coded MapReduce framework.

III. CODED MAPREDUCE: A MOTIVATING EXAMPLE

The motivating example assigns overlapping Map tasks so servers can generate coded intermediate pairs before shuffling. Each coded pair combines values associated with different words and chapters, creating information that can later serve multiple reducers.

  • The example counts four words across 12 chapters using four servers and preserves six assigned chapters per server.
  • Each chapter is assigned to exactly two servers, and every pair of servers shares exactly two chapters.
  • Each server generates three coded pairs by summing intermediate values associated with different words and chapters.
  • A coded pair records a combined value and the two source chapters, such as a pair whose value sums occurrences of two words across two chapters.
  • The reducers remain assigned one word per server: Server 1 evaluates A, Server 2 B, Server 3 C, and Server 4 D.

Data Shuffling

Coded MapReduce reduces shuffling traffic by transmitting coded combinations that multiple servers can decode, while its bounds and numerical comparisons establish substantial and approximately optimal communication savings.

  • 66% less communication load than conventional MapReduce and 50% less than naive assignment with uncoded shuffling are achieved in the word-counting example.
  • A single coded pair can simultaneously deliver two needed values because each receiving server already knows the other value in the sum.
  • Theorem 1 provides upper and lower bounds on the minimum communication load L∗(r) for MapReduce jobs with repetitive subfile assignments.
  • The proposed Coded MapReduce load achieves the upper bound, while the lower bounds use cut-set bounds for multiple valid reducer distributions.
  • When rK increases from 2 to 7 in the numerical example, the coding gain rises from 1.81× to 7× and the overall reduction rises from 2.03× to 21×.
  • Theorem 2 states that Coded MapReduce achieves the minimum communication load within a constant multiplicative factor for any MapReduce job.

V. CODED MAPREDUCE: GENERAL DESCRIPTION AND PERFORMANCE ANALYSIS

The paper presents Coded MapReduce as a scheme for reducing inter-server communication during the shuffling phase of a general MapReduce job.

  • The section introduces the proposed Coded MapReduce scheme and analyzes its inter-server communication load.

A. Coded MapReduce

The general scheme organizes repetitive Map assignments so that missing reducer inputs can be exchanged through coded multicast transmissions. Servers segment requested values, XOR compatible segments, and decode desired information using values already known locally.

  • Each subfile is assigned to pK servers for Map tasks but is actually mapped at rK of them, with rK ≤ pK.
  • The master partitions subfiles into equal-sized batches containing g unique subfiles and assigns each batch to a distinct subset of pK servers.
  • The construction uses repetitive assignments so groups of rK servers share mapped subfiles and create coded multicast opportunities.
  • For each server subset of size rK+1, requested values known exclusively across the subset are partitioned into rK segments.
  • Each server zero-pads associated segments and transmits their bitwise XOR as a coded segment.
  • A receiving server cancels the XOR components it already knows to recover its intended segment.
  • The scheme summarizes this assignment and shuffling procedure as Algorithm 1.

B. Performance of Coded MapReduce

Coded MapReduce uses repeated Map-task assignments and coded multicast transmissions to deliver reducer inputs while reducing inter-server shuffling. Its communication load is analytically characterized, and the scheme provides all required values for reduction.

  • Data delivery: Coded MapReduce delivers every server’s required reducer bits by combining segments in coded transmissions from other servers.A server decodes needed bits using locally known values and the received XOR-coded segments.
  • Map-task assignment: Each subfile is assigned to repeated server subsets, enabling data shuffling over groups of rK + 1 servers.The assignment partitions subfiles by server subsets, while shuffling iterates over every subset of size rK + 1.
  • Coded shuffling: Each server sends a bitwise XOR of zero-padded segments, allowing other servers in the group to recover their required segments.The segments are formed from values associated with the other servers in the subset.
  • Communication load: The proposed scheme’s normalized communication load is obtained by counting coded transmissions across all server subsets and iterations.The analysis derives the load from the segment length, the number of iterations, and normalization by F.

VI. LOWER BOUNDS ON L∗(r)

The lower-bound analysis applies cut-set arguments to compound settings involving multiple valid reducer distributions. It uses the fact that valid reducer distributions have identical communication loads.

  • Lower-bound framework: Two lower bounds on L∗(r) are derived using cut-set bounds over compound extensions of multiple valid reducer distributions.The analysis treats several reducer assignments jointly to constrain the minimum possible inter-server communication.
  • Lower-bound framework: All valid reducer distributions have identical communication loads, enabling the lower-bound arguments to compare their compound settings.The reducer distributions are constructed and analyzed under this distribution-independent communication property.

First Bound

The first bound combines K valid reducer distributions and cuts each server from the transmitted messages and mapping outcomes needed to evaluate all keys. Taking expectations yields a lower bound on L∗(r).

  • Compound reducer distributions: K valid reducer distributions are considered, with each distribution specifying which keys are reduced at each server.The construction partitions keys into groups and uses K distributions across the servers.
  • Compound reducer distributions: At Server k, the compound setting requires evaluation of all keys across the K reducer distributions.The union of the keys assigned to Server k across these distributions equals the full key set.
  • Cut-set argument: The cut separates Server k from messages sent by the other servers and from the mapping outcomes needed for reduction.The server’s decoding requirement supplies the information constraint for the cut-set bound.
  • Result: Taking expectations over Map-task executions produces a lower bound on the minimum inter-server communication load.The argument averages the cut-set inequality over the possible mapping outcomes.

Second Bound

The second bound focuses on keys evaluated at the first s servers and applies a compound cut to those servers across multiple reducer distributions. Since the resulting inequality holds for every s, it yields another lower bound on L∗(r).

  • Compound construction: The second construction focuses on the keys evaluated at the first s servers for every s from 1 through K.The reducer distributions specify which key groups are assigned to these servers.
  • Cut-set argument: The cut contains the first s servers and separates their required values from transmitted messages and local mapping outcomes.The compound setting includes all reducer distributions used in the bound.
  • Result: Taking expectations over Map-task executions gives an inequality that holds for every s.The mapping assignment has rN mapped subfiles for each server in the expectation argument.
  • Result: Because the inequality holds for all s ∈ {1, . . . , K}, it yields a second lower bound on L∗(r).For the example with Q = 4, N = 12, K = 4, and r = 1/2, the first lower bound is tighter than the second.

VII. MAP PROCESSING TIME VS. COMMUNICATION LOAD OF CODED MAPREDUCE

Coded MapReduce trades additional Map processing for reduced inter-server communication during shuffling. This section examines that computation–communication tradeoff.

  • Repetitive Map operations reduce inter-server communication but increase the job’s Map processing time.The tradeoff arises because more Map tasks must be processed across servers.
  • The section analytically and numerically investigates the relationship between Map-task processing time and shuffling communication load.
  • Coded MapReduce’s computation–communication tradeoff determines how repetitive Map execution affects overall job execution.

A. Map Processing Time of Coded MapReduce

The Map phase assigns each subfile to multiple servers and continues until every subfile has been mapped at rK distinct servers. Its processing time is modeled using processor sharing and order statistics, then evaluated alongside shuffling load to expose the computation–communication tradeoff.

  • Map task execution: Each server processes its assigned pN subfiles until every subfile has been mapped at rK distinct servers.The model assumes equal-sized subfiles that are simultaneously available for processing.
  • Map task execution: Under processor sharing, each server’s rate µ is evenly divided among its assigned Map tasks.The analysis assumes the processing rate remains constant throughout Map-task execution.
  • Single-subfile processing time: A subfile’s Map processing time is modeled as the rKth-order statistic of pK i.i.d. exponential service times.The exponential service rate is µ pN under the stated error-free Map-task model.
  • Single-subfile processing time: The average time to map one subfile at rK of its pK assigned servers is derived from the distribution of its processing time.
  • Overall Map processing time: The overall Map processing time is the time until all N subfiles complete their rK-server mappings, based on the maximum of their individual completion times.Its distribution is derived from the i.i.d. subfile processing-time distributions, followed by the average overall processing time.
  • Numerical evaluation: Increasing repetitive mapping makes Map processing longer while reducing the communication required for shuffling.Figures 5 and 6 evaluate this tradeoff for N = 1200 subfiles, Q = 10 keys, K = 10 servers, pK = 7, and µ = 500.
Loading 1512.01625v1…