Struct jupiter::lru::LruCache

pub struct LruCache<V: ByteSize> { /* private fields */ }

Provides a size constrained LRU cache.

A cache behaves just like a Map as long as there is no shortage in storage. However, if either the max number of entries is reached or if the allocated memory is above a certain limit, old (least recently used) entries will be evicted - hence the name LRU cache.

Note, that we also permit to manage and control stale data by assigning each entry two TTLs (time to live). If the soft TTL has expired, the normal get function will no longer return the value. If the hard TTL has expired, even the extended_get function will ignore this entry.

Note that this cache supports graceful handling of stale data to support lazy refreshing. See extended_get for a detailed explanation.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );


lru.put("Foo".to_owned(), "Bar".to_owned()).unwrap();
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

// this will still fit..
lru.put("Foo1".to_owned(), "X".repeat(512)).unwrap();
assert_eq!(lru.get("Foo").is_some(), true);
assert_eq!(lru.get("Foo1").is_some(), true);

// this will hit the max memory constraint...
lru.put("Foo2".to_owned(), "X".repeat(512)).unwrap();
// ..and therefore will throw the two others out:
assert_eq!(lru.get("Foo").is_some(), false);
assert_eq!(lru.get("Foo1").is_some(), false);
assert_eq!(lru.get("Foo2").is_some(), true);

Implementations

impl<V: ByteSize> LruCache<V>

pub fn new( capacity: usize, max_memory: usize, soft_ttl: Duration, hard_ttl: Duration, refresh_interval: Duration ) -> Self

Creates a new cache which can store up to capacity entries or as many until they allocated max_memory of heap.

Sett extended_get for an explanation of soft_ttl, hard_ttl and refresh_interval.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

lru.put("Foo".to_owned(), "Bar".to_owned()).unwrap();
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

pub fn put(&mut self, key: String, value: V) -> Result<()>

Stores the given value for the given key.

Errors

Fails if the given entry is larger than max_memory (the max total size of the cache).

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

lru.put("Foo".to_owned(), "Bar".to_owned());
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

pub fn put_with_secondaries( &mut self, key: String, value: V, secondary_keys: Option<Vec<String>> ) -> Result<()>

Stores the given value for the given key and secondary keys.

These keys can be used to also flush this entry from the cache.

Errors

Fails if the given entry is larger than max_memory (the max total size of the cache).

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

lru.put_with_secondaries("Foo".to_owned(),
                         "Bar".to_owned(),
                         Some(vec!["Foobar".to_owned()]));
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

lru.remove_by_secondary("Foobar");
assert_eq!(lru.get("Foo"), None);

pub fn get(&mut self, key: &str) -> Option<&V>

Returns the value which has previously been stored for the given key or None if no value is present.

Note that get will no longer return a value once its soft_ttl has expired.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// After inserting a value...
lru.put("Foo".to_owned(), "Bar".to_owned());
// ..it can be retrieved.
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

pub fn extended_get(&mut self, key: &str) -> Option<(bool, bool, &V)>

Returns the value which has previously been stored for the given key just like get.

However, this will also return values which *soft_ttl has already expired. Therefore this function doesn’t only return the value itself, but two additional flags (in front of it): ACTIVE and REFRESH.

ACTIVE, the first value of the returned triple indicates whether the value is a normal and still valid value (true). If this is false, the entry is stale (its soft_ttl has expired, but its hard_ttl hasn’t).

The second value in the triple, REFRESH, indicates if the cache encourages the caller to update the stale value. Therefore, this is only ever true, if ACTIVE is false, as otherwise there is no need to refresh anything. For the first time, a stale entry (its value) is returned by this function, the REFRESH flag is returned as true. Any subsequent call for this entry will then return false until either the value is refreshed (via put) or after refresh_interval has expired. During this period, the entry will be reported as ACTIVE again so that it can be distinguished from a fully stale entry.

This can be used to lazy update stale content.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be immediately considered stale and be completely evicted
// after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(0),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// Insert a value...
lru.put("Foo".to_owned(), "Bar".to_owned());

