Case study: Search autocomplete

You type three letters in a shopping app, and a list of ideas appears under the box. The list changes with every letter. The interviewer says: "Design search autocomplete."

A weak answer runs a database query on every key press, or says "use Elasticsearch" and stops. A strong answer says why the list must be ready before the request arrives. It shows a structure where one step is one letter. It also says how a new popular phrase gets in within minutes, and how a rude phrase is removed fast.

At SDE-2 level you should explain the structure, the numbers and the refresh. At SDE-3 level you should also cover safe swaps, trending phrases and a failing part.

Think of a printed dictionary with a thumb index. To find the words that start with "ip", you open one page. All of them are together. Now imagine that someone writes at the top of each section the 8 words that people look up most. You open the page, read the top, and you are done. You never read the whole section.

Autocomplete works in the same way.

What we build

A shopping app has a search box. The letters typed so far are the prefix. For example, "iph" is a prefix of "iphone 15". When the customer pauses, the phone sends the prefix. The server returns up to 8 suggestions: the phrases that start with the prefix and that people search most. Each phrase has a score, a number for how popular it is. A phrase that people search more has a higher score.

The requirements:

1. The prefix has at least 2 letters. The answer has up to 8 phrases, best first.
2. The answer must be faster than the typing. The target is 100 ms for 99 of 100 requests (the p99, lesson 4), measured at the phone.
3. A new popular phrase must show within minutes.
4. An unsafe phrase must never show, and it must go away fast.
5. One person's own searches must never appear for another person.

We keep to prefixes. Spelling fixes (fuzzy search, lesson 80) cost more work, so we leave them out.

Why a normal query is too slow

A database query could be WHERE phrase LIKE 'ip%' ORDER BY count DESC LIMIT 8. A B-tree index (lesson 20) can find the start of the "ip" range fast. But the database must still read every phrase in the range to sort them by count. If 1,000,000 phrases start with "ip", one key press reads 1,000,000 rows.

The inverted index of lesson 80 does not help either. It finds whole words, and it ranks by text match, not by how often people searched the phrase. So the answer must be ready before the request comes.

The trie

A trie (say "try") is a tree where each node stands for one prefix. Each edge is one letter. The path from the root to a node spells its prefix. Here is a trie for two phrases, "ipad" and "iphone":

• root
  • i
    • p
      • a, then d (the phrase "ipad")
      • h, then o, n, e (the phrase "iphone")

To look up "iph", start at the root and follow i, then p, then h. That is 3 steps. The number of steps is the number of letters typed. It does not depend on how many phrases the shop has.

The best 8 on every node

The node for "ip" has a million phrases below it. Walking all of them is the slow query again. So each node keeps a list of the best 8 phrases below it, with their scores. A lookup is now: walk the letters, then read the list at the last node.

The cost is memory and a build step. To save memory, a node holds 8 phrase ids of 4 bytes each. One phrase table holds the text and the score of each phrase once. A node deep in the trie that has 8 or fewer phrases below it needs no list. It can point to them. We ignore this saving in the numbers.

Build. For each phrase, for each of its prefixes, offer the phrase to that node. The node keeps the 8 highest scores. The work is about the number of phrases times their length.

Why build offline? One new search can change the lists of up to 25 nodes, one for each letter of the phrase. Doing this live, while servers read the same nodes, is hard to keep correct. So we build a new trie in a separate place and replace the old one. Nobody changes the trie that readers use, so readers never wait.

Where scores come from

The app writes each search as an event to a log (lesson 59). A job counts the events. Two rules protect the list:

• Count each person once for each phrase for each day. One program cannot push a phrase up by repeating it.
• Leave out a phrase that fewer than 5 different people searched. Rare phrases can be private.

The score is our choice: searches in the last 7 days + 5 x searches in the last day. New counts weigh more, so old topics fade. This is a simple form of the decay in lesson 82.

The job needs exact counts, and the table of phrases fits on one machine. So we do not need the count-min sketch of lesson 82. Use a sketch only when exact counts do not fit.

Keeping it fresh: two layers

The base trie is built every few hours. A phrase that starts trending now would wait for the next build. So we add a trending layer:

1. A stream job is a program that runs all the time and reads new events as they arrive. Here it counts searches for each phrase in 1-minute buckets (lesson 82).
2. A phrase with at least 500 different people in the last 10 minutes joins the trending list.
3. A small trie of only the trending phrases is rebuilt every minute.
4. For each request, the server reads up to 8 phrases from the base trie and up to 8 from the trending trie. It removes repeats, removes blocked phrases, ranks by score and returns 8.

A trending phrase gets the score of its searches in the last 10 minutes x 100. This is our choice, so that it can enter the top 8.

Safe swap. The build job writes a file to object storage (lesson 24). A server loads it next to the old trie and runs checks. The size is close to the old size, test prefixes give answers, and no blocked phrase is inside. Then it starts to use the new trie in one step. It keeps the old file, so a bad build can be undone in seconds.

Blocked phrases. A blocklist is a short list of phrases that must never show. The server checks it on every answer. A new entry works in seconds, with no rebuild.

Serving

The data fits in the memory of one server. So every server holds a full copy, and the load balancer (lesson 28) can send any request to any server. We add copies for traffic. We split data only for size.

