Help with size based eviction that weighs with bytes about moka HOT 2 OPEN

Hi.

It's going to be something like size_of(key) + size_of(value) + overhead. What is the overhead? And is this the right idea?

Yes, it is the right idea.

Overhead per Entry

The overhead per cache entry will be the followings on 64-bit platforms:

*1: Write-order queue is enabled if one or both of the following CacheBuilder method was/were called:

• time_to_live
• support_invalidation_closures

*2: Overhead becomes bigger than the numbers listed here if the crate feature quanta and/or atomic64 is disabled. (They are enabled by default)

Overhead of The Whole Cache

The LFU Filter (CountMin Sketch)

When the cache becomes half-full, the LFU filter (aka CountMin Sketch) will be created for the cache.

The size of the filter is decided by an estimated max number of entries in the cache. Cache uses the following code to estimate:

let estimated_max_num_entries: u64 = ((current_num_entries as f64
    * (current_total_weighted_size as f64 / max_capacity as f64))
    as u64)
    .max(128);  // minimum 128 entries.

The byte size of the LFU filter can be calculated by the following code:

// maximum 8GiB on 64-bit platform.
let byte_size = 8 *
    estimated_max_num_entries
        .min(2u64.pow(30))
        .next_power_of_two();

Here are some examples:

EDIT: Fixed the formula for the LFU filter. Forgot to multiply by 8 as the internal table is Box<[u64]>, not Box<[u8]>.

from moka.

Also my Cache's Values are json_serde::Value and I'm not sure how to calculate their size in memory. Maybe that's a better question for the serde issue tracker though.

If I understand the internal data structure of serde_json::Value correctly, the following function can calculate the byte size of a value. You may want to ask serde_json maintainers if this function makes sense.

use serde_json::Value;

fn size_of_json_val(json: &Value) -> usize {
    use serde_json::Value::*;
    use std::mem::size_of;

    let v_size = size_of::<Value>();
    match json {
        Null | Bool(_) | Number(_) => v_size,
        String(str) => v_size + str.capacity(),
        Array(vec) => {
            v_size
                + vec.iter().map(size_of_json_val).sum::<usize>()
                + v_size * (vec.capacity() - vec.len())
        }
        Object(map) => {
            let s_size = size_of::<std::string::String>();
            v_size
                + map
                    .iter()
                    .map(|(k, v)| s_size + k.capacity() + size_of_json_val(v))
                    .sum::<usize>()
            // Can't do the following because `serde_json::Map` does not have `capacity` method.
            // + (s_size + v_size) * (map.capacity() - map.len())
        }
    }
}

EDIT: Fixed the formula for Object(map) by adding s_size.

from moka.