Struct CacheD 

pub struct CacheD<Key, Value>
where
    Key: Hash + Eq + Send + Sync + Clone + 'static,
    Value: Send + Sync + 'static,
{ /* private fields */ }

CacheD is a high performance, LFU based in-memory cache. Cached provides various behaviors including: put, put_with_weight, put_with_ttl, get, get_ref, map_get_ref, multi_get, delete, put_or_update.

The core abstractions that CacheD interacts with include:

• crate::cache::store::Store: Store holds the key/value mapping.
• crate::cache::command::command_executor::CommandExecutor: CommandExecutor executes various commands of type crate::cache::command::CommandType. Each write operation results in a command to CommandExecutor.
• crate::cache::policy::admission_policy::AdmissionPolicy: AdmissionPolicy maintains the weight of each key in the cache and takes a decision on whether a key should be admitted.
• crate::cache::expiration::TTLTicker: TTLTicker removes the expired keys.

Core design ideas behind CacheD:

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 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.

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, put 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, 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.

Implementations

impl<Key, Value> CacheD<Key, Value>

where Key: Hash + Eq + Send + Sync + Clone + 'static, Value: Send + Sync + 'static,

pub fn new(config: Config<Key, Value>) -> Self

Creates a new instance of Cached with the provided crate::cache::config::Config

pub fn put(&self, key: Key, value: Value) -> CommandSendResult

Puts the key/value pair in the cacheD instance and returns an instance of crate::cache::command::command_executor::CommandSendResult to the clients.

Weight is calculated by the weight calculation function provided as a part of Config.

crate::cache::command::CommandStatus::Rejected is returned to the clients if the key already exists, since v0.0.3.

put is not an immediate operation. Every invocation of put results in crate::cache::command::CommandType::Put to the CommandExecutor. CommandExecutor in turn delegates to the AdmissionPolicy to perform the put operation. AdmissionPolicy may accept or reject the key/value pair depending on the available cache weight.

Since, put is not an immediate operation, clients can await on the response to get the crate::cache::command::CommandStatus

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
}

pub fn put_with_weight( &self, key: Key, value: Value, weight: Weight, ) -> CommandSendResult

Puts the key/value pair in the cacheD instance and returns an instance of crate::cache::command::command_executor::CommandSendResult to the clients.

Weight is provided by the clients.

crate::cache::command::CommandStatus::Rejected is returned to the clients if the key already exists, since v0.0.3.

put_with_weight is not an immediate operation. Every invocation of put_with_weight results in crate::cache::command::CommandType::Put to the CommandExecutor. CommandExecutor in turn delegates to the AdmissionPolicy to perform the put operation. AdmissionPolicy may accept or reject the key/value pair depending on the available cache weight.

Since, put_with_weight is not an immediate operation, clients can await on the response to get the crate::cache::command::CommandStatus

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put_with_weight("topic", "microservices", 50).unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    assert_eq!(50, cached.total_weight_used());
}

pub fn put_with_ttl( &self, key: Key, value: Value, time_to_live: Duration, ) -> CommandSendResult

Puts the key/value pair with time_to_live in the cacheD instance and returns an instance of crate::cache::command::command_executor::CommandSendResult to the clients.

Weight is calculated by the weight calculation function provided as a part of Config.

crate::cache::command::CommandStatus::Rejected is returned to the clients if the key already exists, since v0.0.3.

put_with_ttl is not an immediate operation. Every invocation of put_with_ttl results in crate::cache::command::CommandType::PutWithTTL to the CommandExecutor. CommandExecutor in turn delegates to the AdmissionPolicy to perform the put operation. AdmissionPolicy may accept or reject the key/value pair depending on the available cache weight.

Since, put_with_ttl is not an immediate operation, clients can await on the response to get the crate::cache::command::CommandStatus

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
use std::time::Duration;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put_with_ttl("topic", "microservices", Duration::from_secs(120)).unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
}

pub fn put_with_weight_and_ttl( &self, key: Key, value: Value, weight: Weight, time_to_live: Duration, ) -> CommandSendResult

Puts the key/value pair with time_to_live in the cacheD instance and returns an instance of crate::cache::command::command_executor::CommandSendResult to the clients.

Weight is provided by the clients.

crate::cache::command::CommandStatus::Rejected is returned to the clients if the key already exists, since v0.0.3.

put_with_weight_and_ttl is not an immediate operation. Every invocation of put_with_weight_and_ttl results in crate::cache::command::CommandType::PutWithTTL to the CommandExecutor. CommandExecutor in turn delegates to the AdmissionPolicy to perform the put operation. AdmissionPolicy may accept or reject the key/value pair depending on the available cache weight.

