Art of Codeartofcode
Lesson 10 of 15

34. Design Search Autocomplete (Typeahead)

1
The interview prompt
2
34.1 What do you ask first?
3
34.2 How big is this, really?
4
34.3 What are the doors?
5
34.4 What do we store?
6
34.5 What does the whole system look like?
7
34.6 Trie or prefix index?
8
34.7 How do you compute top-K per prefix?
9
34.8 How do suggestions follow trends?
10
34.9 How do you cache suggestions?
11
34.10 What would you say in the last five minutes?
12
Score yourself
13
Variations to practise
14
Sources
15
Code lab
34. Design Search Autocomplete (Typeahead)

34.9 How do you cache suggestions?

3 min read+10 XP

The same prefix gets the same answer for everyone (no personalisation), which makes caching very effective:

  • Short prefixes dominate. In the chapter's code, prefixes of 4 characters or fewer carry about 22% of all keystroke requests, yet there are only a few hundred one- and two-character prefixes in total. Cache them everywhere: in the browser, at the CDN, in each suggest server's memory.
  • CDN caching with a TTL of minutes (Cache-Control: public, max-age=300) absorbs a large share of the 14,000 a second at the edge (Chapter 26).
  • Client cache: typing "data", backspacing to "dat" and retyping shouldn't call the server again.
  • Invalidation: when a new table is published, versioned cache keys (or short TTLs) roll it out within minutes; for an urgent removal (an offensive suggestion), purge it at the CDN by key.

Interviewer pushback:

  • "Doesn't caching stop trends from showing?" → Only for the TTL: a few minutes of lag on suggestions is fine. For an urgent removal, purge.

Memory code: "Same prefix, same answer: cache it at every layer."