Documentation
¶
Overview ¶
Package cache provides a generic, concurrency-safe LRU + TTL cache (Cache[K,V]) — a kernel primitive (stdlib-only, no domain vocabulary). It reuses the kernel clock so TTL expiry is testable. Fetch on a hit is allocation-free (map lookup + intrusive-list splice); Set allocates one entry per new key. Reads and writes are serialised by a single mutex. Fetch is named Fetch (not Get) because a hit mutates state (LRU promotion + counters).
Package cache — the New constructor configuration.
Package cache — the intrusive doubly-linked LRU node.
Package cache — the key/value pair carried out of the locked section so the OnEvict observer never runs while the cache mutex is held.
Package cache — the read-only counters snapshot.
Package cache — the S3-FIFO side of the policy: admission into the small or main queue, the hit counter, and the walk that picks a victim.
Package cache — the S3-FIFO ghost: the hashes of the keys probation evicted, bounded.
Package cache — the intrusive list each queue is.
Package cache — the eviction policies a Cache runs.
Package cache — Striped: independent Caches behind one hash, each with its own lock.
Index ¶
- type Cache
- func (c *Cache[K, V]) Delete(key K)
- func (c *Cache[K, V]) Expire() int
- func (c *Cache[K, V]) Fetch(key K) (value V, ok bool)
- func (c *Cache[K, V]) Keys() iter.Seq[K]
- func (c *Cache[K, V]) Len() int
- func (c *Cache[K, V]) Purge()
- func (c *Cache[K, V]) Set(key K, val V)
- func (c *Cache[K, V]) SetTTL(key K, val V, ttl time.Duration)
- func (c *Cache[K, V]) Stats() StatsValue
- type Config
- type Policy
- type StatsValue
- type Striped
- func (s *Striped[K, V]) Delete(key K)
- func (s *Striped[K, V]) Expire() int
- func (s *Striped[K, V]) Fetch(key K) (value V, ok bool)
- func (s *Striped[K, V]) Keys() iter.Seq[K]
- func (s *Striped[K, V]) Len() int
- func (s *Striped[K, V]) Purge()
- func (s *Striped[K, V]) Set(key K, val V)
- func (s *Striped[K, V]) SetTTL(key K, val V, ttl time.Duration)
- func (s *Striped[K, V]) Stats() StatsValue
- func (s *Striped[K, V]) Stripes() int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache[K comparable, V any] struct { // contains filtered or unexported fields }
Cache is a generic LRU+TTL cache safe for concurrent use. The zero value is NOT usable — construct with NewCache.
func NewCache ¶
func NewCache[K comparable, V any](cfg Config[K, V]) *Cache[K, V]
NewCache builds a Cache from cfg. A nil cfg.Clock defaults to clock.System.
func (*Cache[K, V]) Delete ¶
func (c *Cache[K, V]) Delete(key K)
Delete removes key if present. An explicit Delete does NOT fire OnEvict (that hook is for capacity/expiry removals only).
func (*Cache[K, V]) Expire ¶ added in v0.27.0
Expire removes every entry whose deadline has passed and reports how many it removed. Each counts as an eviction and reaches OnEvict after the lock is released, as a lazy expiry does. The cache starts no goroutine: the caller decides when, and how often, to call it — on a ticker of its own, or on its scheduler. It costs O(k log n) for k expired entries; an entry without a deadline costs nothing, and a cache without any reads no clock.
func (*Cache[K, V]) Fetch ¶
Fetch returns the value for key and whether it was present and unexpired. A hit promotes the entry to most-recently-used (hence Fetch, not a pure Get).
func (*Cache[K, V]) Keys ¶ added in v0.27.0
Keys yields the keys present and unexpired when the loop starts, in no particular order. They are copied under the read lock and yielded after it is released, so the loop's body may call the cache — Set, Delete, Fetch — without deadlocking; what the body changes is not seen by the loop. A walk is not a read: no entry is promoted and no counter moves. Each loop allocates one slice of the keys.
func (*Cache[K, V]) Len ¶
Len returns the current live entry count (including not-yet-reaped expired entries — expiry is lazy unless Expire runs).
func (*Cache[K, V]) Purge ¶
func (c *Cache[K, V]) Purge()
Purge drops every entry without firing OnEvict.
func (*Cache[K, V]) Set ¶
func (c *Cache[K, V]) Set(key K, val V)
Set stores key=val with the cache's default TTL.
func (*Cache[K, V]) SetTTL ¶
SetTTL stores key=val with an explicit ttl (0 = no expiry), overriding the default for this entry only.
func (*Cache[K, V]) Stats ¶
func (c *Cache[K, V]) Stats() StatsValue
Stats returns a point-in-time copy of the hit/miss/eviction counters.
type Config ¶
type Config[K comparable, V any] struct { // MaxEntries caps the live entry count (LRU eviction above it). 0 = unbounded. MaxEntries int // DefaultTTL applies to Set entries (SetTTL overrides per-entry). 0 = no expiry. DefaultTTL time.Duration // Clock is the time source (injectable for tests). nil = clock.System. Clock clock.Clock // OnEvict, if non-nil, is called with the key+value of every entry removed by // capacity eviction or expiry (not by an explicit Delete/Set-overwrite). OnEvict func(key K, val V) // MaxWeight caps the summed weight of the live entries, evicting above it as // MaxEntries does; both apply when both are set. 0 = unbounded. An entry // heavier than MaxWeight alone is stored and evicts every other entry: the // primitive has no error to refuse it with. MaxWeight int64 // WeightOf, if non-nil, weighs an entry when it is stored; a negative answer // counts as 0, and one above math.MaxInt32 as math.MaxInt32. nil = every // entry weighs 1, so MaxWeight is then a count. WeightOf func(key K, val V) int64 // Policy chooses the victim when the cache is full. The zero value is // PolicyLRU. Policy Policy }
Config parameterises a Cache. The zero value is valid: an unbounded cache with no default TTL, the system clock, and no eviction callback.
type Policy ¶ added in v0.27.0
type Policy uint8
Policy chooses which entry a full Cache evicts. The zero value is PolicyLRU, today's behaviour; an unknown value runs as PolicyLRU, and Stats says which policy runs.
const ( // PolicyLRU evicts the least-recently-used entry: every hit moves its entry // to the front. A scan of cold keys longer than the capacity flushes the // whole hot set. PolicyLRU Policy = iota // PolicyS3FIFO is S3-FIFO (Yang et al., SOSP 2023): a new key enters a small // probationary FIFO holding a tenth of the capacity; one hit there promotes // it to the main FIFO when it reaches the tail, none sends its key to a // bounded ghost set, and a key the ghost remembers is admitted straight into // main. A one-time scan therefore churns the small queue and leaves the hot // set in main. A hit only sets a counter — it moves nothing. PolicyS3FIFO )
type StatsValue ¶
type StatsValue struct {
Hits uint64
Misses uint64
Evictions uint64
// Weight is the summed weight of the live entries when the cache weighs
// them — Config.MaxWeight or Config.WeightOf set — and 0 when it does not.
Weight int64
// Policy is the eviction policy that runs: Config.Policy, or PolicyLRU
// for a value the cache does not know.
Policy Policy
}
StatsValue is a point-in-time copy of a Cache's counters. Hits/Misses count Fetch outcomes; Evictions counts capacity + expiry removals (not explicit Deletes).
type Striped ¶ added in v0.27.0
type Striped[K comparable, V any] struct { // contains filtered or unexported fields }
Striped spreads its keys over independent Caches — stripes — each behind its own lock, so goroutines working on keys of different stripes never wait for one another. A key always lands in the same stripe, chosen by a hash of the key.
Each stripe holds an equal share of MaxEntries and MaxWeight, at least one unit when the bound is set: the policy is exact within a stripe and approximate across them — the victim is the least-recently-used entry of the stripe that overflowed, not of the whole cache. OnEvict fires per stripe, outside that stripe's lock, as a Cache fires it. With one stripe a Striped behaves exactly as one Cache.
The zero value is NOT usable — construct with NewStriped.
func NewStriped ¶ added in v0.27.0
func NewStriped[K comparable, V any](cfg Config[K, V], stripes int, hash func(key K) uint64) *Striped[K, V]
NewStriped builds a Striped of the given number of stripes from cfg, whose bounds it divides between them. A stripe count below 1 is 1. A nil hash uses hash/maphash over a seed drawn for this Striped alone.
func (*Striped[K, V]) Delete ¶ added in v0.27.0
func (s *Striped[K, V]) Delete(key K)
Delete removes key from its stripe, without firing OnEvict.
func (*Striped[K, V]) Expire ¶ added in v0.27.0
Expire sweeps every stripe, one lock at a time, and reports how many entries it removed in total.
func (*Striped[K, V]) Fetch ¶ added in v0.27.0
Fetch returns the value for key and whether it was present and unexpired, from key's stripe, recording the hit as that stripe's policy does.
func (*Striped[K, V]) Keys ¶ added in v0.27.0
Keys yields the keys of every stripe, a stripe at a time, each stripe's copied under its read lock and yielded after it is released, as Cache.Keys does, so the loop's body may call s. The stripes are read one after another, so under concurrent writes the walk is no single instant's.
func (*Striped[K, V]) Len ¶ added in v0.27.0
Len returns the live entry count summed over the stripes. The stripes are read one after another, so under concurrent writes the sum is no single instant's.
func (*Striped[K, V]) Purge ¶ added in v0.27.0
func (s *Striped[K, V]) Purge()
Purge drops every entry of every stripe without firing OnEvict.
func (*Striped[K, V]) Set ¶ added in v0.27.0
func (s *Striped[K, V]) Set(key K, val V)
Set stores key=val in key's stripe with the default TTL.
func (*Striped[K, V]) SetTTL ¶ added in v0.27.0
SetTTL stores key=val in key's stripe with an explicit ttl (0 = no expiry).
func (*Striped[K, V]) Stats ¶ added in v0.27.0
func (s *Striped[K, V]) Stats() StatsValue
Stats returns the counters summed over the stripes, read one after another.