Stretto 是 https://github.com/dgraph-io/ristretto 的纯 Rust 实现。

A high performance thread-safe memory-bound Rust cache.

英文 | 简体中文

功能

• 内部可变性 - 不需要使用 Arc<RwLock<Cache<...>> 进行并发代码，你只需要 Cache<...> 或 AsyncCache<...>
• 同步和异步 - Stretto 支持同步和运行时无关的异步。
  • 在同步中，Cache 启动两个额外的操作系统级别线程。一个是策略线程，另一个是写入线程。
  • 在异步中，AsyncCache 启动两个额外的绿色线程。一个是策略线程，另一个是写入线程。
• 存储策略 Stretto 只存储值，这意味着缓存不存储键。
• 高命中率 - 使用 Dgraph 开发者的独特准入/驱逐策略配对，Ristretto 的性能在同类中最佳。
  • 驱逐：SampledLFU - 与精确 LRU 相当，在搜索和数据库跟踪上性能更优。
  • 准入：TinyLFU - 以较小的内存开销（每个计数器 12 位）获得额外的性能。
• 高吞吐量 - 使用各种技术来管理竞争，结果是卓越的吞吐量。
• 基于成本的驱逐 - 任何被认为有价值的大型新项目都可以驱逐多个较小的项目（成本可以是任何东西）。
• 完全并发 - 你可以使用任意多的线程，吞吐量下降很小。
• 指标 - 可选的性能指标，包括吞吐量、命中率和其他统计数据。
• 简单的 API - 只需确定你的理想 CacheBuilder/AsyncCacheBuilder 值，然后你就可以开始运行。

目录

• 功能
• 目录
• 安装
• 相关
• 使用
  • 示例
    • 同步
    • 异步
  • 配置
    • 计数器数量
    • 最大成本
    • 键构建器
    • 缓冲区大小
    • 度量
    • 忽略内部成本
    • 清理持续时间
    • 更新验证器
    • 回调
    • 成本计算器
    • 哈希器
• 致谢
• 许可证

安装

• 使用缓存。

[dependencies]
stretto = "0.8"

或者

[dependencies]
stretto = { version = "0.8", features = ["sync"] }

• 使用AsyncCache

[dependencies]
stretto = { version = "0.8", features = ["async"] }

• 同时使用Cache和AsyncCache

[dependencies]
stretto = { version = "0.8", features = ["full"] }

相关

如果您想查看一些基本的缓存实现（no_std），请参阅 https://crates.io/crates/caches。

使用

示例

同步

use std::time::Duration;
use stretto::Cache;

fn main() {
    let c = Cache::new(12960, 1e6 as i64).unwrap();

    // set a value with a cost of 1
    c.insert("a", "a", 1);
    // set a value with a cost of 1 and ttl
    c.insert_with_ttl("b", "b", 1, Duration::from_secs(3));

    // wait for value to pass through buffers
    c.wait().unwrap();

    // when we get the value, we will get a ValueRef, which contains a RwLockReadGuard
    // so when we finish use this value, we must release the ValueRef
    let v = c.get(&"a").unwrap();
    assert_eq!(v.value(), &"a");
    v.release();

    // lock will be auto released when out of scope
    {
        // when we get the value, we will get a ValueRef, which contains a RwLockWriteGuard
        // so when we finish use this value, we must release the ValueRefMut
        let mut v = c.get_mut(&"a").unwrap();
        v.write("aa");
        assert_eq!(v.value(), &"aa");
        // release the value
    }

    // if you just want to do one operation
    let v = c.get_mut(&"a").unwrap();
    v.write_once("aaa");

    let v = c.get(&"a").unwrap();
    assert_eq!(v.value(), &"aaa");
    v.release();

    // clear the cache
    c.clear().unwrap();
    // wait all the operations are finished
    c.wait().unwrap();
    assert!(c.get(&"a").is_none());
}

异步

Stretto支持运行时无关的AsyncCache，您需要在构建AsyncCache时传递一个spawner。

use std::time::Duration;
use stretto::AsyncCache;

