multicache

README

multicache - High-Performance Multi-Tier Cache

multicache is a high-performance cache for Go implementing the S3-FIFO algorithm from the SOSP'23 paper "FIFO queues are all you need for cache eviction". It combines best-in-class hit rates, multi-threaded scalability, and an optional multi-tier architecture for persistence.

Our philosophy: Hit rate matters most (cache misses are expensive), then throughput (handle load), then single-threaded latency. We aim to excel at all three.

Why "multi"?

Multi-Threaded Performance

Designed for high-concurrency workloads with dynamic sharding (up to 2048 shards) that scales with GOMAXPROCS. At 32 threads, multicache delivers 185M+ QPS for GetOrSet operations.

Multi-Tier Architecture

Stack fast in-memory caching with durable persistence:

┌─────────────────────────────────────┐
│         Your Application            │
└─────────────────┬───────────────────┘
                  │
┌─────────────────▼───────────────────┐
│    Memory Cache (microseconds)      │  ← L1: S3-FIFO eviction
└─────────────────┬───────────────────┘
                  │ async write / sync read
┌─────────────────▼───────────────────┐
│   Persistence Store (milliseconds)  │  ← L2: localfs, Valkey, Datastore
└─────────────────────────────────────┘

Persistence backends:

• pkg/store/localfs - Local files (JSON, zero dependencies)
• pkg/store/valkey - Valkey/Redis
• pkg/store/datastore - Google Cloud Datastore
• pkg/store/cloudrun - Auto-selects Datastore or localfs
• pkg/store/null - No-op for testing

All backends support optional S2 or Zstd compression via pkg/store/compress.

Features

• Best-in-class hit rates - S3-FIFO beats LRU by 5%+ on real traces (learn more)
• Multi-threaded throughput - 185M+ QPS at 32 threads, scales with core count
• Low latency - 7ns reads, 100M+ QPS single-threaded, zero-allocation updates
• Thundering herd prevention - GetSet deduplicates concurrent loads
• Per-item TTL - Optional expiration
• Graceful degradation - Cache works even if persistence fails

Usage

As a stupid-fast in-memory cache:

import "github.com/codeGROOVE-dev/multicache"

// strings as keys, ints as values
cache := multicache.New[string, int]()
cache.Set("answer", 42)
val, found := cache.Get("answer")

Or as a multi-tier cache with local persistence to survive restarts:

import (
  "github.com/codeGROOVE-dev/multicache"
  "github.com/codeGROOVE-dev/multicache/pkg/store/localfs"
)

p, _ := localfs.New[string, User]("myapp", "")
cache, _ := multicache.NewTiered(p)

cache.SetAsync(ctx, "user:123", user) // Don't wait for the key to persist
cache.Store.Len(ctx)                  // Access persistence layer directly

With S2 compression (fast, good ratio):

import "github.com/codeGROOVE-dev/multicache/pkg/store/compress"

p, _ := localfs.New[string, User]("myapp", "", compress.S2())

How about a persistent cache suitable for Cloud Run or local development? This uses Cloud DataStore if available, local files if not:

import "github.com/codeGROOVE-dev/multicache/pkg/store/cloudrun"

p, _ := cloudrun.New[string, User](ctx, "myapp")
cache, _ := multicache.NewTiered(p)

Performance against the Competition

multicache prioritizes hit rate first, multi-threaded throughput second, and single-threaded latency third—but aims to excel at all three. We have our own built in make bench that asserts cache dominance:

>>> TestLatencyNoEviction: Latency - No Evictions (Set cycles within cache size) (go test -run=TestLatencyNoEviction -v)
| Cache         | Get ns/op | Get B/op | Get allocs | Set ns/op | Set B/op | Set allocs |
|---------------|-----------|----------|------------|-----------|----------|------------|
| multicache       |       7.0 |        0 |          0 |      23.0 |        0 |          0 |
| lru           |      23.0 |        0 |          0 |      23.0 |        0 |          0 |
| ristretto     |      28.0 |       13 |          0 |      77.0 |      118 |          3 |
| otter         |      34.0 |        0 |          0 |     160.0 |       51 |          1 |
| freecache     |      74.0 |        8 |          1 |      53.0 |        0 |          0 |
| tinylfu       |      80.0 |        0 |          0 |     110.0 |      168 |          3 |

- 🔥 Get: 229% better than next best (lru)
- 🔥 Set: 0.000% better than next best (lru)

