Rafael Romão's Coding Labs

Lab L04 · Java + Go

Implementing per-key request coalescing

Build a request coalescer (“single flight”): when many callers ask for the same key while a load for that key is already running, they wait on that one load instead of starting their own. When the load finishes — successfully or not — the key is forgotten, so the next request starts a fresh load. Each caller gets its own future, so one caller giving up never cancels the load for the others.

The task

A popular restaurant's menu falls out of cache and 500 requests for it arrive within the same 50 ms. Without coalescing, all 500 miss the cache and send the same query to the database at once — a cache stampede. With coalescing, the first request starts the query and the other 499 attach to it. This is not a cache: results are not kept after the load completes. It is also not idempotency: it only merges concurrent identical reads inside one process.

request("menu:42")request("menu:42")request("menu:42")in-flight mapmenu:42 → shared futureloader("menu:42")called onceeach caller gets its own copy()first request: start loadothers joinload done → key removednext request: new load
Three callers, one load. The map entry lives only while the load runs; the timeline shows that a request after completion starts over.

What you implement

public final class RequestCoalescer<V> {
    public RequestCoalescer(int capacity,                 // max distinct keys loading at once
                            Executor executor,            // runs the loads
                            Function<String, V> loader);  // the expensive call
    public CompletableFuture<V> request(String key);     // join the in-flight load or start one
    public void closeAndWait() throws InterruptedException; // reject new requests, wait for running loads
}

Rules

  • Concurrent request("k") calls while a load of k is running → loader is called once; every caller's future completes with the same value, or the same exception.
  • Each call returns an independent future (e.g. shared.copy()). Cancelling it does not cancel the load or anyone else's future.
  • When a load completes or fails, the key is removed. A later request("k") calls loader again. A failure is therefore never “stuck” on the key.
  • capacity bounds distinct keys in flight. A request for a new key while capacity keys are loading → RejectedExecutionException; requests for a key already in flight still join it.
  • If the executor rejects the load, that flight fails with the rejection and its key is cleaned up.
  • closeAndWait(): later requests → RejectedExecutionException; the method returns once all running loads have finished.

Worked example

  1. capacity = 2. Three threads call request("a") → loader("a") runs once.
  2. request("b") → a second load starts. request("c") → RejectedExecutionException (two keys already in flight).
  3. Load of a returns 42 → all three a futures complete with 42; a is removed.
  4. request("c") is now accepted. request("a") again → a brand-new loader("a") call.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: RequestCoalescer.java · tests: RequestCoalescerTest.java. Go starter: group.go · tests: group_test.go, lifecycle_test.go.

cd java
./gradlew test --tests 'labs.singleflight.*'

cd go
go test -race -count=1 ./singleflight
Reveal the reference solutions

Java: RequestCoalescer.java
Go: group.go

When to use

Use this lab when several callers request the same expensive value at once. A map of in-flight loads lets callers share one computation per string key. A positive capacity bounds the number of distinct retained keys, not the number of callers waiting for each key. Completed results are removed rather than cached, and a later request starts another load. Failures are shared with current waiters and do not permanently occupy the key.

Coalescing is not durable idempotency. It neither survives restart nor guarantees that a remote side effect happens once. Use it for appropriately repeatable loads, not as the correctness boundary for a payment or external mutation. Java and Go examples live in the singleflight packages under solutions/.

Steps

  1. Make key scope precise. A key must identify the same operation, input, tenant, and relevant authorization scope. Sharing results across different permissions can leak data. The examples use strings; the caller must derive them safely and bound their lengths where necessary.
  2. Publish before starting. Under one lock, find an existing flight or install a new completion object. Reject a new distinct key at capacity, but allow another waiter on an existing key. Run the loader outside the lock so unrelated keys can progress and arbitrary loader code cannot hold the coordination lock.
  3. Separate cancellation scopes. Go receives an owner context for the loader and a separate caller context for each wait. Cancelling one wait does not cancel shared work. Java returns an independent copy of the shared future, so cancelling that copy cannot cancel the loader or another caller's future. A Java executor and loader remain externally owned.
  4. Finish and remove. Store the outcome, remove the in-flight entry, and notify waiters. A subsequent request may start just after removal while old callers are still receiving their completed outcome; the guarantee concerns active loader execution, not a retained cache entry. Catch ordinary load failures and convert Go panics into results so a failed computation does not strand all waiters. A runtime-fatal failure or a Go loader calling Goexit is outside this recovery policy.
  5. Handle dispatch failure. If the Java executor rejects scheduling, remove the installed entry and fail its future. Otherwise a rejected task could occupy a slot forever. Loaders must not recursively request and wait on their own key, which creates a dependency cycle.
  6. Test boundaries. Hold a loader with a latch, request the same key twice, cancel one waiter, and verify the remaining result. Attempt another key at capacity. Release a failed load and verify a later request can retry. Go tests also check that the shared flight remains retained after the initiating caller cancels. Add bounded concurrent-history tests before stronger correctness claims.

Checklist

Join and recall

The Go and Java references expose close-and-wait: close admission before joining active loads. The owner still supplies cancellation to blocked loaders; do not join from a loader or synchronous completion callback. Rebuild flight installation from memory. Variation: cancel the first waiter while another remains; acceptance requires one load and a successful remaining result.

  • Keys identify the same computation and security scope
  • Shared work does not use an individual caller's cancellation context
  • Dispatch failure and load failure release distinct-key capacity
  • Completed results are not accidentally advertised as cached values
  • The owner handles loader cancellation and waits before releasing dependencies

Signals

Working: overlapping same-key requests share a load, cancellation affects only its caller, and failures permit a later retry.

Going wrong: one caller cancels everyone, an executor rejection strands a key, or an uncooperative loader retains a slot forever. Distinct-key capacity does not bound total callers or result size. Close-and-wait joins loads but still requires owner-supplied cancellation for blocked dependencies.

Related