Using Lock-Free Design for Throughput-Optimized Cache Eviction
Chao Dong, Fang Wang, Hong Jiang, Dan Feng · Proceedings of the ACM on Measurement and Analysis of Computing Systems · 2025
In large-scale information systems, storage device performance continues to improve while workloads expand in size and access characteristics. This growth puts tremendous pressure on caches and storage hierarchy in terms of concurrent throughput. However, existing cache eviction policies often struggle to provide adequate concurrent throughput due to their reliance on coarse-grained locking mechanisms and complex data structures. This paper presents a practical approach to cache eviction algorithm design, called Mobius, that optimizes the concurrent throughput of caches and reduces cache operation latency by utilizing lock-free data structures, while maintaining comparable hit ratios. Mobius includes two key designs. First, Mobius employs two lock-free FIFO queues to manage cache items, ensuring that all cache operations are executed efficiently in parallel. Second, Mobius integrates a consecutive detection mechanism that merges multiple modifications during eviction into a single operation, thereby reducing data races. Extensive evaluations using both synthetic and real-world workloads from high-concurrency clusters demonstrate that Mobius achieves a concurrent-throughput improvement ranging from 1.2× to 8.5× over state-of-the-art methods, while also maintaining lower latency and comparable cache hit ratios. The implementation of Mobius in CacheLib and RocksDB highlights its effectiveness in enhancing cache performance in practical scenarios.