>>> TestLatencyWithEviction: Latency - With Evictions (Set uses 20x unique keys) (go test -run=TestLatencyWithEviction -v)
| Cache         | Get ns/op | Get B/op | Get allocs | Set ns/op | Set B/op | Set allocs |
|---------------|-----------|----------|------------|-----------|----------|------------|
| multicache       |       7.0 |        0 |          0 |      94.0 |        0 |          0 |
| lru           |      24.0 |        0 |          0 |      83.0 |       80 |          1 |
| ristretto     |      31.0 |       14 |          0 |      73.0 |      119 |          3 |
| otter         |      34.0 |        0 |          0 |     176.0 |       61 |          1 |
| freecache     |      69.0 |        8 |          1 |     102.0 |        1 |          0 |
| tinylfu       |      79.0 |        0 |          0 |     115.0 |      168 |          3 |

- 🔥 Get: 243% better than next best (lru)
- 💧 Set: 29% worse than best (ristretto)

>>> TestZipfThroughput1: Zipf Throughput (1 thread) (go test -run=TestZipfThroughput1 -v)

### Zipf Throughput (alpha=0.99, 75% read / 25% write): 1 threads

| Cache         | QPS        |
|---------------|------------|
| multicache       |  100.26M   |
| lru           |   44.58M   |
| tinylfu       |   18.42M   |
| freecache     |   14.07M   |
| otter         |   13.52M   |
| ristretto     |   11.32M   |

- 🔥 Throughput: 125% faster than next best (lru)

>>> TestZipfThroughput16: Zipf Throughput (16 threads) (go test -run=TestZipfThroughput16 -v)

### Zipf Throughput (alpha=0.99, 75% read / 25% write): 16 threads

| Cache         | QPS        |
|---------------|------------|
| multicache       |   36.46M   |
| freecache     |   15.00M   |
| ristretto     |   13.47M   |
| otter         |   10.75M   |
| lru           |    5.87M   |
| tinylfu       |    4.19M   |

- 🔥 Throughput: 143% faster than next best (freecache)

>>> TestMetaTrace: Meta Trace Hit Rate (10M ops) (go test -run=TestMetaTrace -v)

### Meta Trace Hit Rate (10M ops from Meta KVCache)

| Cache         | 50K cache | 100K cache |
|---------------|-----------|------------|
| multicache       |   71.16%  |   78.30%   |
| otter         |   41.12%  |   56.34%   |
| ristretto     |   40.35%  |   48.99%   |
| tinylfu       |   53.70%  |   54.79%   |
| freecache     |   56.86%  |   65.52%   |
| lru           |   65.21%  |   74.22%   |

- 🔥 Meta trace: 5.5% better than next best (lru)

>>> TestHitRate: Zipf Hit Rate (go test -run=TestHitRate -v)

### Hit Rate (Zipf alpha=0.99, 1M ops, 1M keyspace)

| Cache         | Size=1% | Size=2.5% | Size=5% |
|---------------|---------|-----------|---------|
| multicache       |  63.80% |    68.71% |  71.84% |
| otter         |  61.77% |    67.67% |  71.33% |
| ristretto     |  34.91% |    41.23% |  46.58% |
| tinylfu       |  63.83% |    68.25% |  71.56% |
| freecache     |  56.65% |    57.84% |  63.39% |
| lru           |  57.33% |    64.55% |  69.92% |

- 🔥 Hit rate: 0.34% better than next best (tinylfu)

Want even more comprehensive benchmarks? See https://github.com/tstromberg/gocachemark where we win the top score.

Implementation Notes

multicache implements the S3-FIFO algorithm from the SOSP'23 paper with these optimizations for production use:

