Skip to end of metadata
Go to start of metadata

You are viewing an old version of this content. View the current version.

Compare with Current View Version History

« Previous Version 3 Next »

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.

Step 2 - High-level design

Step 3 - Design deep dive

Step 4 - Wrap up

  • No labels