February 26, 2016
In computer systems, caches create the ability to simply and effectively boost the performance of any downstream layer, either storage or memory. Literature is rife with a variety of cache replacement algorithms that have optimized cache utilization irrespective of the workload. Unfortunately, conventional cache replacement algorithms have been designed for datapathcaches, wherein each cache miss leads to a cache insertion operation and in most cases, a cache eviction operation as well. These cache updating operations are expensive, often unnecessary, and in many cases counter-productive to cache performance. Non-datapath caches, on the other hand, are not required to perform a cache update on every cache miss. Thus, one can apply opportunistic cache updates, whereby case-by-case decisions can be made whether to perform a cache update. A host-side flash cache is an example of a non-datapath cache. Host-side flash caches are attractive because they can reduce the demands placed on network storage, speed up I/O performance, and provide I/O latency and throughput control. In initial work, we demonstrated that the state-of-the-art external (or second-level) caching algorithm, ARC, had significant shortcomings which compromise both the cache hit-rate as well as the cache update rate. When used with a non-datapath cache, such as a host-side flash cache, this results in not just performance loss but also compromised device lifetime. We then demonstrated using production enterprise workloads that selectively activating the ARC replacement mechanisms based on workload states can offer significant benefit in terms of both cache hit-rate and update-rate. In this project, we will investigate and develop an entirely new class of cache replacement algorithms that are tailored specifically for non-datapath caches. To this end, our focus will be on developing and evaluating algorithms that are aware of workload states and that can intelligently and selectively perform cache updates such as to benefit both cache hit-rate and cache update-rate, and consequently, cache device lifetime. Our past work was limited to modifying ARC and more significantly, the algorithm we evaluated used a set of statically chosen parameters for enabling the selective caching mechanisms we built. In this project, we will build upon this initial work to make selective caching independent of the underlying caching algorithm and evaluate it for a variety of conventional (e.g., LRU, CLOCK) as well as newer (e.g., LIRS, MQ) cache replacement algorithms. Further, we will develop adaptive versions of the selective caching algorithm so that workload-based parameter configuration is no longer necessary.