sturdyc

For batch operations, sturdyc provides stampede protection by deduplicating cache misses across multiple batches.

If several concurrent requests (via GetOrFetchBatch) contain overlapping IDs that are currently being fetched, the cache will:

1. Deduplicate the misses.
2. Assemble the response for each caller by picking records from multiple in-flight requests.

This allows the cache to resolve requests for IDs that belong to different in-flight batches without generating any additional outgoing requests to the data source.

// Example of a batch fetch function
var count atomic.Int32
fetchFn := func(_ context.Context, ids []string) (map[string]int, error) {
	count.Add(1)
	time.Sleep(time.Second * 5)

	response := make(map[string]int, len(ids))
	for _, id := range ids {
		num, _ := strconv.Atoi(id)
		response[id] = num
	}

	return response, nil
}

// Requesting batches concurrently
for _, batch := range batches {
	go func() {
		res, _ := cacheClient.GetOrFetchBatch(context.Background(), batch, keyPrefixFn, fetchFn)
		log.Printf("got batch: %v\n", res)
	}()
}

By default, if a record is not found, the cache cannot store anything, leading to repeated I/O operations for every subsequent request for that ID.

To prevent this performance degradation, you can enable Missing Record Storage. When enabled, the cache will mark keys that return sturdyc.ErrNotFound as "missing". Subsequent requests for these keys will immediately return sturdyc.ErrMissingRecord without hitting the upstream data source.

If you use WithEarlyRefreshes, these missing records will be refreshed periodically. If the upstream eventually returns a valid value, the record will automatically transition from "missing" to having a cached value.

Implementation Details:

• For GetOrFetch: Return sturdyc.ErrNotFound in the fetch function.
• For GetOrFetchBatch: Omit the missing keys from the returned map.
• Detection: Check for sturdyc.ErrMissingRecord in your application logic to handle missing data (e.g., returning a 404 or a default state).

To prevent cache stampedes (thundering herd) where many concurrent requests for an expired or evicted key hit the underlying data source at once, sturdyc performs in-flight tracking for every key.

When using GetOrFetch, the cache ensures that there is never more than a single in-flight request per key. If multiple goroutines call GetOrFetch for the same key simultaneously, only the first one triggers the fetchFn. Subsequent callers wait for that single in-flight request to complete and then receive the cached result.

	var count atomic.Int32
	fetchFn := func(_ context.Context) (int, error) {
		// Increment the count so that we can assert how many times this function was called.
		count.Add(1)
		time.Sleep(time.Second)
		return 1337, nil
	}

	// Fetch the same key from 5 goroutines.
	var wg sync.WaitGroup
	for i := 0; i < 5; i++ {
		wg.Add(1)
		go func() {
			// We'll ignore the error here for brevity.
			val, _ := cacheClient.GetOrFetch(context.Background(), "key2", fetchFn)
			log.Printf("got value: %d\n", val)
			wg.Done()
		}()
	}
	wg.Wait()

	log.Printf("fetchFn was called %d time\n", count.Load())
	log.Println(cacheClient.Get("key2"))

Early refreshes prevent frequently used records from expiring by continuously refreshing them in the background. This significantly reduces tail latency (P99) because the I/O operation to refresh the data happens asynchronously before the TTL expires.

Key Behaviors:

• On-demand scheduling: Background refreshes are only scheduled if a key is requested again after a configurable interval. Unused keys are not naively refreshed and will expire normally.
• Asynchronous updates: The request that triggers a background refresh will receive the old value immediately; the new value is updated in the cache asynchronously.
• Stale data prevention: To prevent infrequently requested keys from remaining perpetually stale, you can configure a synchronous refresh delay. If a key is older than this delay, the next request will block and wait for a fresh value (synchronous refresh).
• Fallback mechanism: If a synchronous refresh fails, the cache will still serve the existing (stale) value as a fallback rather than returning an error.

To avoid the combinatorial explosion of cache keys when fetching batches of items, sturdyc does not use the entire batch as a single cache key. Instead, it decomposes the batch and caches each record individually.

When you call GetOrFetchBatch, the library:

1. Applies a KeyFn to each ID in the requested batch to check for individual cache hits.
2. Identifies the IDs that are missing from the cache (cache misses).
3. Passes only those missing IDs to your provided BatchFetchFn.
4. Takes the resulting map from the BatchFetchFn and stores each record individually in the cache using the KeyFn.

This approach ensures that even if you request different subsets of a large dataset, you still benefit from high cache hit rates for the overlapping items.

func (c *Client[T]) GetOrFetchBatch(ctx context.Context, ids []string, keyFn KeyFn, fetchFn BatchFetchFn[T]) (map[string]T, error) {}

