ascache

package module
v0.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 3, 2026 License: MPL-2.0 Imports: 12 Imported by: 0

README

as-cache — Adaptive Selection Cache

CI Go Reference Go Report Card

A Go library that uses a Multi-Armed Bandit (MAB) algorithm to select the cache replacement policy at runtime, measuring candidate policies against your real traffic instead of asking you to guess.

Status

Pre-1.0: the API may still change, and nothing here has been run in production that I know of. What has been done is measurement -- every claim below comes from a reproducible run against published traces, not from intuition, and the concurrency has been exercised under the race detector and adversarially reviewed. Read Evidence and decide for yourself; the numbers are there so you do not have to take "experimental" or "production-ready" on trust.

Three things are worth knowing before adopting it.

No single policy wins everywhere, and that is the point. On real traces the best fixed policy changes: 2Q wins on the Twitter and OLTP traces, W-TinyLFU on the ARC P3 and LIRS traces -- and on OLTP, W-TinyLFU is second-worst. Tuned sensibly, adaptive selection lands within about a point of the best fixed policy on most traces and beats it on one, without being told which to pick.

It is sensitive to configuration. The same traces with a too-short epoch lose up to 7 points and cost 30x the per-operation time, because the cache spends its life migrating rather than serving. See Configuring it before drawing conclusions from your own numbers.

Memory costs less than the obvious guess. Running N policies in parallel does not multiply memory by N, because shadow policies hold keys and eviction bookkeeping but never real values. Measured with six policies over 50k entries of 256-byte values:

Configuration Memory Multiplier
single LRU 18.5 MiB 1.00x
adaptive, 6 policies 48.9 MiB 2.65x
adaptive, 6 policies, ShadowSampleRate: 0.05 24.5 MiB 1.32x

Per-operation cost on a warm cache, same configurations (Get, 0 allocs/op throughout):

Configuration ns/op allocs/op
single LRU 32 0
adaptive, 6 policies 618 0
adaptive, 6 policies, sampled 82 0
When to use it
  • You do not know which policy suits your traffic, and cannot easily find out.
  • Your traffic changes shape and you would rather not re-tune.
  • You want the measurement more than the switching. ObserveOnly mode gives you that at zero risk -- see Advisor mode.
When not to use it
  • You have already measured your traffic and know which policy wins. Use that policy directly; this library's best case is roughly to match it.
  • The hot path is latency-critical at single-digit nanoseconds. Even sampled, the adaptive layer costs several times a bare LRU per operation.
  • You need a hard memory ceiling. The multiplier is modest but real.
  • You cannot give it enough traffic per epoch to measure anything. Arms that are within noise of each other reorder run to run, so a cache seeing a handful of requests per epoch will pick essentially at random. Advice() reports Epochs so you can tell whether it has seen enough. If the reason is that your traffic is spread across many replicas rather than genuinely thin, see Running a fleet.
  • Your keyspace is small enough to fit in the cache. Every policy scores the same when nothing is ever evicted, and you are paying for shadows that can never tell you anything.

Problem

Choosing the right cache replacement algorithm for a workload is a separate research task. This library sidesteps that decision by running candidate policies in parallel (shadow caching), measuring hit/miss rates per epoch, and using Thompson Sampling to pick the winner dynamically.

Idea

One policy is active and serves every request. The others run as shadows: they see each key, never its value, and answer the question "would I have had this?" — a hit rate measured on your traffic rather than guessed from a paper.

On each request:

  1. The active policy serves the read or write and counts its own hit or miss.
  2. The sampler decides whether the shadows see the key at all. When ShadowSampleRate is below 1 they track a deterministic fraction of the keyspace and shrink to match, so per-operation cost stops scaling with the number of policies.
  3. Selected keys go to every shadow as Add(key, zeroValue). Shadows hold keys and eviction bookkeeping, never data, which is why N policies do not cost N times the memory — and why no caller can ever be handed a shadow's zero.

Then once per epoch, on a background goroutine:

  1. Every arm reports its hits and misses — the active one included, measured over the same sampled substream, so no arm is judged on more evidence than another. Counters reset; the epoch is the unit of evidence.
  2. The bandit receives that evidence and names the arm for the next epoch. Beta posteriors updated with each arm's hits and misses, drawn from by Thompson sampling, is the usual choice — bandit.NewThompson is one — but the interface is yours to implement, and bandit.NewDistributed pools the evidence across a fleet.
  3. If the named arm is not the active one, stability gates decide whether the improvement is worth a switch. On a switch, data moves according to the migration strategy, and the outgoing policy rewrites its entries to zero values, keeping the keys its eviction bookkeeping needs. It is a shadow now, and shrinks to the miniature capacity shadows run at if sampling is on.

The measurement is the durable part, and you can have it without the switching: ObserveOnly runs every arm and reports which would have served you best, while the cache behaves exactly like the policy you built it with.

Usage

See examples/basic/main.go for a complete runnable example with an HTTP server and a Thompson Sampling adapter (via stitchfix/mab).

Supported Cache Methods

Policy Status Notes
LRU implemented via hashicorp/golang-lru/v2
LFU implemented native O(1) implementation in lfu/; policies.NewLFU
2Q implemented policies.NewTwoQueue
Random implemented policies.NewRandomPolicy
TTL implemented policies.NewTTL
ARC implemented policies/arc — separate module, patented
W-TinyLFU implemented policies/tinylfu — separate module

AdaptiveCache API

All methods are safe for concurrent use.

Method Description
Add(key, value) bool Add or update a key; returns true if an eviction occurred
Get(key) (V, bool) Retrieve a value; records a hit or miss
Contains(key) bool Check presence without recording a hit
Peek(key) (V, bool) Read value without recording a hit
Remove(key) bool Delete a key from all policies
Purge() Clear all policies and reset migration state
Keys() []K Keys in the active policy
Values() []V Values in the active policy
Len() int Number of entries in the active policy
Resize(size) int Resize all policies; returns total eviction count
Stats() GlobalStats Cumulative hit/miss counts for the active policy
ActivePolicy() PolicyType Which policy is currently serving requests
Close() error Stop the background epoch goroutine

Settings

type Settings struct {
    // EpochDuration controls how often the bandit re-evaluates policies.
    EpochDuration time.Duration

    // EvictPartialCapacityFilling allows switching before the cache is full.
    // When false, the bandit only runs once the active policy reaches capacity.
    EvictPartialCapacityFilling bool

    // MigrationStrategy controls data transfer on policy switch.
    // Default: MigrationCold.
    MigrationStrategy MigrationStrategy

    // ShadowSampleRate has shadows track a fraction of the keyspace.
    // Zero means 1 (no sampling). See "Reducing shadow overhead".
    ShadowSampleRate  float64
    MinShadowCapacity int

    // Switch stability gates; all inactive at zero.
    // See "Keeping switches stable".
    MinHitRateImprovement float64
    SwitchCooldownEpochs  int64
    MinEpochRequests      int64
}

