CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 3 of 8 · 1 min read

First design

A table and a SQL query.

The book splits the system in two.

  • Data gathering service: collects the queries users type and counts them.
  • Query service: given a prefix, returns the 5 most frequent queries.

First version. Keep a table of query and frequency. When users search "twitch", "twitter", "twitter" and "twillo", the table shows twitch 1, twitter 2 and twillo 1. To answer "tw", select the rows whose query starts with "tw", order by frequency, and take 5.

This works for a small table. At scale the database becomes the bottleneck. Every key press means a search over a large table, with up to 48,000 of them a second at peak. A faster structure is needed.

A worked example (made up). Suppose the table holds 100 million queries and a prefix matches 500,000 of them. Each key press would have to sort 500,000 rows to find the best 5. Doing that tens of thousands of times a second is not possible within 100 ms.

Common mistake

Running the top-5 query against the main database on every key press. It is correct but far too slow, and it would harm the rest of the product that shares the database.

Check yourself: 1. What does the data gathering service do? 2. Why does the first design fail at scale? 3. What makes the prefix "tw" costly in the example?