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