Efficiency
Work in Progress
Least Recently Used is a popular eviction policy due to its simplicity and good hit rate in common scenarios. In favorable workloads LRU is rarely optimal and in cases such as full table scans the hit rate may be very low. 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 are sacrifice O(n) worst case times for 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 demonstrates a program access exhibiting high time locality and low frequency.
...
For tiny caches Window TinyLfu mimics an LFU policy because the window is too small capture the highly temporal, low frequent entries. As the size increases, the window becomes large that the policy has an optimal hit rate. By requiring that the window is at least 1 the policy is able to perform optimally in this workload.
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."
...
