sieve

go-sieve - SIEVE cache eviction for Go

A Go implementation of the SIEVE cache eviction algorithm (NSDI'24, Zhang et al.), engineered from the ground up for highly concurrent, read-heavy workloads. Generic over key and value types.

The read path (Get()) is fully lock-free — a single atomic load on the key→index map plus a single atomic bit update on a shared visited bitfield. No mutex, no pointer chasing, no per-entry allocations, zero GC traffic on hits. Under parallel load this is ~90–300x faster than hashicorp/golang-lru and scales linearly with cores: measured at 1–3 ns/op across 32 goroutines on real-world cache traces. The write path uses a single short-held mutex and a pre-allocated node pool, so Add()/Probe() also avoid per-operation heap allocation in steady state.

If you need a cache that many goroutines hit simultaneously on the read path — an HTTP response cache, a DNS resolver cache, an authz decision cache, a hot-path object lookup — this implementation is built for that shape. For purely single-threaded use, hashicorp/golang-lru may be marginally faster on the sequential write path; under any concurrency, Sieve wins decisively.

SIEVE uses a FIFO queue with a roving "hand" pointer: cache hits set a visited bit (lazy promotion), and eviction scans from the hand clearing visited bits until it finds an unvisited node (quick demotion). It matches or exceeds LRU/ARC hit ratios with far less bookkeeping — validated here on ~300M requests from the MSR Cambridge and Meta Storage trace repositories.

Key Design Elements

Array-backed indexed list. Marc Brooker observed that SIEVE's mid-list removal prevents a simple circular buffer. Rather than Tobin Baker's "swap tail into hole" workaround, this implementation uses a doubly-linked list with int32 indices into a pre-allocated backing array. This preserves SIEVE's exact eviction semantics while eliminating all interior pointers — the GC sees a flat []node with no pointers to trace (for non-pointer K, V types).

xsync.MapOf for concurrent access. The key→index map uses puzpuzpuz/xsync.MapOf which stores int32 values inline in cache-line-padded buckets — no traced pointers per entry. Get() is fully lock-free; only Add()/Probe() (on miss) and Delete() take the global mutex.

Columnar slot state (slotState). Each node's lock and visited counter are hoisted out of the node struct into a separate contiguous []uint64 — one word per slot, laid out as a column alongside the []node array. This columnar split has three effects:

1. the eviction hand scans IsVisited by walking a dense []uint64 sequentially — 8 slots per cache line, hardware-prefetch friendly — without pulling in key/val data it doesn't need;
2. Get()'s LockAndMark writes only to the slotState word for that slot, so it never dirties the cache line holding the node's key/val — no false sharing with concurrent readers of adjacent nodes
3. []uint64 contains no pointers, so the GC never traces it, unlike node fields that may hold pointer-typed K/V.

Within each word, bit 63 is a spinlock and the low bits are a saturating visited counter (1 bit at k=1, ⌈log₂(k+1)⌉ bits for higher k).

Pre-allocated node pool. All nodes are allocated once at cache creation in a contiguous array. A bump allocator + intrusive freelist (reusing node.next) provides O(1) alloc/free with zero heap allocations during steady-state operation.

TOCTOU-safe concurrent writes. Add() and Probe() use a double-check pattern: fast-path Load() outside the lock, re-check under mu.Lock() before inserting. This prevents duplicate nodes from concurrent writers racing on the same key.

Benchmark Results

Benchmarked against hashicorp/golang-lru v2.0.7 (LRU and ARC) on a 13th Gen Intel Core i9-13900 with 32 cores and 32GB of RAM:

• Ubuntu/Linux 24.04 (kernel 6.8.0-106)
• go1.26.1
• GOMAXPROCS=32

Benchmarks live in bench/ as a separate module to avoid polluting go.mod.

Commands used (no name filter — every benchmark in every package runs):

cd bench && make bench    # synthetic comparison, count=3
cd bench && make trace    # trace replay + miss ratio + GC, count=1

Full raw results: bench-results.md.

Reading the parallel ns/op numbers

The sub-2 ns/op numbers in the parallel tables below are real but need context: they are aggregate throughput.

Go's b.RunParallel distributes b.N total operations across GOMAXPROCS goroutines and reports ns/op = wall_clock / b.N. When 32 goroutines complete 1 billion Get()s in ~1 second, the reported number is 1.0 ns/op — meaning "the system produces one completed Get every ~1 ns." The per-core latency is ~32 ns (1.0 × 32 cores), which is consistent with two L1/L2-hot atomic operations on a 5 GHz CPU.

LRU/ARC report ~200–600 ns/op under the same conditions — not because a single Get is 200x slower, but because every Get takes a mutex. The 32 goroutines serialize through one lock, so throughput is flat regardless of core count. On a single goroutine (see BenchmarkReplay, sequential), SIEVE and LRU are within 15% of each other — the ~100–300x gap is a concurrency-scaling story.

After warmup, the working data structures (map buckets, node array, visited bitfield) are resident in CPU cache — L1/L2 for small traces, L3 for larger ones. Real workloads with lower temporal locality will see higher per-core latency, but the relative advantage over mutex-bound LRU/ARC holds whenever there is any parallelism at all.

Parallel Micro-Benchmarks (count=3, medians)

Probe_Parallel is SIEVE-only — LRU's PeekOrAdd and ContainsOrAdd skip recency promotion and are not semantic equivalents. Delete_Parallel is the one micro where SIEVE loses: LRU's single-lock linked-list unlink edges out SIEVE's slot-state clear (163 vs 230 ns/op). ARC is slowest (254 ns/op) because its T1/T2/B1/B2 bookkeeping doubles the work.

Trace Replay Results

This implmentation is benchmarked against real-world cache traces from the libCacheSim trace repository — 14 MSR Cambridge enterprise block I/O traces + 5 Meta Storage (Tectonic) block traces totalling ~300M requests. Each trace was replayed with a cache sized at 10% of unique keys, comparing SIEVE (k=1, k=2, k=3) against hashicorp/golang-lru (LRU and ARC).

Parallel Get throughput (warm cache, 32 goroutines, ns/op, zero allocs)

SIEVE's lock-free Get() is ~100–300x faster than LRU/ARC under concurrent read load. Every trace, every cache:

The k=3 saturating counter adds under 10% overhead to the read path. This benchmark pre-warms the cache with a full trace replay, then hammers Get() only — the ideal scenario for a read-heavy cache in steady state.

Parallel Replay throughput (cold cache, mixed read+write, 32 goroutines, ns/op)

This is Probe() for SIEVE and Get+Add for LRU/ARC, hammered in parallel with no warmup. It measures the steady-state workload a real cache faces: reads and writes interleaved, evictions happening live. The previous table's numbers reflect the best-case read ceiling; this table reflects what throughput you actually get when your cache is doing work.

Under concurrent cold-cache replay, SIEVE is ~18–62x faster than LRU/ARC. The best case is msr_prxy_0 (95% hits, so the lock-free fast path dominates); the worst case is msr_web_2 (98% miss ratio, almost every call takes the write lock) — and even there SIEVE is 18x faster.

Miss ratio (every trace)

Cache sized at 10% of unique keys. Bold = best in row.

Overall best (bold): ARC has the lowest miss ratio in 11 of 18 rows, LRU in 5 (all meta_storage), SIEVE k=3 in 2 (msr_prn_1 and msr_src1_1). SIEVE k=1 is never the overall best.

Head-to-head, SIEVE k=1 vs LRU (the typical deployment choice): SIEVE k=1 has lower miss ratio on 10 of 18 traces, LRU on 8. When SIEVE is better the margins are large (msr_src1_0: 12.9 points, msr_usr_1: 4.5, msr_prn_1: 4.3). When LRU is better the margins are narrow (all 5 meta_storage: 2–3 points each).

SIEVE's case rests on throughput Miss ratios are competitive (SIEVE is never dramatically worse than LRU), and SIEVE is 18–300x faster under any concurrency. SIEVE k=3 produces the single-best entry in the entire table on msr_prn_1 (0.3796 vs LRU 0.4341, ARC 0.4148).

Memory during replay

On the 13.2M-request meta_storage/block_traces_1 trace (601K-entry cache), TestGCPressure reports:

SIEVE allocates 2.7x less than LRU and 6.5x less than ARC during replay — the array-backed node pool and inline-int32 xsync.MapOf are structural wins.

Full per-trace tables (sequential replay ns/op, B/op, miss ratio for every trace) are in bench-results.md. Methodology and trace-loading details are in bench/README.md.

Usage

import "github.com/opencoff/go-sieve"

// Create a cache mapping string keys to int values, capacity 1000.
c, err := sieve.New[string, int](1000)
if err != nil {
    log.Fatal(err) // ErrInvalidCapacity or ErrInvalidVisitClamp
}

// Or, for constant arguments, use Must to get a one-liner:
c := sieve.Must(sieve.New[string, int](1000))

c.Add("foo", 42)

if val, ok := c.Get("foo"); ok {
    fmt.Println(val) // 42
}

// Probe inserts only if absent; returns the cached value if present.
val, _, r := c.Probe("foo", 99)
// val == 42, r.Hit() == true

c.Delete("foo")
c.Purge() // reset entire cache

SIEVE-k

WithVisitClamp(k) creates a SIEVE-k cache where each entry uses a saturating counter instead of a single visited bit. An item accessed k+1 times survives k eviction passes before being evicted. k=1 is equivalent to classic SIEVE (the default). Use k=2 or k=3 for workloads with repeated access patterns where extra eviction resistance is beneficial.

// Classic SIEVE (k=1, the default)
c, err := sieve.New[string, int](1000)

// SIEVE-k=3: items survive up to 3 eviction passes
c, err := sieve.New[string, int](1000, sieve.WithVisitClamp(3))

New returns an error for capacity <= 0 (ErrInvalidCapacity) and for WithVisitClamp(k) with k > sieve.MaxVisitClamp (255 — ErrInvalidVisitClamp). Clamp values below 1 are silently rounded up to 1.

Eviction Handling

Add() and Probe() return the evicted entry (if any) along with a CacheResult bitmask. This allows callers to handle evictions synchronously without channels, goroutines, or lifecycle management.

c := sieve.Must(sieve.New[string, int](1000))

ev, r := c.Add("foo", 42)
if r.Evicted() {
    cleanupDisk(ev.Key, ev.Val)
}

// CacheResult bitmask:
//   CacheHit   — key was already present (value updated, no eviction)
//   CacheEvict — an entry was evicted to make room (mutually exclusive with CacheHit)

Purge() and Delete() do not report evictions.

API

Options

GC Note

When K or V is a pointer type (including string, which contains an internal pointer in Go), the node array will still contain GC-traced pointers. The GC pressure reduction is most dramatic for scalar key/value types (int, [16]byte, fixed-size structs).

License

BSD-2-Clause. See the source files for the full license text.