Refresh coalescing improves efficiency by buffering background refreshes for keys that share the same options (e.g., same filters, sorting, or transformations). Instead of refreshing each key individually, the cache groups IDs that belong to the same option permutation into a single batch request.

To use this, you must use PermutatedBatchKeyFn to generate keys based on an options struct and enable the feature using WithRefreshCoalescing(batchSize, batchBufferTimeout) when creating the client.

• batchSize: The number of IDs to gather before triggering a refresh.
• batchBufferTimeout: The maximum time to wait for a batch to fill before triggering the refresh anyway.

// Example configuration for refresh coalescing
batchSize := 3
batchBufferTimeout := time.Second * 30

cacheClient := sturdyc.New[string](capacity, numShards, ttl, evictionPercentage,
    sturdyc.WithEarlyRefreshes(minRefreshDelay, maxRefreshDelay, retryBaseDelay),
    sturdyc.WithRefreshCoalescing(batchSize, batchBufferTimeout),
)

To prevent cache stampedes in new containers during traffic spikes, you can sync in-memory caches with a distributed key-value store (like Redis). sturdyc treats distributed storage as a high-priority data source: it queries the distributed store before the underlying data source and writes refreshed records back to it.

To use this, implement the DistributedStorage interface and pass it to sturdyc.New using the sturdyc.WithDistributedStorage option.

Note: You are responsible for configuring the TTL and eviction policies of your distributed storage. It is recommended to use short TTLs to avoid stale data.

type DistributedStorage interface {
	Get(ctx context.Context, key string) ([]byte, bool)
	Set(ctx context.Context, key string, value []byte)
	GetBatch(ctx context.Context, keys []string) map[string][]byte
	SetBatch(ctx context.Context, records map[string][]byte)
}

// Usage
cacheClient := sturdyc.New[string](capacity, numShards, ttl, evictionPercentage,
	sturdyc.WithDistributedStorage(storage),
)

If you want to use distributed storage as a robustness feature (e.g., to serve stale data if an upstream system is down), use the WithDistributedStorageEarlyRefreshes option.

This mode allows you to set a long TTL on your distributed store. If sturdyc finds a record in the distributed storage that is older than the specified threshold, it will attempt to refresh it from the underlying data source. If the refresh fails, the cache falls back to the value in the distributed storage.

To support this, you must implement the DistributedStorageEarlyRefreshes interface, which includes Delete and DeleteBatch methods. These methods are called when a refresh fails because the key is no longer present in the underlying data source, allowing the cache to propagate the deletion to the distributed store immediately.

type DistributedStorageEarlyRefreshes interface {
	DistributedStorage
	Delete(ctx context.Context, key string)
	DeleteBatch(ctx context.Context, keys []string)
}

// Usage
cacheClient := sturdyc.New[string](capacity, numShards, ttl, evictionPercentage,
	sturdyc.WithDistributedStorageEarlyRefreshes(storage, time.Minute),
)

You can monitor cache performance by implementing the MetricsRecorder or DistributedMetricsRecorder interfaces and passing them to the client via sturdyc.WithMetrics or sturdyc.WithDistributedMetrics.

Standard Metrics (MetricsRecorder):

• Cache hits/misses
• Background/Synchronous refreshes
• Missing records
• Evictions (including forced evictions and entry counts)
• Shard distribution
• Coalesced refresh batch sizes
• Cache size observation

Distributed Metrics (DistributedMetricsRecorder): If using distributed storage, you can implement this interface to track:

• Distributed cache hits/misses
• Distributed refreshes
• Distributed missing records
• Distributed stale fallbacks

type MetricsRecorder interface {
	CacheHit()
	CacheMiss()
	AsynchronousRefresh()
	SynchronousRefresh()
	MissingRecord()
	ForcedEviction()
	EntriesEvicted(int)
	ShardIndex(int)
	CacheBatchRefreshSize(size int)
	ObserveCacheSize(callback func() int)
}

type DistributedMetricsRecorder interface {
	MetricsRecorder
	DistributedCacheHit()
	DistributedCacheMiss()
	DistributedRefresh()
	DistributedMissingRecord()
	DistributedFallback()
}

// Usage for basic metrics
cacheBasicMetrics := sturdyc.New[any](
	cacheSize,
	shardSize,
	cacheTTL,
	evictWhenFullPercentage,
	sturdyc.WithMetrics(metricsRecorder),
)

// Usage for distributed metrics
cacheDistributedMetrics := sturdyc.New[any](
	cacheSize,
	shardSize,
	cacheTTL,
	evictWhenFullPercentage,
	sturdyc.WithDistributedStorage(metricsRecorder),
	sturdyc.WithDistributedMetrics(metricsRecorder),
)