CoursesSystem design from first principles to design review

Practice chapter 5 of 5

Design a search across independent shards

When can the coordinator return the true top three?

A shard owns part of a dataset. In scatter/gather, a coordinator sends a query to several shards and combines the replies. For a global ranking, first agree on a single ordering, including a stable tie breaker. Assume each item belongs to exactly one shard and all shards see a fixed dataset for this query.

Worked example

West returns scores 98, 89, 85. East returns 97, 92, 80. Merge the two sorted lists and take 98, 97, 92. An item ranked fourth on its own shard already has three items ahead of it globally, so it cannot enter the global top three.

Try it

West wants to save bandwidth by returning only two items. Construct a counterexample. Then suppose both shards report a score of 92 at the cutoff. What must the API specify?

Compare your answer

If West holds 99, 98 and 97 while East tops out at 91, returning two from West loses the true third item. Give all shards and the coordinator the same tie rule, such as lower unique item ID first. Without it two runs can disagree on the last item even on fixed data.

Source · Brendan Burns · Designing Distributed Systems, Scatter/Gather

What can the API promise when one shard is late?

Parallel calls overlap, but a complete response still waits for the slowest required shard. An API may offer partial results when its deadline expires. The response then needs to communicate which part of the dataset was searched so a caller can interpret an empty list.

Worked example

Search reaches West in 30 ms and East in 70 ms. North is still silent at the 100 ms deadline. For an exploratory map, return the two shards with a partial flag. For a question that requires proof across all regions, report the result as unavailable. Silently returning “none” would turn a timeout into a claim about data.

Try it

Assume ten independent shards, each with a 99% chance of meeting the same deadline. Estimate the chance of a complete response. What would invalidate that estimate in production?

Compare your answer

All ten must finish, so the probability under the assumption is 0.99 raised to 10, about 90.4%. A shared queue, network path or overloaded coordinator makes delays dependent. Measure end-to-end completion and partial-result rates together with per-shard timings under the same workload.

Source · Brendan Burns · Designing Distributed Systems, Scatter/Gather