Efficiency
Work in Progress
Least Recently Used is a popular eviction policy due to its simplicity and good hit rate in common scenarios. However, in typical workloads LRU is not optimal and has a poor hit rate in cases like full scans. The following sections compare the best alternatives after an extensive evaluation. For brevity only the top three performing O(1) eviction policies are discussed. This excludes Clock based policies that trade O(n) worst case time complexity in order to be more amenable to concurrent implementations.
For Caffeine 2.0 the Window TinyLfu policy was chosen due to its optimal hit rate, low memory footprint, and simplicity.
ARC...
LIRS...
W-TinyLfu...
The eviction policies are compared against Bélády's optimal for the theoretical upper bound. A subset of the traces evaluated are described to provide a range of workloads.
WikiBench provides a trace of 10% of all user requests issued to Wikipedia. This workload follows a Zipf distribution, which is the pattern that most application exhibit.
...
This trace is provided by the authors of the LIRS algorithm and exhibits a looping access pattern.
...
This trace is provided by UCSD CS-240a and demonstrates exhibits a high time locality and low frequency pattern.
...
This trace is provided by the authors of the ARC algorithm and is described as "a database server running at a commercial site running an ERP application on top of a commercial database."
...
This trace is provided by the authors of the ARC algorithm and "contains references to a CODASYL database for a one hour period."
...
