parcio / lfu-cache

A Rust implementation of a constant time LFU cache

lfu-cache

An implementation of a constant time Least Frequently Used (LFU) cache roughly based on the paper by Shah, Mitra, and Matani.

Example

use lfu_cache::LfuCache;
let mut cache = LfuCache::with_capacity(2);

// Fill up the cache.
cache.insert("foo", 3);
cache.insert("bar", 4);

// Insert returns the evicted value, if a value was evicted, in case additional
// bookkeeping is necessary for the value to be dropped.
let maybe_evicted = cache.insert("baz", 5);

// In the case of a tie, the most recently added value is evicted.
assert!(cache.get(&"bar").is_none());
assert_eq!(maybe_evicted, Some(4));

cache.get(&"baz");
// Otherwise, the least frequently value is evicted.
assert_eq!(cache.pop_lfu(), Some(3));

Reasons to use this implementation

• Zero dependencies.
• Small dependency, only providing the necessary features.
• Fully documented and fully tested (including miri).
• Respects Rust API guidelines: interface is implements most container APIs where possible.
• Performant: Hits around 10 million insertions per section (using i32 as elements; see benches.rs for bench implementation).

Reasons not to use this implementation

• Internally, this codebase uses unsafe as it works with raw pointers.
• This can be considered a microcrate, which may be undesired if dependency count is a concern.

Alternatives

• Consider the lfu crate for an implementation written in only safe Rust.
• Consider matthusifer/lfu_rs for another implementation of the same paper.

Deviances from the paper

This implementation very closely follows the paper, but has one modification to ensure correctness. Each node in the node list contains a Rc containing the key it was stored under, and the lookup table instead is indexed on a Rc<Key> instead. This is to ensure that the correct key-value in the lookup table can be evicted when popping the least frequently used item.

This modification was necessary as the hash is surjective, and so each item necessarily needs to contain some reference to the original key it was stored under to ensure that we evict the correct key during hash collisions.

An alternative solution would be to use an monotonically increasing counter, but the additional bookkeeping over an Rc which functionally provides the same benefit is unnecessary.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.