Lib.rs

Cached 是一个由 高性能、LFU 基于内存缓存，受 Ristretto 启发。

API 文档可在 这里 查找。

内容组织

• 特性
• 核心设计理念
• 用法
• 示例
• 测量缓存命中率
• 常见问题解答
• 参考文献

特性

🔹 高缓存命中率：提供高缓存命中率，更多内容请参阅测量缓存命中率部分

🔹 高吞吐量：提供所有读写操作的高吞吐量。结果可在这里找到

🔹 简单的API：提供简洁的API，包括 put、get、multi_get、map_get、delete 和 put_or_update

🔹 多种获取变体：提供 get、map_get、multi_get、multi_get_iterator 和 multi_get_map_iterator

🔹 基于TTL和访问频率的淘汰策略：淘汰策略基于提供的 time_to_live 或键的访问频率

🔹 完全并发：提供对并发put、get、delete和put_or_update的支持

🔹 指标：提供各种指标，如：CacheHits、CacheMisses、KeysAdded、KeysDeleted 等，并将指标作为 StatsSummary 暴露给客户端

🔹 可配置：提供可配置参数，允许客户端选择最适合自己的配置

核心设计理念

1. LFU (最少使用)

CacheD是一个基于LFU的缓存，这使其必须存储每个键的访问频率。在类似于HashMap的数据结构中存储访问频率意味着用于存储频率的空间与缓存中键的数量成正比。因此，权衡方案是使用概率数据结构，例如count-min sketch。Cached在crate::cache::lfu::frequency_counter::FrequencyCounter中使用count-min sketch来存储每个键的频率。

2. 内存限制

CacheD是一个内存限制缓存。它使用Weight作为表示空间的术语。每个键/值对都有一个权重，客户端可以在放置键/值对时提供权重，或者权重是自动计算的。为了创建CacheD的新实例，客户端提供缓存的总权重，这表示为缓存保留的总空间。CacheD确保它永远不会超过缓存的最大权重。

3. 接受/拒绝传入键

当CacheD实例分配的空间已满时，放置新的键/值对将导致AdmissionPolicy决定是否接受传入的键/值对。这个决定基于估计传入键的访问频率，并将其与键样本的估计访问频率进行比较。

4. 细粒度锁

CacheD尽可能使用细粒度锁而不是粗粒度锁。

5. 表达性API

Cached向客户端提供了表达性API。例如，put操作不是即时操作，它将在稍后的某个时间点发生。put操作的返回类型是crate::cache::command::command_executor::CommandSendResult的实例，客户端可以使用它来await直到put操作的状态返回。

同样，put_or_update操作接受一个crate::cache::put_or_update::PutOrUpdateRequest的实例，从而允许客户端非常明确地指定他们想要执行的类型更改。

用法

将此添加到您的Cargo.toml

[dependencies]
tinylfu-cached = "0.0.4"

示例

确定Config参数值，您就可以开始了。

//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));
}

以下代码示例在句柄上使用了一个await。

#[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);
}

以下代码示例没有使用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");
    }
}

测量缓存命中率

使用Zipf分布和rand_distr crate来衡量缓存命中率。每个键和值都是类型u64，系统计算的单个键/值对的权重为40字节。详细信息请查看权重计算。

基准测试使用以下参数运行

/// 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;

缓存命中率基准测试可在此处找到，其结果可在此处找到。

所有基准测试都在macOS Monterey（版本12.6），2.6 GHz 6核Intel Core i7，16 GB 2667 MHz DDR4上运行。

常见问题解答

1. CacheWeight 的含义是什么？

CacheWeight 指的是为缓存保留的总大小。以下是一个示例：

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

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

此示例创建了一个大小为 1024 字节的 Cached 实例。当空间满时，新的键值对的 put 操作将导致 AdmissionPolicy 决定是否接受该键值对。如果新的键值对被接受，则将淘汰一些现有的键值对以创建所需的空间。

2. 我需要指定键值对的权重作为 put 操作的一部分吗？

Cached 提供了 put_with_weight 方法，该方法接受一个键、一个值和权重。如果客户端知道键值对的权重，则可以调用此方法；否则，Cached 会自动确定键值对的权重。有关权重计算逻辑，请参阅 weight_calculation.rs。

3. 客户端能否提供自己的权重计算函数？

是的，客户端可以提供自己的权重计算函数。以下是一个示例代码：

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);

此示例通过提供自定义的 weight_calculation_fn 创建一个 Cached 实例，该函数将每个键值对的权重都返回为 1。

4. get 和 get_ref 方法在 Cached 中的区别是什么？

当值可克隆时，才可用 get 方法，而即使值不可克隆，get_ref 方法也是可用的。 get_ref 返回一个 KeyValueRef 的选项，其生命周期绑定到来自 DashMap 的 RwLockReadGuard 的生命周期。这意味着在使用的范围内，get_ref 将持有对键（或映射桶）的 RwLock，而 get 将返回克隆的值。

如果 T 不可克隆，则客户端可以将 Arc<T> 作为值传递。以下是一个示例：

#[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());

此示例创建了一个值类型为 Arc<Name> 的 Cached 实例。这允许客户端使用 multi_get_iterator 方法。

请参阅 cached.rs 中的测试 get_value_for_an_existing_key_if_value_is_not_cloneable_by_passing_an_arc。

7. 能否只更新键的超时时间或权重？

是的，PutOrUpdateRequest 允许客户端更新键的 value、weight 或 time_to_live。假设键 "topic" 存在于 Cached 实例中，以下是一个示例：

//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. put、put_or_update 和 delete 的返回类型意味着什么？

所有 put、put_or_update 和 delete 操作都实现了 单一更新队列模式，并返回一个 CommandSendResult 实例，允许客户端获取等待的句柄。

CommandSendResult 是 Result<Arc<CommandAcknowledgement>, CommandSendError> 的别名。如果在缓存关闭时执行 put、put_or_update 或 delete 操作，则会导致错误。

CommandSendResult 的成功部分是一个 CommandAcknowledgement 实例，它返回一个句柄供客户端执行 await。

参考文献

• Ristretto
• Tiny-LFU
• BP-Wrapper

标志设计使用 logo.com