ascache

package module
v0.3.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.

One policy is active and serves every request. The others run as shadows: they see each key, never its value, and answer "would I have had this?" Once per epoch every arm reports its hit rate, a bandit names the winner, and the cache switches if the win is worth the migration. Full mechanism in docs/design.md.

Documentation

Document Contents
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, adapting your own cache
Advisor mode ObserveOnly, Advice(), and the metrics module
Evidence Every measured claim: policy tables, competing libraries, real traces, sampling fidelity, fleets
Benchmarking Reproducible replays, benchclient, make evidence
Running a fleet Pooling evidence across replicas through Valkey or Redis

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 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 the 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. Read tuning 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 -- 2.65x for six policies, 1.32x with sampling on. Per-operation cost is 32 ns/op for a single LRU against 82 sampled and 618 unsampled; the full tables have the details.

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.

Usage

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")

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

Policies

Policy Constructor Notes
LRU policies.NewLRU via hashicorp/golang-lru/v2
LFU policies.NewLFU native O(1) implementation in lfu/
2Q policies.NewTwoQueue scan-resistant
Random policies.NewRandomPolicy the control arm worth beating
TTL policies.NewTTL expiry as well as recency
ARC policies/arc.NewPolicy separate module — patented by IBM
W-TinyLFU policies/tinylfu.NewPolicy separate module; the strongest baseline

Details and caveats in docs/policies.md.

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
Advice() Advice Which policy is winning, and by how much
ActivePolicy() PolicyType Which policy is currently serving requests
Close() error Stop the background epoch goroutine

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, or epoch requests must be set",
)

ErrInvalidEpochDuration is returned by NewAdaptiveCache when neither epoch clock is set: Settings.EpochDuration is zero or negative and Settings.EpochRequests is zero, so nothing would ever end an epoch.

View Source 
var ErrInvalidEpochRequests = errors.New("epoch requests must not be negative")

ErrInvalidEpochRequests is returned by NewAdaptiveCache when Settings.EpochRequests is negative.

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)

Get returns the value stored for key by the active policy, feeding the same lookup to every shadow policy that samples the key.

When Settings.EpochRequests is set, the call that completes an epoch runs it here, after every lock this method took has been released - runEpoch needs the write lock, and a Get still holding the read lock would deadlock against it.

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 is how often the cache re-evaluates its policies on a
	// wall clock. Either this or EpochRequests must be set; setting both
	// applies both, and whichever comes first ends the epoch.
	EpochDuration time.Duration

	// EpochRequests ends an epoch every N Get calls instead of on a clock.
	//
	// Wall-clock epochs make a cache's behaviour depend on how fast the
	// machine runs it: replaying one trace twice re-evaluates a different
	// number of times, so the hit rate moves between runs and cannot be
	// compared with anything. Counting requests removes the clock from the
	// measurement entirely - the same trace produces the same epochs, the
	// same switches and the same hit rate on any machine, which is what a
	// benchmark or a regression test needs.
	//
	// Get is the unit because Get is what produces evidence: hits and misses
	// are recorded there and nowhere else, so this counts exactly the
	// requests the bandit is shown. A workload that only writes never ends an
	// epoch, which is correct - there is nothing to compare policies on.
	//
	// The epoch runs on the goroutine that happens to make the Nth Get, so
	// that one call pays for the switch and any migration it triggers. In
	// production prefer EpochDuration, which keeps that work on the
	// background goroutine. Zero (the default) disables request counting.
	EpochRequests int64
	// 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
benchclient 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.