Storage Systems - Projects - Caching Technologies

ARC: Adaptive Replacement Cache: Adaptive Replacement Cache (ARC) is a scan-resistant, low space/time complexity, adaptive algorithm for effective read cache management. ARC outperforms LRU for a wide range of workloads. For example, for a huge, real-life workload generated by a large commercial search engine with a 4GB cache, ARC's hit ratio was dramatically better than that of LRU (40.44 percent vs. 27.62 percent).

SARC: Sequential prefetching in Adaptive Replacement Cache Sequential-prefetching in Adaptive Replacement Cache (SARC) is an efficient adaptive algorithm for managing read caches with both demand-paged and prefetched data. SARC is available in IBM's flagship storage controllers - IBM System Storage DS6000 and DS8000 series. On a widely adopted performance benchmark, SPC-1, SARC reduces the miss ratio by 11%, and increases the peak throughput by 12.5%, effectively increasing the cache space by 33%.

Other Contributions: The IBM Storoage System DS8000 series was enhanced with a new prefetching algorithm that preloads and manages sequential data in the cache so it always contains the needed sequential data before it is requested. This lead to a 100% hit ratio for most sequential workloads. Another innovation involved eliminating undesirable interactions between the read- and write-cache management while still allowing both caches to beneficially share memory resources. The combined benefit of these two technologies yielded an improvement of 15% in the peak throughput achieved by the system in the widely adopted performance benchmark, SPC-1.

WOW: Wise Ordering for Writes Write caches using fast, non-volatile storage are now widely used in modern storage controllers since they enable hiding latency on writes. A write caching policy must decide what data to destage. On one hand, to exploit temporal locality, we would like to destage data that is least likely to be re-written soon with the goal of minimizing the total number of destages. On the other hand, to exploit spatial locality, we would like to destage writes so as to minimize the average cost of each destage.WOW is a novel algorithm, namely, for write cache management that effectively combines and balances temporal and spatial locality. It convincingly outperforms both CSCAN (Circular Scan) and LRW (Least Recently Written) policies.

AMP: Adaptive Multi-stream Prefetching in a Shared Cache Prefetching is a widely used technique in modern data storage systems. There are two problems that plague the state-of-the-art sequential prefetching algorithms: (i) cache pollution, which occurs when prefetched data replaces more useful prefetched or demand-paged data, and (ii) prefetch wastage, which happens when prefetched data is evicted from the cache before it can be used. AMP provides a cache management policy that resolves these problems for a cache shared by multiple sequential request streams. AMP is provably optimal, and beats all other sequential prefetching algorithms convincingly across a wide variety of workloads and cache sizes.