Medium · Core building blocks
Search autocomplete
As people type, they expect suggestions after every letter, in the blink of an eye. Most people type the same popular beginnings. When news breaks, one phrase suddenly dominates. Practise this medium system design problem for free with a Google or GitHub account.
The brief
As people type, they expect suggestions after every letter, in the blink of an eye. Most people type the same popular beginnings. When news breaks, one phrase suddenly dominates.
Think of suggestions as you type, like Google.
Users, scale and requirements
- Who uses it
- 200 million people a month
- Audience in plain numbers
- 200,000,000 people per month
- Normal peak
- ≈ 60,000 requests per second
- Request mix
- Search: 96%; Analytics event: 4%
- Speed for 99 of 100 requests
- Search: ≈ 400 ms
- Successful requests
- 99.9%
- Data safety
- Best effort: small losses are tolerated.
- Monthly budget
- ≈ $92,000
- Data at rest
- ≈ 0.5 TB
- Where users are
- North America: 45%; Europe: 30%; Asia Pacific: 25%
- Home region
- North America
- Waiting deadlines
- Search: 900 seconds; Analytics event: 3,600 seconds
≈ marks an approximation, just as in the game. Waiting deadlines measure the age of queued work and are separate from interactive response time.
- Typing is debounced: about 5 requests for each finished search (approx.).
- The suggestion index holds the 50 million most popular prefixes.
Questions that shape the design
How fast must suggestions appear?
About 100 ms feels instant for people near the servers. Counting the trip across an ocean for everyone else, the target here is a 400 ms p99 (approx.).
Do suggestions need to include something that happened five minutes ago?
A few minutes late is fine. Hourly refresh of the main list is acceptable, trending words faster.
Do we log what people type?
Yes, so the next list can be built, but logging must never slow a suggestion.
The traffic day
Consumer traffic, busiest in the evening. The clock covers 00:00 to 24:00 in the home region. Events add pressure on top of that normal traffic.
14:00 · Viral spike
A post blows up. Traffic climbs to several times normal within minutes.
Traffic reaches 6 times the scheduled load; rises over 600 seconds, holds for 3,600 seconds and eases over 3,600 seconds.
14:05 · Hot key
One item gets a huge share of traffic: a celebrity profile, one product, one merchant.
Affected share: 40%. Duration: ≈ 3,600 seconds.
What a strong design has to handle
- Most people type the same first few letters. Which answers repeat the most?
- Serve hot prefixes quickly while publishing fresh index generations safely.
- A longer time to keep prefixes saves the index but delays trending words. Trending words can use a short-lived fast list.
- Caching only short prefixes captures most traffic with little memory. Long rare prefixes would waste cache.
Make a prediction, run a full traffic day, then compare the result. The in-game editorial opens after a finished day and includes measured reference designs.
Concepts to practise
Related problems
- Medium
Music streaming
People search for songs, build playlists and press play. The audio is the heavy part, and a hit song is played by millions at once. Playback must not stutter, even when part of your system fails.
- Easy
URL shortener
People paste a long web address and get back a short one. Millions of other people then tap that short link, so reading is almost everything. Keep every tap fast, and never lose a link.
- Easy
News site
You run a news site. Millions read the same few stories, and when something big happens almost everyone opens the same page in the same minute. Editors publish all day, and readers expect fresh headlines.
- Medium
Short-video feed
People swipe through an endless feed of clips of 10 to 30 seconds. The next clip must already be on the phone before the swipe. One clip can suddenly get millions of views, and every view is a signal that picks what to show next.