// Due to the exotic settings of the cache, the entry is immediately stale and a refresh
// is requested...
assert_eq!(lru.extended_get("Foo").unwrap(), (false, true, &"Bar".to_owned()));
// ..but not for again for the next 2s (in the meantime it is reported as non-stale).
assert_eq!(lru.extended_get("Foo").unwrap(), (true, false, &"Bar".to_owned()));

// If we add a value again, it is also again immediately stale and a refresh would be
// requested...
lru.put("Foo".to_owned(), "Bar1".to_owned());
assert_eq!(lru.extended_get("Foo").unwrap(), (false, true, &"Bar1".to_owned()));

pub fn remove(&mut self, key: &str)

Removes the entry for the given key if present.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// After inserting a value...
lru.put("Foo".to_owned(), "Bar".to_owned());
// ..it can be retrieved.
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

// However, once it is removed...
lru.remove("Foo");
// ..it's no longer accessible.
assert_eq!(lru.get("Foo"), None);

pub fn remove_by_secondary(&mut self, secondary_key: &str)

Removes the entry for the given secondary key if present.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// After inserting a value...
lru.put_with_secondaries("A".to_owned(), "Bar1".to_owned(), Some(vec![ "A".to_owned(), "B".to_owned() ]));
lru.put_with_secondaries("Foo".to_owned(), "Bar2".to_owned(), Some(vec![ "A".to_owned(), "B".to_owned() ]));
lru.put_with_secondaries("Bar".to_owned(), "Bar3".to_owned(), Some(vec![ "B".to_owned() ]));
// ..it can be retrieved.
assert_eq!(lru.get("A").unwrap(), &"Bar1".to_owned());
assert_eq!(lru.get("Foo").unwrap(), &"Bar2".to_owned());

// Removing by secondary key "A"...
lru.remove_by_secondary("A");
assert_eq!(lru.len(), 1);
// ...only deletes the first two (with the appropriate key)...
assert_eq!(lru.get("A"), None);
assert_eq!(lru.get("Foo"), None);
// ...but not the 3rd with another secondary key...
assert_eq!(lru.get("Bar").unwrap(), &"Bar3".to_owned());

pub fn keys(&self) -> impl Iterator<Item = &String> + '_

Returns all keys which are currently in the cache.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// After inserting a value...
lru.put("Foo".to_owned(), "Bar".to_owned());

// Its keys report proper data...
assert_eq!(lru.keys().next().unwrap(), "Foo");

pub fn flush(&mut self)

Removes all entries in this cache.

Note that this will also zero all metrics (reads, writes, cache hits).

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// After inserting a value...
lru.put("Foo".to_owned(), "Bar".to_owned());
// ..it can be retrieved.
assert_eq!(lru.get("Foo").unwrap(), &"Bar".to_owned());

// However, once the cache is flushed...
lru.flush();

// ..it's no longer accessible.
assert_eq!(lru.get("Foo"), None);

pub fn len(&self) -> usize

Returns the number of elements in the cache.

Note that this might include entries which have reached their hard_ttl and can therefore not be used via get or extended_get. However these will of course be evicted once the cache makes room for new entries.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

assert_eq!(lru.len(), 0);
lru.put("Foo".to_owned(), "Bar".to_owned());
assert_eq!(lru.len(), 1);

pub fn is_empty(&self) -> bool

Determines if the cache is completely empty.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

assert_eq!(lru.is_empty(), true);
lru.put("Foo".to_owned(), "Bar".to_owned());
assert_eq!(lru.is_empty(), false);

pub fn capacity(&self) -> usize

Returns to overall capacity (max number of entries) of this cache.

pub fn set_capacity(&mut self, capacity: usize)

Changes the maximal number of entries permitted in this cache.

Note that most probably it is smarter to limit the max_memory than the number of entries.

Examples

// Specifies a cache which can store up to 10 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(10,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// Add some entries...
lru.put("Foo".to_owned(), "Bar".to_owned());
lru.put("Foo1".to_owned(), "Bar".to_owned());
lru.put("Foo2".to_owned(), "Bar".to_owned());
lru.put("Foo3".to_owned(), "Bar".to_owned());
lru.put("Foo4".to_owned(), "Bar".to_owned());
lru.put("Foo5".to_owned(), "Bar".to_owned());
assert_eq!(lru.len(), 6);

