Ristretto

Ristretto is a Go cache library built by the Dgraph team to give Badger and Dgraph a contention-free, high-throughput caching layer. It pairs a TinyLFU admission policy with SampledLFU eviction so that only genuinely valuable items get in, and the items most likely to be reused stay resident, producing hit ratios competitive with exact LRU on real-world traces without the cost of an exact algorithm.

Unlike a naive mutex-guarded map, Ristretto is engineered for concurrency from the ground up: Get calls are buffered through a lock-free ring buffer, Set calls pass through a channel-backed buffer so bursts of writes can be dropped under contention rather than stalling callers, and the underlying storage is sharded across 256 locked maps to spread lock contention. The result is a cache that scales cleanly across many goroutines with little throughput degradation.

It exposes a small, generic API (Cache[K, V]) with cost-based eviction, meaning any item can be assigned an arbitrary “cost” — bytes, weight, or anything else — so a single large valuable item can evict several smaller ones. Optional TTL support, an onEvict/onReject callback hook, and built-in throughput/hit-ratio metrics round out the feature set, all configured through a single Config struct.

What You Get

• A generic Cache[K, V] type with a Config struct for tuning counters, max cost, and buffer sizes
• TinyLFU-based admission control that filters out low-value Set calls before they consume cache space
• SampledLFU eviction that samples candidate keys instead of scanning the whole cache, keeping eviction cheap
• Cost-based accounting so items can represent memory bytes, weight, or any arbitrary unit for capacity decisions
• Optional per-item TTL with a background cleanup goroutine that expires stale entries
• Built-in Metrics for hits, misses, keys added/evicted, cost added/evicted, and buffer drop rates

Common Use Cases

• Adding an in-process read cache in front of a database or key-value store to cut latency and load
• Caching computed or serialized values behind a Badger/Dgraph-style storage engine
• Rate-sensitive services that need a bounded-memory cache under many concurrent goroutines without lock contention
• Replacing a homegrown LRU map with a library that offers cost-aware, TinyLFU-informed eviction decisions
• Embedding a fast local cache in CLI tools or services where an external cache like Redis is unnecessary

Under The Hood

Architecture Ristretto layers three cooperating subsystems behind the public Cache[K, V] type in cache.go: a sharded concurrent store (store.go) holding the actual key/value data across 256 locked maps plus a shared expiration map for TTL entries, a defaultPolicy (policy.go) that decides admission/eviction using a tinyLFU admission filter and sampledLFU eviction tracker, and a lock-free ringBuffer (ring.go) that batches Get-access notifications before forwarding them to the policy’s processItems goroutine over a buffered channel. Writes go through a separate setBuf channel processed asynchronously so bursts of Sets can be intentionally dropped under contention rather than blocking callers — a deliberate eventual-consistency tradeoff the README documents explicitly. This separation (storage vs. policy vs. access-tracking) means the eviction algorithm can evolve without touching the concurrent map implementation, and a caller that changes the store implementation wouldn’t need to touch policy logic at all.

Tech Stack Ristretto v2 targets Go 1.24+ (toolchain 1.25) and depends on a small, deliberately minimal set of packages: cespare/xxhash/v2 for fast key hashing, dgryski/go-farm as an alternative hash source, dustin/go-humanize for human-readable metric formatting, and stretchr/testify for assertions in tests. A companion z package ships its own low-level utilities — a custom Allocator that amortizes small allocations via z.Calloc, platform-specific mmap/calloc files for jemalloc and non-jemalloc builds, a bloom filter (bbloom.go), and a B-tree — reflecting the library’s systems-level focus on avoiding GC pressure in hot paths. There is no external runtime dependency beyond the Go standard library’s sync, sync/atomic, and time packages for the core cache logic.

Code Quality The project has extensive test coverage: cache_test.go, policy_test.go, store_test.go, sketch_test.go, ring_test.go, ttl_test.go, and stress_test.go exercise the public API, internal policy decisions, and concurrent stress scenarios, with the z subpackage carrying its own parallel test files for the allocator, bloom filter, and B-tree. Error handling favors explicit return values ((V, bool) for lookups, (*Item[V], bool) for policy decisions) over panics except for a few documented invariant violations (e.g. a cost larger than MaxCost). Two GitHub Actions workflows run CI for both the core library and downstream Dgraph-facing tests, and comments are dense throughout Config and public types, explaining tuning tradeoffs rather than restating the obvious.

What Makes It Unique Ristretto’s differentiator is combining a TinyLFU admission filter with SampledLFU eviction rather than a plain LRU or pure LFU — admission decides whether a new item is even worth the cost of displacing something else, which is what lets it match exact-LRU-class hit ratios while staying cheap to run under contention. Pairing that with buffered, batchable Get/Set paths and a custom low-level allocator (avoiding per-item GC overhead) is a level of systems engineering uncommon in general-purpose Go caching libraries, most of which use a straightforward mutex-guarded map with simple LRU.