Documentation
¶
Overview ¶
Package sfcache provides a local, thread-safe, fixed-size cache for expensive lookups with single-flight deduplication.
Concurrent callers asking for the same key share a single lookup: one goroutine calls the external service and the others wait for its result. Values are cached for a TTL, the capacity is bounded, and an optional stale-if-error window keeps serving the last known good value while the upstream is down.
Usage ¶
The value type is inferred from the lookup function, so Cache.Lookup returns typed values with no assertions:
cache := sfcache.New(func(ctx context.Context, key string) (*Customer, error) {
return fetchCustomer(ctx, key)
}, sfcache.Config{Size: 256, TTL: 5 * time.Minute})
customer, err := cache.Lookup(ctx, "customer:123")
Settings that do not depend on the cache types live in Config; those that do live in options (WithTTLFunc).
Caching ¶
Only successful lookups are cached, for Config.TTL (a nil value is a value). Errors are shared with the callers coalesced onto the same lookup but never cached, so the next call retries; the failed key leaves an already-expired entry behind until it is reclaimed or overwritten. A lookup that failed with its OWN context's error publishes nothing at all. Whatever the lookup function returns is passed through as-is, including a non-nil value alongside a non-nil error.
A Config.TTL <= 0 serves no value from the cache and only coalesces, unless WithTTLFunc gives the entry a positive TTL. With stale-if-error enabled the last value is still retained and can be served after a failed refresh.
Expiration uses the monotonic clock, which on most platforms does not advance while the system is suspended: TTLs are effectively extended by the suspended time.
Cached values are shared by reference: treat them as read-only.
Capacity ¶
Config.Size bounds the values held, not Cache.Len. Len can exceed Size by the number of lookups in flight, plus the residue of a failed lookup, plus one value when a stale revive can evict nothing. The excess is reclaimed as those lookups complete and the next value is stored.
A store may only evict something worth less than what it stores:
- a failed lookup stores no value, so it reclaims only entries that hold nothing worth keeping, and otherwise leaves the cache over capacity;
- a stale revive may also take a value that is itself being served stale: the one no caller has asked for, or else the one closest to its own deadline. When it can take nothing it exceeds the capacity by one value, reclaimed by the next successful store;
- only a successful lookup may displace a valid entry, taking the one closest to expiring.
A lookup that is merely attempted, and may yet fail, can never cost the cache a live value.
Every entry is held in one of three queues, in deadline order, so an eviction takes the head of a queue rather than searching for it. A store costs O(log Size) holding the exclusive write lock, and one with no victim it may take says so in constant time. Cache hits take only the read lock.
Cache.PurgeExpired is the only linear pass. It sifts entries out one at a time while few have expired, and past a fraction of the queue rebuilds the heap around the survivors instead, so its cost is then bounded by what the cache HOLDS rather than by what it removes. It holds the exclusive write lock throughout: on a cache whose entries all expire together it is the longest lock this package takes.
The queues hold a copy of each key, so they cost about sizeof(K) + 16 bytes per entry on top of the value: roughly 27 for a word-sized key, 35 for a string key.
Single flight and context ¶
The external lookup runs under the context of the caller that started it. A caller that finds a lookup already in flight for its key waits for it and takes its result, which under heavy churn may come from a later flight than the one it first awaited.
ErrLookupAborted is returned to a caller whose context ends while it WAITS for an in-flight lookup, or before its own lookup would start. The caller that RAN the lookup receives the lookup function's own error instead. No lookup is started with an already-ended context, while FRESH cached values are served regardless of context state.
A stale value is not: serving one requires attempting a refresh, so a caller that arrives with an already-ended context gets ErrLookupAborted, not the stale value. A caller whose context dies DURING its own lookup can still be handed one, with a nil error.
If a lookup fails with the error of the context of the caller that ran it, that error is not shared: a coalesced waiter retries with its own context. The test is errors.Is against the context's error, so an upstream error that wraps context.DeadlineExceeded or context.Canceled is treated as context-induced when the producing context has also ended. The cost is one extra lookup.
If a waiter's context ends at the same instant the awaited lookup completes, either outcome may be observed.
The lookup function must honor context cancellation and eventually return: one that hangs forever pins its key until Cache.Remove or Cache.Reset. It must not call Cache.Lookup for the same key of the same cache, which self-deadlocks. If it panics, the panic reaches the caller that ran it and the waiters retry.
Cache.Remove and Cache.Reset invalidate the lookups in flight: the result is returned to the caller that ran it but not cached, and the callers coalesced onto it are released to retry. The orphaned lookup still runs to completion on its own context.
Stale-if-error ¶
With Config.MaxStale or Config.MaxStaleOnFailure set, a failed refresh serves the last known good value with a NIL error, so callers cannot tell a stale value from a fresh one. The revived entry stays expired, so every call still attempts a refresh and the first success replaces it. The stale window takes precedence over the context-induced retry above. An entry whose last outcome was an error is never served stale.
Stale protection is best-effort: the value is lost to Cache.Remove, Cache.Reset, a panicking lookup or TTL function, and capacity eviction. Cache.PurgeExpired also loses it, except for a key whose refresh is already in flight, whose value is held by the flight rather than by an entry.
Key requirements ¶
A key must be hashable and equal to itself. An interface key holding an unhashable dynamic type panics, in Cache.Lookup and in Cache.Remove alike, as any map access would. A key that is not equal to itself — one that is or contains a NaN — could never be found in a map again, so Cache.Lookup rejects it with ErrInvalidKey before any lookup is attempted.
Example applications in this repository:
- github.com/tecnickcom/nurago/pkg/awssecretcache
- github.com/tecnickcom/nurago/pkg/dnscache
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrInvalidKey = errors.New("sfcache: the key is not equal to itself (NaN) and can never be cached")
ErrInvalidKey is returned by Cache.Lookup for a key that is not equal to itself: one that is or contains a NaN (a float field of a struct key is enough). Such a key hashes to a map slot that no subsequent lookup can reach, so it can be neither cached nor coalesced.
var ErrLookupAborted = errors.New("sfcache: lookup aborted by context")
ErrLookupAborted is returned by Cache.Lookup when the caller's context ends while waiting for an in-flight lookup, or when it has already ended before an external lookup would start. It wraps the context error, so errors.Is with context.Canceled or context.DeadlineExceeded keeps working.
var ErrNilLookupFunc = errors.New("sfcache: the lookup function is nil")
ErrNilLookupFunc is returned by Cache.Lookup when the cache was constructed with a nil lookup function.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache[K comparable, V any] struct { // contains filtered or unexported fields }
Cache is a generic, size-bounded single-flight cache with TTL expiration.
It must be used through the pointer returned by New and never copied. A copy shares the original's maps but gets its own lock and its own copy of the eviction queues, so the two diverge on the first store through either handle and corrupt each other's queues. go vet's copylocks check rejects the copy.
func New ¶
func New[K comparable, V any](lookupFn LookupFunc[K, V], cfg Config, opts ...Option[K, V]) *Cache[K, V]
New constructs a single-flight cache with the given lookup function and configuration. If lookupFn is nil, a default one is used that always fails with ErrNilLookupFunc.
Example (StaleIfError) ¶
ExampleNew_staleIfError shows the RFC 5861 stale window: it is measured from the value's original expiration, so it only covers a key that is looked up again within TTL + MaxStale.
package main
import (
"context"
"errors"
"fmt"
"time"
"github.com/tecnickcom/nurago/pkg/sfcache"
)
// outageLookupFn returns a lookup function that succeeds once and then behaves
// as if the upstream had gone down.
func outageLookupFn() func(context.Context, string) (string, error) {
var calls int
return func(_ context.Context, _ string) (string, error) {
calls++
if calls == 1 {
return "value-1", nil
}
return "", errors.New("upstream outage")
}
}
func main() {
c := sfcache.New(outageLookupFn(), sfcache.Config{
Size: 8,
TTL: 10 * time.Millisecond,
MaxStale: 1 * time.Minute,
})
val, err := c.Lookup(context.TODO(), "some_key")
fmt.Println(val, err)
time.Sleep(20 * time.Millisecond) // let the entry expire
// The refresh fails: the last known good value is served instead.
val, err = c.Lookup(context.TODO(), "some_key")
fmt.Println(val, err)
}
Output: value-1 <nil> value-1 <nil>
Example (StaleOnFailure) ¶
ExampleNew_staleOnFailure shows the failure-anchored stale window: it is measured from the failed refresh, so it also covers a key that has been idle for far longer than TTL + MaxStale, which is where MaxStale alone would return the outage error instead.
package main
import (
"context"
"errors"
"fmt"
"time"
"github.com/tecnickcom/nurago/pkg/sfcache"
)
// outageLookupFn returns a lookup function that succeeds once and then behaves
// as if the upstream had gone down.
func outageLookupFn() func(context.Context, string) (string, error) {
var calls int
return func(_ context.Context, _ string) (string, error) {
calls++
if calls == 1 {
return "value-1", nil
}
return "", errors.New("upstream outage")
}
}
func main() {
c := sfcache.New(outageLookupFn(), sfcache.Config{
Size: 8,
TTL: 10 * time.Millisecond,
MaxStale: 10 * time.Millisecond,
MaxStaleOnFailure: 1 * time.Minute,
})
val, err := c.Lookup(context.TODO(), "some_key")
fmt.Println(val, err)
// Idle well past TTL + MaxStale: the RFC 5861 window is long closed.
time.Sleep(50 * time.Millisecond)
// The refresh fails: the last known good value is served anyway, for
// MaxStaleOnFailure measured from this failure.
val, err = c.Lookup(context.TODO(), "some_key")
fmt.Println(val, err)
}
Output: value-1 <nil> value-1 <nil>
func (*Cache[K, V]) Len ¶
Len returns the current number of entries, including the expired ones not yet reclaimed and the keys being resolved. It can therefore exceed Config.Size, which bounds only the values held.
func (*Cache[K, V]) Lookup ¶
Lookup returns the value for the key, coalescing concurrent requests for the same key into a single external lookup.
A non-expired cached value is returned immediately. Otherwise the caller either runs the lookup itself or waits for the one already in flight and takes its result. Successful values are cached for the TTL; errors are shared with the coalesced callers but never cached, so the next call retries.
With stale-if-error enabled (see Config.MaxStale and Config.MaxStaleOnFailure), a failed refresh may instead return the last known good value with a NIL error.
ErrLookupAborted is returned to a caller whose context ends while it WAITS for an in-flight lookup, or before its own lookup would start; the caller that RAN the lookup receives the lookup function's own error. See the package documentation for the full context semantics.
Example ¶
package main
import (
"context"
"fmt"
"time"
"github.com/tecnickcom/nurago/pkg/sfcache"
)
func main() {
// example lookup function that returns the key as value:
// the cache value type V is inferred from its return type.
lookupFn := func(_ context.Context, key string) (string, error) {
return key, nil
}
// create a new cache with a lookupFn function, a maximum number of 3 entries, and a TTL of 1 minute.
c := sfcache.New(lookupFn, sfcache.Config{Size: 3, TTL: 1 * time.Minute})
val, err := c.Lookup(context.TODO(), "some_key")
fmt.Println(val, err)
}
Output: some_key <nil>
func (*Cache[K, V]) PurgeExpired ¶
PurgeExpired removes every expired entry and returns how many it removed. Lookups in flight are not affected.
NOTE: this forfeits stale-if-error protection for every key it purges, not only for those a failed refresh already revived: any value retained to be served stale rides on an expired entry. Calling PurgeExpired on a timer voids the protection that Config.MaxStale and Config.MaxStaleOnFailure provide, before any outage happens.
NOTE: it is the longest hold of the exclusive write lock this package takes, blocking every other caller for the whole pass. Calling it is rarely necessary: an expired entry is reclaimed for free by the next store that needs its room.
Example ¶
package main
import (
"context"
"fmt"
"time"
"github.com/tecnickcom/nurago/pkg/sfcache"
)
func main() {
lookupFn := func(_ context.Context, key string) (string, error) {
return key, nil
}
c := sfcache.New(lookupFn, sfcache.Config{Size: 8, TTL: 10 * time.Millisecond})
_, _ = c.Lookup(context.TODO(), "some_key")
time.Sleep(20 * time.Millisecond) // let the entry expire
// Expired entries are otherwise only removed lazily.
fmt.Println(c.PurgeExpired(), c.Len())
}
Output: 1 0
type Config ¶ added in v1.152.0
type Config struct {
// Size is the maximum number of VALUES the cache holds. A Size <= 0 is clamped
// to 1. It is not a hard bound on [Cache.Len] (see the capacity section of the
// package documentation).
Size int
// TTL is the default time-to-live of a successfully looked up value.
// A TTL <= 0 disables value caching while still coalescing duplicate in-flight
// requests for the same key (unless a per-entry TTL is set via [WithTTLFunc]).
// A negative TTL behaves exactly like a zero one.
TTL time.Duration
// MaxStale enables RFC 5861 stale-if-error semantics: when a refresh of an expired
// key fails, the last known good value is returned instead (with a nil error), but
// only until its ORIGINAL expiration plus MaxStale.
//
// The window is anchored to the value's expiration, not to the failure, so a key
// idle for longer than TTL + MaxStale gets no protection at all. Use
// [Config.MaxStaleOnFailure] to protect rarely fetched keys.
//
// A MaxStale <= 0 disables it (default).
MaxStale time.Duration
// MaxStaleOnFailure enables failure-anchored stale-if-error: when a refresh of an
// expired key fails, the last known good value is returned instead (with a nil
// error) for up to MaxStaleOnFailure measured from that first failure, however long
// the key had been idle before it. Unlike [Config.MaxStale] it holds for cold keys.
//
// The window is anchored once, by the first failed refresh: further failures keep
// serving the same value until that deadline but never push it back, so a
// permanently failing upstream cannot make a value immortal.
//
// When both are set, the value is served stale until the later of the two
// deadlines. A MaxStaleOnFailure <= 0 disables it (default).
MaxStaleOnFailure time.Duration
}
Config holds the settings of a Cache that do not depend on its key and value types; those that do live in an Option.
The zero Config is valid: a single-entry cache that caches no value and only coalesces concurrent lookups.
type LookupFunc ¶
type LookupFunc[K comparable, V any] func(ctx context.Context, key K) (V, error)
LookupFunc is the generic function signature for external lookup calls.
type Option ¶
type Option[K comparable, V any] func(c *Cache[K, V])
Option is a type to allow setting custom cache options.
Options carry the settings that depend on the cache's key and value types, so their type parameters are inferred from their own argument. Settings that mention neither K nor V cannot be inferred and live in Config instead.
func WithTTLFunc ¶
func WithTTLFunc[K comparable, V any](ttlFn TTLFunc[K, V]) Option[K, V]
WithTTLFunc overrides the cache-wide TTL for individual entries.
After each successful lookup, ttlFn is called with the key and the value it returned: a positive result becomes that entry's TTL, while a zero or negative result falls back to the cache-wide Config.TTL. A nil ttlFn leaves the cache-wide TTL in effect for every entry. Values revived by stale-if-error (see Config.MaxStale and Config.MaxStaleOnFailure) bypass ttlFn: a stale serve is not a successful lookup. So does a failed one: ttlFn never sees the value of a lookup that returned an error.
It is called for every successful lookup, including one whose result is not ultimately cached because Cache.Remove or Cache.Reset invalidated it mid-flight.
NOTE: ttlFn runs synchronously on the goroutine that performed the lookup, and NOT under the cache's lock, so it may call other methods of the same cache. It must not call Cache.Lookup for the key it is being called for, which self-deadlocks against that key's own flight. If it panics, the panic propagates to the caller that ran the lookup, nothing is stored (the value that lookup fetched is lost, and so is any stale-if-error protection the key had), and no entry is evicted on its behalf.
Use this when freshness is a property of the data itself, such as caching DNS records with their authoritative TTL or credentials with a known expiration.
Example ¶
package main
import (
"context"
"fmt"
"time"
"github.com/tecnickcom/nurago/pkg/sfcache"
)
func main() {
type record struct {
addr string
ttl time.Duration
}
// The looked-up data carries its own freshness.
lookupFn := func(_ context.Context, _ string) (record, error) {
return record{addr: "192.0.2.1", ttl: 30 * time.Second}, nil
}
// Each entry is cached for the TTL carried by its value instead of the
// cache-wide default.
c := sfcache.New(lookupFn, sfcache.Config{Size: 8, TTL: 1 * time.Minute},
sfcache.WithTTLFunc(func(_ string, r record) time.Duration {
return r.ttl
}),
)
r, err := c.Lookup(context.TODO(), "example.com")
fmt.Println(r.addr, err)
}
Output: 192.0.2.1 <nil>
Source Files