Crate caches

source ·

Expand description

Caches

This is a Rust implementation for popular caches (support no_std).

See Introduction, Installation and Usages for more details.

Introduction

The MSRV for this crate is 1.55.0.

LRU
LRUCache, SegmentedCache, TwoQueueCache and AdaptiveCache.
LFU
TinyLFU, SampledLFU, and WTinyLFUCache

Installation

std

[dependencies]
caches = "0.2.0"

no_std

[dependencies]
caches = {version: "0.2.0", features: ["core"]}

Roadmap

0.2: Support TinyLFU, SampledLFU, WTinyLFUCache
0.3: Support LIRS, DLIRS, DSLRU
0.4: Add ttl feature to support

If you want a high-performance thread-safe modern cache, please see https://crates.io/crates/stretto

Acknowledgments

The implementation of RawLRU is highly inspired by Jerome Froelich’s LRU implementation and std::collections library of Rust.
Thanks for HashiCorp’s golang-lru providing the amazing Go implementation.
Ramakrishna’s paper: Caching strategies to improve disk system performance
The implementation of TinyLFU and SampledLFU are inspired by Dgraph’s ristretto and dgryski’s go-tinylfu.
Gil Einziger’s paper: TinyLFU: A Highly Efficient Cache Admission Policy

Modules

lfu

LFU based caches implementation.

lru

LRU based caches implementation.

AdaptiveCache is a fixed size Adaptive Replacement Cache (ARC). ARC is an enhancement over the standard LRU cache in that tracks both frequency and recency of use. This avoids a burst in access to new entries from evicting the frequently used older entries. It adds some additional tracking overhead to a RawLRU cache with default evict callback policy, computationally it is roughly 2x the cost, and the extra memory overhead is linear with the size of the cache. ARC has been patented by IBM, but is similar to the TwoQueueCache (2Q) which requires setting parameters.

AdaptiveCacheBuilder

AdaptiveCacheBuilder is used to help build a AdaptiveCache with custom configuration.

DefaultEvictCallback

DefaultEvictCallback is a noop evict callback.

RawLRU

A fixed size RawLRU Cache

SegmentedCache

SegmentedCache is a fixed size Segmented LRU Cache.

SegmentedCacheBuilder

SegmentedCacheBuilder is used to help build a SegmentedCache with custom configurations.

TwoQueueCache

TwoQueueCache is a fixed size 2Q cache. 2Q is an enhancement over the standard LRU cache in that it tracks both frequently and recently used entries separately. This avoids a burst in access to new entries from evicting frequently used entries. It adds some additional tracking overhead to the RawLRU cache, and is computationally about 2x the cost, and adds some metadata over head. The AdaptiveCache is similar to the TwoQueueCache, but does not require setting any parameters.

TwoQueueCacheBuilder

TwoQueueCacheBuilder is used to help build a TwoQueueCache with custom configuration.

WTinyLFUCache

WTinyLFUCache implements the W-TinyLFU, based on the paper TinyLFU: A Highly Efficient Cache Admission Policy

WTinyLFUCacheBuilder

WTinyLFUCacheBuilder is used to help build a TinyLFUCache with custom configurations.