Adaptive Selection Cache · Go

Experiment with cache eviction policies.

as-cache runs several eviction policies at once. One is active and serves every request; the rest run as shadows that see each key, never its value, and answer "would I have had this?" Once per epoch a multi-armed bandit selects the policy for the next epoch; optional stability gates can restrict switching.

This is experimental research software. For a general-purpose production cache, start with otter or theine; see the measured comparison. Automatic switching has not established a general advantage.

7 policies + 2 experimental FIFO arms planned for v0.5 Thompson sampling Go 1.25+ MPL 2.0 pre-1.0, v0.4.0

How it works

Per request

The active policy stores real values and serves the caller. A shared sampler gates the shadow fan-out, so shadows track a miniature of the same substream and fewer requests fan out to every shadow.

Per epoch

Every arm reports counts over the same sampled keyspace. Counts are not scaled up; miniature shadows can still change rates and rankings. The bandit uses these measurements to select a policy.

On switch

Optional stability gates limit switching; a migration strategy (cold, warm, or gradual) moves data so a switch never serves a shadow's placeholder as a real value.

Quick start

go get github.com/sshaplygin/as-cache
go get github.com/sshaplygin/as-cache/policies
go get github.com/sshaplygin/as-cache/bandit

lru, _ := policies.NewLRU[string, int](10000)
twoQ, _ := policies.NewTwoQueue[string, int](10000)

cache, err := ascache.NewAdaptiveCache(
    []ascache.Policy[string, int]{lru, twoQ},
    bandit.NewThompson(0.9, 1), // discount, seed
    &ascache.Settings{EpochDuration: time.Minute, ShadowSampleRate: 0.05},
)
if err != nil {
    return err
}
defer cache.Close()

cache.Add("k", 1)
v, ok := cache.Get("k")

Prefer measurement without the switching? ObserveOnly mode keeps the configured policy active while Advice() reports measured rankings. Sampling can change those estimates and measurement still adds overhead — see advisor mode.

Policies

Policy	Constructor	Notes
LRU	policies.NewLRU	via hashicorp/golang-lru/v2
LFU	policies.NewLFU	native O(1) implementation
2Q	policies.NewTwoQueue	scan-resistant
Random	policies.NewRandomPolicy	the control arm worth beating
TTL	policies.NewTTL	expiry as well as recency
ARC	arc.NewPolicy	separate module — patented by IBM
W-TinyLFU	tinylfu.NewPolicy	separate module; asynchronous, workload-dependent
S3-FIFO	fifo.NewS3FIFOPolicy	experimental, unreleased module; three static FIFO queues (SOSP '23)
SIEVE	fifo.NewSievePolicy	experimental, unreleased module; one queue and a sweeping hand (NSDI '24)

What the evidence says

The current dataset contains twelve trace workloads and three consecutive measurement batches. Randomness and asynchronous maintenance produce variation; observed ranges do not bound future runs. Read the generated tables and provenance.

Comparison	Scope and limits
Fixed and adaptive policies	All nine arms; 10/20/50 request epochs; fifteen observations for each nondeterministic cell. No guaranteed improvement or worst-policy floor.
Workload context	Distinct keys, cache/keyspace fraction, compulsory-miss ceilings and effective sampling are published. On MSR prn/web leading policies tie; src1_2/usr margins are below 0.04 points.
Sampling	Requested rate 5%, experimental floor 64. Effective rates are 12.8% and 6.4% on the small LIRS caches, 5% elsewhere.
ObserveOnly	LRU stays active on all twelve traces; per-arm advice and retrospective comparisons with standalone policy medians are retained. These comparisons do not measure serving losses from following advice; the sweep is not a real-service trial.
Object versus byte budgets	Meta GET traffic is compared in both libCacheSim LRU modes under an explicit byte-budget convention. The nine-policy matrix remains an entry-count comparison.
Cost	Shadows retain keys and metadata and add work on the request path. Host-specific timings remain raw diagnostics, not stable product claims.

What to investigate

Experiments it supports

Compare policy rankings on a workload whose reuse pattern is unknown.
Measure how changing traffic, epoch length and migration affect selection.
Collect advice with switching disabled; account for measurement overhead and sampling distortion.

Skip it when

You have already measured your traffic and know which policy wins. Use that policy directly.
The hot path is latency-critical at single-digit nanoseconds.
You need a hard memory ceiling, or cannot give it enough traffic per epoch to measure anything.
Your keyspace fits in the cache — every policy scores the same when nothing is evicted.

Documentation

Getting started	Install and run the cache
Releasing	Development workspace, candidate checks and publication
Design	How it works per request and per epoch, the Bandit interface, what is not done
Configuration	Every Settings field, migration strategies, sampling, stability gates, tuning
Policies	The ready-made arms, ARC's patent split, W-TinyLFU's caveats
Advisor mode	ObserveOnly, Advice(), and the metrics module
Evidence	Every measured claim: policy tables, real traces, sampling fidelity
Benchmarking	Reproducible replays, benchclient, make evidence