Fixed-capacity in-memory caches for Go.
- High hit ratio.
tinylfuadmits 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,s3fifoandsieveread 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.
GetManyloads up to 32 entries from memory in parallel. - Evictions handed back.
Setreturns the entry it replaced or evicted. - Statistics.
stats.Wrapcounts hits, misses and evictions. - Safe for concurrent use, and depends only on the standard library.
go get github.com/floatdrop/evict
Requires Go 1.26 or later.
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.
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).
- Left: requests answered on S3, disk reads of a search engine, by cache size. Caches
in one shard; otter and
tinylfuvary 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.
otteris otter v2;golang-lruandgolang-lru/2qare hashicorp's.- Averaged over 11 traces:
tinylfu47.9% of requests, otter 47.5%,s3fifo44.8%,lru36.6%. The gap betweentinylfuand otter is within how much they vary between replays. tinylfuwas 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
uint64keys 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.
| Package | Use it when | Watch out for |
|---|---|---|
tinylfuTinyLFU 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). |
s3fifoS3-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. |
sieveSIEVE |
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). |
twoq2Q |
a quarter or more of the operations are writes, or one goroutine uses the cache | Reads take a lock; more memory than lru. |
lruleast 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.
- 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);Clearlets go of everything. The slots take 2–4 KiB per CPU, so for very many small caches, uselru. - 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.
lrumust agree with hashicorp'sgolang-lruon every request of a trace.
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.