tinylfu-cached

Cached is a high performance, LFU based in-memory cache in Rust inspired by Ristretto.

The API documentation is available here.

Content organization

• Features
• Core design ideas
• Usage
• Examples
• Measuring cache-hit ratio
• FAQs
• References

Features

🔹 High Cache-hit ratio: Provides high-cache ratio, more on this in the measuring-cache-hit-ratio section

🔹 High throughput: Provides high throughput for all read and write operations. The results are available here

🔹 Simple API: Provides clean and simple APIs for put, get, multi_get, map_get, delete and put_or_update

🔹 Multiple get variants: Provides get, map_get, multi_get, multi_get_iterator and multi_get_map_iterator

🔹 TTL and Access frequency based eviction: Eviction is based either on time_to_live if provided or the access frequency of the keys

🔹 Fully concurrent: Provides support for concurrent puts, gets, deletes and put_or_updates

🔹 Metrics: Provides various metrics like: CacheHits, CacheMisses, KeysAdded, KeysDeleted etc., and exposes the metrics as StatsSummary to the clients

🔹 Configurable: Provides configurable parameters to allow the clients to choose what works best for them

Core design ideas

1. LFU (least frequently used)

CacheD is an LFU based cache which makes it essential to store the access frequency of each key. Storing the access frequency in a HashMap like data structure would mean that the space used to store the frequency is directly proportional to the number of keys in the cache So, the tradeoff is to use a probabilistic data structure like count-min sketch. Cached uses count-min sketch inside crate::cache::lfu::frequency_counter::FrequencyCounter to store the frequency for each key.

2. Memory bound

CacheD is a memory bound cache. It uses Weight as the terminology to denote the space. Every key/value pair has a weight, either the clients can provide weight while putting a key/value pair or the weight is auto-calculated. In order to create a new instance of CacheD, clients provide the total weight of the cache, which signifies the total space reserved for the cache. CacheD ensure that it never crosses the maximum weight of the cache.

3. Admission/Rejection of incoming keys

After the space allocated to the instance of CacheD is full, put of a new key/value pair will result in AdmissionPolicydeciding whether the incoming key/value pair should be accepted. This decision is based on estimating the access frequency of the incoming key and comparing it against the estimated access frequencies of a sample of keys.

4. Fine-grained locks

CacheD makes an attempt to used fine-grained locks over coarse grained locks wherever possible.

5. Expressive APIs

Cached provides expressive APIs to the clients. For example, the put operation is not an immediate operation, it happens at a later point in time. The return type of put operation is an instance of crate::cache::command::command_executor::CommandSendResult and clients can use it to await until the status of the put operation is returned.

Similarly, the put_or_update operation takes an instance of crate::cache::put_or_update::PutOrUpdateRequest, thereby allowing the clients to be very explicit in the type of change they want to perform.

Usage

Add this to your Cargo.toml:

[dependencies]
tinylfu-cached = "0.0.4"

Examples

Identify the Config parameter values and you are good to go.

//Total counters in count-min sketch based frequency counter
const COUNTERS: TotalCounters = 100;
//Total capacity of the cache, used as the capacity parameter in DashMap
//It defines the number of items that the cache may store
const CAPACITY: TotalCapacity = 10;
//Total weight of the cache that determines the total cache size (in bytes)
const CACHE_WEIGHT: Weight    = 100;

#[tokio::test]
async fn put_a_key_value() {
    let cached = CacheD::new(ConfigBuilder::new(COUNTERS, CAPACITY, CACHE_WEIGHT).build());
    let acknowledgement =
            cached.put("topic", "LFU cache").unwrap();
     
     let status = acknowledgement.handle().await;
     assert_eq!(CommandStatus::Accepted, status);
    
     let value = cached.get(&"topic");
     assert_eq!(Some("LFU cache"), value);
}

#[tokio::test]
async fn get_value_for_an_existing_key_and_map_it() {
    let cached = CacheD::new(ConfigBuilder::new(COUNTERS, CAPACITY, CACHE_WEIGHT).build());

    let acknowledgement =
        cached.put_with_weight("topic", "LFU cache", 20).unwrap();
    let _ = acknowledgement.handle().await;

    let value = cached.map_get(&"topic", |value| value.to_uppercase());
    assert_eq!("LFU CACHE", value.unwrap());
}