Migration Strategies

Strategy Behaviour Trade-off
MigrationCold (default) New active policy starts empty Simple; causes a temporary miss spike
MigrationWarm All key/value pairs copied at switch time No miss spike; O(n) work at switch
MigrationGradual Keys promoted on Get; one key drained per Add Spreads migration cost; window closes at the next epoch at the latest

Architecture

AdaptiveCache
  |-- active policy  (CacheWrapper -> real Cacher impl)
  |-- shadow policy  (CacheWrapper -> real Cacher impl, zero-value adds only,
  |                   optionally a sampled miniature -- see ShadowSampleRate)
  |-- Bandit         (Thompson Sampling via stitchfix/mab)
  |-- background goroutine (epoch ticker -> tryChangePolicy -> migrateData)

Implementing the Bandit Interface

type Bandit interface {
    // RecordStats delivers one policy's hit/miss stats since its last
    // report; every policy reports, the active one included.
    RecordStats(stats ShadowStats)

    // SelectPolicy returns the policy that should become active next epoch.
    SelectPolicy() PolicyType
}

A full Thompson Sampling adapter using stitchfix/mab is provided in examples/basic/main.go.

Reducing shadow overhead

Running policies in parallel costs something on every operation: each shadow is another lookup and another lock. Since a shadow exists only to estimate a hit rate, and a hit rate can be estimated from a sample, ShadowSampleRate lets shadows track a deterministic fraction of the keyspace instead of mirroring everything.

&ascache.Settings{
    EpochDuration:    time.Minute,
    ShadowSampleRate: 0.05, // shadows track 5% of keys
}

Shadows shrink along with the rate, so each remains a faithful miniature of a full-size cache rather than an undersized one, and every shadow samples the same keys so their hit rates stay comparable. The active policy still serves every key -- only the measurement is sampled, and it is sampled for the active policy too, so no arm is judged on more evidence than another. Stats() continues to report real, unsampled traffic.

The effect is that per-operation cost stops scaling with the number of policies. Measured with mutex-backed stub policies on an Apple M1 Max at -benchtime=300ms, so the numbers isolate what the adaptive layer adds rather than what any particular policy costs:

Benchmark shadows sampling off rate 0.05
Get 1 97 ns/op 35 ns/op
Get 3 148 ns/op 38 ns/op
GetParallel 1 271 ns/op 181 ns/op
GetParallel 3 405 ns/op 185 ns/op
Add 1 110 ns/op 52 ns/op
Add 3 193 ns/op 59 ns/op
MixedParallel 1 183 ns/op 87 ns/op

Read the Get rows down the shadow count. Unsampled, a third shadow costs another 50ns, because every operation visits every policy. Sampled, going from one shadow to three costs 3ns -- the fan-out happens on 5% of operations, so adding a policy is close to free. That is what makes carrying seven arms practical.

Reproduce with go test -run '^$' -bench . -benchtime=300ms .

Sampling is off by default. Very small caches disable it automatically, since a miniature of a handful of entries measures noise rather than a policy.

Keeping switches stable

By default every bandit selection is applied. On noisy traffic two policies that perform almost identically can trade places every epoch, and each switch costs a migration. Three settings damp that, all inactive at their zero value:

&ascache.Settings{
    MinHitRateImprovement: 0.02, // require a 2-point hit-rate win to switch
    SwitchCooldownEpochs:  3,    // and at most one switch every 3 epochs
    MinEpochRequests:      500,  // and ignore epochs with thin evidence
}

Ready-made policies

The core module has no dependencies. Ready-made arms live in a companion module, so you pull in a cache library only if you use one:

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

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

cache, err := ascache.NewAdaptiveCache(
    []ascache.Policy[string, int]{
        lru,
        twoQ,
        policies.NewRandomPolicy[string, int](10000),
        policies.NewTTL[string, int](10000, 5*time.Minute),
    },
    myBandit,
    &ascache.Settings{EpochDuration: time.Minute, ShadowSampleRate: 0.05},
)
Policy Constructor Notes
LRU policies.NewLRU hashicorp/golang-lru/v2
LFU policies.NewLFU this repository's O(1) LFU; strong on stationary popularity, weak when it shifts
2Q policies.NewTwoQueue scan-resistant; a scan cannot flush the working set
Random policies.NewRandomPolicy no bookkeeping; the control arm worth beating
TTL policies.NewTTL expiry as well as recency
ARC policies/arc.NewPolicy separate module — see below
W-TinyLFU policies/tinylfu.NewPolicy separate module; the strongest baseline

Random is worth keeping in the mix precisely because it assumes nothing: a policy that cannot beat random on your traffic is not earning its bookkeeping.

ARC is a separate module
go get github.com/sshaplygin/as-cache/policies/arc

ARC is patented by IBM (US 6,996,676), which is why upstream hashicorp/golang-lru moved it to its own module in v2. This repository keeps that split, so importing policies never pulls a patented implementation into your build and the choice to use ARC is always explicit. Whether the patent still restricts anything is a question for you and your counsel.

Adapting your own cache

Any type satisfying Cacher[K, V] can be an arm. If your cache does not report evictions or cannot be resized — as 2Q and ARC do not — wrap it:

cache, err := policies.Adapt[string, int](size, func(size int) (policies.PartialCacher[string, int], error) {
    return mylib.New[string, int](size)
})

Note that Resize on an adapted cache rebuilds it, discarding whatever adaptation the algorithm had learned. AdaptiveCache resizes shadow policies when its own capacity changes, so adapted policies are heavier arms to carry than natively resizable ones.

W-TinyLFU
go get github.com/sshaplygin/as-cache/policies/tinylfu

Carried in its own module so otter and its dependencies stay out of builds that do not use it. This is the arm worth including if the question is whether an adaptive cache beats the state of the art rather than whether it beats LRU.

Note that otter reports an approximate size, so this policy's Len() is approximate. Set EvictPartialCapacityFilling: true when using it, since the capacity gate compares Len() against Cap() for exact equality.

Advisor mode

The safest way to adopt this library is not to let it switch anything. In ObserveOnly mode the cache behaves exactly like the first policy you give it -- nothing ever migrates, nothing ever switches -- while every other policy is measured in the background against your real traffic.

cache, err := ascache.NewAdaptiveCache(
    []ascache.Policy[string, int]{lru, twoQ, tinyLFU},
    nil, // observing needs no bandit
    &ascache.Settings{
        EpochDuration:    time.Minute,
        ObserveOnly:      true,
        ShadowSampleRate: 0.05,
    },
)

// ... later, after real traffic ...
fmt.Println(cache.Advice())

On this traffic TwoQueue beats LRU by 3.28 points of hit rate, over 240 epochs.
Rates are estimated from 5.0% of the keyspace.

policy      hit rate         hits       misses
 TwoQueue      59.62%       596200       403800
