PaperlayerView exact revision on arXiv

Source-linked AI summary

The Family of MapReduce and Large Scale Data Processing Systems

Sherif Sakr, Anna Liu, Ayman G. Fayoumi

arXiv:1302.2966v1cs.DB

TL;DR

Large-scale data growth created demand for scalable data-processing architectures beyond conventional approaches. This survey examines MapReduce and related systems, including extensions, SQL-like interfaces, and alternative designs, and concludes that the family is mature but still requires advances for complex data models and other challenges.

  • Problem

    The basic MapReduce architecture had limitations, including constrained support for complex data models and insufficiently developed solutions for some large-scale processing challenges.

  • Method

    The paper surveys MapReduce-based approaches, performance and capability improvements, SQL-like interfaces, and related large-scale data-processing systems.

  • Results

    The survey finds that MapReduce and Hadoop are sufficiently mature for widespread use across academic and industrial application domains.

  • Takeaways & Limitations

    MapReduce and database systems are expected to coexist and complement each other in different scenarios.

  • Takeaways & Limitations

    The simplicity of MapReduce creates challenges for efficiently handling complex data models such as nested models, XML, hierarchical models, RDF, and graphs.

Abstract

from arXiv · show

In the last two decades, the continuous increase of computational power has produced an overwhelming flow of data which has called for a paradigm shift in the computing architecture and large scale data processing mechanisms. MapReduce is a simple and powerful programming model that enables easy development of scalable parallel applications to process vast amounts of data on large clusters of commodity machines. It isolates the application from the details of running a distributed program such as issues on data distribution, scheduling and fault tolerance. However, the original implementation of the MapReduce framework had some limitations that have been tackled by many research efforts in several followup works after its introduction. This article provides a comprehensive survey for a family of approaches and mechanisms of large scale data processing mechanisms that have been implemented based on the original idea of the MapReduce framework and are currently gaining a lot of momentum in both research and industrial communities. We also cover a set of introduced systems that have been implemented to provide declarative programming interfaces on top of the MapReduce framework. In addition, we review several large scale data processing systems that resemble some of the ideas of the MapReduce framework for different purposes and application scenarios. Finally, we discuss some of the future research directions for implementing the next generation of MapReduce-like solutions.

1. INTRODUCTION

The growth of scientific and enterprise data has driven demand for scalable, cost-effective processing architectures. MapReduce addresses this demand with a simple, fault-tolerant programming model, while this survey reviews its extensions and related systems.

  • Motivation: Scientific instruments and enterprises now generate massive datasets, including about 30 TeraBytes daily from the Large Synoptic Survey Telescope and 15 TeraBytes daily collected by Facebook.These data streams include astronomy, physics, biology, customer interactions, sales, and advertising information.
  • Motivation: Growing large-scale data analysis needs have spurred solutions across industry and science, while parallel databases remain expensive, difficult to administer, and insufficiently fault-tolerant for long-running queries.The cited applications include web-data, clickstream, network-monitoring, simulation, sensor, and laboratory-data analysis.
  • MapReduce response: MapReduce enables large-scale processing on commodity clusters that can scale to thousands of nodes while isolating developers from data distribution, scheduling, and fault-tolerance details.Its programming model is described as simple and powerful.
  • Cloud computing: Cloud computing offers reduced provisioning time, pay-as-you-go costs, and virtually unlimited throughput by adding servers as workloads increase.These benefits support hosting data-intensive applications in centralized, large-scale datacenters.
  • Survey scope: The survey examines MapReduce-based performance and capability improvements, SQL-like interfaces, related large-scale processing systems, and future directions for MapReduce-like solutions.It responds to limitations in the basic MapReduce architecture through a comprehensive review of research and industrial approaches.

2. MAPREDUCE FRAMEWORK: BASIC ARCHITECTURE

