Check if entry was truly inserted when using the LFU policy

[ChillFish8]

I couldn't quite wrap my head around the docs and code, when using the LFU policy is there any way to actually know if the entry was inserted or not by the admission filter?

Use case: I was a set of steps that need to run in the event the entry was inserted, but not unless it actually accepted or not. Under normal circumstances, with an LRU this is simple enough, but with the LFU I'm not sure Moka guarantees that when calling insert the entry will actually stay in the cache or not.

[tatsuya6502]

Hi. Unfortunately, we cannot check if an entry was truly inserted when using the TinyLFU policy.

With the TinyLFU policy, the cache works as follows:

• The insert method always inserts the entry into the cache, even if the cache is full.
• There is no way to know if the entry will soon be rejected by the LFU filter, or if it will be accepted and kept for a while.
• When the maintenance task is implicitly or explicitly processed, the LFU filter will decide whether to accept or reject the entry.
  • If the entry's popularity is higher then the LRU entry's popularity, the entry will be accepted.
• When an entry is removed from the cache, the eviction listener is called.
  • As of moka@v0.12.x, the removal cause is Size for both rejected and accepted entries. So we cannot know if the entry was rejected or accepted.

The following example demonstrates the behavior of the TinyLFU policy:

use moka::sync::Cache;

fn main() {
    // Create a cache with the max capacity 100.
    let cache = Cache::builder()
        .max_capacity(100)
        .eviction_listener(|k, _v, cause| {
            println!("Evicted key: {:?}, cause: {:?}", k, cause);
        })
        .build();

    // When a cache is created, its LFU filter is disabled.
    // It will be enabled when the cache is half full.

    // Insert 50 entries to the cache to make it half full.
    for i in 1..=50 {
        cache.insert(i, i);
    }

    // Now the cache is half full. This will enable the LFU filter.
    cache.run_pending_tasks();

    // Access 100 keys once to set the popularity of these keys to 1.
    for i in 1..=100 {
        cache.get(&i);
    }

    // Insert 50 more entries to the cache. So the cache is full now.
    for i in 51..=100 {
        cache.insert(i, i);
    }

    cache.run_pending_tasks();

    println!("entry_count(): {}", cache.entry_count()); // 100

    println!("Insert 101th entry to the cache.");
    cache.insert(101, 101);
    // Note: contains_key does not increase the popularity of the key.
    println!("contains_key(&101): {}", cache.contains_key(&101)); // true
    cache.run_pending_tasks(); // key 101 should be evicted. (rejected by the LFU filter)
    println!("contains_key(&101): {}", cache.contains_key(&101)); // false

    println!("Access key 101 twice to set its popularity two.");
    cache.get(&101);
    cache.get(&101);

    println!("Insert 101th entry to the cache again.");
    cache.insert(101, 101);
    println!("contains_key(&101): {}", cache.contains_key(&101)); // true
    cache.run_pending_tasks(); // key 1 (the LRU) should be evicted.
    println!("contains_key(&101): {}", cache.contains_key(&101)); // true
}

$ cargo run 
   Compiling ...
     Running ...
entry_count(): 100
Insert 101th entry to the cache.
contains_key(&101): true
Evicted key: 101, cause: Size
contains_key(&101): false
Access key 101 twice to set its popularity two.
Insert 101th entry to the cache again.
contains_key(&101): true
Evicted key: 1, cause: Size
contains_key(&101): true

[ChillFish8]

Thanks for the really detailed answer!

If the entry is always inserted (at least initially) then this actually works for my use case or at least I can work around it well enough since at least I know the behaviour is consistent.