*LRU           56.34%       563400       436600
 Random        54.80%       548000       452000

* currently active

That answers a question that is otherwise expensive to ask, at no risk: you learn whether a different eviction policy would serve your traffic better, and by how much, without changing what your cache does. Acting on the answer is then your choice -- switch to that policy directly, or turn ObserveOnly off and let the bandit do it.

Advice() is safe to call at any time. Check Epochs before believing it: a handful of epochs is not evidence.

Observability

A cache that changes its own eviction policy needs to be visible in staging. The metrics module turns the cache's accounting into a scrapeable snapshot and publishes it via expvar (standard library only):

go get github.com/sshaplygin/as-cache/metrics

if err := metrics.Publish("cache", myCache); err != nil {
    log.Panic(err)
}
// snapshot now appears in /debug/vars under "cache"

metrics.Take(cache) returns the same data as a struct if you would rather feed it somewhere else. The series worth graphing is active_policy over time; the one worth alerting on is improvement, which measures how much hit rate the cache is currently leaving on the table.

For Prometheus, wrap metrics.Take in a collector -- how metrics are named and labelled belongs to your application, not to a cache library, so this package does not impose a dependency on it.

Running a fleet

One replica of a service sees one replica's traffic. If you run fifty of them behind a load balancer, each cache sees a fiftieth of the requests, and the "you cannot give it enough traffic per epoch to measure anything" caveat above stops being about your traffic and starts being about how it was divided.

The bandit module pools that evidence back together through Valkey or Redis. Each replica publishes its per-epoch counts; one replica per coordination epoch reads the fleet's aggregate, chooses, and publishes the choice for the others to apply.

client := goredis.NewClient(&goredis.Options{Addr: "valkey:6379"})
store, err := redisstore.New(redisstore.Options{Client: client})
if err != nil {
    return err
}
defer store.Close()

b, err := bandit.NewDistributed(bandit.Config{
    Store:             store,
    Namespace:         "sessions",
    CoordinationEpoch: time.Second,
})
if err != nil {
    return err
}
defer b.Close()

cache, err := ascache.NewAdaptiveCache(arms, b, &ascache.Settings{
    EpochDuration: 50 * time.Millisecond,
})

Read the fleet evidence below before reaching for it. The answer is yes in one specific regime -- replicas individually too starved of traffic to rank their own arms -- and no everywhere else, and which case you are in is measurable in advance.

Two clocks, not one. EpochDuration is how often each cache measures; CoordinationEpoch is how often the fleet decides. They are deliberately different scales. Cache epochs are tuned in tens of milliseconds, which is below both a round trip to the store and any clock agreement a fleet can be assumed to have. Measure on the fast clock, coordinate on the slow one; a second is a sensible starting point.

No replica's clock is ever consulted. Buckets are derived from the store's clock inside a Lua script, so a fleet needs no clock synchronisation at all and a machine with a skewed clock cannot write its counts into a window nobody reads.

Nothing touches the network on the cache's path. The cache calls its bandit while holding its write lock, so a round trip there would stall every Get in the process — and Go's RWMutex queues readers behind a waiting writer, so a store that hangs would hang the cache. RecordEpoch folds numbers into a buffer and SelectPolicy is an atomic load; all I/O happens on the bandit's own goroutine, once per coordination epoch.

When the store is unreachable, each replica falls back to a local Thompson bandit fed by its own reports, which is exactly the behaviour of a cache that was never distributed. Nothing fails and nothing blocks. Counts measured during the outage are discarded rather than replayed on recovery — evidence that arrives in the wrong window is worse than no evidence. Snapshot().Fallback is the field to alert on: the cache looks entirely healthy either way.

Only integers cross the wire. Per-policy hit and miss counts, a node id and a policy name. No cache keys and no cache values ever leave the process. Everything written carries a TTL, so a fleet that stops running leaves nothing behind.

Requires Redis 7.0 or Valkey 7.2 and above. docker-compose.yml brings up both for local testing; make redis-test runs the store suite against each.

Which replicas pool with which

Pooling is only meaningful between caches measuring the same thing. A hit rate from a 1000-entry cache says nothing about a 100-entry one, and averaging them describes neither — with nothing in the numbers to show it happened.

So Namespace is not the whole key. A fingerprint of each cache's measurement regime — its arms, its capacity and its sample rate — is appended to it, and replicas that share a name without sharing a regime pool separately rather than pooling wrongly. Snapshot().Namespace and Snapshot().Regime are where to look when a fleet has unexpectedly split in two. Epoch duration deliberately is not part of it: a replica reporting twice as often contributes twice the counts at the same rate, and rates are what the comparison is made on.

The two modes

ModeLeader (the default) elects one replica per coordination epoch to decide for everyone, so the fleet runs one policy at a time. ModeSharedPosterior has every replica draw its own selection from the pooled evidence, so no election happens and replicas may run different policies indefinitely.

Leader election is the default for a reason that is not obvious. The active arm on a replica is measured at full capacity while every shadow runs on a miniature, and shadows measure a point or two pessimistic. Under leader election every replica has the same arm in the flattering role, so the bias applies uniformly and largely cancels when the counts are summed. Under shared-posterior selection it does not: an arm active on most of the fleet is mostly measured in the flattering role, so it accumulates an advantage in proportion to how widely it is already deployed. EvidenceShadowOnly removes that feedback by discarding active-role counts, which is why it is available under shared-posterior selection and rejected under leader election — where the fleet-wide active policy is nobody's shadow and would have no evidence at all.

Pooling changes how much evidence a posterior sees

A Beta posterior narrows with the square root of what it has seen, and a fleet supplies evidence in proportion to its size. A thousand replicas produce posteriors sharp enough that every Thompson draw returns the same arm — the bandit stops exploring precisely at the scale where missing a workload change is most expensive. MaxEvidence caps the effective sample size, keeping the measured rate and discarding the surplus certainty. The default puts an arm's posterior standard deviation at about a sixth of a percentage point.

Decay works the same way for the same reason: a shared counter cannot be decayed in place, because every replica applying the multiplication would compound it once per replica and a fleet of fifty would forget fifty times faster than a fleet of one. The store holds plain per-bucket sums and the weighting happens on read, so the arithmetic is identical at any fleet size.

Evidence

make evidence replays a suite of deterministic workloads against every policy and against the adaptive cache. The numbers below are from an M1 Max, cache capacity 500, 200k requests per workload. Reproduce with make evidence; the generators are in bench/workload.go.

Hit rate by policy and workload:

Workload LRU LFU 2Q ARC Random W-TinyLFU
zipf (skewed popularity) 66.9% 73.5% 72.0% 73.2% 62.6% 73.3%
uniform (no structure) 10.0% 10.0% 10.0% 10.0% 10.1% 12.3%
loop (cycle just over capacity) 0.0% 0.0% 68.6% 0.1% 82.1% 94.0%
scan (hot set + sweeps) 30.0% 40.0% 40.0% 40.0% 32.0% 39.7%
phase-shift (alternating regimes) 34.5% 69.7% 61.5% 39.9% 68.2% 82.1%