MapReduce expresses distributed computations through Map and Reduce functions over key/value pairs and executes them across commodity clusters. Its architecture assigns map and reduce tasks through a master-worker system, groups intermediate values by key, and processes the grouped data into output.

  • Programming model: MapReduce takes key/value pairs as input and produces key/value pairs as output through user-defined Map and Reduce functions.Map emits intermediate key/value pairs; Reduce merges values associated with each intermediate key.
  • Programming model: The framework is designed for high performance on large clusters of commodity PCs and hides data distribution, scheduling, and fault-tolerance details from application developers.Its shared-nothing architecture supports scalability and parallelization.
  • Hadoop implementation: Hadoop is an open-source Java library that implements MapReduce for data-intensive distributed applications and is widely used in production.The paper uses MapReduce and Hadoop interchangeably in the remainder of its discussion.
  • Execution flow: Input data is split into M pieces, while a master assigns M map tasks and R reduce tasks to available workers.One program instance becomes the master and the remaining instances serve as workers.
  • Execution flow: Reduce workers read buffered map output from local disks, sort it by intermediate key, and pass each key with its values to the user’s Reduce function.Sorting groups occurrences of the same key before reduction.

3. EXTENSIONS AND ENHANCEMENTS OF THE MAPREDUCE FRAMEWORK

The survey reviews extensions that address limitations in basic MapReduce, especially inefficient joins, data placement, and execution flow. These approaches add join strategies, multi-dataset processing, data colocation, and pipelining to improve large-scale analytics.

  • Motivation for extensions: Basic MapReduce supports flexible processing but has limitations including inefficient output handling, textual formats, absent index use, and costly multi-dataset joins.The survey identifies these issues as targets for subsequent improvements.
  • Join strategies: Standard repartition joins dynamically partition both relations by join key, while improved repartition joins buffer only the smaller input and stream the larger one.The improved strategy addresses memory pressure caused by skewed or low-cardinality join keys.
  • Join strategies: A decision tree selects join strategies using relative data size, referenced-key fraction, preprocessing availability, and network-transfer cost.Without preprocessing, broadcasting is preferred when its network cost is lower; with preprocessing, semi-join variants and sufficiently partitioned directed joins are favored.
  • Join strategies: Broadcast joins move only the smaller relation, avoiding preprocessing and reducing network overhead relative to repartition-based joins.The approach incurs an extra scan of the smaller relation to identify referenced join keys.
  • Multi-dataset processing: MapReduce-Merge enables multiple-dataset processing by allowing reducers to emit key/value lists and adding a merge phase across separate data lineages.The merge combines reduced outputs by keys and supports self-merge when both lineages are identical.
  • Data placement: CoHadoop colocates related files while retaining Hadoop’s load-balancing and fault-tolerance properties, reducing shuffling and network overhead for multi-file applications.It adds a file property and locator table to place related files on the same datanodes.
  • Pipelining and streaming: Pipelining lets reducers process mapper output as it is produced, enabling early approximations, continuous queries, greater parallelism, and lower response time.The approach broadens MapReduce to stream processing and event monitoring.

4. SYSTEMS OF DECLARATIVE INTERFACES FOR THE MAPREDUCE FRAMEWORK

Declarative interfaces make MapReduce-based data analysis more accessible by raising the programming level above custom map and reduce code. The surveyed systems span scripting languages, SQL-like interfaces, optimization pipelines, and warehouse-oriented abstractions.

  • Motivation: MapReduce’s two primitives simplify parallel programming but its key/value input format and two-stage flow make joins and multi-stage computations rigid.Common operations also require custom code, which can be difficult to reuse and maintain.
  • Sawzall: Sawzall processes one input record at a time and emits results to external aggregators such as Sum, Average, Maximum, and Minimum.Its compiler and byte-code interpreter execute programs directly from source code.
  • FlumeJava: FlumeJava provides Java abstractions for composing parallel collections and translating one or more data-parallel pipelines into a single program.The library is designed for developing and running data-parallel pipelines on top of MapReduce.
  • Pig Latin: Pig Latin occupies a middle position between SQL-style declarative queries and low-level MapReduce programming, while supporting user-defined functions and nested data.Its logical plan forms a DAG, is optimized, and is compiled into a series of MapReduce jobs.
  • Hive: Hive brings relational tables, columns, partitions, and a subset of SQL to Hadoop while retaining Hadoop’s extensibility and flexibility.HiveQL supports DDL, loading, and insertion, while its metastore stores reusable table metadata; row updates and deletions are unsupported.
  • HadoopDB: HadoopDB combines MapReduce coordination with single-node PostgreSQL databases, pushing query processing into databases to target scalability, performance, fault tolerance, and heterogeneous operation.Queries are expressed in SQL and parallelized across nodes using MapReduce.

