HAC: Hybrid Adaptive Caching for Distributed Storage Systems

Miguel Castro, Atul Adya, Barbara Liskov, and Andrew C. Myers
MIT Laboratory for Computer Science,
545 Technology Square, Cambridge, MA 02139
{castro,adya,liskov,andru}@lcs.mit.edu

Abstract:

This paper presents HAC, a novel technique for managing the client cache in a distributed, persistent object storage system. HAC is a hybrid between page and object caching that combines the virtues of both while avoiding their disadvantages. It achieves the low miss penalties of a page-caching system, but is able to perform well even when locality is poor, since it can discard pages while retaining their hot objects. It realizes the potentially lower miss rates of object-caching systems, yet avoids their problems of fragmentation and high overheads. Furthermore, HAC is adaptive: when locality is good it behaves like a page-caching system, while if locality is poor it behaves like an object-caching system. It is able to adjust the amount of cache space devoted to pages dynamically so that space in the cache can be used in the way that best matches the needs of the application.

The paper also presents results of experiments that indicate that HAC outperforms other object storage systems across a wide range of cache sizes and workloads; it performs substantially better on the expected workloads, which have low to moderate locality. Thus we show that our hybrid, adaptive approach is the cache management technique of choice for distributed, persistent object systems.

• Lazy Reference Counting for Transactional Storage Systems

Technical Memo MIT/LCS/TM-567, MIT Laboratory for Computer Science, November 1997. Miguel Castro, Atul Adya, and Barbara Liskov

Contents:

• 1 Introduction
• 2 System Overview
• 2.1 Servers
• 2.2 Page and Object Format
• 2.3 Clients
• 3 Hybrid Adaptive Caching
• 3.1 Compaction
• 3.2 Replacement Policy
• 3.2.1 Object Usage Computation
• 3.2.2 Frame Usage Computation
• 3.2.3 The Candidate Set
• 3.2.4 Selection of Victims
• 3.3 Replacement in the Background
• 3.4 Summary
• 4 Performance Evaluation
• 4.1 Experimental Setup
• 4.1.1 Traversals
• 4.1.2 Parameter Settings
• 4.2 Miss Rate
• 4.2.1 Systems Studied
• 4.2.2 Comparison with QuickStore
• 4.2.3 Additional Experiments
• 4.2.4 Comparison with GOM
• 4.3 Hit Time
• 4.4 Miss Penalty
• 4.5 Overall Performance
• 4.6 Traversals With Updates
• 5 Conclusions
• Acknowledgements
• References

Miguel Castro, Atul Adya, Barbara Liskov, and Andrew C. Myers. HAC: Hybrid Adaptive Caching for Distributed Storage Systems. Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint-Malo, France, 5-8 October 1997.

This research was supported in part by DARPA contract DABT63-95-C-005, monitored by Army Fort Huachuca, and in part by DARPA contract N00014-91-J-4136, monitored by the Office of Naval Research. M. Castro is supported by a PRAXIS XXI fellowship.

Copyright ©1997 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or ``permissions@acm.org''