stretto

Stretto is a high-performance, thread-safe, memory-bound Rust cache. It is a pure Rust implementation of the Ristretto cache.

Key features include:

• Internal Mutability: You can use Cache<...> or AsyncCache<...> directly in concurrent code without needing to wrap them in Arc<RwLock<...>>.
• Sync and Async Support: Supports both synchronous and runtime-agnostic asynchronous usage.
• High Hit Ratios: Uses a combination of TinyLFU for admission and SampledLFU for eviction to achieve best-in-class performance.
• Cost-Based Eviction: Allows for eviction based on arbitrary costs, enabling large items to evict multiple smaller items.
• Fully Concurrent: Designed for high throughput with minimal contention across many threads.
• Store Policy: Stretto stores only the value, not the key.
• Metrics: Provides optional performance metrics for throughput, hit ratios, and other statistics.

To reproduce the benchmark results shown in the documentation, you can use the cachebench repository. This requires cloning the repo recursively and running the benchmark command with the appropriate features enabled.

Prerequisites:

• git (with recursive support)
• zstd for decompressing trace files
• cargo (Rust toolchain)

Steps:

1. Clone the repository: git clone --recursive https://github.com/al8n/cachebench.git
2. Decompress the traces: cd cachebench/cache-trace/arc && for f in *.lis.zst; do zstd -d "$f"; done && cd ../..
3. Run the benchmark command provided below.

git clone --recursive https://github.com/al8n/cachebench.git
cd cachebench/cache-trace/arc && for f in *.lis.zst; do zstd -d "$f"; done && cd ../..
cargo run --release --features "stretto,quick_cache,tiny-ufo,moka-v012" -- \
    -f oltp,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,s1,s2,s3,ds1,concat,merge-p,merge-s -n 16

Use the CacheBuilder struct to customize cache settings when creating a new Cache instance. Key configuration options include:

• num_counters: Number of 4-bit access counters for admission/eviction. A good rule of thumb is 10x the expected number of items in a full cache.
• max_cost: Defines the eviction threshold. Can represent a count of items or a byte budget.
• ignore_internal_cost: If true (default), max_cost tracks only user-supplied costs. If false, it accounts for ~56 bytes of per-entry bookkeeping (key, conflict, version, etc.).
• metrics: Enable for real-time stats (note: carries a ~10% throughput overhead).
• cleanup_duration: Frequency of expired value cleanup (default is 500ms).
• buffer_size: Controlled via set_insert_stripe_high_water(items). Tuning this affects how many items are batched before being sent to the policy processor. Values between 64–256 are recommended for caches under 10K capacity.

Stretto does not store the actual key; it uses a KeyBuilder to process keys into hashes.

• TransparentKeyBuilder: Use this if your key implements the TransparentKey trait (faster).
• DefaultKeyBuilder: Use this for all other keys.
• Custom Implementation: Implement the KeyBuilder trait to define your own hashing logic. If you want 128-bit hashes, implement hash_conflict and use the full (u64, u64) return from build_key. Otherwise, return 0 for hash_conflict to behave like a 64-bit hash.

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

Use CacheCallback to perform custom operations when cache events occur. This is useful for manual memory deallocation or logging.

• on_exit: Called whenever a value is removed (eviction, rejection, or manual removal).
• on_evict: Called specifically for evictions; passes the Item<Self::Value>.
• on_reject: Called when the policy rejects an insertion.

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

    /// on_exit is called whenever a value is removed from cache.
    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)
    }
}