Table of contents
Part of nurago, a collection of independent Go packages for backend services.
import "github.com/tecnickcom/nurago/pkg/sfcache"
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
When To Use
- Many goroutines request the same key at once and the upstream should see one request.
- Values expire on a TTL and the cache must stay bounded in size.
- You want to keep serving the last good value while the upstream is down.
Example
// 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>
Full source is in example_sfcache_test.go. More runnable examples are on pkg.go.dev.
Dependencies
This package reaches no external module: it uses only the Go standard library.