SCOPE: easy and efficient parallel processing of massive data sets

ABSTRACT

Companies providing cloud-scale services have an increasing need to store and analyze massive data sets such as search logs and click streams. For cost and performance reasons, processing is typically done on large clusters of shared-nothing commodity machines. It is imperative to develop a programming model that hides the complexity of the underlying system but provides flexibility by allowing users to extend functionality to meet a variety of requirements.

In this paper, we present a new declarative and extensible scripting language, SCOPE (Structured Computations Optimized for Parallel Execution), targeted for this type of massive data analysis. The language is designed for ease of use with no explicit parallelism, while being amenable to efficient parallel execution on large clusters. SCOPE borrows several features from SQL. Data is modeled as sets of rows composed of typed columns. The select statement is retained with inner joins, outer joins, and aggregation allowed. Users can easily define their own functions and implement their own versions of operators: extractors (parsing and constructing rows from a file), processors (row-wise processing), reducers (group-wise processing), and combiners (combining rows from two inputs). SCOPE supports nesting of expressions but also allows a computation to be specified as a series of steps, in a manner often preferred by programmers. We also describe how scripts are compiled into efficient, parallel execution plans and executed on large clusters.

REFERENCES

• 1: Apache. Hadoop. http://lucene.apache.org/hadoop/, 2008.
• 2: Apache. Pig. http://incubator.apache.org/pig/, 2008.
• 3: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 4: Lingkun Chu , Hong Tang , Tao Yang , Kai Shen, Optimizing data aggregation for cluster-based internet services, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 5: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 6: Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 7: G. Graefe. The Cascades framework for query optimization. IEEE Data Eng. Bull., 18(3): 1995.
• 8: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 9: Hongjun Lu , K. L. Tan , Beng-Chin Ooi, Query Processing in Parallel Relational Database Systems, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 10: Christopher Olston , Benjamin Reed , Utkarsh Srivastava , Ravi Kumar , Andrew Tomkins, Pig latin: a not-so-foreign language for data processing, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376726]
• 11: Rob Pike , Sean Dorward , Robert Griesemer , Sean Quinlan, Interpreting the data: Parallel analysis with Sawzall, Scientific Programming, v.13 n.4, p.277-298, October 2005
• 12: Hung-chih Yang , Ali Dasdan , Ruey-Lung Hsiao , D. Stott Parker, Map-reduce-merge: simplified relational data processing on large clusters, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247602]
• 13: Yahoo! Research, PNUTS - Platform for Nimble Universal Table Storage, http://research.yahoo.com/node/212, 2008

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Languages, Management, Performance