CacheD is a high performance, LFU based in-memory cache in Rust inspired by Ristretto.
The API documentation is available here.
Read the blog on Designing an in-memory LFU cache.
๐น 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
- 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.
- 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.
- 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 AdmissionPolicy
deciding 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.
- Fine-grained locks
CacheD makes an attempt to used fine-grained locks over coarse grained locks wherever possible.
- 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.
Add this to your Cargo.toml
:
[dependencies]
tinylfu-cached = "0.0.4"
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");
}
}
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.
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 (denoted by CAPA)
const ITEMS: usize = CAPACITY * 16;
Weight | Zipf exponent | Cache-hit ratio |
---|---|---|
100_000 * 40 | 0.9 | ~57.47% |
100_000 * 40 | 1.001 | ~73.41% |
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.
- 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.
- 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.
- 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.
- What is the difference between
get
andget_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.
- 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
.
- 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.
- 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();
- What does the return type of
put
,put_or_update
anddelete
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
.
The logo is built using logo.com