Since, put_with_weight_and_ttl is not an immediate operation, clients can await on the response to get the crate::cache::command::CommandStatus

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
use std::time::Duration;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put_with_weight_and_ttl("topic", "microservices", 50, Duration::from_secs(120)).unwrap().handle().await;
    assert_eq!(50, cached.total_weight_used());
    assert_eq!(CommandStatus::Accepted, status);
}

pub fn put_or_update( &self, request: PutOrUpdateRequest<Key, Value>, ) -> CommandSendResult

Performs a put if the key does not exist or an update operation, if the key exists. PutOrUpdateRequest is a convenient way to perform put or update operation. put_or_update attempts to perform the update operation on crate::cache::store::Store first. If the update operation is successful then the changes are made to TTLTicker and AdmissionPolicy, if applicable. If the update is not successful then a put operation is performed.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
use tinylfu_cached::cache::put_or_update::PutOrUpdateRequestBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    let _ = cached.put_or_update(PutOrUpdateRequestBuilder::new("topic").value("Cached").build()).unwrap().handle().await;
    let value = cached.get(&"topic");
    assert_eq!(Some("Cached"), value);
}

pub fn delete(&self, key: Key) -> CommandSendResult

Deletes the key/value pair from the instance of CacheD. Delete is a 2 step process:

1. Marks the key as deleted in the crate::cache::store::Store. So, any get operations on the key would return None. This step is immediate.

2. Sends a crate::cache::command::CommandType::Delete to the CommandExecutor which causes the key weight to be removed from AdmissionPolicy. This step may happen at a later point in time.

Since, delete is not an immediate operation, clients can await on the response to get the crate::cache::command::CommandStatus

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    let _ = cached.delete(&"topic").unwrap().handle().await;
    assert_eq!(None, cached.get(&"topic"));
}

pub fn get_ref( &self, key: &Key, ) -> Option<KeyValueRef<'_, Key, StoredValue<Value>>>

Returns an optional reference to the key/value present in the instance of Cached.

The reference is wrapped in crate::cache::store::key_value_ref::KeyValueRef. KeyValueRef contains DashMap’s Ref dashmap::mapref::one::Ref which internally holds a RwLockReadGuard for the shard. Any time get_ref method is invoked, the Store returns Option<KeyValueRef<'_, Key, StoredValue<Value>>>. If the key is present in the Store, get_ref will return Some<KeyValueRef<'_, Key, StoredValue<Value>>>.

Hence, the invocation of get_ref will hold a lock against the shard that contains the key (within the scope of its usage).

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    let value = cached.get_ref(&"topic");
    let value_ref = value.unwrap();
    let stored_value = value_ref.value();
    assert_eq!("microservices", stored_value.value());
}

pub fn map_get_ref<MapFn, MappedValue>( &self, key: &Key, map_fn: MapFn, ) -> Option<MappedValue>

where MapFn: Fn(&StoredValue<Value>) -> MappedValue,

Returns an optional MappedValue for key present in the instance of Cached.

The parameter map_fn is an instance of Fn that takes a reference to crate::cache::store::stored_value::StoredValue and returns any MappedValue. This is an extension to get_ref method. If the key is present in Cached, it returns Some(MappedValue), else returns None.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    let value = cached.map_get_ref(&"topic", |stored_value| stored_value.value_ref().to_uppercase());
    assert_eq!("MICROSERVICES", value.unwrap());
}

pub fn total_weight_used(&self) -> Weight

Returns the total weight used in the cache.

pub fn stats_summary(&self) -> StatsSummary

Returns an instance of crate::cache::stats::StatsSummary.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::config::ConfigBuilder;
use tinylfu_cached::cache::stats::StatsType;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 200).build());
    let _ = cached.put("topic", "microservices").unwrap().handle().await;
    let _ = cached.put("cache", "cached").unwrap().handle().await;
    let _ = cached.get(&"topic");
    let _ = cached.get(&"cache");
    let stats_summary = cached.stats_summary();
    assert_eq!(2, stats_summary.get(&StatsType::CacheHits).unwrap());
}

pub fn shutdown(&self)

Shuts down the cache.

Shutdown involves the following:

