Using Lock-Free Design for Throughput-Optimized Cache Eviction

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 high cache 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 concurrency. Second, Mobius integrates a consecutive detection mechanism that merges multiple modifications during eviction into a single operation, thereby reducing data races. The implementation of Mobius in CacheLib and RocksDB highlights its high concurrency in both synthetic and real-world workloads.