A hot cache key can send many identical misses to the database while its value is being rebuilt. Single-flight request coalescing makes the first miss the loader and lets later requests for that key share the in-flight load.
Design a SingleFlightCache class:
SingleFlightCache(int loadDuration, int ttl) configures the simulated load time and freshness duration.String request(String key, int timestamp) returns "loader", "coalesced", or "hit".
For each key independently:
- An absent or expired key starts a load and returns
"loader". The load completes at timestamp + loadDuration. - A request strictly before that completion time returns
"coalesced". - At the completion time, the value becomes fresh and the request returns
"hit". - A completed value is fresh while
timestamp < readyAt + ttl. It is expired at equality.
Input timestamps are nondecreasing across calls.
Example 1:
Input:
Output:
Explanation: The load finishes at 3, and the entry is fresh on [3, 8). The request at 8 starts a new load.
Example 2:
Input:
Output:
Explanation: Each key has its own load. Requests for one key never coalesce with a different key.
Constraints
1 <= loadDuration, ttl <= 10^61 <= key.length <= 400 <= timestamp <= 10^9- Timestamps are nondecreasing across all calls.
- At most
500 calls are made to request.
Coalesce Concurrent Cache Missesmedium