Make Cache Fetch Thread-Safe and Single-Flight

A TTL cache adds fetch(key, loader, ttl): return a valid cached value immediately; otherwise call the loader, cache a successful result, and return it. Loader errors must not be cached. Explain how to make this operation safe and efficient when many threads request the same key.

Constraints & Assumptions

• The loader can take 100 milliseconds or longer and may fail or time out.
• Different keys should usually load concurrently.
• The cache supports put, get, delete, and fetch.
• A key can be replaced or deleted while a load is in flight.
• Practice assumption: values are immutable once published.

Clarifying Questions to Ask

• Should concurrent callers share the same loader result and error?
• Does delete invalidate an in-flight fetch?
• Are loaders cancelable, and is stale-on-error allowed?
• Is the cache in one process or distributed across processes?

Part 1: Thread-Safe Core State

Define synchronization for the value map, TTL metadata, and any recency or cleanup structures. Explain the linearization point of each operation.

Hints

• Correctness involves coordinated structures, not only a thread-safe dictionary.

What This Part Should Cover

• Atomic state transitions
• Bounded lock scope
• Expiration and replacement races

Part 2: Fetch and Key Conflicts

Prevent a miss storm for one key while preserving concurrency across keys. Handle loader success, error, timeout, delete, and replacement.

Hints

• The thread performing slow I/O should not hold the global cache lock.
• Consider how a waiter identifies the exact generation it joined.

What This Part Should Cover

• Per-key request coalescing
• Generation-aware publication
• Explicit error and cancellation semantics