Skip to content
floatdropPublic

About

Fixed-capacity in-memory caches for Go

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

25 Commits

Folders and files

Repository files navigation

evict

Go Reference CI

Fixed-capacity in-memory caches for Go.

  • High hit ratio. tinylfu admits a new entry only if it is asked for more often than the one it would evict, and sizes its queues to the workload.
  • Reads that scale. tinylfu, s3fifo and sieve read without locks.
  • No allocations after New. Entries live in arrays, linked by 32-bit indices.
  • Nothing for the GC to scan when keys and values hold no pointers.
  • Batch lookups. GetMany loads up to 32 entries from memory in parallel.
  • Evictions handed back. Set returns the entry it replaced or evicted.
  • Statistics. stats.Wrap counts hits, misses and evictions.
  • Safe for concurrent use, and depends only on the standard library.

Install

go get github.com/floatdrop/evict

Requires Go 1.26 or later.

Usage

package main

import (
	"fmt"

	"github.com/floatdrop/evict/tinylfu"
)

func main() {
	cache := tinylfu.New[string, int](10_000)

	cache.Set("a", 1)
	cache.Set("b", 2)

	if value, ok := cache.Get("a"); ok {
		fmt.Println(value)
	}

	// Set hands back what it pushed out: the previous entry for the key, or
	// the entry that was evicted to make room.
	if key, value, displaced := cache.Set("a", 10); displaced {
		fmt.Println("dropped", key, value)
	}

	// GetMany looks up a batch of keys. On a cache too large for the CPU's
	// caches, 32 keys per call take about half the time per key of Get.
	// For fewer than four keys, call Get.
	keys := []string{"a", "b", "c"}
	values := make([]int, len(keys))
	found := make([]bool, len(keys))
	cache.GetMany(keys, values, found)
	for i, key := range keys {
		if found[i] {
			fmt.Println(key, values[i])
		}
	}
}

Every package implements evict.Cache; sieve, s3fifo and tinylfu also have GetMany.

Statistics

cache := stats.Wrap(tinylfu.New[string, int](10_000))

s := cache.Stats()
fmt.Println(s.HitRatio(), s.Evictions, s.Len, s.Cap)

The counts only go up; s.Sub(prev) gives those of an interval. A Get that hits took 10–14% longer through the wrapper (tinylfu, Apple M3 Max).

Benchmarks

Hit ratio on the S3 trace by cache capacity Throughput of ReadThrough with a million entries by number of CPUs

  • Left: requests answered on S3, disk reads of a search engine, by cache size. Caches in one shard; otter and tinylfu vary between replays, so theirs are medians of 11.
  • Right: reads of a million entries that store the key on a miss, by number of CPUs, on an Apple M3 Max.
  • otter is otter v2; golang-lru and golang-lru/2q are hashicorp's.
  • Averaged over 11 traces: tinylfu 47.9% of requests, otter 47.5%, s3fifo 44.8%, lru 36.6%. The gap between tinylfu and otter is within how much they vary between replays.
  • tinylfu was designed on these traces. On 14 others, in a simulation not in this repository, it was level with S3-FIFO and W-TinyLFU.
  • In the chart on the right, the lock-free caches do 2.1–2.4 times as many operations as otter on 8 CPUs.
  • On 8 CPUs otter wins when 10–25% of the operations overwrite entries. These are numbers from one machine; otter's own, from Linux on x86, show its writes scaling better.
  • 56–100 bytes per entry with uint64 keys and values. A GC cycle with 10 million entries takes 0.2–0.3 ms, against 530 ms for otter.

bench/README.md has the method, every table, and make bench to rerun them.

Choosing a policy

Package Use it when Watch out for
tinylfu
TinyLFU over S3-FIFO
in doubt: the workload is unknown, or has loops or scans, and is read far more than written Evicting writes are 8–13% slower than in s3fifo. Hit ratios vary between runs by up to 5.6 points. Where keys come back once or twice after the same while, lru can do far better (docs).
s3fifo
S3-FIFO
you want the same results on every run, or the workload has no loops On looping workloads it can fall as low as lru. Writes cost about twice what they do in lru.
sieve
SIEVE
reading through has to be as fast as possible, and you have checked your workload It can collapse on loops: on one trace it answers under 1% of requests where lru answers 44% (when not to use it).
twoq
2Q
a quarter or more of the operations are writes, or one goroutine uses the cache Reads take a lock; more memory than lru.
lru
least recently used
memory counts most, or you want behavior everyone knows The lowest hit ratio of these five on 9 of the 11 traces; reads take a lock.

Every package takes WithShards. twoq and s3fifo also have options for tuning their queues (what that is worth for s3fifo); tinylfu tunes its own.

How it works

  • Arrays, not pointers. Each shard allocates its nodes once and links them by 32-bit index. An open-addressing index with three slots per entry maps a 32-bit hash to a node, so a lookup compares hashes before it touches an entry.
  • Shards. The upper half of a key's hash picks a shard, which writers lock on its own; the lower half indexes the key within it. Each shard evicts from its own share of the capacity. A cache under 512 entries is one shard; a larger one has up to eight per CPU, of 256 entries or more. WithShards(1) gives a policy's textbook behavior.
  • Lock-free reads (sieve, s3fifo, tinylfu). A reader pins the node it reads in a slot of its own and checks that the index still points there. Writers never change a node that a reader can reach: a new value goes into a fresh node, and a node is reused only once no slot pins it. A read writes only to a cache line its CPU has to itself. Removed entries stay referenced until their shard collects them in a batch (an eighth of its capacity, 1,024 at most); Clear lets go of everything. The slots take 2–4 KiB per CPU, so for very many small caches, use lru.
  • Admission (tinylfu). Each shard keeps a count-min sketch of how often keys are asked for, cached or not; only writers update it, picking up the reads counted on entries. Once the shard is full, a new entry gets into the main queue only if the sketch rates its key above the entry that queue would evict next. The size of the small queue is tuned by hill climbing, as in Caffeine.
  • Tests. Every cache runs one conformance suite, is checked against a simple model of its policy step by step, and is fuzzed against that model. Lock-free reads are tested under the race detector. lru must agree with hashicorp's golang-lru on every request of a trace.

What it does not do

No expiry, no weights or sizes in bytes, no loading functions. If you need those, or if many CPUs overwrite a tenth to a quarter of what they read, use otter.

License

MIT

About

Fixed-capacity in-memory caches for Go

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages