Skip to content

Composable caches for rust

License

Apache-2.0, Unknown licenses found

Licenses found

Apache-2.0
LICENSE.txt
Unknown
LICENSE.template
Notifications You must be signed in to change notification settings

LucaFulchir/ccache

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

48 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CCache, Composable Caches

Some caches are a combination of multiple others This project tries to create a minimal framework to implement such caches, and provides a common hashmap and traits to reuse and reimplement everything in any way you want.

We also provide an (optional) way to store other metadata along with the values in the cache and have callbacks triggered for every get/insert operation

Current caches implemented

  • LRU
  • SLRU
  • W-TiniyLFU (scan variant, named SW-TinyLFU

ScanWindow Tiny LFU

The basic idea is to implement a w-tlfu cache as per this paper

W-TLFU works by having counters which are all halved every X accesses.
This seems problematic for larger caches, so instead we implemented a lazy scan: instead of just a counter, each object keeps a generation (Day/Night) along with the counter.
Every time an object is accessed we scan it and the next one.
If the generation is not the current one, the counter is halved.

Due to memory alignment SW-TLFU does not implement the "doorkeeper" bloom filter and stores the counters directly in the hashmap used by the caches.

Status/Help needed

  • Shared LRU/SLRU/SW-TLFU done
  • completely untested
  • not benchmarked
  • We can probably simplify the pointers in the user::Entry with smaller indexes
  • some use of unsafe that I hope could be resolved but am not knowledgeable enough in rust
  • More documentation needed
  • common traits for all caches
  • more advanced methods that just get/insert?
  • common allocators
  • wrappers to have templates with less parameters

Structure:

Hashmap

We had to reimplement an hashmap since the standard ones do not let you access its entries by index, and are not stable (the objects can move around on insert/remove)

The implementation is based on the same RawTable used by hashbrown

user::Entry

You can reimplement you own entry type, assuming you provide the necessary traits

You can add or better hide some fields, like swtlfu::Full32 does to cram a Generation and a counter in the cache id

Entries must know in which sub-cache they are, but if you are only using one cache you can use PhantomData

SharedXXX

This is the implementation of a shared cache. By Shared cache we mean one or more probably more caches that reuse the same (shared) hashmap

About

Composable caches for rust

Resources

License

Apache-2.0, Unknown licenses found

Licenses found

Apache-2.0
LICENSE.txt
Unknown
LICENSE.template

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages