Design Search Suggestions
As people type into a search box, the service suggests completions after every keystroke, so it has to answer in a few tens of milliseconds. Suggestions come from what people have searched for, ranked by popularity and refreshed as new topics trend. Every submitted search is logged so the popularity numbers can be rebuilt from scratch whenever the ranking changes.
Constraints
- A suggestion must arrive within 80 ms
- About 10,000 suggestion requests per second at peak, and three times that when news breaks
- Most prefixes are asked for constantly, so answers are highly cacheable
- Personalised suggestions are a bonus; a slow personaliser must not delay the box
- Popularity is rebuilt from a log of searches that can be read again
- Keep infrastructure under $7,500 a month
Scenarios to survive
Typical peak
Steady typing across the site.
Interviewer asks: Why can almost every request be answered from memory, and what is the cost of a miss?
Breaking news (3x)
A news event triples the requests, all for a few prefixes.
Interviewer asks: A handful of prefixes become huge. What keeps one hot key from overloading one node?
The prefix cache is lost
Every request falls through to the search index.
Interviewer asks: The cache is gone. Can the index carry the load, and what do you do first?
Personalisation hangs
Whatever runs personalisation becomes 30x slower.
Interviewer asks: The personaliser hangs. What does the person see, and how long do you wait?
What a good design must do
- Suggestions meet the latency target at peak
- The breaking news surge passes
- Total monthly cost stays within $7,500
- Answers come from a cache in front of a search index, with a Stream for the search log
- Something rebuilds popularity from the log and can replay it
- Something records submitted searches
- Losing the cache does not stop suggestions
- A hung personaliser cannot slow suggestions
- The design explains how hot prefixes are handled