Intermediate Data Caching Optimization for Multi-Stage and Parallel Big Data Frameworks
Preprint
Abstract
In the era of big data and cloud computing, large amounts of data are generated from user applications and need to be processed in the datacenter. Data-parallel computing frameworks, such as Apache Spark, are widely used to perform such data processing at scale. Specifically, Spark leverages distributed memory to cache the intermediate results, represented as Resilient Distributed Datasets (RDDs). This gives Spark an advantage over other parallel frameworks for implementations of iterative machine learning and data mining algorithms, by avoiding repeated computation or hard disk accesses to retrieve RDDs. By default, caching decisions are left at the programmer's discretion, and the LRU policy is used for evicting RDDs when the cache is full. However, when the objective is to minimize total work, LRU is woefully inadequate, leading to arbitrarily suboptimal caching decisions. In this paper, we design an algorithm for multi-stage big data processing platforms to adaptively determine and cache the most valuable intermediate datasets that can be reused in the future. Our solution automates the decision of which RDDs to cache: this amounts to identifying nodes in a direct acyclic graph (DAG) representing computations whose outputs should persist in the memory. Our experiment results show that our proposed cache optimization solution can improve the performance of machine learning applications on Spark decreasing the total work to recompute RDDs by 12%.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- EAD: elasticity aware deduplication manager for datacenters with multi-tier storage systemsCluster Computing, 2018
- LCS: An Efficient Data Eviction Strategy for SparkInternational Journal of Parallel Programming, 2016
- In-Memory Big Data Management and Processing: A SurveyIEEE Transactions on Knowledge and Data Engineering, 2015
- FemtoCaching: Wireless Content Delivery Through Distributed Caching HelpersIEEE Transactions on Information Theory, 2013
- An enhanced extreme learning machine based on ridge regression for regressionNeural Computing and Applications, 2011
- Extreme Learning Machine for Regression and Multiclass ClassificationIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2011
- Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures2010
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policiesIEEE Transactions on Computers, 2001