#[tokio::test]
async fn update_the_weight_of_an_existing_key() {
    let cached = CacheD::new(ConfigBuilder::new(COUNTERS, CAPACITY, CACHE_WEIGHT).build());

    let acknowledgement =
        cached.put("topic", "LFU cache").unwrap();
    let _ = acknowledgement.handle().await;

    let acknowledgement =
        cached.put_or_update(PutOrUpdateRequestBuilder::new("topic").weight(29).build()).unwrap();
    let _ = acknowledgement.handle().await;

    let value = cached.get_ref(&"topic");
    let value_ref = value.unwrap();
    let stored_value = value_ref.value();
    let key_id = stored_value.key_id();

    assert_eq!("LFU cache", stored_value.value());
    assert_eq!(Some(29), cached.admission_policy.weight_of(&key_id));
}

The following code shows an example with an await on the handle.

#[tokio::main]
async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 100, 1000).build());

    let acknowledgement =
        cached.put("topic", "cache").unwrap();
    
    let status = acknowledgement.handle().await;
    assert_eq!(CommandStatus::Accepted, status);

    let value = cached.get(&"topic").unwrap();
    assert_eq!("cache", value);
}

The following code shows an example without an await.

fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 100, 1000).build());

    let _ = cached.put("topic", "microservices").unwrap();

    let value = cached.get(&"topic");
    if let Some(value) = value {
        assert_eq!("microservices", value);
    } else {
        println!("Key/value pair is not yet added");
    }
}

Measuring cache-hit ratio

Cache-hit ratio is measured with Zipf distribution using rand_distr crate. Each key and value is of type u64, and the system calculated weight of a single key/value pair is 40 bytes. Check Weight calculation for more details.

The benchmark runs with the following parameters:

/// Defines the total number of key/value pairs that may be loaded in the cache
const CAPACITY: usize = 100_000;

/// Defines the total number of counters used to measure the access frequency.
const COUNTERS: TotalCounters = (CAPACITY * 10) as TotalCounters;

/// Defines the total size of the cache.
/// It is kept to CAPACITY * 40 because the benchmark inserts keys and values of type u64.
/// Weight of a single u64 key and u64 value without time_to_live is 40 bytes. Check `src/cache/config/weight_calculation.rs`
/// As a part of this benchmark, we preload the cache with the total number of elements = CAPACITY.
/// We want all the elements to be admitted in the cache, hence weight = CAPACITY * 40 bytes.
const WEIGHT: Weight = (CAPACITY * 40) as Weight;

/// Defines the total sample size that is used for generating Zipf distribution.
/// Here, ITEMS is 16 times the CAPACITY to provide a larger sample for Zipf distribution.
/// W/C = 16, W denotes the sample size, and C is the cache size 
const ITEMS: usize = CAPACITY * 16;

Benchmark for Cache-hit is available here and its result is available here.

All the benchmarks are run on macOS Monterey (Version 12.6), 2.6 GHz 6-Core Intel Core i7, 16 GB 2667 MHz DDR4.

FAQs

1. What is the meaning of CacheWeight?

CacheWeight refers to the total size reserved for the cache. Let's take the following example:

const COUNTERS: TotalCounters = 100;
const CAPACITY: TotalCapacity = 10;
const CACHE_WEIGHT: Weight    = 1024;

let cached = CacheD::new(ConfigBuilder::new(COUNTERS, CAPACITY, CACHE_WEIGHT).build());

This example creates an instance of Cached with a total size of 1024 bytes. After the space is full, put of a new key/value pair will result in AdmissionPolicy deciding whether the incoming key/value pair should be accepted. If the new key/value pair gets accepted, some existing key/value pairs are evicted to create the required space.

2. Do I need to specify the weight of the key/value pair as a part of the put operation?

Cached provides put_with_weight method that takes a key, a value and the weight. Clients can invoke this method if the weight of the key/value pair is known; otherwise, Cached automatically determines the weight of the key/value pair. Refer to weight_calculation.rs to understand the weight calculation logic.

3. Is it possible for the clients to provide their own weight calculation function?

Yes, clients can provide their own weight calculation function. Let's look at the following code:

