Evaluator cache stampede prevention

[thomasmaas]

Problem

Authorino's evaluator cache uses a fixed TTL with synchronous expiration. When multiple cache entries expire simultaneously under high concurrency, all requests miss the cache at once and flood the upstream identity/metadata sources (e.g., a database-backed API key validation service). This "thundering herd" or "cache stampede" pattern causes:

• Sudden load spikes on upstream services at every TTL boundary
• Upstream timeout failures when the burst exceeds the service's capacity
• Cascading failures when the wasm auth-service timeout (200ms default) is shorter than the upstream's burst response time

Observed behavior

Performance testing at scale (up to 512 concurrent requests, single shared API key, TTL=60s on METADATA and AUTHZ evaluators) showed:

• 93-100% cache hit rate during steady state — cache works well when warm
• 27 simultaneous cache misses out of 768 requests when the TTL expired at the 91s mark
• All 27 requests hit the upstream service concurrently instead of 1 request revalidating while others serve stale
• Three latency tiers during stampede: 1-4ms (idle upstream), ~105ms (internal queueing), ~149ms (full contention)

Proposed solutions

One or more of these strategies would mitigate the stampede:

1. Probabilistic early expiration (PER): Randomly expire a fraction of requests slightly before the TTL, spreading revalidation over time instead of a single instant. This is the simplest approach and doesn't require coordination between goroutines.

2. Single-flight / mutex revalidation: When a cache entry expires, allow only one request to perform the revalidation while other concurrent requests continue serving the stale cached value. Go's singleflight package is designed for exactly this pattern.

3. Staggered / jittered TTL: Add per-entry random jitter to the TTL at cache write time (e.g., TTL = 60s ± 10s) so entries don't all expire at the same wall-clock time.

Additional considerations

• Authorino's evaluator cache memory grows with the number of distinct cache keys (e.g., unique API keys). There is currently no configured memory limit. Consider adding a max-entries or max-memory-bytes configuration to prevent unbounded growth in production.
• The cache.ttl field on evaluators is the only tuning knob today. More granular configuration (jitter range, max stale age) would help operators balance freshness vs. stampede risk.

References

• Performance data from PSAP team scale testing (512 concurrent, GuideLLM workload)
• Authorino evaluator cache: pkg/evaluators/cache.go

[Taimoo-r]

Hi @thomasmaas, this is a really well-documented issue and I'd like to work on it if it's open for an external contribution.

I read through pkg/evaluators/cache.go and the stampede is clear from the current implementation: evaluatorCache wraps freecache via gocache, Get treats anything with ttl <= 0 as a plain miss with no coordination, and Set writes with the store's default expiration (c.store.Set(key, valueAsBytes, nil)), so every entry sharing a TTL expires on the same wall-clock instant and each concurrent miss independently revalidates upstream.

Of the three strategies you outlined, I'd suggest landing them in this order, smallest and least risky first:

1. Jittered TTL — contained entirely within cache.go. At Set time, apply a per-entry random jitter (e.g. ttl ± jitterFraction) via a per-call store.Set(..., &store.Options{Expiration: jittered}) instead of relying on the default expiration. Spreads out the expiry boundary with no cross-goroutine coordination.
2. Single-flight revalidation — dedupe concurrent misses so only one request revalidates while the others serve the stale value. golang.org/x/sync/singleflight fits well. One thing I want to confirm: the cache here only exposes Get/Set, and the actual upstream revalidation happens in the caller (the metadata/authz evaluators). Do you prefer the single-flight coordination to live in the evaluator layer around the cache calls, or to fold a GetOrSet(key, revalidateFn) method into EvaluatorCache so the coalescing is encapsulated?

On the memory-limit note: it looks like EvaluatorCacheSize already bounds freecache to a fixed byte budget, so growth may be capped today (with LRU-style eviction inside freecache) rather than unbounded. Happy to add explicit max-entries / jitter-range config as a follow-up if you'd like, but I'd keep this first PR focused on the stampede itself.

Could you confirm this is available to pick up, and whether you'd like all three strategies or just single-flight + jitter to start? I'll open a scoped PR with tests and a small concurrency benchmark once I know your preference. Thanks!