LRC: Dependency-Aware Cache Management for Data Analytics Clusters
Preprint
Abstract
Memory caches are being aggressively used in today's data-parallel systems such as Spark, Tez, and Piccolo. However, prevalent systems employ rather simple cache management policies--notably the Least Recently Used (LRU) policy--that are oblivious to the application semantics of data dependency, expressed as a directed acyclic graph (DAG). Without this knowledge, memory caching can at best be performed by "guessing" the future data access patterns based on historical information (e.g., the access recency and/or frequency), which frequently results in inefficient, erroneous caching with low hit ratio and a long response time. In this paper, we propose a novel cache replacement policy, Least Reference Count (LRC), which exploits the application-specific DAG information to optimize the cache management. LRC evicts the cached data blocks whose reference count is the smallest. The reference count is defined, for each data block, as the number of dependent child blocks that have not been computed yet. We demonstrate the efficacy of LRC through both empirical analysis and cluster deployments against popular benchmarking workloads. Our Spark implementation shows that, compared with LRU, LRC speeds up typical applications by 60%.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- SPEC CPU2000: measuring CPU performance in the New MillenniumComputer, 2000
- Implementation and performance of integrated application-controlled file caching, prefetching, and disk schedulingACM Transactions on Computer Systems, 1996
- RAID: high-performance, reliable secondary storageACM Computing Surveys, 1994
- Caching in the Sprite network file systemACM Transactions on Computer Systems, 1988
- Operating system support for database managementCommunications of the ACM, 1981
- Principles of Optimal Page ReplacementJournal of the ACM, 1971
- Evaluation techniques for storage hierarchiesIBM Systems Journal, 1970
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966