Clock2Q+: A Simple and Efficient Replacement Algorithm for Metadata Cache in VMware vSAN

Cache replacement is central to data system performance, yet metadata caches exhibit access patterns that differ substantially from data caches. In particular, metadata blocks often exhibit dense bursts of correlated references (e.g., multiple lookups that touch tuples that co-reside on the same metadata page). Treating such bursts as repeated independent hits can misclassify cold metadata as hot, polluting the cache and degrading hit ratio. We present Clock2Q+, a cache eviction algorithm deployed in the metadata cache of VMware vSAN, a production-grade distributed storage system. Clock2Q+ is the latest stage of nearly a decade of iterative evolution of vSAN's caching layer, shaped by real-world deployment, customer-driven feature requests, and an emphasis on simplicity as a first-class requirement for long-term maintainability. Clock2Q+ has a three-queue structure similar to S3-FIFO, and introduces a correlation window at the head of the Small FIFO in which accesses do not set the reference bit, preventing short-term correlated bursts from triggering premature promotion; accesses beyond this window set the bit so genuinely hot blocks are promoted efficiently. Clock2Q+ achieves the highest median and mean miss-ratio improvement among the state-of-the-art policies we evaluate on both metadata and data workloads, with the largest per-trace gap over S3-FIFO reaching a 28.5% relative miss-ratio reduction on metadata traces. To support production deployment, Clock2Q+ is engineered for low per-hit overhead and multi-core scalability, with allocation-free, array-based structures, fine-grained synchronization, dirty-page-aware eviction and promotion, bounded per-eviction work, and online cache resizing.