FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion
Juncheng Yang, Ziyue Qiu, Yazhuo Zhang, Yao Yue, K. V. Rashmi
Abstract
LRU has been the basis of cache eviction algorithms for decades, with a plethora of innovations on improving LRU's miss ratio and throughput. While it is well-known that FIFO-based eviction algorithms provide significantly better throughput and scalability, they lag behind LRU on miss ratio, thus, cache efficiency.
Topics & Concepts
Computer scienceDemotionFIFO (computing and electronics)FIFO and LIFO accountingCacheThroughputScalabilityCache algorithmsParallel computingPromotion (chess)CPU cacheOperating systemPoliticsWirelessLawPolitical scienceAdvanced Data Storage TechnologiesCaching and Content DeliveryDistributed systems and fault tolerance