#[tokio::main]
async fn main() {
    // In this example, we use tokio runtime, so we pass tokio::spawn when constructing AsyncCache
    let c: AsyncCache<&str, &str> = AsyncCache::new(12960, 1e6 as i64, tokio::spawn).unwrap();

    // set a value with a cost of 1
    c.insert("a", "a", 1).await;

    // set a value with a cost of 1 and ttl
    c.insert_with_ttl("b", "b", 1, Duration::from_secs(3)).await;

    // wait for value to pass through buffers
    c.wait().await.unwrap();

    // when we get the value, we will get a ValueRef, which contains a RwLockReadGuard
    // so when we finish use this value, we must release the ValueRef
    let v = c.get(&"a").unwrap();
    assert_eq!(v.value(), &"a");
    // release the value
    v.release(); // or drop(v)

    // lock will be auto released when out of scope
    {
        // when we get the value, we will get a ValueRef, which contains a RwLockWriteGuard
        // so when we finish use this value, we must release the ValueRefMut
        let mut v = c.get_mut(&"a").unwrap();
        v.write("aa");
        assert_eq!(v.value(), &"aa");
        // release the value
    }

    // if you just want to do one operation
    let v = c.get_mut(&"a").unwrap();
    v.write_once("aaa");

    let v = c.get(&"a").unwrap();
    println!("{}", v);
    assert_eq!(v.value(), &"aaa");
    v.release();

    // clear the cache
    c.clear().await.unwrap();
    // wait all the operations are finished
    c.wait().await.unwrap();

    assert!(c.get(&"a").is_none());
}

配置

当您想要自定义缓存设置时，将使用CacheBuilder结构体来创建Cache实例。

计数器数量

num_counters是用于进入和驱逐的4位访问计数器的数量。Dgraph的开发者发现，当缓存满载时，将此设置为预期保留项目数的10倍时，性能良好。

例如，如果您预计每个项目的成本为1，且max_cost为100，则将num_counters设置为1,000。或者，如果您使用可变成本值，但预计缓存满载时保留约10,000个项目，则将num_counters设置为100,000。重要的是满载缓存中的唯一项目数量，而不一定是max_cost值。

最大成本

max_cost用于确定驱逐决策。例如，如果最大成本为100，则新项目成本为1并使总缓存成本增加到101时，将驱逐1个项目。

max_cost也可以用来表示最大字节数。例如，如果最大成本为1,000,000（1MB）且缓存已满载1,000个1KB项目，则新项目（被接受）会导致5个1KB项目被驱逐。

max_cost可以是任何值，只要它与调用insert时使用的成本值匹配即可。

键构建器

pub trait KeyBuilder {
    type Key: Hash + Eq + ?Sized;

    /// hash_index is used to hash the key to u64
    fn hash_index<Q>(&self, key: &Q) -> u64
        where 
            Self::Key: core::borrow::Borrow<Q>,
            Q: Hash + Eq + ?Sized;

    /// if you want a 128bit hashes, you should implement this method,
    /// or leave this method return 0
    fn hash_conflict<Q>(&self, key: &Q) -> u64
        where 
            Self::Key: core::borrow::Borrow<Q>,
            Q: Hash + Eq + ?Sized;
    { 0 }

    /// build the key to 128bit hashes.
    fn build_key<Q>(&self, k: &Q) -> (u64, u64) 
        where 
            Self::Key: core::borrow::Borrow<Q>,
            Q: Hash + Eq + ?Sized;
    {
        (self.hash_index(k), self.hash_conflict(k))
    }
}

KeyBuilder是用于每个键的哈希算法。在Stretto中，缓存永远不会存储真实键。键将通过KeyBuilder进行处理。Stretto有两个默认内置键构建器，一个是TransparentKeyBuilder，另一个是DefaultKeyBuilder。如果您的键实现了TransparentKey特质，则可以使用TransparentKeyBuilder，这比DefaultKeyBuilder更快。否则，您应该使用DefaultKeyBuilder。您还可以通过实现KeyBuilder特质为Cache编写自己的键构建器。

请注意，如果您想要128位哈希，应使用完整的(u64, u64)，否则只需在u64的位置填充，它将表现得像任何64位哈希。

pub trait UpdateValidator: Send + Sync + 'static {
    type Value: Send + Sync + 'static;

    /// should_update is called when a value already exists in cache and is being updated.
    fn should_update(&self, prev: &Self::Value, curr: &Self::Value) -> bool;
}

pub trait CacheCallback: Send + Sync + 'static {
    type Value: Send + Sync + 'static;

    /// on_exit is called whenever a value is removed from cache. This can be
    /// used to do manual memory deallocation. Would also be called on eviction
    /// and rejection of the value.
    fn on_exit(&self, val: Option<Self::Value>);

    /// on_evict is called for every eviction and passes the hashed key, value,
    /// and cost to the function.
    fn on_evict(&self, item: Item<Self::Value>) {
        self.on_exit(item.val)
    }

    /// on_reject is called for every rejection done via the policy.
    fn on_reject(&self, item: Item<Self::Value>) {
        self.on_exit(item.val)
    }
}

pub trait Coster: Send + Sync + 'static {
    type Value: Send + Sync + 'static;

    /// cost evaluates a value and outputs a corresponding cost. This function
    /// is ran after insert is called for a new item or an item update with a cost
    /// param of 0.
    fn cost(&self, val: &Self::Value) -> i64;
}