skip to content

In a typeahead service with a sub-100 ms budget, why does caching results for short prefixes pay off so well?

level: middleimportance: should knowfreq 48%

answer

  1. count the possible short prefixes
  2. every query starts somewhere
  3. network dominates the budget
  4. same answer for everyone
  5. cache key includes locale

basics

~20 s

Short prefixes are few, most typed queries pass through them, and their suggestion lists change slowly, so a small cache near users gets a high hit rate and removes both server work and much of the network round trip.

solid answer

~40 s

The number of short prefixes is tiny: one to three lowercase Latin letters give only `26 + 676 + 17,576 = 18,278` strings. Almost every typed query passes through its first few characters, so those few entries receive a large share of all suggestion traffic. Their lists also change slowly, because the ranking of the most popular completions is stable, so a TTL of minutes loses little freshness. Put together, a cache of a few megabytes can absorb much of the load. Because non-personalized results are identical for everyone, they can even be cached at a CDN edge via standard HTTP caching headers, which cuts the network round trip that dominates a `100 ms` budget for distant users. Long prefixes are the opposite: numerous, rarely repeated, and poor cache candidates.

go deeper

for a junior

Recall the core reason: few short prefixes, lots of traffic through them, answers that change slowly. That combination makes them cheap to cache with a high hit rate.

for a middle

Explain the budget split, compute the number and size of short-prefix entries with stated assumptions, and say why edge caching attacks the network share.

for a senior

Show the production judgment: cache-key completeness, TTL against freshness and removals, and keeping personalization after the cache read.

for a principal

Weigh edge caching against personalization and trending freshness as product choices, and decide which prefixes get which tier and purge policy.

## Where a sub-100 ms budget goes Typeahead feels instant when suggestions appear within roughly **100 ms** of a keystroke. That budget is shared by several stages. An illustrative split for a user far from the serving region: | Stage | Illustrative share | |---|---| | Network round trip, user to serving region and back | 40-80 ms | | Server-side lookup and serialization | 5-15 ms | | Browser rendering of the dropdown | a few ms | The figures are assumptions, not measurements, but the shape is typical: once the server lookup is a precomputed read, the **network** is often the biggest line item. Two levers remain: make fewer requests reach the origin, and serve answers from closer to the user. Caching short-prefix results pulls both. ## Why short prefixes are the ideal cache keys Four properties line up: 1. **They are few.** Over 26 lowercase Latin letters there are 26 one-letter, 676 two-letter and 17,576 three-letter prefixes, **18,278** in total. Other scripts and digits raise the count, but it stays small next to the long tail. 2. **They are hot.** Most typed queries pass through their first few characters, so these few keys see a large fraction of all requests. 3. **They are stable.** The top completions of `sh` do not change minute to minute, so a TTL of several minutes rarely serves anything meaningfully stale. 4. **They are small.** Illustratively, 10 suggestions of about 30 bytes each is **300 bytes** per entry; 18,278 x 300 bytes is roughly **5.5 MB** per locale. A few megabytes of cache that catches a large share of traffic is about as good a deal as caching offers. ## Why long prefixes are poor cache keys - The number of distinct long prefixes is enormous, growing with every unusual query. - Each one is requested rarely, so the **hit rate** is low and most entries expire unused. - The backing lookup for a long prefix is already cheap in a precomputed structure. A common policy is to cache aggressively up to a length threshold and let longer prefixes go straight to the suggestion servers. ## Where the cache can live - **In-process** on each suggestion server: removes the structure walk but not the network hop. - **Shared in-memory key-value cache** in the serving region: shields the suggestion servers during spikes. - **CDN edge**: if the response depends only on the prefix and locale, a `GET` with the prefix in the URL and a `Cache-Control: max-age=...` header lets edge nodes answer near the user, removing most of the round trip. Client-side caching and request cancellation are frontend concerns and sit outside this server-side picture. ## What breaks shared caching - **Personalization.** If the list depends on the user, a cache keyed only by prefix can serve one user's suggestions to another. Either add user-level keys (and lose the hit rate) or cache the **non-personalized base** and apply a small per-user rerank after the cache. - **Trending updates.** A long TTL on short prefixes can hide a newly trending term for the whole TTL. Keep TTLs short for the hottest prefixes or purge them when the trending overlay changes. - **Locale and safety rules.** The cache key must include every input that changes the answer, such as language, region and safe-search setting. ## Summary Short prefixes combine small count, high traffic, slow change and small size, which is the textbook profile of a good cache key. Caching them, ideally at the edge, attacks the network share of the budget that server optimizations cannot reach.

  • How do you keep a prefix-result cache correct when suggestions are personalized?
    Cache only the shared, non-personalized base list keyed by prefix plus locale and safety settings, and apply the per-user rerank after the cache read. Keying the cache by user as well would keep it correct but would collapse the hit rate, since each user-prefix pair repeats rarely.
  • What TTL trade-off do you face on the hottest short prefixes?
    A longer TTL raises the hit rate and shields the origin, but it delays newly trending terms and suggestion removals for the whole TTL. Teams usually pick a few minutes and add an explicit purge for urgent removals, so safety fixes do not wait for expiry.

saying these in an interview costs you the question

  • Cache every prefix equally; long prefixes are just as valuable.
  • Caching is pointless because the server lookup is already fast.
  • A cache keyed only by prefix is fine for personalized suggestions.
  • The server lookup is always the largest part of the latency budget.
  • Suggestion responses cannot be cached at a CDN.