1. Marking is_shutting_down to true
2. Sending a crate::cache::command::CommandType::Shutdown to the crate::cache::command::command_executor::CommandExecutor
3. Shutting down crate::cache::expiration::TTLTicker
4. Clearing the data inside crate::cache::store::Store
5. Clearing the data inside crate::cache::policy::admission_policy::AdmissionPolicy
6. Clearing the data inside crate::cache::expiration::TTLTicker

Any attempt to perform an operation after the CacheD instance is shutdown, will result in an error.

However, there is race condition sort of a scenario here. Consider that shutdown() and put() on an instance of Cached are invoked at the same time. Both these operations result in sending different commands to the CommandExecutor. Somehow, the Shutdown command goes in before the put command. This also means that the client could have performed await operation on response from put. It becomes important to finish the future of the put command that has come in at the same time shutdown was invoked.

This is how shutdown in CommandExecutor is handled, it finishes all the futures in the pipeline that are placed after the Shutdown command. All such futures ultimately get crate::cache::command::CommandStatus::ShuttingDown.

impl<Key, Value> CacheD<Key, Value>

where Key: Hash + Eq + Send + Sync + Clone + 'static, Value: Send + Sync + Clone + 'static,

pub fn get(&self, key: &Key) -> Option<Value>

Returns an optional reference to the Value in the instance of Cached.

This method is only available if the Value type is Cloneable. This method clones the value and returns it to the client.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    let value = cached.get(&"topic");
    assert_eq!(Some("microservices"), value);
}

pub fn map_get<MapFn, MappedValue>( &self, key: &Key, map_fn: MapFn, ) -> Option<MappedValue>

where MapFn: Fn(Value) -> MappedValue,

Returns an optional MappedValue for key present in the instance of Cached.

The parameter map_fn is an instance of Fn that takes the cloned Value and returns any MappedValue This is an extension to the get method.

This method is only available if the Value type is Cloneable. If the key is present in Cached, it returns Some(MappedValue), else returns None.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::command::CommandStatus;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    assert_eq!(CommandStatus::Accepted, status);
    let value = cached.map_get(&"topic", |value| value.to_uppercase());
    assert_eq!("MICROSERVICES", value.unwrap());
}

pub fn multi_get<'a>( &self, keys: Vec<&'a Key>, ) -> HashMap<&'a Key, Option<Value>>

Returns values corresponding to multiple keys.

It takes a vector of reference of keys and returns a HashMap containing the key reference and the optional Value. If the value is present for a key, the returned HashMap will contain the key reference and Some(Value). If the value is not present for a key, the returned HashMap will contain the key reference and None as the value.

This method is only available if the Value type is Cloneable.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    let values = cached.multi_get(vec![&"topic", &"non-existing"]);
    assert_eq!(&Some("microservices"), values.get(&"topic").unwrap());
    assert_eq!(&None, values.get(&"non-existing").unwrap());
}

pub fn multi_get_iterator<'a>( &'a self, keys: Vec<&'a Key>, ) -> MultiGetIterator<'a, Key, Value>

Returns an instance of MultiGetIterator that allows iterating over multiple keys and getting the value corresponding to each key.

It takes a vector of reference of keys and an instance of MultiGetIterator

This method is only available if the Value type is Cloneable.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    let mut iterator = cached.multi_get_iterator(vec![&"topic", &"non-existing"]);
    assert_eq!(Some("microservices"), iterator.next().unwrap());
    assert_eq!(None, iterator.next().unwrap());
    assert_eq!(None, iterator.next());
}

pub fn multi_get_map_iterator<'a, MapFn, MappedValue>( &'a self, keys: Vec<&'a Key>, map_fn: MapFn, ) -> MultiGetMapIterator<'a, Key, Value, MapFn, MappedValue>

where MapFn: Fn(Value) -> MappedValue,

Returns an instance of MultiGetMapIterator that allows iterating over multiple keys, performing a map operation over each key and then getting the value corresponding to each key.

It takes a vector of reference of keys and an instance of MultiGetIterator.

This method is only available if the Value type is Cloneable.

use tinylfu_cached::cache::cached::CacheD;
use tinylfu_cached::cache::config::ConfigBuilder;
#[tokio::main]
 async fn main() {
    let cached = CacheD::new(ConfigBuilder::new(100, 10, 100).build());
    let status = cached.put("topic", "microservices").unwrap().handle().await;
    let mut iterator = cached.multi_get_map_iterator(vec![&"topic", &"non-existing"], |value| value.to_uppercase());
    assert_eq!(Some("MICROSERVICES".to_string()), iterator.next().unwrap());
    assert_eq!(None, iterator.next().unwrap());
    assert_eq!(None, iterator.next());
}