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 .
@cite_27: The design of efficient storage hierarchies generally involves the repeated running of "typical" program address traces through a simulated storage system while various hierarchy design parameters are adjusted. This paper describes a new and efficient method of determining, in one pass of an address trace, performance measures for a large class of demand-paged, multilevel storage systems utilizing a variety of mapping schemes and replacement algorithms. The technique depends on an algorithm classification, called "stack algorithms," examples of which are "least frequently used," "least recently used," "optimal," and "random replacement" algorithms. The techniques yield the exact access frequency to each storage device, which can be used to estimate the overall performance of actual storage hierarchies.
@cite_25: ABSTP CT. A formal model is presented for paging algorithms under -order nonstationary assumptions about program behavior. When processing a program under paging in a given memory, a given paging policy generates a certain (expected) number of page calls, i.e., its "cost." Under usual assumptions about memory system organization, minimum cost is always achieved by a demand paging algorithm. The minimum cost for -order program behavior assumptions is expressed as a dynamic programming problem whose solution yields an optimal replacement algorithm. Solutions are exhibited in several 0-order cases of interest. Paging algorithms that implement and approximate the minimum cost are discussed.
@cite_6: The underutilization of disk parallelism and file cache buffers by traditional file systems induces I O stall time that degrades the performance of modern microprocessor-based systems. In this paper, we present aggressive mechanisms that tailor file system resource management to the needs of I O-intensive applications. In particular, we show how to use application-disclosed access patterns (hints) to expose and exploit I O parallelism and to allocate dynamically file buffers among three competing demands: prefetching hinted blocks, caching hinted blocks for reuse, and caching recently used data for unhinted accesses. Our approach estimates the impact of alternative buffer allocations on application execution time and applies a cost-benefit analysis to allocate buffers where they will have the greatest impact. We implemented informed prefetching and caching in DEC''s OSF 1 operating system and measured its performance on a 150 MHz Alpha equipped with 15 disks running a range of applications including text search, 3D scientific visualization, relational database queries, speech recognition, and computational chemistry. Informed prefetching reduces the execution time of the first four of these applications by 20 to 87 . Informed caching reduces the execution time of the fifth application by up to 30 .
@cite_15: As the performance gap between disks and micropocessors continues to increase, effective utilization of the file cache becomes increasingly immportant. Application-controlled file caching and prefetching can apply application-specific knowledge to improve file cache management. However, supporting application-controlled file caching and prefetching is nontrivial because caching and prefetching need to be integrated carefully, and the kernel needs to allocate cache blocks among processes appropriately. This article presents the design, implementation, and performance of a file system that integrates application-controlled caching, prefetching, and disk scheduling. We use a two-level cache management strategy. The kernel uses the LRU-SP (Least-Recently-Used with Swapping and Placeholders) policy to allocate blocks to processes, and each process integrates application-specific caching and prefetching based on the controlled-aggressive policy, an algorithm previously shown in a theoretical sense to be nearly optimal. Each process also improves its disk access latency by submittint its prefetches in batches so that the requests can be scheduled to optimize disk access performance. Our measurements show that this combination of techniques greatly improves the performance of the file system. We measured that the running time is reduced by 3 to 49 (average 26 ) for single-process workloads and by 5 to 76 (average 32 ) for multiprocess workloads.
LRU @cite_27 and LFU @cite_25 are the two widely used caching algorithms. As shown in Section , neither algorithm adapts well to the data access pattern in data analytic clusters even though they are simple to implement. Many cache policies evict prefetch data blocks through hints from applications @cite_15 @cite_6 , which are provided by the programmers to indicate what data will be referenced again and when. Nevertheless, inserting such hints can be difficult to the programmer, who has to carefully examine the underlying data access pattern.