const COUNTERS: TotalCounters = 100;
const CAPACITY: TotalCapacity = 10;
const CACHE_WEIGHT: Weight    = 1024;

let weight_calculation: Box<WeightCalculationFn<&str, &str>> 
            = Box::new(|_key, _value, _is_time_to_live_specified| 1);
let config 
            = ConfigBuilder::new(COUNTERS, CAPACITY, CACHE_WEIGHT)
                           .weight_calculation_fn(weight_calculation).build();

let cached = CacheD::new(config);

This example creates an instance of Cached by providing a custom weight_calculation_fn that returns 1 as the weight of every key/value pair.

4. What is the difference between get and get_ref methods of Cached?

The method get is available only if the value is cloneable, whereas the method get_ref is available even if the value is not cloneable. get_ref returns an option of KeyValueRef whose lifetime is bound to the lifetime of RwLockReadGuard<'a, HashMap<K, V, S>> from DashMap. This means get_ref will hold a RwLock against the key (or the map bucket) within the scope of its usage, whereas get will return the cloned value.

5. Does Cached provide a feature to get the values corresponding to multiple keys?

Yes, Cached provides multi_get, multi_get_iterator and multi_get_map_iterator methods if the Value type is Cloneable.

6. I can't clone the value, however I need multi_get_iterator. Is there an option?

Clients can pass Arc<T> as the value if T is not cloneable. Let's take the following example:

#[tokio::test]
#[derive(Eq, PartialEq, Debug)]
struct Name {
    first: String,
    last: String,
}

let cached: CacheD<&str, Arc<Name>> = CacheD::new(ConfigBuilder::new(100, 10, 1000).build());

let acknowledgement =
    cached.put("captain", 
               Arc::new(Name { 
                            first: "John".to_string(), last: "Mcnamara".to_string() 
                        })).unwrap();
let _ = acknowledgement.handle().await;

let acknowledgement =
    cached.put("vice-captain", 
               Arc::new(Name { 
                            first: "Martin".to_string(), last: "Trolley".to_string() 
                        })).unwrap();
let _ = acknowledgement.handle().await;

let mut iterator = cached.multi_get_iterator(vec![&"captain", &"vice-captain", &"disk"]);

assert_eq!("John", iterator.next().unwrap().unwrap().first);
assert_eq!("Martin", iterator.next().unwrap().unwrap().first);
assert_eq!(None, iterator.next().unwrap());

The example creates an instance of Cached where the value type is Arc<Name>. This allows the clients to use multi_get_iterator method.

Refer to the test get_value_for_an_existing_key_if_value_is_not_cloneable_by_passing_an_arc in cached.rs.

7. Is it possible to update just the time to live or the weight of a key?

Yes, PutOrUpdateRequest allows the clients to update the value, weight or time_to_live for a key. Let's assume that the key "topic" exists in an instance of Cached and consider the following example:

//updates the weight of the key
cached.put_or_update(
  PutOrUpdateRequestBuilder::new("topic").weight(29).build()).unwrap();

//updates the value of the key
cached.put_or_update(
    PutOrUpdateRequestBuilder::new("topic").value("microservices").build()).unwrap();

//updates the time to live of the key
cached.put_or_update(
  PutOrUpdateRequestBuilder::new("topic").time_to_live(Duration::from_secs(100)).build()).unwrap();

//removes the time to live of the key
cached.put_or_update(
  PutOrUpdateRequestBuilder::new("topic").remove_time_to_live().build()).unwrap();

//updates the value and time to live of the key
cached.put_or_update(
  PutOrUpdateRequestBuilder::new("topic").value("microservices").time_to_live(Duration::from_secs(10)).build()).unwrap(); 

8. What does the return type of put, put_or_update and delete signify?

All of the put, put_or_update and delete operations implement singular update queue pattern and return an instance of CommandSendResult that allows the clients to get a handle on which they can await.

CommandSendResult is an alias for Result<Arc<CommandAcknowledgement>, CommandSendError>. It will result in an error if either of put, put_or_update or delete operations are performed when the cache is being shut down.

The success part of CommandSendResult is an instance of CommandAcknowledgement, which returns a handle to the clients to perform await.

References

• Ristretto
• Tiny-LFU
• BP-Wrapper

The logo is built using logo.com