5. RELATED LARGE SCALE DATA PROCESSING SYSTEMS

The survey reviews systems that resemble MapReduce ideas while using different architectures for declarative execution, dataflow processing, resource coordination, and iterative analytics. These systems extend expressiveness, platform integration, or data reuse beyond the basic MapReduce model.

  • Scope: The reviewed systems resemble MapReduce for different purposes but do not follow its architecture or use the infrastructure of open-source implementations such as Hadoop.They are treated as related large-scale data-processing systems rather than MapReduce implementations.
  • SCOPE and Cosmos: SCOPE is a declarative language that hides platform and implementation details while allowing extensible extractors, processors, reducers, and combiners.Its SQL-like syntax is extended with C# expressions and libraries.
  • SCOPE and Cosmos: Cosmos combines append-only petabyte-scale storage, distributed execution, and SCOPE compilation into efficient parallel execution plans.Applications are represented as dataflow DAGs with processes as vertices and data flows as edges.
  • Dryad: Dryad executes coarse-grain data-parallel applications as dataflow graphs whose vertices communicate through files, TCP pipes, and shared-memory FIFOs.Dryad permits arbitrary numbers of vertex inputs and outputs and maps logical graphs onto physical resources at runtime.
  • DryadLINQ: DryadLINQ generalizes SQL and MapReduce through strongly typed .NET objects and general-purpose imperative and declarative dataset operations.It uses LINQ to provide a hybrid programming model in a traditional high-level language.
  • Spark: Spark targets iterative and interactive applications by caching reusable resilient distributed datasets in memory while retaining MapReduce scalability and fault tolerance.RDD lineage records transformations so lost partitions can be rebuilt selectively.
  • Spark: Spark provides parallel operations over RDDs, but its reduce results are collected at the driver and it does not support grouped reduce as in MapReduce.RDDs can be created from files, Scala collections, or transformations of existing RDDs.

6. CONCLUSIONS

The survey examines MapReduce-based scalable data-processing systems and concludes that MapReduce and Hadoop are mature and widely used, but will coexist with database systems and still require further advances.

  • The article surveys the MapReduce family of approaches for developing scalable data-processing systems and solutions.
  • MapReduce and Hadoop are sufficiently mature for widespread use across academic and industrial application domains.
  • The authors expect MapReduce and database systems to coexist and complement each other in different scenarios.
  • Further work is needed in energy efficiency, debugging large-scale distributed computations, programming-model expressiveness, and complex data-model processing.
  • MapReduce's simplicity creates challenges for efficiently processing nested, XML, hierarchical, RDF, and graph data models.

A. APPLICATION OF THE MAPREDUCE FRAMEWORK

MapReduce systems are increasingly used for large-scale data analysis because their simple interface supports diverse analytical tasks and their flexibility supports varied data and deployment scales.

  • MapReduce's simple interface can express SQL queries, data mining, machine learning, and graph-processing tasks through sets of jobs.
  • MapReduce is flexible because it is independent of storage systems and can analyze structured and unstructured data.
  • MapReduce is scalable, supporting installation across increasing numbers of servers as workloads grow.