1. Dynamic Sharding - Up to 2048 shards (capped at 2× GOMAXPROCS) for concurrent workloads
2. Bloom Filter Ghosts - Two rotating Bloom filters instead of storing keys, 10-100× less memory
3. Lazy Ghost Checks - Only check ghosts at capacity, saving latency during warmup
4. Intrusive Lists - Zero-allocation queue operations
5. Fast-path Hashing - Specialized int/string hashing via wyhash
6. Higher Frequency Cap - Max freq=7 (vs paper's 3) for better hot/warm discrimination

The core algorithm follows the paper closely: items enter the small queue, get promoted to main after 2+ accesses, and evicted items are tracked in a ghost queue to inform future admissions.

License

Apache 2.0

Documentation

Overview

Package multicache provides a high-performance adaptive cache with optional persistence.

Index

• type Cache
  • func New[K comparable, V any](opts ...Option) *Cache[K, V]
  • func (*Cache[K, V]) Close()
  • func (c *Cache[K, V]) Delete(key K)
  • func (c *Cache[K, V]) Flush() int
  • func (c *Cache[K, V]) Get(key K) (V, bool)
  • func (c *Cache[K, V]) GetSet(key K, loader func() (V, error), ttl ...time.Duration) (V, error)
  • func (c *Cache[K, V]) Len() int
  • func (c *Cache[K, V]) Set(key K, value V, ttl ...time.Duration)
  • func (c *Cache[K, V]) SetIfAbsent(key K, value V, ttl ...time.Duration) (V, bool)
• type Option
  • func Size(n int) Option
  • func TTL(d time.Duration) Option
• type Store
• type TieredCache
  • func NewTiered[K comparable, V any](store Store[K, V], opts ...Option) (*TieredCache[K, V], error)
  • func (c *TieredCache[K, V]) Close() error
  • func (c *TieredCache[K, V]) Delete(ctx context.Context, key K) error
  • func (c *TieredCache[K, V]) Flush(ctx context.Context) (int, error)
  • func (c *TieredCache[K, V]) Get(ctx context.Context, key K) (V, bool, error)
  • func (c *TieredCache[K, V]) GetSet(ctx context.Context, key K, loader func(context.Context) (V, error), ...) (V, error)
  • func (c *TieredCache[K, V]) Len() int
  • func (c *TieredCache[K, V]) Set(ctx context.Context, key K, value V, ttl ...time.Duration) error
  • func (c *TieredCache[K, V]) SetAsync(ctx context.Context, key K, value V, ttl ...time.Duration) error

Types

type Cache

type Cache[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Cache is a fast in-memory cache without persistence. All operations are context-free and never return errors.

func New

func New[K comparable, V any](opts ...Option) *Cache[K, V]

New creates a new in-memory cache.

Example:

cache := multicache.New[string, User](
    multicache.Size(10000),
    multicache.TTL(time.Hour),
)
defer cache.Close()

cache.Set("user:123", user)              // uses default TTL
cache.Set("user:123", user, time.Hour)   // explicit TTL
user, ok := cache.Get("user:123")

func (*Cache[K, V]) Close

func (*Cache[K, V]) Close()

Close releases resources held by the cache. For Cache this is a no-op, but provided for API consistency.

func (*Cache[K, V]) Delete

func (c *Cache[K, V]) Delete(key K)

Delete removes a value from the cache.

func (*Cache[K, V]) Flush

func (c *Cache[K, V]) Flush() int

Flush removes all entries from the cache. Returns the number of entries removed.

func (*Cache[K, V]) Get

func (c *Cache[K, V]) Get(key K) (V, bool)

Get retrieves a value from the cache. Returns the value and true if found, or the zero value and false if not found.

func (*Cache[K, V]) GetSet

func (c *Cache[K, V]) GetSet(key K, loader func() (V, error), ttl ...time.Duration) (V, error)

GetSet retrieves a value from the cache, or calls loader to compute and store it. This prevents thundering herd: if multiple goroutines request the same missing key concurrently, only one loader runs while others wait for its result.

Example:

user, err := cache.GetSet("user:123", func() (User, error) {
    return fetchUserFromDB("123")
})

// Or with explicit TTL:
user, err := cache.GetSet("user:123", func() (User, error) {
    return fetchUserFromDB("123")
}, time.Hour)

func (*Cache[K, V]) Len

func (c *Cache[K, V]) Len() int

Len returns the number of entries in the cache.

func (*Cache[K, V]) Set

func (c *Cache[K, V]) Set(key K, value V, ttl ...time.Duration)

Set stores a value in the cache. If no TTL is provided, the default TTL is used. If no default TTL is configured, the entry never expires.

func (*Cache[K, V]) SetIfAbsent

func (c *Cache[K, V]) SetIfAbsent(key K, value V, ttl ...time.Duration) (V, bool)

SetIfAbsent stores value only if key doesn't exist. Returns the existing value and true if found, or the new value and false if stored. Unlike GetSet, this has no thundering herd protection - use when value is precomputed.

type Option

type Option func(*config)

Option configures a Cache.

func Size

func Size(n int) Option

Size sets the maximum number of entries in the memory cache. Default is 16384.

func TTL

func TTL(d time.Duration) Option

TTL sets the default TTL for cache entries. Entries without an explicit TTL will use this value. Default is 0 (no expiration).

type Store

type Store[K comparable, V any] interface {
	// ValidateKey checks if a key is valid for this persistence store.
	ValidateKey(key K) error

	// Get retrieves a value from persistent storage.
	Get(ctx context.Context, key K) (V, time.Time, bool, error)

	// Set saves a value to persistent storage with an expiry time.
	Set(ctx context.Context, key K, value V, expiry time.Time) error

	// Delete removes a value from persistent storage.
	Delete(ctx context.Context, key K) error

	// Cleanup removes expired entries older than maxAge.
	Cleanup(ctx context.Context, maxAge time.Duration) (int, error)

	// Location returns the storage location for a given key.
	Location(key K) string

	// Flush removes all entries from persistent storage.
	Flush(ctx context.Context) (int, error)

	// Len returns the number of entries in persistent storage.
	Len(ctx context.Context) (int, error)

	// Close releases any resources held by the persistence store.
	Close() error
}

Store defines the interface for cache persistence backends. Uses only standard library types, so implementations can satisfy it without importing this package.

type TieredCache

type TieredCache[K comparable, V any] struct {
	// Store provides direct access to the persistence layer.
	// Use this for persistence-specific operations:
	//   cache.Store.Len(ctx)
	//   cache.Store.Flush(ctx)
	//   cache.Store.Cleanup(ctx, maxAge)
	Store Store[K, V]
	// contains filtered or unexported fields
}

TieredCache is a cache with an in-memory layer backed by persistent storage. The memory layer provides fast access, while the store provides durability. Core operations require context for I/O, while memory operations like Len() do not.

func NewTiered

func NewTiered[K comparable, V any](store Store[K, V], opts ...Option) (*TieredCache[K, V], error)

NewTiered creates a cache with an in-memory layer backed by persistent storage.

Example:

store, _ := localfs.New[string, User]("myapp", "")
cache, err := multicache.NewTiered[string, User](store,
    multicache.Size(10000),
    multicache.TTL(time.Hour),
)
if err != nil {
    return err
}
defer cache.Close()

cache.Set(ctx, "user:123", user)              // uses default TTL
cache.Set(ctx, "user:123", user, time.Hour)   // explicit TTL
user, ok, err := cache.Get(ctx, "user:123")
storeCount, _ := cache.Store.Len(ctx)

func (*TieredCache[K, V]) Close

func (c *TieredCache[K, V]) Close() error

Close releases resources held by the cache.

func (*TieredCache[K, V]) Delete

func (c *TieredCache[K, V]) Delete(ctx context.Context, key K) error

Delete removes a value from the cache. The value is always removed from memory. Returns an error if persistence deletion fails.

func (*TieredCache[K, V]) Flush

func (c *TieredCache[K, V]) Flush(ctx context.Context) (int, error)

Flush removes all entries from the cache, including persistent storage. Returns the total number of entries removed from memory and persistence.

func (*TieredCache[K, V]) Get

func (c *TieredCache[K, V]) Get(ctx context.Context, key K) (V, bool, error)

Get retrieves a value from the cache. It first checks the memory cache, then falls back to persistence.

func (*TieredCache[K, V]) GetSet

func (c *TieredCache[K, V]) GetSet(ctx context.Context, key K, loader func(context.Context) (V, error), ttl ...time.Duration) (V, error)

GetSet retrieves a value from the cache (memory or persistence), or calls loader to compute and store it. This prevents thundering herd: if multiple goroutines request the same missing key concurrently, only one loader runs while others wait for its result.

Example:

user, err := cache.GetSet(ctx, "user:123", func(ctx context.Context) (User, error) {
    return fetchUserFromAPI(ctx, "123")
})

// Or with explicit TTL:
user, err := cache.GetSet(ctx, "user:123", func(ctx context.Context) (User, error) {
    return fetchUserFromAPI(ctx, "123")
}, time.Hour)

func (*TieredCache[K, V]) Len

func (c *TieredCache[K, V]) Len() int

Len returns the number of entries in the memory cache. For persistence entry count, use cache.Store.Len(ctx).

func (*TieredCache[K, V]) Set

func (c *TieredCache[K, V]) Set(ctx context.Context, key K, value V, ttl ...time.Duration) error

Set stores a value in the cache. If no TTL is provided, the default TTL is used. The value is ALWAYS stored in memory, even if persistence fails. Returns an error if the key violates persistence constraints or if persistence fails.

func (*TieredCache[K, V]) SetAsync

func (c *TieredCache[K, V]) SetAsync(ctx context.Context, key K, value V, ttl ...time.Duration) error

SetAsync stores a value in the cache, handling persistence asynchronously. If no TTL is provided, the default TTL is used. Key validation and in-memory caching happen synchronously. Persistence errors are logged but not returned (fire-and-forget). Returns an error only for validation failures (e.g., invalid key format).