Crate cache_advisor

A simple eviction manager with 256 shards and two segments to provide for scan resistance. Tells you when to evict items from a cache.

features:

• two-segment LRU, protects against cache pollution from single-hit items
• 256 shards accessed via non-blocking flatcombining
• local access buffer that must fill up before accessing shared state
• compresses the costs associated with each item to a u8 using a compression technique that will converge to the overall true sum of costs over time, but allows for much less memory to be used for accounting.

Examples

use cache_advisor::CacheAdvisor;

// each shard stores 10 bytes, 10% of that is in the entry cache
let mut ca = CacheAdvisor::new(256 * 10, 10);

// add item 0 into entry cache
let should_evict = ca.accessed_reuse_buffer(0, 1);
assert!(should_evict.is_empty());

// promote item 0 into main cache
let should_evict = ca.accessed_reuse_buffer(0, 1);
assert!(should_evict.is_empty());

// hit other items only once, like a big scan
for i in 1..5000 {
    let id = i * 256;
    let evicted = ca.accessed_reuse_buffer(id, 1);

    // assert that 0 is never evicted while scanning
    assert!(!evicted.contains(&(0, 1)));
}

let mut zero_evicted = false;

// hit other items more than once, assert that zero does get
// evicted eventually.
for i in 1..5000 {
    let id = i * 256;
    zero_evicted |= ca.accessed_reuse_buffer(id, 1).contains(&(0, 1));
    zero_evicted |= ca.accessed_reuse_buffer(id, 1).contains(&(0, 1));
    zero_evicted |= ca.accessed_reuse_buffer(id, 1).contains(&(0, 1));
}

assert!(zero_evicted);

Structs

CacheAdvisor

A simple eviction manager with 256 shards and two segments to provide for scan resistance. Tells you when to evict items from a cache.