Upgrade the cache policy from TinyLFU to W-TinyLFU

[tatsuya6502]

Currently, Moka cache uses TinyLFU as the admission/eviction policies (with a small buffer in front of the LFU filter). While it works well for many workloads like database, search, and analytics, it will not work well for recency-biased workloads, like job queues and event streams.

To provide better hit rate for such workloads, do the followings:

• Upgrade the cache admission/eviction policy from TinyLFU to Window-TinyLFU (W-TinyLFU).
• Implement hill climbing to auto-tune the size of the LRU window for current workload.

For more details, see the "Eviction Policy" chapter of an article about Java Caffeine cache:
http://highscalability.com/blog/2019/2/25/design-of-a-modern-cachepart-deux.html

[tatsuya6502]

I started to implement the Window-TinyLFU policy.

• Diff: https://gitlab.com/moka-labs/moka-gh249-support-w-tinylfu/moka/-/compare/main...w-tinylfu
• An updated driver for Caffeine Simulator.
  • Support Window-TinyLFU policy in a new version of Moka caffeine-sim-drivers#2

[tatsuya6502]

In last April, I ran Caffeine Simulator against Moka. However, hit/miss ratio was not good for my Window-TinyLFU implementation (The purple line). Maybe I did something wrong with my implementation.

[tatsuya6502]

However, hit/miss ratio was not good for my Window-TinyLFU implementation (The purple line). Maybe I did something wrong with my implementation.

Fixed. There was a bug that prevented a W-TinyLFU cache from activating the LFU filter. So the popularity of keys was always zero.

https://gitlab.com/moka-labs/moka-gh249-support-w-tinylfu/moka/-/commit/9abf50718fb1e3419456d772250fbdd559e9b9cb

-                if self.eviction_policy == EvictionPolicyConfig::TinyLfu
-                    && self.should_enable_frequency_sketch(&eviction_state.counters)
+                if matches!(
+                    self.eviction_policy,
+                    EvictionPolicyConfig::TinyLfu | EvictionPolicyConfig::WindowTinyLfu { .. },
+                ) && self.should_enable_frequency_sketch(&eviction_state.counters)
                 {
                     self.enable_frequency_sketch(&eviction_state.counters).await;
                 }