Similarity between windowed LFU and LRU-k caching?

[GavinRay97]

Hiya, I was reading the Javadoc comment in the simulations directory about Windowed LFU, and I was curious how similar this is to the idea of an LRU-k eviction policy?

For reference:

• The LRU-K Page Replacement Algorithm For Database Disk Buffering
• https://en.wikipedia.org/wiki/Page_replacement_algorithm#Variants_on_LRU

The general idea is to store an access history for each entry, and to compute the distance between the current and the k-th access
If multiple keys have less than k recorded accesses, fall back to LRU to evict one of the candidates:

/*
 * The LRU-k algorithm evicts a frame whose backward k-distance is maximum
 * of all frames. Backward k-distance is computed as the difference in time between
 * current timestamp and the timestamp of kth previous access.
 *
 * A frame with less than k historical references is given
 * +inf as its backward k-distance. When multiple frames have +inf backward k-distance,
 * classical LRU algorithm is used to choose victim.
 */

Thank you =)

[ben-manes]

Are you referring to the the Window LFU policy from Karakostas & Serpanos?

Caffeine implements Window TinyLFU, which is a different policy from either of those. It is amortized O(1) where a frequency histogram is maintained across all entries (current and historical) to determine whether to admit an entry. This policy differs from most LFUs because it is not about choosing a victim, but instead is an admission criteria. In that policy the "window" is short for "admission window" to delay the evaluation criteria for promotion into the "main" region, similar to SLRU's probation vs protected regions which promotes on access. The size of the admission window is workload dependent and we size it dynamically using hill climbing. This combination allows for a higher hit rate because it avoid cache pollution (one-hit wonders) and remembers historic items (not just the working set).

[GavinRay97]

This policy differs from most LFUs because it is not about choosing a victim, but instead is an admission criteria.

Ohh, understood now.

In that policy the "window" is short for "admission window" to delay the evaluation criteria for promotion into the "main" region, similar to SLRU's probation vs protected regions which promotes on access. The size of the admission window is workload dependent and we size it dynamically using hill climbing. This combination allows for a higher hit rate because it avoid cache pollution (one-hit wonders) and remembers historic items (not just the working set).

Thank you for the thorough explanation!