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

Metadata caches show correlated references that trick LRU/2Q/CLOCK/S3-FIFO into marking blocks “hot.” Clock2Q+ uses three queues + a correlation window so near-duplicate hits don’t set the reference bit.

• Characterized metadata correlation across block-cache datasets (e.g., B-tree leaves).
• Designed/implemented Clock2Q+ for high-locality requests.
• Observed up to 28.5% miss-ratio reduction on metadata traces; wins carry to data traces.

Clock2Q+ is designed for production use, offering low CPU overhead, minimal memory requirements, efficient multi-CPU scaling, and ease of implementation. It outperforms existing algorithms on both metadata and data traces, and has been deployed in VMware’s vSAN and VDFS storage products.