This paper has described a new technique for managing the client cache in a distributed persistent object system. HAC is a hybrid between page and object caching that combines the virtues of both while avoiding their disadvantages: it achieves the low overheads of a page-caching system, but does not have high miss rates when spatial locality is poor; and it achieves the low miss rates of object-caching systems, while avoiding their problems of storage fragmentation and high overheads for managing the cache at a fine granularity. Furthermore, HAC is adaptive: when spatial locality is good, it behaves like a page-caching system, avoiding the overheads of object caching where it has low benefit. If spatial locality is poor, it behaves like an object-caching system, taking advantage of the low miss rates to offset the increased overheads. It is able to dynamically adjust the amount of cache space devoted to pages so that space in the cache can be used in the way that best matches the needs of the application.
The paper compares HAC to QuickStore, the best page-caching system in the literature, and shows that HAC significantly outperforms QuickStore for the range of spatial locality that can be expected using practical clustering algorithms. The paper also shows HAC outperforms GOM, the best dual-buffering system in the literature. Since GOM was shown to have lower miss rates than object-caching systems and our overheads are very low, we claim HAC will also outperform the best object-caching systems. Therefore, we believe hybrid adaptive caching is the cache management technique of choice for distributed, persistent object storage systems.
Miguel Castro, Atul Adya, Barbara Liskov, and Andrew Myers
Copyright ©1997 by the Association for Computing Machinery