Versions Compared
| Version | Old Version 2 | New Version 3 |
|---|---|---|
| Changes made by | ||
| Saved on |
Key
- This line was added.
- This line was removed.
- Formatting was changed.
| Tip |
|---|
The Framework proposed in this space (Alex Xu) is applied to propose a design : Getting started - a framework to propose... |
Introduction
Autocomplete or word completion is a feature in which an application predicts the rest of a word a user is typing. In graphical user interfaces, users can typically press the tab key to accept a suggestion or the down arrow key to accept one of several. Autocomplete is involved in many search features on various platforms like Facebook, Instagram, Google search, etc.
Step 1 - Understand the problem and establish the scope
Matching at the beginning or the middle ? | both. |
|---|---|
How many suggestion should be returned ? | 5 |
How system knows which 5 suggestions to return ? | Popularity, decided by historical query frequency |
System supports spell check ? | NO. |
Search queries in English ? Multi-language ? | Yes, for now. |
Allow capitalization and special characters ? | NO. |
How many users ? | 10 million DAU (daily active user). |
Requirements
Fast response time : within 100 ms. So, low latency.
Relevant to the search term whatever prefix user has entered.
Sorted : By popularity or other ranking models.
Scalable : High traffic volume.
Highly available : remain available and accessible when system is offline, slows down or experiences network errors.
Back-of-the-envelope calculations
Traffic estimations
Assume 10 million DAU
Average person performs 10 searches per day.
20 bytes of data per query string : assume 4 words and each word contains 5 characters on average.
4 words * 5 characters = 20 bytes per query.
For 1 character entered in search box, a request is sent to the backend : average 20 requests are sent for 1 search query.
10 million * 10 queries / day * 20 characters / 24 hours / 2600 sec = approx. 24 000 query per sec (QPS).
Peak QPS = QPS * 2 = approx. 48 000 QPS.
Storage estimations
Assume 20% of daily queries are new. 10 million * 10 queries per day * 20 bytes per query * 20% = 0.4 GB → new data added to storage daily.
0.4 GB *365 = 146 GB per year.
On this page.
| Table of Contents |
|---|