Two things stand out. LRU and LFU both score exactly zero on loop, where a cyclic scan just over capacity evicts every key immediately before it is needed again -- that is the textbook pathology, and it is worth knowing your workload is not that shape. And W-TinyLFU wins or ties nearly everywhere here.

Does adaptive selection beat picking one policy?

On these workloads: no, and this is the honest result.

Workload Adaptive Best fixed Worst fixed Adaptive vs best
zipf 73.3% LFU 73.5% 62.6% -0.2 pts
uniform 10.0% W-TinyLFU 12.3% 10.0% -2.3 pts
loop 77.5% W-TinyLFU 94.0% 0.0% -16.5 pts
scan 38.9% LFU/2Q/ARC 40.0% 30.0% -1.1 pts
phase-shift 78.8% W-TinyLFU 82.1% 34.5% -3.3 pts

Adaptive selection reliably beats the worst fixed choice, sometimes hugely (77.5% against LRU's 0.0% on loop). It never meaningfully beats the best one. Even on phase-shift -- the workload built specifically to need adaptation -- a fixed W-TinyLFU wins by 3.8 points.

The timeline explains why. Replaying phase-shift and sampling ActivePolicy() throughout:

phase      Z------L------Z------L------Z------L------Z------L------   (Z = zipf, L = loop)
LRU        ###
TwoQueue      #######
ARC                  ##
TinyLFU          #########################################################

share of time active: LRU 2%, TwoQueue 6%, ARC 1%, TinyLFU 90%

The bandit works exactly as designed: it explores, identifies W-TinyLFU, and holds it for 90% of the run. It does not oscillate at phase boundaries, because there is no crossover to exploit -- W-TinyLFU is the best arm in both regimes. The remaining gap is the price of exploring and of migrating between arms.

So the case for this library is not "it beats the best policy." It is:

  • You do not know which policy is best for your traffic, and the cost of guessing wrong is large (0.0% vs 94.0% on loop). Adaptive selection bounds that downside without requiring you to know.
  • It tells you what to use. The most valuable output may be the measurement rather than the switching -- see advisor mode.

For a workload that genuinely crosses over, the picture could differ. These are synthetic, and the section below shows real traces overturning the conclusion.

Real traces

./scripts/fetch-traces.sh downloads five published traces (nothing is committed -- see docs on traces), then AS_CACHE_TRACES=... make evidence replays them. Adaptive here runs a 50ms epoch with warm migration and ShadowSampleRate: 0.05:

Trace Requests Best fixed Worst fixed Adaptive Delta
Twitter Twemcache cluster052 1.0M 2Q 59.6% LFU 41.4% 59.4% -0.25 pts
ARC OLTP (FAST '03) 0.9M 2Q 68.3% LFU 45.4% 67.1% -1.19 pts
ARC P3 (FAST '03) 2.0M W-TinyLFU 11.7% LRU 1.9% 12.7% +0.92 pts
LIRS 2_pools 100k W-TinyLFU 54.8% Random 50.1% 54.4% -0.36 pts
LIRS loop 505k W-TinyLFU 45.9% LRU/LFU 0.0% 42.5%* -3.43 pts

* loop needs a 2ms epoch: it is short and changes character quickly, so a 50ms epoch gives the bandit too few epochs to react and it drops to 33.3%.

Note that the best fixed policy is not the same policy across traces. On OLTP, W-TinyLFU -- the strongest general-purpose baseline -- comes second to last at 63.2% while 2Q wins at 68.3%. That is the case for not committing to a policy in advance, and it does not show up on synthetic workloads, where W-TinyLFU wins nearly everything.

LFU is the sharpest illustration of why synthetic workloads mislead. It is the best policy on synthetic zipf (73.5%) and the worst on both large real traces (41.4% on Twitter, 45.4% on OLTP). Synthetic Zipf holds popularity stationary, which is exactly the assumption classic LFU makes; real traffic shifts, and an entry that was hot once keeps a frequency count that holds it resident long after it stops being useful. That is the failure W-TinyLFU's aged frequency sketch exists to avoid, and it is invisible until you replay real traffic.

Configuring it

The epoch duration is the setting that matters most, and the failure mode is not subtle. Measured on the ARC P3 trace with a 20k-entry cache:

Configuration Hit rate ns/op
50ms epoch, warm migration 12.2% 540
2ms epoch, warm migration 4.8% 13,476
2ms epoch, cold migration 0.9% 580

An epoch short enough to trigger frequent switches makes the cache copy its entire contents on every switch, so it spends its time migrating rather than serving. Cold migration is worse: it discards the cache at each switch, which on the OLTP trace costs 28 points.

Rules of thumb:

  • Make the epoch long enough that migrating the cache is a small fraction of the work done in it, and short enough that the workload sees many epochs.
  • Prefer MigrationWarm. MigrationCold is only reasonable if switches are rare.
  • The stability gates help on steady traffic and hurt on fast-changing traffic -- they cost 37 points on loop, which needs to re-adapt constantly.
Does sampling distort the comparison?

Sampled shadows are only sound if a miniature ranks policies the way full-size shadows would. Measured directly across four sample rates, against full-size shadows as ground truth:

zipf   full-size  ARC=81.4% 2Q=81.2% LFU=81.0% TTL=79.2% LRU=79.2% W-TinyLFU=79.1% Random=22.5%
       rate 0.05  ARC=66.1% 2Q=66.0% LFU=65.6% W-TinyLFU=64.4% LRU=62.5% TTL=61.6% Random=22.2%
       rate 0.10  ARC=85.4% 2Q=85.4% LFU=85.2% W-TinyLFU=84.1% TTL=83.8% LRU=83.7% Random=38.1%
       rate 0.30  ARC=77.7% 2Q=77.5% LFU=77.4% W-TinyLFU=76.5% LRU=75.3% TTL=75.0% Random=20.8%
       rate 0.50  ARC=84.7% 2Q=84.6% LFU=84.4% W-TinyLFU=82.9% LRU=82.9% TTL=82.9% Random=22.3%

scan   full-size  2Q=28.3% ARC=28.3% LFU=28.3% W-TinyLFU=27.2% TTL=21.4% LRU=21.4% Random=17.0%
       rate 0.05  2Q=26.4% ARC=26.4% LFU=26.4% W-TinyLFU=24.0% TTL=19.9% LRU=19.9% Random=16.2%
       rate 0.10  2Q=29.6% ARC=29.6% LFU=29.6% W-TinyLFU=28.9% LRU=22.4% TTL=22.4% Random=17.7%
       rate 0.30  2Q=28.9% ARC=28.9% LFU=28.9% W-TinyLFU=27.8% LRU=21.8% TTL=21.8% Random=17.3%
       rate 0.50  2Q=28.2% ARC=28.2% LFU=28.2% W-TinyLFU=25.8% TTL=21.4% LRU=21.4% Random=17.0%

Sampling picks the same best policy at every rate, on both workloads -- zero regret, including at the aggressive 5%. Every clearly separated pair of arms is ranked the same way sampled as full-size: 0 inversions out of 3 pairs on zipf and 6 on scan, at all four rates.

What sampling does not give you is an estimate of the absolute hit rate. Read the zipf rows down the rate column: ARC measures 66% at rate 0.05 and 85% at rate 0.10, against 81% full-size. The estimate depends on which slice of the keyspace the seed happened to select, and a different slice has different reuse, so a sampled rate can land either side of the true one. Do not read a shadow's absolute number as a prediction of what that policy would achieve.

That is fine for the purpose, because the bandit only ever needs to know which arm is better, never by how much in absolute terms. It is not fine if you were planning to quote a shadow's hit rate as a forecast -- for that, run the policy for real, or set ShadowSampleRate to 0 and pay for full-size shadows.

Higher rates cost more and buy no better ranking here, so 0.05 is a reasonable default. Raise it if your keyspace is small enough that 5% of it is only a handful of keys -- MinShadowCapacity guards the degenerate end by raising the effective rate rather than letting a miniature shrink into noise.

Does pooling across a fleet help?

Only in the regime it was built for, and it is worth checking you are in that regime before turning it on. All figures are 8 replicas, cache capacity 300 to 500, make evidence.

The case it exists for is a replica that sees too little traffic per epoch to rank its own arms. Reproducing that requires holding each replica to a request rate — an unpaced replay delivers thousands of requests per epoch however small the workload is, it just finishes sooner. Paced to roughly 8 requests per cache epoch per replica:

Setup Hit rate Policies in use at the end
best fixed (ARC) 62.8% 1
pooled, leader-elected 58.3-59.5% 1-2
each replica deciding alone 55.5-55.9% 5

Pooling gains 2.3 to 3.9 points over independent replicas, across four runs. The last column is the mechanism: a replica with eight requests an epoch cannot tell its arms apart, so the fleet scatters across five different policies, several of them poor. Pooled, the fleet has 64 requests an epoch of evidence and stays on one.

Now the same comparison where replicas are not starved — the unpaced replays every other measurement here uses:

Workload Pooled Deciding alone Best fixed
zipf, split evenly 68.2% 70.4% 73.0%
zipf, sharded by key 86.2% 87.4% LFU 88.2%
phase-shift 82.0% 82.0% 2Q 83.0%
mixed fleet (half loop, half zipf) 36.6% 41.7% —

Pooling loses whenever the replicas could already measure for themselves, by 1 to 2 points on uniform traffic and by 5.1 points on a fleet whose replicas serve different workloads. The mixed-fleet row is the clearest: a fleet-wide decision is a compromise, and when half your replicas want the policy the other half are worst served by, forcing agreement costs more than the disagreement did.

Most of the loss on uniform traffic is the fleet simply getting fewer chances to change its mind:

local (no coordination):     70.42%
coordination epoch 10ms:     70.01%  (-0.41)
coordination epoch 25ms:     69.75%  (-0.67)
coordination epoch 50ms:     68.20%  (-2.21)
coordination epoch 200ms:    66.95%  (-3.47)

The gap closes monotonically as coordination speeds up — but it closes towards break-even, never past it, and a 10ms coordination epoch is where a real round trip stops being negligible. Note that these replays coordinate through an in-process store, so coordination is free in a way it will not be for you: the setting that looks best here is the one that costs most to run.

So the rule is: pool when your replicas are individually starved of traffic, run the same workload shape as each other, and are numerous enough that the pooled evidence is meaningfully thicker. Otherwise let each replica decide alone — it is simpler, it needs no store, and on this evidence it is also better. Advice() in observe-only mode will tell you which case you are in before you deploy anything.

What is not done

  • Reads take a lock. Every read delegates to the active policy under the cache's RWMutex. Serving them from an atomic.Pointer instead would remove the cache's own share of the per-operation cost, but a retry protocol has to wrap all six read delegations, retries are not free of side effects (a retried read double-counts its own hit and double-bumps recency), and MigrationGradual cannot go lock-free at all, because promotion mutates from inside Get. Deferred as its own change rather than smuggled into another.
  • Epochs are wall-clock driven and cannot be stepped, so every measurement of the bandit is timing-sensitive. This is why the evidence suite is excluded from -race, and it makes the bandit awkward to test deterministically.
  • No adaptive sizing. The cache's capacity is whatever you set. Only the choice of policy adapts.
  • Nothing here has run in production that I know of.

References

License

Mozilla Public License 2.0.

MPL 2.0 is file-level copyleft. You may use this library in a closed-source application without opening your own code; if you modify one of these files and distribute the result, that file's source must be made available under the same licence. Each publishable module carries its own copy of the licence, because a Go module zip contains only its own directory.

Documentation

Overview

Package ascache is a cache that chooses its own eviction policy.

Choosing a replacement policy normally means guessing which one suits your traffic, and the cost of guessing wrong is large: on a cyclic access pattern just larger than the cache, LRU serves a 0% hit rate where W-TinyLFU serves 92%. This library removes the guess. It runs candidate policies side by side, measures them against your real traffic, and either tells you which one wins or switches to it for you.

How it works

One policy is active and serves real data. The others are shadows: they receive the same key stream with zero values, purely so their hit rates can be compared. Every epoch each policy reports what it measured to a Bandit, which picks the policy for the next epoch. 

cache, err := ascache.NewAdaptiveCache(
    []ascache.Policy[string, int]{lru, twoQ, tinyLFU},
    myBandit,
    &ascache.Settings{EpochDuration: time.Minute},
)
defer cache.Close()

The API is a superset of hashicorp/golang-lru/v2, so an existing cache can be swapped for one of these without changing call sites. AdaptiveCache.Stats, AdaptiveCache.Advice, AdaptiveCache.ActivePolicy and AdaptiveCache.Close are the additions.

Ready-made policies live in companion modules, so the core has no dependencies: github.com/sshaplygin/as-cache/policies for LRU, 2Q, Random and TTL, .../policies/arc for ARC, .../policies/tinylfu for W-TinyLFU.

Start by observing

The lowest-risk way to adopt this is not to let it switch anything. With Settings.ObserveOnly the cache behaves exactly like the first policy it was given, while every other policy is measured in the background, and AdaptiveCache.Advice reports what it found. No bandit is needed in this mode. 

cache, _ := ascache.NewAdaptiveCache(policies, nil, &ascache.Settings{
    EpochDuration: time.Minute,
    ObserveOnly:   true,
})
// ... later ...
fmt.Println(cache.Advice())

Cost

Shadow policies hold keys and eviction bookkeeping but never values, so they cost far less than a full copy: six policies measure at 2.65x the memory of one, and 1.32x with Settings.ShadowSampleRate set. Sampling has shadows track a deterministic fraction of the keyspace, which stops per-operation cost scaling with the number of policies.

What to expect

Adaptive selection reliably beats the worst policy you might have picked and lands close to the best. On published traces it comes within about a point of the best fixed policy and occasionally beats it, without being told in advance which that is. It will not dramatically outperform a policy you have already measured and know suits your traffic.

Epoch duration is the setting that matters most: too short and the cache spends its time migrating between policies rather than serving. See the README for measurements and configuration guidance.

Index

Constants

View Source 
const DefaultMinShadowCapacity = 256

DefaultMinShadowCapacity is the miniature capacity floor applied when Settings.MinShadowCapacity is zero.

Variables

View Source 
var ErrDuplicatePolicy = errors.New("duplicate policy type")

ErrDuplicatePolicy is returned by NewAdaptiveCache when two policies report the same PolicyType.

View Source 
var ErrEmptyPolicies = errors.New("must provide non zero policies size")

ErrEmptyPolicies is returned by NewAdaptiveCache when the policies slice is nil or empty.

View Source 
var ErrInvalidEpochDuration = errors.New("epoch duration must be positive")

ErrInvalidEpochDuration is returned by NewAdaptiveCache when Settings.EpochDuration is zero or negative: time.NewTicker panics on non-positive durations.

View Source 
var ErrNilBandit = errors.New("bandit must not be nil")

ErrNilBandit is returned by NewAdaptiveCache when the bandit is nil.

View Source 
var ErrNilPolicy = errors.New("policy must not be nil")

ErrNilPolicy is returned by NewAdaptiveCache when one of the provided policies is nil.

View Source 
var ErrNilSettings = errors.New("settings must not be nil")

ErrNilSettings is returned by NewAdaptiveCache when settings is nil.

Functions

This section is empty.

Types

type AdaptiveCache 

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

AdaptiveCache is a cache that automatically selects the best replacement policy at runtime using a Multi-Armed Bandit algorithm.

func NewAdaptiveCache 

func NewAdaptiveCache[K comparable, V any](
	policies []Policy[K, V],
	bandit Bandit,
	settings *Settings,
) (*AdaptiveCache[K, V], error)

NewAdaptiveCache validates its inputs and starts the background epoch goroutine. Callers must call Close to stop that goroutine.

func (*AdaptiveCache[K, V]) ActivePolicy 

func (c *AdaptiveCache[K, V]) ActivePolicy() PolicyType

ActivePolicy returns the PolicyType that is currently serving cache operations. It is safe to call concurrently.

func (*AdaptiveCache[K, V]) Add 

func (c *AdaptiveCache[K, V]) Add(key K, value V) bool

func (*AdaptiveCache[K, V]) Advice 

func (c *AdaptiveCache[K, V]) Advice() Advice

Advice reports which policy has served this cache's traffic best.

It is safe to call at any time and does not disturb measurement. The advice is only as good as the traffic behind it: a cache that has run for a few epochs, or one whose policies are within noise of each other, has nothing useful to say, and Epochs is included so a caller can tell.

func (*AdaptiveCache[K, V]) Close 

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

Close stops the background epoch goroutine and waits for it to exit. It is idempotent and safe to call concurrently; every call returns nil after the goroutine has stopped.

func (*AdaptiveCache[K, V]) Contains 

func (c *AdaptiveCache[K, V]) Contains(key K) bool

func (*AdaptiveCache[K, V]) Get 

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

func (*AdaptiveCache[K, V]) Keys 

func (c *AdaptiveCache[K, V]) Keys() []K

func (*AdaptiveCache[K, V]) Len 

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

func (*AdaptiveCache[K, V]) Peek 

func (c *AdaptiveCache[K, V]) Peek(key K) (value V, ok bool)

func (*AdaptiveCache[K, V]) Purge 

func (c *AdaptiveCache[K, V]) Purge()

func (*AdaptiveCache[K, V]) Remove 

func (c *AdaptiveCache[K, V]) Remove(key K) bool

func (*AdaptiveCache[K, V]) Resize 

func (c *AdaptiveCache[K, V]) Resize(size int) int

Resize sets the cache's capacity to size and returns the total number of entries evicted across all policies. Shadow policies are resized to the miniature capacity that corresponds to size rather than to size itself, so they stay faithful simulations of a cache of the requested capacity.

The sample rate itself is fixed for the life of the cache: changing it would change which keys are sampled, invalidating every shadow's accumulated state. The miniature capacity therefore follows the rate directly here, without the MinShadowCapacity floor that construction applies - see scaledCapacity.

func (*AdaptiveCache[K, V]) Stats 

func (c *AdaptiveCache[K, V]) Stats() GlobalStats

Stats returns the cumulative hits and misses served by the cache: totals folded up to the last reporting epoch (globalStats) plus the active policy's counters accumulated since then.

func (*AdaptiveCache[K, V]) Values 

func (c *AdaptiveCache[K, V]) Values() []V

type Advice 

type Advice struct {
	// Epochs is how many epochs actually measured something and fed this
	// advice. Advice from a handful of epochs is not worth acting on. It
	// counts reporting epochs rather than elapsed ticks, so an epoch the
	// capacity gate skipped is not counted as evidence.
	//
	// It resets to nothing for a policy that changes role, so shortly after a
	// switch the advice is deliberately thin rather than confidently stale.
	Epochs int64
	// Active is the policy serving requests.
	Active PolicyType
	// Best is the policy with the highest measured hit rate.
	Best PolicyType
	// Improvement is how many percentage points Best beats Active by. It is
	// zero when they are the same policy.
	Improvement float64
	// Sampled reports whether the measurements come from a sampled substream,
	// in which case the rates are estimates.
	Sampled bool
	// SampleRate is the fraction of the keyspace measured, 1 when sampling is
	// off.
	SampleRate float64
	// Reports holds every policy, best hit rate first.
	Reports []PolicyReport
}

Advice is what the cache has learned about which policy suits the traffic it has seen.

It is the answer to a question that is otherwise expensive to ask: not "is my cache fast" but "would a different eviction policy serve my traffic better, and by how much". Running in ObserveOnly mode makes that answerable without ever changing what the cache does.

func (Advice) String 

func (a Advice) String() string

String renders the advice as a short human-readable summary.

type Bandit 

type Bandit interface {
	// RecordStats delivers one policy's performance report. On every
	// reporting epoch each policy reports — the active policy included — so
	// implementations receive a full set of arms and must not synthesize
	// stats for the active arm themselves. When
	// Settings.EvictPartialCapacityFilling is false, epochs where the active
	// policy is not yet full skip reporting entirely; counters then
	// accumulate and the next report spans the skipped epochs.
	//
	// It is not called on a bandit that also implements EpochBandit; that
	// interface's RecordEpoch replaces it.
	RecordStats(stats ShadowStats)

	// SelectPolicy asks the bandit to choose which policy should become the
	// active one for the next epoch.
	//
	// Returning a policy the cache was not built with - Undefined included,
	// which is the natural answer from a bandit that has not yet formed an
	// opinion - is not an error and means no change.
	SelectPolicy() PolicyType
}

Bandit chooses which policy should be active, given what each has measured.

This package ships no implementation, because the choice of strategy is the interesting part and depends on how quickly the traffic changes. Ready-made ones live in the companion github.com/sshaplygin/as-cache/bandit module: a local Thompson sampler, and a distributed bandit that pools evidence across a fleet through Valkey or Redis.

Implementations must not block

Both methods are called from the epoch goroutine while it holds the cache's write lock, so for as long as either runs, every Get and Add in the process is stalled behind it. A bandit that talks to the network, reads a file, or waits on a channel must do it on its own goroutine and have these methods only exchange buffered state. This is not a performance guideline: Go's RWMutex queues new readers behind a waiting writer, so a multi-second timeout here is a multi-second outage for the whole cache.

type CacheStats 

type CacheStats interface {
	GetStats() PolicyStats
	ResetStats()
}

CacheStats is the hit/miss accounting a policy exposes so its performance can be compared with the other arms.

type CacheWrapper 

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

func NewCache 

func NewCache[K comparable, V any](
	cache Cacher[K, V],
	policy PolicyType,
	size int,
) *CacheWrapper[K, V]

func (*CacheWrapper[K, V]) Cap 

func (c *CacheWrapper[K, V]) Cap() int

func (*CacheWrapper[K, V]) Get 

func (c *CacheWrapper[K, V]) Get(key K) (value V, ok bool)

func (*CacheWrapper[K, V]) GetStats 

func (c *CacheWrapper[K, V]) GetStats() PolicyStats

func (*CacheWrapper[K, V]) GetType 

func (c *CacheWrapper[K, V]) GetType() PolicyType

func (*CacheWrapper[K, V]) Name 

func (c *CacheWrapper[K, V]) Name() string

func (*CacheWrapper[K, V]) ResetStats 

func (c *CacheWrapper[K, V]) ResetStats()

func (*CacheWrapper[K, V]) Resize 

func (c *CacheWrapper[K, V]) Resize(size int) int

Resize changes the wrapped cache's capacity and keeps Cap in step with it. The embedded Cacher's Resize would otherwise be promoted directly, leaving Cap reporting the capacity the wrapper was built with forever.

type Cacher 

type Cacher[K comparable, V any] interface {
	Add(key K, value V) (evicted bool)
	Contains(key K) bool
	Get(key K) (value V, ok bool)
	Keys() []K
	Len() int
	Peek(key K) (value V, ok bool)
	Purge()
	Remove(key K) (present bool)
	Resize(size int) (evicted int)
	Values() []V
}

Cacher is the cache interface an eviction policy must satisfy to be used as an arm. It is deliberately identical to the method set of hashicorp/golang-lru/v2, so an existing cache is usually already a Cacher, and so an AdaptiveCache is a drop-in replacement for one.

type EpochBandit added in v0.2.0 

type EpochBandit interface {
	Bandit

	// RecordEpoch delivers every arm's measurements for one reporting epoch.
	// The report and its Stats slice are freshly allocated for each call and
	// are never reused by the cache, so an implementation may retain them.
	//
	// The same non-blocking rule applies as to the rest of Bandit: this runs
	// under the cache's write lock.
	RecordEpoch(report EpochReport)
}

EpochBandit is an optional extension of Bandit for implementations that need to see a reporting epoch as a whole rather than as a sequence of per-policy calls.

RecordStats hands over one arm at a time with no epoch identifier, no marker for where one epoch ends and the next begins, and no indication of which arm was serving traffic. That is enough for a bandit that only accumulates posteriors, and not enough for one that has to publish an epoch's evidence somewhere else - which needs to know what to key it by, when the epoch is complete, and that the active arm's numbers were measured at full capacity while every shadow's were measured on a miniature.

A Bandit that implements this receives exactly one RecordEpoch call per reporting epoch and no RecordStats calls at all.

type EpochReport added in v0.2.0 

type EpochReport struct {
	// EpochID is the cache's epoch counter at the time of the report. It
	// counts ticks, including those the EvictPartialCapacityFilling gate
	// skipped, so consecutive reports are not necessarily consecutive IDs.
	// It is process-local: two caches in two processes share no origin, so it
	// orders one cache's reports and nothing more.
	EpochID int64

	// Active is the policy that was serving traffic during the epoch. Its
	// counts were measured at full capacity over the sampled substream; every
	// other arm's were measured on a miniature of that capacity. The rates are
	// comparable by construction, but not identically measured, and pooling
	// one arm's active-role numbers with another's shadow-role numbers gives
	// the active one a systematic advantage.
	Active PolicyType

	// Stats holds one entry per arm, ordered by PolicyType so the report is
	// reproducible, and carries the same counts RecordStats would have
	// delivered individually.
	Stats []ShadowStats

	// Capacity is the nominal capacity of the active policy: the size the
	// cache actually serves at.
	//
	// It is reported because a hit rate only means something alongside the
	// capacity it was measured at. A bandit pooling evidence from several
	// caches has to refuse to pool measurements taken at different sizes -
	// otherwise it averages a 1000-entry cache's hit rate with a 100-entry
	// cache's and acts on a number that describes neither.
	Capacity int

	// SampleRate is the fraction of the keyspace the measurements cover, 1
	// when Settings.ShadowSampleRate is off. Like Capacity, it is part of what
	// makes two caches' numbers comparable: shadows run as miniatures scaled
	// to this rate, so two caches sampling differently are simulating
	// different things.
	SampleRate float64
}

EpochReport is one reporting epoch's complete set of measurements, delivered to a bandit that implements EpochBandit.

It exists because the per-arm ShadowStats stream loses three things a bandit coordinating with anything outside the process needs: which epoch the numbers belong to, where the epoch ends, and which arm was active.

type GlobalStats 

type GlobalStats struct {
	Hits   int64
	Misses int64
}

GlobalStats holds aggregate hit/miss statistics exposed to callers.

type MigrationStrategy 

type MigrationStrategy uint

MigrationStrategy controls how key/value pairs are transferred when the active policy changes. 

const (
	// MigrationCold starts the new active policy from an empty state. This is
	// the simplest strategy but causes a temporary cache-miss spike after every
	// policy switch.
	MigrationCold MigrationStrategy = iota + 1

	// MigrationWarm copies all key/value pairs from the old active policy into
	// the new active policy at switch time. Shadow zero-value entries in the
	// target policy are purged first so that only real values are served.
	MigrationWarm

	// MigrationGradual lazily drains the old active policy into the new one.
	// During the window each Get() promotes the requested key from the old
	// policy into the new active — when it is still eligible (not overwritten
	// by a shadow Add, already promoted, or evicted from the source) — before
	// the lookup is counted, so served requests register as hits; each Add()
	// call migrates at most one additional key. While the window is open,
	// Get() takes the write lock, serializing reads.
	//
	// The window closes when no eligible keys remain, on Purge(), on the next
	// policy switch, and in any case at the next epoch boundary - a workload
	// that simply stops touching the pending keys must not leave it open
	// forever, holding the source at full capacity with its values retained.
	MigrationGradual
)

type Policy 

type Policy[K comparable, V any] interface {
	Cacher[K, V]

	// Cap reports the capacity. hashicorp/golang-lru/v2 has no such method,
	// but the adaptive layer needs it: shadow policies run at a reduced
	// capacity and are restored to their full one when promoted.
	Cap() int

	CacheStats
	GetType() PolicyType
}

Policy is a cache that can serve as one arm of an AdaptiveCache: a Cacher that also reports its capacity, its measurements, and which policy it is.

type PolicyReport 

type PolicyReport struct {
	// Policy is the arm this report describes.
	Policy PolicyType
	// Hits and Misses are the requests measured for this policy in its current
	// role - as the active policy, or as a shadow - since it last changed
	// role. Under ShadowSampleRate these are counts over the sampled
	// substream, not over all traffic: the rate is meaningful, the magnitude
	// is a sample.
	Hits   int64
	Misses int64
	// Active reports whether this policy was serving requests when the report
	// was taken.
	Active bool
}

PolicyReport is one policy's measured performance over the cache's lifetime.

func (PolicyReport) HitRate 

func (r PolicyReport) HitRate() float64

HitRate returns the fraction of measured requests this policy served, or 0 when it has measured nothing.

type PolicyStats 

type PolicyStats struct {
	Hits   int64
	Misses int64
}

type PolicyType 

type PolicyType uint

PolicyType identifies a cache replacement policy. 

const (
	// Undefined is the zero value and names no policy.
	Undefined PolicyType = iota
	// LRU evicts the least recently used entry.
	LRU
	// LFU evicts the least frequently used entry.
	LFU
	// TwoQueue evicts using the 2Q algorithm, which keeps a small recent-access
	// queue in front of a frequently-accessed queue so a scan cannot flush the
	// working set.
	TwoQueue
	// ARC evicts using Adaptive Replacement Cache, which balances recency
	// against frequency on its own. The algorithm is patented by IBM, so its
	// adapter lives in a separate module that nothing else depends on.
	ARC
	// Random evicts an arbitrary entry. It is a useful control arm: a policy
	// that cannot beat random on a workload is not earning its bookkeeping.
	Random
	// TTL evicts by expiry as well as by recency.
	TTL
	// TinyLFU evicts using the W-TinyLFU family, which gates admission on a
	// frequency sketch so a new key must earn its place against the entry it
	// would displace. It is the strongest general-purpose baseline in wide
	// use, and the one an adaptive cache has to beat to justify itself.
	TinyLFU
)

func (PolicyType) String 

func (i PolicyType) String() string

type Settings 

type Settings struct {
	EpochDuration time.Duration
	// EvictPartialCapacityFilling allows policy switching even when the cache
	// is not yet full.
	EvictPartialCapacityFilling bool
	// MigrationStrategy determines how data is moved when the active policy
	// changes. Defaults to MigrationCold (zero value).
	MigrationStrategy MigrationStrategy

	// MinHitRateImprovement is the hit-rate advantage, as an absolute
	// difference in [0,1], that the bandit's selection must hold over the
	// active policy in the epoch just measured before the switch is applied.
	// It damps oscillation between policies that perform almost identically.
	// Zero (the default) applies every selection the bandit makes.
	MinHitRateImprovement float64

	// SwitchCooldownEpochs is the number of epochs that must elapse after a
	// policy switch before another switch is allowed, counted from the last
	// switch or from cache creation if none has happened yet. Zero (the
	// default) allows a switch on every epoch.
	SwitchCooldownEpochs int64

	// MinEpochRequests is the number of requests (hits plus misses) both the
	// active policy and the candidate must have observed in the measured
	// epoch before a switch is allowed, so the cache does not react to a
	// handful of samples. Zero (the default) imposes no minimum.
	//
	// The requests counted are the ones the bandit sees, which under
	// ShadowSampleRate means sampled requests: at a rate of 0.05 a threshold
	// of 100 is reached after roughly 2000 real requests.
	MinEpochRequests int64

	// ShadowSampleRate is the fraction of the keyspace, in (0,1], that shadow
	// policies track. Shadows exist only to estimate a hit rate, and a hit
	// rate can be estimated from a sample: at 0.05 a shadow skips 95% of the
	// operations it would otherwise mirror, which is where the bulk of the
	// adaptive layer's overhead goes.
	//
	// Shadows shrink with the rate so each remains a faithful miniature of a
	// full-size cache, and every shadow samples the same keys so their hit
	// rates stay comparable. The active policy still serves every key; only
	// the measurement is sampled, and it is sampled for the active policy too
	// so that all arms carry equally weighted evidence.
	//
	// Zero (the default) means 1: shadows mirror every key, which is the
	// behaviour of earlier versions.
	ShadowSampleRate float64

	// ObserveOnly runs the cache as a measurement instrument: every policy is
	// still measured each epoch and reported to the bandit, but the active
	// policy never changes and no migration ever happens.
	//
	// This is the zero-risk way to adopt the library. The cache behaves
	// exactly like the single policy you gave it first, while Advice() answers
	// the question that is otherwise expensive to ask: would a different
	// eviction policy serve this traffic better, and by how much. Once the
	// answer is in, either switch to that policy directly or turn this off and
	// let the bandit do it.
	ObserveOnly bool

	// MinShadowCapacity is the floor on a shadow's miniature capacity. A
	// miniature of a handful of entries measures noise rather than a policy,
	// so when the sample rate would shrink a shadow below this floor the
	// effective rate is raised instead, up to the point where sampling
	// disables itself entirely. Zero (the default) applies
	// DefaultMinShadowCapacity.
	MinShadowCapacity int
}

Settings configures the behaviour of AdaptiveCache.

type ShadowStats 

type ShadowStats struct {
	Policy PolicyType
	Hits   int64
	Misses int64
}

ShadowStats holds one policy's hit/miss counts since its last report — normally one epoch, or several when reporting was skipped because the cache was not yet full (EvictPartialCapacityFilling=false). Every policy reports through this channel on each reporting epoch, the active policy included, so the bandit's posterior for the active arm does not go stale while reports flow.

Source Files

View all Source files

Directories

Path Synopsis
bandit module
redis module
lfu module
metrics module
policies module
arc module
tinylfu module

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.