// Now request that the cache is reduced to only 3 entries...
lru.set_capacity(3);
assert_eq!(lru.capacity(), 3);

// ensure that all other entries are gone...
assert_eq!(lru.len(), 3);

pub fn max_memory(&self) -> usize

Returns the maximal amount of memory to be (roughly) occupied by this cache.

pub fn set_max_memory(&mut self, max_memory: usize)

Specifies the maximal amount of memory to be (roughly) occupied by this cache.

Examples

// Specifies a cache which can store up to 128 entries which can allocated up to 1024 bytes of
// memory. Each entry will be considered stale after 1m and be completely evicted after 1h.
// Stale entries are refreshed at most every 2s.
let mut lru = LruCache::new(128,
                            1024,
                            Duration::from_secs(60),
                            Duration::from_secs(60 * 60),
                            Duration::from_secs(2),
        );

// Add some entries...
lru.put("Foo0".to_owned(), "Bar".to_owned());
lru.put("Foo1".to_owned(), "Bar".to_owned());
lru.put("Foo2".to_owned(), "Bar".to_owned());
lru.put("Foo3".to_owned(), "Bar".to_owned());
lru.put("Foo4".to_owned(), "Bar".to_owned());
lru.put("Foo5".to_owned(), "Bar".to_owned());
assert_eq!(lru.len(), 6);

// Now request that the cache is reduced to only 14 bytes...
lru.set_max_memory(14);
assert_eq!(lru.max_memory(), 14);

// .. this will kick each but the last two entries out of the cache..
assert_eq!(lru.len(), 2);

pub fn soft_ttl(&self) -> Duration

Returns the current soft time to live to apply on entries.

See extended_get for a detailed description on TTLs.

pub fn set_soft_ttl(&mut self, soft_ttl: Duration)

Specifies the current soft time to live to apply on entries.

Note that this will not affect existing entries, but only ones placed in the cache after this call.

See extended_get for a detailed description on TTLs.

pub fn hard_ttl(&self) -> Duration

Returns the current hard time to live to apply on entries.

See extended_get for a detailed description on TTLs.

pub fn set_hard_ttl(&mut self, hard_ttl: Duration)

Specifies the current hard time to live to apply on entries.

Note that this will not affect existing entries, but only ones placed in the cache after this call.

See extended_get for a detailed description on TTLs.

pub fn refresh_interval(&self) -> Duration

Returns the refresh suppression interval.

See extended_get for a detailed description on this topic.

pub fn set_refresh_interval(&mut self, refresh_interval: Duration)

Specifies the refresh suppression interval to use.

Note that this is not

See extended_get for a detailed description on this topic.

pub fn allocated_memory(&self) -> usize

Returns the amount of memory allocated to store the data of the keys and values of this cache.

The returned value is in bytes. Note that this most probably a rough estimate but should account for the largest part of allocated memory.

pub fn total_allocated_memory(&self) -> usize

Returns the total amount of memory allocated by this cache.

In contrast to allocated_memory() this method also tries to account for the internal hash map and other metadata. Note that these are most probably only estimates as not all involved structures are well known.

The returned value is in bytes.

pub fn utilization(&self) -> f32

Returns the cache utilization in percent.

pub fn memory_utilization(&self) -> f32

Returns the memory utilization in percent.

pub fn hit_rate(&self) -> f32

Returns the cache hit rate in percent.

Note that all metrics are reset when flush() is called.

pub fn write_read_ratio(&self) -> f32

Returns the write read ration in percent.

This simply computes how many of the operations were writes. A healthy cache has way more reads than writes, therefore this might be a helpful metric.

Note that all metrics are reset when flush() is called.

pub fn reads(&self) -> usize

Returns the total number of reads performed on this cache since the last flush.

pub fn writes(&self) -> usize

Returns the total number of writes performed on this cache since the last flush.