Request Coalescing

A popular cache key expires. In the next 50 milliseconds, 500 requests for that key arrive, every one of them misses, and all 500 stampede your database for the same row. This is the thundering herd (or cache stampede), and the fix is request coalescing: when several callers ask for the same key at the same time, one of them does the work and the rest wait for its result.

You are given an upstream object with a single slow method:

upstream.fetch(key)   # slow; returns the value for key

Implement Coalescer:

• __init__(self, upstream)
• get(self, key) — return the value for key. If a fetch for that key is already in flight, do not start a second one: wait for the in-flight fetch and return its result.

Requirements:

• Concurrent calls for the same key trigger exactly one upstream.fetch
• Every concurrent caller receives the same result
• Different keys are coalesced independently and never block each other
• This is not a cache: once a fetch completes, a later call starts a fresh fetch
• No busy-waiting — waiters must block, not spin

Constraints:

• Use threading primitives (Lock, Event, Condition)
• get is called from many threads simultaneously
• Holding a lock for the whole fetch is not acceptable — that serializes different keys