Home
The cache hit rate is an important factor in determining the performance of a cache. Since the cache stores a portion of the data retrieved from the slower media on the faster media, the performance of the cache is determined by the cache miss rate (number of misses per second).
When cache's capacity is exceeded, it has to select an entry to evict to make some room. Least Recently Used (LRU) 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 may have a poor hit rate in cases like full scans.
Moka, which is inspired by Caffeine cache, is currently using the TinyLFU policy due to its high hit rate and low memory footprint.
It employs the Least Frequently Used (LFU) filter as the admission policy to determine if accept a new entry based on its popularity. The LFU filter relies on a frequency sketch to probabilistically estimate the historic usage of an entry. Once the entry is admitted to the cache, it will be managed by doubly linked list based LRU eviction policy.
In the future, we will upgrade Moka's TinyLFU to the Window-TinyLFU, or W-TinyLFU. It is used by Caffeine today.
It has an admission LRU window in front of the LFU filter. The admission window will deal with entries with high temporal, while the LFU filter and segmented LRU will be dealing with entries with high popularity. The admission window is adaptive. It will adjust its size automatically based on the workload.
Here are some benchmarking results for Moka. We used Caffeine cache's simulator, with a JNI-based Moka driver developed by us. (We will open-source the driver soon)
We are comparing Moka v0.7.0's hit ratios against the followings eviction policies available in the simulator:
- Bélády's optimal policy, for the theoretical upper bound.
- LRU policy, which is commonly employed in mary cache implementations.
The simulator supports many other eviction/admission policies and some Java based products. If you are curious, please see the configuration file for the complete list of supported policies and products.
This trace is provided by the authors of the ARC algorithm and is described as "disk read accesses initiated by a large commercial search engine in response to various web search requests."
Higher is better.
- Green line: Bélády's optimal policy
- Blue line: Moka v0.7.0
- Red line: LRU policy
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."
Higher is better.
- Green line: Bélády's optimal policy
- Blue line: Moka v0.7.0
- Red line: LRU policy
- Caffeine cache's Efficiency page, which has more detailed descriptions about cache policies.
- TinyLFU: A Highly Efficient Cache Admission Policy
- ARC: A Self-Tuning, Low Overhead Replacement Cache