Cache.rs

I’ve been toying around with the idea of implementing a low & predictable latency caching library in Rust for a while. It’s interesting to me from a couple of perspectives: having low-level control over memory layout, while honouring Rust’s type system and its guarantees; as well as trying to reconcile the efficiency guarantees, with that level of control, and possibly supporting pluggable eviction algorithms while not hurting performance. The latter I actually think isn’t possible: i.e. some sacrifice on the design side on the altar of performance will forever be required, which will come at odds with the pluggable eviction. But I still would like to toy with the challenge.

Warning

This is all just me fooling around as of now. I’m merely trying to get a thing that works & exposes a somewhat sensible API. Once I have that sorted out, I’ll iterate over the implementation and start making it faster…​

Initial features

• ✓ Cache through API

• ✓ Once-and-only-once loading

• ✓ Clock eviction

• ✓ Thread-safe, with interior mutability

• ❏ Segmented storage, leveraging std::hash

• ❏ Fine(r) grained locking (i.e. don’t lock the entire Cache/Segment on populating, as populating could take a while)

Roadmap

v0.1.0

• ✓ Basic API

• ✓ Minimal & naive implementation of the API

v0.2.0

• ❏ Finer grained locking

• ❏ Proper segmenting

• ❏ First pass of performance improvements

v0.3.0

• ❏ Perf optimizations on CacheThrough

• ❏ Start adding other cache APIs (i.e. other than CacheThrough, maybe a cache-aside?)

v0.4.0

• ❏ More eviction algorithms?

• ❏ Composability? …​ of caches & evictors?

v1.0.0

• Whenever we have a nice set of tools in the toolbox :)

I think the v0.x releases should inform how to resolve the tension between API & performance.

Implementation details

The key part in this I think, but that’s the point behind the whole project, is to be able to walk the clock hand in a CPU cache friendly way. Probably requiring the clock bit information to be held in a different data structure than the cache entries themselves. This will come at a slight overhead on cache hits to update the bit.

The other interesting part is making this work in an optimistic way with regards to coordination primitives. Hence the idea to use interior mutability for cache entries, but fall to different strategies for the eviction data; possibly lowering the guarantees for these.

Finally, trying to plug another eviction algorithm (probably LRU, which requires a different approach to storing the eviction data) and see how that affects the design.

Current API proposal

let cache = cachers::CacheThrough::new(size); // (1)
let value: Option<Arc<V>> = cache.get(key, populating_fn); // (2)
let updated: Option<Arc<V>> = cache.udpate(key, updating_fn); // (3)
cache.remove(key); // (4)

1. cache is not mut, and <K, V> is inferred; the cache would contain at most size entries;

2. key in this case would be a miss, invoking populating_fn only once, whether cache even if cache was shared across threads all trying to access the same key. populating_fn returns the value Some<V> to populate entry for key: K. The .get then returns a Option<Arc<V>>, with None if the populating_fn returned a None

3. .udpate forces an update to the key, whether it was already present or not. updating_fn receives the key but also, unlike populating_fn, a Option<Arc<V>> that represents the previous value if present; .update then returns the updated V

4. remove invalidates the mapping to key without proposing a new value. Which is effectively the equivalent of an .update(key, |_, _| None). I wonder if this is even necesary…​ it’s here tho!