#1288

feat: Admission Policy

Opensfc-gh-rnarubinopened 6mo ago

Hey folks. I am working on new functionality and would like to hear your thoughts on interface design.

All of the function names and return types in these examples are made up, better names and types to be determined.

I'd like a configurable admission policy for the cache: given a key &K, determine if the value is worth caching at all. Unlike the cache Filter this evaluates just the key, the value may not be known yet. This is similar to the StorageFilterCondition (though it should take K instead of the u64 hash), except applied to the whole cache and not just storage.

Consider this read-through get_or_maybe_fetch workflow:

  1. get_or_maybe_fetch(k: &K, fetch: F)
  2. cache checks whether k is already cached 2a. on hit: return Entry::Hit(k, v, source: Memory|Disk)
  3. on miss: check the admission policy should_cache(k: &K) -> bool 3a. should_cache false: return Entry::Rejected
  4. should_cache true: fetch F
  5. insert into cache, return Entry::Hit(k, v, source: Outer)

Read-aside caching can have similar behavior using just get_or_reject

  1. get_or_reject(k: &K)
  2. check the cache 2a. hit: return Entry::Hit(k, v)
  3. miss: check the admission policy should_cache(k: &K) -> bool 3a. false: return Entry::Rejected 3b. true: return Entry::Miss

The internal implementation can take a few forms. There's tiny-lfu, which is pretty generic and could be combined with any eviction policy. This could make sense as a AdmissionPolicy trait, and plug it into some layer adjacent to the cache. Another option is LARC, which has admission and eviction built together into a single algorithm. In that case it makes less sense as an independent AdmissionPolicy and instead should be just another Eviction type with slightly different behavior.

Do you have thoughts on how this should look?

Activity

0

No activity yet.