System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• present the user with a set of suggestions in real-time as she is typing
• If no suggestions available, display 'No suggestions Available'

Non-Functional:

List non-functional requirements for the system...

• correctness - display valid suggestions
• responsive and real-time - suggestions to be shown as the user is typing
• light-weight service
• system should have as many words or phrases in its vocabulary to provide useful suggestions

Capacity estimation

Estimate the scale of the system you are going to design...

For a web-based service like Google or Amazon Search, the number of searches per second is very high - 10 million per second approx

Number of search words or phrases in a language = 1 million approx

Average size of 1 word = 10 bytes

Amount of storage for storing 1M words/phrases = 10 MB

This is a read-only system for an end-user. A user never updates the suggestion system. This is a stateless service

API design

Define what APIs are expected from the system...

• Client Plugin requests a set of suggestions

GET https:///suggestions

Response - a trie of top ranked suggestions

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

This is a read-heavy system.

Given the volume of data and number of concurrent requests, a NoSQL Database using Key-Value Store is suitable for the system.

Key:

word/phrase. --- String

Value:

rank. ---- long

In-memory, the suggestions are stored using a 'Trie' data structure.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Overall Architecture

===============

User: End-user which performs the search and gets suggestion. The user may or may not search with the available suggestions.

Client Plugin: The type-ahead suggestion system has a client plugin which runs on the client's browser or app. This is required to avoid latency where each character typed by the client is sent to server and the response is obtained back. This can be an AJAX plugin.

Suggestion Service: Service running on the Server. The client plugin gets a set of suggestions from the service on startup.

Suggestions DB: Persistent store of suggestions for each word and phrase

Search: When the user presses 'Enter' the requested word or phrase is given to the Search service. Search service provides feedback to the Suggestion Service to build its vocabulary and rank the suggestions.

Components in the Suggestion System

===============================

Ranker: Assigns a rank to each word or phrase based on how frequently it is used, most recent searches by a user, trending searches etc. Results with higher rank are displayed first.

Vocabulary Builder: Adds new words and phrases as users use them to Search.

Both Ranker and Vocabulary Builder use feedback from the Search system.

Cache: A cache of trending searches, recent searches etc.

De-duplication: A periodic job which de-duplicates the phrases which mean the same, for example - 'restaurants near me' and 'nearby restaurants'.

Suggestions DB: Persistent Store of words and phrases offered as suggestions.

The suggestion system uses a combination of static and dynamic words/phrases to build the suggestions.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Initial Startup Before Any Feedback is Available

=====================================

• The suggestion service starts with a list of 'seed words/phrases' initially. This seed set is provided to the client plugin.

• As the client types, the client plugin provides suggestions

Subsequent Searches

==================

• The client plugin periodically fetches updated suggestions from the server as the vocabulary builds and gets updated via feedback

How many suggestions are provided?

The Suggestion system can provide the top 5 suggestions for each phrase to the client, to avoid overflowing the Client's memory.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

The suggestion system stores suggestions as 'tries'. Each node has an associated rank .

Overall Architecture

===============

User: End-user which performs the search and gets suggestion. The user may or may not search with the available suggestions.

Client Plugin: The type-ahead suggestion system has a client plugin which runs on the client's browser or app. This is required to avoid latency where each character typed by the client is sent to server and the response is obtained back. This can be an AJAX plugin.

Suggestion Service: Service running on the Server. The client plugin gets a set of suggestions from the service on startup.

Suggestions DB: Persistent store of suggestions for each word and phrase

Search: When the user presses 'Enter' the requested word or phrase is given to the Search service. Search service provides feedback to the Suggestion Service to build its vocabulary and rank the suggestions.

Components in the Suggestion System

===============================

Ranker: Assigns a rank to each word or phrase based on how frequently it is used, most recent searches by a user, trending searches etc. Results with higher rank are displayed first.

Vocabulary Builder: Adds new words and phrases as users use them to Search.

Both Ranker and Vocabulary Builder use feedback from the Search system.

Cache: A cache of trending searches, recent searches etc.

De-duplication: A periodic job which de-duplicates the phrases which mean the same, for example - 'restaurants near me' and 'nearby restaurants'.

Suggestions DB: Persistent Store of words and phrases offered as suggestions.

The suggestion system uses a combination of static and dynamic words/phrases to build the suggestions.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

• Client Plugin running on the client's browser to avoid Round Trip Latency to/from the server.
• Dynamic and Static ways of building the vocabulary

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

• As the suggestion vocabulary increases, it can be difficult to store it in a single DB. 1 possible solution are: 1)sharding

• DDoS: The service can get overwhelmed if it gets a very high number of requests concurrently. This can be addressed by using rate-limiting and installing a CDN to serve the requests of Client Plugin

• Single Point of Failure: A single Suggestion server can cause the service to be unavailable in case of a failure. In-sync replicas on standby can be used to mitigate this.

• Building in-memory Trie on Startup or Recovery: Building the in-memory Trie can be time consuming. Many caching solutions provide a persistent cache and can tolerate DB failures for hours.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

• multiple languages - The type-ahead suggestion system can be enhanced to show suggestions in multiple languages
• personalization - personalization can be incorporated by using Machine Learning techniques.