CoursesSystem design from first principles to design review

Puzzle 16 · 17 of 19

Can two cache misses share one read?

Make overlapping requests for the same reading share the work and observe how a failed read propagates.

All puzzles in this course

The problem

In the routing puzzle, round robin could send two requests to the same worker. Keep their destination fixed and change what they ask for. The map entry for west expires. Two drivers ask for west before its replacement arrives. Another asks for east, which also has no usable cache entry. All three requests reach the same service instance. How many times should it read each lot from storage?

See it

Two west callers await one pending west result CallersPendingStorage West 1westRead 1 West 2 EasteastRead 2 3 callers · 2 reads

Scroll sideways to see the full diagram.

  1. The first west caller creates a pending entry and starts one storage read.

    Step 1 of 4
  2. The second west caller arrives before the result. Follow its arrow to the existing west entry. No second arrow goes to storage.

    Two west requests already share a pending lookup. Can the arriving east caller reuse that result?

    Step 2 of 4
  3. East needs different data. It creates a separate entry and starts another storage read.

    Step 3 of 4
  4. Three callers receive results from two underlying reads. On completion each pending entry is removed. If west fails, both west callers share that failure.

    Step 4 of 4

The building block

A cache keeps a completed answer for later use. Request coalescing lets callers that need the same answer share work that is still underway. Picture two people at a counter asking when the same train leaves. The clerk starts one lookup and gives its answer to both. Someone asking about another train needs a separate lookup.

The first caller stores a promise, a value in the program representing a future result, under the lot name. The next caller for that lot can take the same promise. When it settles, remove it whether it succeeded or failed. A request arriving later can start a fresh lookup. A completed-answer cache would need its own freshness and eviction rules.

Trace the pending reads

The fixture starts three calls before waiting for any result. The storage function counts actual invocations and yields once so the requests overlap. It returns a known map or fails with a known error. The last call happens after the burst finishes. Compare Independent reads with Share reads for each lot.

if (!pending.has(key)) {
  const result = fetchReading(key).finally(() => {
    if (clearSettled) pending.delete(key);
  });
  pending.set(key, result);
}
return pending.get(key);

Read the complete runnable code
async function readBurst(share, failWest, clearSettled = true) {
  const pending = new Map();
  const calls = { west: 0, east: 0 };

  async function fetchReading(key) {
    calls[key]++;
    const shouldFail = key === 'west' && failWest;
    await Promise.resolve(); // Let all three callers enter before completion.
    if (shouldFail) throw new Error('temporarily unavailable');
    return key + ' map';
  }

  function read(key) {
    if (!share) return fetchReading(key);
    if (!pending.has(key)) {
      const result = fetchReading(key).finally(() => {
        if (clearSettled) pending.delete(key);
      });
      pending.set(key, result);
    }
    return pending.get(key);
  }

  const results = await Promise.allSettled(['west', 'west', 'east'].map(read));
  const describe = item => item.status === 'fulfilled' ? item.value : 'unavailable';
  const burst = { phase: 'burst', westCalls: calls.west, eastCalls: calls.east,
    replies: results.map(describe).join(', ') };
  failWest = false;
  const [later] = await Promise.allSettled([read('west')]);
  return [burst, { phase: 'later read', westCalls: calls.west,
    eastCalls: calls.east, replies: describe(later) }];
}

In the independent burst storage receives two west requests and one east request. Sharing reduces west to one while both west callers receive the result. Now choose the failure scenario. One failed west read reaches both west callers. East still succeeds. The later west lookup succeeds because the failed promise was removed. The counts shown in the later row include the earlier calls.

Go deeperWhat belongs in the sharing key?

Suppose the public map shows only free spaces, while an attendant can also see reserved names. A key containing only the lot would combine requests for different answers. Build the key from every input that changes what callers may see, or share only the public part after checking access. Giving one caller a shorter deadline can end that caller's wait while the other caller still needs the shared result.

What happens if two service instances each keep this dictionary?

Simultaneous misses can produce one storage read per instance for the same key.

Back to the main puzzle

Try it

Select the scenario that keeps the failed promise. Only cleanup changes. Before running it, predict how many west calls reach storage in the later row and which reply that driver receives.

Compare your result

The later read finds the old rejected promise and fails again. West still has only one storage call even though storage has recovered. Restore the failed-read scenario with normal cleanup and explain why sharing an in-flight read cannot by itself make an old completed map entry fresh.

Check yourself

Which two requests share storage work?

Not quite. Different lots need different data.

Right. Their requested result and the time of their pending lookup coincide.

If the shared west read fails, who sees the failure?

Not quite. Both await the same result. Re-read that part ↑

Right. Sharing includes the outcome of failure.

Why remove the entry when it settles?

Not quite. Removing during the fetch would defeat sharing. Re-read that part ↑

Right. A later read should be able to start fresh work.

Sources

What you now know

Sharing a pending result by key removes duplicate work while that result is being fetched.

Sharing a request also shares its failure. How can callers give a failing dependency time to recover?