image:https://gitlab.com/alexsnaps/cachers/badges/master/pipeline.svg[link="https://gitlab.com/alexsnaps/cachers/commits/master",title="pipeline status"]
# 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
* [x] Cache through API
* [x] Once-and-only-once loading
* [x] Clock eviction
* [x] 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
* [x] Basic API
* [x] 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
[source,rust]
----
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!