Accelerating large-scale data exploration through data diffusion

ABSTRACT

Data-intensive applications often require exploratory analysis of large datasets. If analysis is performed on distributed resources, data locality can be crucial to high throughput and performance. We propose a "data diffusion" approach that acquires compute and storage resources dynamically, replicates data in response to demand, and schedules computations close to data. As demand increases, more resources are acquired, thus allowing faster response to subsequent requests that refer to the same data; when demand drops, resources are released. This approach can provide the benefits of dedicated hardware without the associated high costs, depending on workload and resource characteristics. The approach is reminiscent of cooperative caching, web-caching, and peer-to-peer storage systems, but addresses different application demands. Other data-aware scheduling approaches assume dedicated resources, which can be expensive and/or inefficient if load varies significantly. To explore the feasibility of the data diffusion approach, we have extended the Falkon resource provisioning and task scheduling system to support data caching and data-aware scheduling. Performance results from both micro-benchmarks and a large scale astronomy application demonstrate that our approach improves performance relative to alternative approaches, as well as provides improved scalability as aggregated I/O bandwidth scales linearly with the number of data cache nodes.

REFERENCES

• 1: W. Xiaohui, et al. "Implementing data aware scheduling in Gfarm using LSF scheduler plugin mechanism", 2005 International Conference on Grid Computing and Applications, pp.3--10, 2005
• 2: P. Fuhrmann. "dCache, the commodity cache," IEEE Mass Storage Systems and Technologies 2004
• 3: 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
• 4: Ioan Raicu , Yong Zhao , Catalin Dumitrescu , Ian Foster , Mike Wilde, Falkon: a Fast and Light-weight tasK executiON framework, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362680]
• 5: Ioan Raicu , Ian Foster , Alex Szalay, Harnessing grid resources to enable the dynamic analysis of large astronomy datasets, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188611]
• 6: I. Raicu, I. Foster, A. Szalay, G. Turcu. "AstroPortal: A Science Gateway for Large-scale Astronomy Data Analysis", TeraGrid Conference 2006
• 7: A. Szalay, J. Bunn, J. Gray, I. Foster, I. Raicu. "The Importance of Data Locality in Distributed Computing Applications", NSF Workflow Workshop 2006
• 8: Frank B. Schmuck , Roger L. Haskin, GPFS: A Shared-Disk File System for Large Computing Clusters, Proceedings of the Conference on File and Storage Technologies, p.231-244, January 28-30, 2002
• 9: SDSS: Sloan Digital Sky Survey, http://www.sdss.org/, 2007
• 10: K. Ranganathan, I. Foster, "Simulation Studies of Computation and Data Scheduling Algorithms for Data Grids", Journal of Grid Computing, V1(1) 2003
• 11: 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
• 12: I. Raicu, C. Dumitrescu, I. Foster. "Dynamic Resource Provisioning in Grid Environments", TeraGrid Conf. 2007
• 13: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 14: John A. Stankovic , Krithi Ramamritham , Douglas Niehaus , Marty Humphrey , Gary Wallace, The Spring System: Integrated Support for Complex Real-TimeSystems, Real-Time Systems, v.16 n.2-3, p.223-251, May 1999 [doi>10.1023/A:1008051107382]
• 15: G.B. Berriman, et al. "Montage: a Grid Enabled Engine for Delivering Custom Science-Grade Image Mosaics on Demand." SPIE Conference on Astronomical Telescopes and Instrumentation, 2004
• 16: Y. Zhao, M. Hategan, B. Clifford, I. Foster, G. von Laszewski, I. Raicu, T. Stef-Praun, M. Wilde. "Swift: Fast, Reliable, Loosely Coupled Parallel Computation", IEEE Workshop on Scientific Workflows 2007
• 17: Ragib Hasan , Zahid Anwar , William Yurcik , Larry Brumbaugh , Roy Campbell, A Survey of Peer-to-Peer Storage Techniques for Distributed File Systems, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II, p.205-213, April 04-06, 2005 [doi>10.1109/ITCC.2005.42]
• 18: Stefan Podlipnig , Laszlo Böszörmenyi, A survey of Web cache replacement strategies, ACM Computing Surveys (CSUR), v.35 n.4, p.374-398, December 2003 [doi>10.1145/954339.954341]
• 19: Riccardo Lancellotti , Bruno Ciciani , Michele Colajanni, A Scalable Architecture for Cooperative Web Caching, Revised Papers from the NETWORKING 2002 Workshops on Web Engineering and Peer-to-Peer Computing, p.29-41, May 19-24, 2002
• 20: C. Catlett, et al. "TeraGrid: Analysis of Organization, System Architecture, and Middleware Enabling New Types of Applications," HPC 2006
• 21: 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
• 22: I. Raicu, I. Foster. "Characterizing Storage Resources Performance in Accessing the SDSS Dataset," Tech. Report, Univ of Chicago, 2006
• 23: X. Wei, W.W. Li, O. Tatebe, G. Xu, L. Hu, and J. Ju. "Integrating Local Job Scheduler -- LSF with Gfarm", Parallel and Distributed Processing and Applications, Springer Berlin, Vol. 3758/2005, pp 196--204, 2005
• 24: ANL/UC TeraGrid Site Details, http://www.uc.teragrid.org/tg-docs/tg-tech-sum.html, 2007
• 25: CAS SkyServer, http://cas.sdss.org/dr6/en/tools/search/sql.asp, 2007
• 26: I. Raicu, Y. Zhao, I. Foster, A. Szalay. "A Data Diffusion Approach to Large Scale Scientific Exploration," Microsoft eScience Workshop at RENCI 2007
• 27: A. Bialecki, M. Cafarella, D. Cutting, O. O'Malley. "Hadoop: a framework for running applications on large clusters built of commodity hardware", http://lucene.apache.org/hadoop/, 2005
• 28: T. Kosar. "A New Paradigm in Data Intensive Computing: Stork and the Data-Aware Schedulers", IEEE CLADE 2006
• 29: John Bent , Douglas Thain , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , Miron Livny, Explicit control a batch-aware distributed file system, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.27-27, March 29-31, 2004, San Francisco, California
• 30: I. Raicu. "Harnessing Grid Resources with Data-Centric Task Farms", Technical Report, University of Chicago, 2007
• 31: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 32: I. Raicu, I. Foster. "A Comparison of Data Diffusion to the GPFS Shared File System", Technical Report, University of Chicago, 2007
• 33: Y. Zhao, I. Raicu, I. Foster, M. Hategan, V. Nefedova, M. Wilde. "Realizing Fast, Scalable and Reliable Scientific Computations in Grid Environments", Grid Computing Research Progress, Nova Pub. 2008
• 34: J. Gray. "Distributed Computing Economics", Technical Report MSR-TR-2003-24, Microsoft Research, Microsoft Corporation, 2003
• 35: Min Cai , Ann Chervenak , Martin Frank, A Peer-to-Peer Replica Location Service Based on a Distributed Hash Table, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.56, November 06-12, 2004 [doi>10.1109/SC.2004.7]
• 36: William Allcock , John Bresnahan , Rajkumar Kettimuthu , Michael Link, The Globus Striped GridFTP Framework and Server, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.54, November 12-18, 2005 [doi>10.1109/SC.2005.72]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Storage hierarchies

General Terms:
Design, Management, Measurement, Performance

Keywords:
Falkon, Swift, data caching, data diffusion, data management, data-aware scheduling, data-intensive applications, grid