• The phone waits 150 ms after the last key press, asks only from 2 letters, and cancels an old request when a new key comes.
• Short prefixes. The 2-letter and 3-letter prefixes are few and change slowly. A CDN (lesson 36) keeps their answers for 5 minutes.
• Personal suggestions. The phone adds the customer's own recent searches. The shared answer never holds personal data. A shared cache stores a response under the prefix, so the next person would receive it.
• Failure. If a server dies, the load balancer stops using it. If all suggestions fail, the app hides the list. The search box still works.

A shopping app builds autocomplete.

Assumptions (made up to teach with, not real data):

• 50 million people use the app each day, with 6 searches each: 300 million searches a day.
• The phone sends 5 requests for each search. The peak is 3 times the average (lesson 14).
• 40% of requests are for 2-letter and 3-letter prefixes, which a CDN answers.
• 50 million different phrases of 25 letters on average. The trie has 300 million nodes, because phrases share prefixes. A node takes 64 bytes: 32 for 8 ids and 32 for the letter and links. A row of the phrase table takes 29 bytes: 25 for the text and 4 for the score.
• 1,000,000 phrases start with "ip".
• One server answers 5,000 requests per second. We plan for 70%. Servers have 64 GB of memory.
• A search takes 100 bytes in the log.

Step 1: requests. 300,000,000 x 5 = 1,500,000,000 requests a day. 1,500,000,000 / 86,400 = 17,361 per second. The peak is 17,361 x 3 = 52,083 per second.

Step 2: servers. The CDN takes 40%, so servers see 60%: 52,083 x 0.6 = 31,250 per second. At 70% a server takes 5,000 x 0.7 = 3,500. 31,250 / 3,500 = 8.9, so 9. We want one zone to be able to fail, so we run 9 in each of 2 zones (separate groups of data centres): 18 servers. If a zone fails, 9 servers take 31,250 / 9 = 3,472 each, which is 69%.

Step 3: memory. The nodes: 300,000,000 x 64 bytes = 19,200,000,000 bytes = 19.2 GB. The phrase table: 50,000,000 x 29 = 1,450,000,000 bytes = 1.45 GB. Together 20.65 GB. During a swap a server holds two tries: 2 x 20.65 = 41.3 GB, which fits in 64 GB. A server with 32 GB would fail at the swap.

Step 4: lookup against scan. For "iph" the lookup takes 3 steps, and then it reads 8 ids. This answers the predict box. For "ip", a scan reads 1,000,000, against 2 steps. That is 1,000,000 / 2 = 500,000 times more.

Step 5: build. 50,000,000 phrases x 25 letters = 1,250,000,000 offers to a node. Assume one core does 5,000,000 offers per second: 1,250,000,000 / 5,000,000 = 250 seconds, about 4 minutes. Assume the whole job (count, build, check, write the file) takes 30 minutes, and it runs every 3 hours. A new phrase can wait up to 3 hours + 30 minutes = 3.5 hours.

Step 6: scores. "iphone 15" has 100,000 searches in 7 days (counted by the rules above), 40,000 of them in the last day. Score = 100,000 + 5 x 40,000 = 300,000. "iphone 14" has 120,000 in 7 days and 10,000 in the last day. Score = 120,000 + 5 x 10,000 = 170,000. The newer phone ranks first, although the older one has more searches in total.

Step 7: trending. A new phone launches, and 40,000 searches a minute arrive. In 10 minutes that is 400,000 searches. Assume most come from different people. This is far above the limit of 500 people. Assume the log pipeline needs up to 2 minutes, the bucket 1 minute, the rebuild 1 minute and the servers 1 minute to load it. The phrase shows in at most 5 minutes, not 3.5 hours. The last hour holds 300,000,000 / 24 = 12,500,000 searches. Assume 3,000,000 different phrases at 50 bytes: 150 MB. Exact counts fit, so no sketch is needed.

Step 8: the log. 300,000,000 x 100 bytes = 30 GB a day.

• A trie with the best 8 on each node solves speed: 3 steps, not 1,000,000 rows. It costs 20.65 GB of memory, a build job, and data that is up to hours old. I would use a plain database query when the phrase list is small.
• A trending layer solves the delay of the base build: 5 minutes, not 3.5 hours. It costs a second structure and a merge on every request. It also needs checks against abuse. I would add it when new topics matter, as in a shop with launches.
• Full copies solve uneven load. They cost memory on every server. I would split the data only when it no longer fits, and then split by a hash of the first 3 letters.

"A database index on the phrase column makes autocomplete fast." The index finds the start of the range. The database still reads and sorts every phrase in it, which is 1,000,000 rows for "ip".

"I should update the trie on every search, so it is always fresh." One search changes the lists of up to 25 nodes, while readers use them. Build a new trie in a separate place, and use the trending layer for speed.

"I will give each server some first letters, so each holds less." The data is only 20.65 GB, so there is no need. Letters are not equally busy. Suppose there are 26 servers, one letter each, and 3 letters carry half of the 31,250 requests. Those 3 servers get 15,625 / 3 = 5,208 each, which is 104% of their limit. The other 23 servers get about 679 each.

1. What is a trie? Why does each node keep its best 8 phrases?
2. A trie has 200,000,000 nodes of 64 bytes each. The phrase table has 30,000,000 rows of 24 bytes each. (a) How much memory does one trie need? (b) How much is needed during a swap? (c) At the server, 20,000 requests per second arrive. One server takes 4,000 per second, and you plan for 70%. How many servers do you need?
3. A new phone launches at 6 pm. At 9 pm the suggestions show only old models. The base trie is built once a day at 3 am. Why does this happen, and what do you add?