A.1 MapReduce for Large Scale XML Processing

The survey describes MapReduce-based approaches for processing large XML documents, including ChuQL, which extends XQuery for distributed XML computation.

  • Large XML processing has been investigated using the MapReduce framework.
  • ChuQL extends XQuery syntax, grammar, and semantics to support distributed XML processing with MapReduce.
  • ChuQL distributes computation across multiple XQuery engines running in Hadoop.

A.2 MapReduce for Large Scale RDF Processing

MapReduce-based RDF processing approaches target semantic metadata and SPARQL workloads through query translation, graph-pattern matching, and RDF-specific partitioning and planning.

  • RDF represents semantic metadata as subject-predicate-object tuples describing relationships among uniquely identified resources.
  • PigSPARQL processes SPARQL queries by translating them into Pig Latin programs executed as MapReduce jobs on Hadoop.
  • Other work investigates SPARQL graph-pattern matching using multi-way joins over RDF triples.
  • RDF partitioning approaches include Predicate Split and Predicate Object Split, combined with summary statistics for estimating join selectivities.
  • The proposed RDF query-planning algorithm generates plans whose cost is bounded by a stated bound.

A.3 MapReduce for Large Scale Graph Processing

MapReduce-based systems support scalable processing and querying of massive graphs, but chained MapReduce stages can impose communication, serialization, and coordination overhead. GBASE addresses graph storage and incidence-matrix queries through block-oriented processing, while Pregel is introduced as a scalable graph-processing platform.

  • Motivation: Graphs are widely used to model structural relationships in applications including social, computer, telecommunication, recommendation, biological, and Web networks.This broad use has motivated research into scalable processing mechanisms for massive graph datasets.
  • Graph management systems: GBASE is a scalable graph management system that stores homogeneous graph regions efficiently through block compression.It partitions a raw edge file into homogeneous blocks.
  • Graph management systems: GBASE uses grid selection to minimize disk accesses and applies MapReduce-based algorithms to answer incidence-matrix queries.Its query engine represents inputs as query vectors and graph operations as unified matrix-vector multiplication.
  • Graph management systems: GBASE executes appropriate block matrix-vector multiplication modules to handle different graph query inputs and operations.The query engine unifies input types as query vectors and operations through unified matrix-vector multiplication.
  • Graph-processing challenges: Chaining MapReduce invocations for graph algorithms requires passing the entire graph state between stages, creating communication, serialization, and coordination overhead.The survey identifies this approach as ill-suited for graph processing and potentially suboptimal in performance.

A.4 Other MapReduce Applications

MapReduce has been applied to diverse data-intensive tasks beyond graph processing, including entity resolution, similarity joins, clustering, spatial management, and social-media matching. These systems translate workflows or computational stages into distributed processing across Hadoop or other cluster resources.

  • Entity resolution: Dedoop provides a MapReduce-based entity-resolution framework supporting complex matching workflows and machine-learning-generated match classifiers.Its workflows are automatically translated into MapReduce jobs for parallel execution on Hadoop clusters.
  • Duplicate detection and similarity joins: MapDupReducer applies MapReduce to near-duplicate detection, while related work develops parallel set-similarity joins over records.The set-similarity approach uses three stages, partitions data across nodes, balances workload, and limits replication.
  • Clustering and preprocessing: DisCo uses MapReduce for distributed data preprocessing and co-clustering from raw data through final clusters.Other work targets subspace clustering in very large moderate-to-high dimensional datasets.
  • Statistical processing: R exchanges data with Hadoop by sending aggregation-processing queries and receiving aggregated data for statistical processing or visualization.This workflow connects MapReduce-style aggregation with R-based analysis.
  • Spatial and social-media applications: MapReduce applications also include bulk construction of R-Trees, aerial-image quality computation, and social-media content matching.The spatial tasks involve vector and raster data, while GreedyMR and StackMR distribute content between information suppliers and consumers.
Loading 1302.2966v1…