CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 2 of 8 · 2 min read

Scope and numbers

Five suggestions, in 100 milliseconds.

Think of a librarian who hears the first letters of a title and calls out the five books people ask for most. The answer must come before the visitor finishes the word, or it is of no use.

Autocomplete (also called type-ahead) shows likely completions while a user types. It is often described as a "top k" problem: return the k most searched queries for a prefix.

Questions and the answers assumed here (from the book's sample talk).

  1. Match only the start of a query, or also the middle? Only the start.
  2. How many suggestions? 5.
  3. How are they chosen? By how often each query was searched before.
  4. Spell check? No.
  5. Language? English, lowercase letters only.
  6. Users? 10 million daily active users (DAU).

Requirements.

  • R1. Fast: results within about 100 milliseconds, or the box stutters.
  • R2. Relevant: suggestions match the typed prefix.
  • R3. Sorted by popularity.
  • R4. Scalable for heavy traffic.
  • R5. Available even when part of the system is down.

Numbers (from the book). A user makes 10 searches a day. A query is 4 words of 5 letters, so 4 × 5 = 20 bytes. Each letter typed sends one request, so a search sends about 20 requests. Queries per second: 10,000,000 × 10 × 20 / 86,400 = about 23,000, which the book rounds to 24,000. Peak is twice that, about 48,000. If 20 per cent of daily queries are new, the new data is 10,000,000 × 10 × 20 bytes × 20% = 0.4 GB a day.

The key points: the request rate is high because every key press is a request, and the data growth is small. Speed is the problem, not storage.

Top k

A top k query asks for the k items with the highest score, such as the 5 most searched queries starting with a prefix.

Example: for the prefix "tw", the top 5 might be twitter, twitch, twilight, twin and twelve.

Check yourself: 1. Why is the request rate high even for a small user base? 2. Why is the storage growth small? 3. What is the time limit, and why?