Google Typeahead System Design
Tags: database, c, algorithms, programming
Published: 2021-01-27 10:51:12

Search Bar → User is typing a few characters, you should be able to return the top 10 suggestions to the user for the typed char.
Suggestion to be returned should have the maximum frequency in your table. 

type world in search "CA"
CA → 

CAT → 20K <- frequency count
CATTLE → 25K  <- frequency count

CAMEL
CAR
CABS


CATASTROPHIC → 20001   <- frequency count

CAME
CAMEL
CAMELS

If a user searches a particular  word in the search bar if the world is in the dictionary so increase the frequency count of the world and if not found in the dictionary so added the new world into the dictionary

Generally, the high-level design question consists of 4 parts
Requirements.
Estimations.
Detail Design.
Monitoring and Alerting and Backups.

1.Requirements (5-7 mins):
Functional
Should be able to return the top 10 suggestions.
Update the frequency of the word which has been searched. 
Here we are considering only words and not sentences.  (Assumption)
Wait for another 500ms before you return the next results.[Suppose user type CA and wait a second and this time user type CAME then return top 10 results
Spells checks are not required (Out of Scope)[it might be possible used made spell check so you don't need to consider]
Customized Suggestions (Out of Scope)[based on user previous searches]
Region-specific searches (Out of Scope)
Only digits and alphabets have to be considered.
Non-Functional → Req. which as an Engineer should be decided and not considering non-functional requirements might lead to bad design and hamper the user experience. 
Latency → Low approx 10 ms[user type something and give a result within 10ms] 
Availability → High Availability[Result should become as soon as possible and System is available for user]
Consistency → Not required immediately but the system should be eventually consistent.
Reliability
The system should be reliable in the sense that it doesn’t capture user-specific information.
Best suggestions are returned from the <a href="https://www.learnbay.io/system-design-and-design-pattern-2/">System design online course</a>. 
Security layers are in-place. [Authentication or Authorization]
Rate Limiter

2.Estimations (5-7 mins):
When you start with estimation you have to make assumptions or you ask for your interviewer. 
It consists of two parts
QPS
Capacity
Assumptions:
Approx 100M word search per day.
0.001% of the words being searched are new into the system.


QPS (Query Per Second): It consists of two parts
   Read QPS
  Write QPS
Read QPS[Return top 10 suggestion from system]
100 * 10^6 (Per day) / 24 * 60 * 60 (86400)
10^8 /  10^5 
10^3 = 1000 read QPS * 2 (Multiplier) = 2000 
Write QPS[Searching a particular keyword into the system]
Read to write ratio is 3:1 [Because suppose we write something 'CA' gives top 10 results and wait time is 500ms and again type 'CAT' return the top 10 results before we write into what we read from the system. so user read request is 3 and write is 1]
Write QPS → 600 - 700 writes per second.
Capacity[How much capacity in ram or disk or space need to resources]
100M search per day
For an entry 
Word 
Freq
500M (Current Dict.)[Consider only English dictionary]
500M * (7 sizes on avg of each word) * (1 char is 1 byte) * 100 bytes → Words already present[Each word takes space.]
Every Day → 500 M * 0.001 → 50K new words every day.  → 50K * 7 * 100 → 35K * 10^3 = 35M per day new words
For next 1 year
500M*7*100 + 35M*365 bytes 
= 35M * 10^4 +  ~(1M * 10^4)
= 36 * 10^6 * 10 ^ 4 / (1024 * 1024 * 1024)
= 360 GB of data per year. 


3.Details Design (30-35 mins):
APIs[List down all apis]

Read API → User is waiting for the result
Get Request 
get suggestions(char[] prefix);
Return → Nothing, Success/Failure 
The system is a read-heavy system and should optimize for returning the results asap. Return Top 10 Suggestions
Update API →  User is not waiting for the result
Post Request
updateFreqForWord(char[] word)
      Return → Nothing, Success/Failure 

The system is a read-heavy system and should optimize for returning the result asap
Write can be slower as well because users really don’t care about the increase in the frequency.  → Preference to be given to read before the write.
System Design Modelling[ Create design and components]
        There are some components that are always present in the system.
        Client 
        Authentication or Authorization  [Load balancer or Microsystem architecture or Orchestration layer] 
        Web server[read/update api]
        2 load balancer performs business logic
        App server  [Cache] [suggestion service store sorted <a href="https://www.learnbay.io/data-structure-algorithm-in-python-sdet-and-data-scientist/">Data structure training in Python</a>]
        Database
       Replication of Data

  -> Return top 10 suggestion
 -> Return frequency  searched word
->Instead of store key-value, we can store prefix and pair of word and frequency
->Read is faster 
->store key-value [data base-1 for update ] , we can store prefix and pair of word and frequency[database-2 for read purpose
->Initialize a threshold value when it crosses so update database -2 via offline job[comparing frequency and update frequency]
->one table is a frequency table and another table is a prefix table so it does not affect the write database.

Refer diagram:1.1



Tables and Indexes[List down all tables]
SQL DB
NoSql DB
Table 1 (Suggestion Table) 
String prefix ← Key
List<Pair<Freq, String>> top 10 Suggestions
Table 2 (WordFreq Table)
String word ← Key (Pk)
Int64 Freq ← Value
Scaling 
Horizontal [adding more resources instead of changing the size of the resources]
Vertical
Prefer a mix of horizontal and vertical scaling
Sharding and partitioning of  the data : 
Range Based sharding → Suggestion Table
A, B, C…. Z → 26 Instances
2nd layer A is heavily loaded 
AA - AP, AQ - AZ
Date Based shading
For every day you create a separate shard. [you have rolling window]
Word, Freq 
2nd Layer → Range Based 
A-G H-P Q-Z
Replications
       In general, read from the master and write from the slave.
(Suggestion Table) → up to 5 replications[Master -slave] (all servers at the same level)
(WordFreq Table) → (Master-Master) → 2 replications.[You can write two servers at the same time]
Caching  :
		The cache can be a database

80-20 rule
80% of the requests on the system will query for 20% of the data and the remaining 20% of the requests will be querying on 80% of the data. 
Cache those 20% prefixes. 
Trie → Cache Optimize on reading and write 
Invalidations
Strategy to remove a prefix from the cache. 
Load Balancing
Helps in better distribution of load across layers. 
Round Robin Strategy for balancing the load between the servers/machine.
Auths (Authentications and Authorizations)
Not required for this design at the user level. 


4.Monitoring and Alerting and Backups(2-3 mins):

Helps monitor the latency of each of the API.
Monitor success and a failure rate of the API
QPS for each of the API
Monitoring on caches. 
Alerting 
→ Alerts on failure if requests fail x times in a window of a time (1 hour, 10 mins, 20 mins)
Alerting on the latency → If x% of requests from total requests within a window is taking more than t ms to return the results. 
BackUps
Retrieval of data that could be lost because of some bug. 
Product Metrics on backups. 
Create metrics for experiments on backups. 

Digram: 1.1



Cache Design

We need to store words and we should know the top 10 suggestions for every prefix.

   
The latency of returning the response should be below.


CAR → 20k
CAMEL → 30k
CATTLE → 1K
CABS → 4K
CAP
CARTOON
CAGE
CAPE → 100

Problem [ java use hashmap or python use dictionary ]:
We store keys as the word and frequency as values. We have to iterate through all the world present in a dictionary or hash map and see how many start with "CA" return the top 10 suggestions. We need time to save data and need extra memory for appearing in the word  "CA ".
To overcome this problem we use another famous data structure that stores a lot of the words.

<a href="https://www.learnbay.io/data-structures-algorithms/">Data Structures online courses</a>: Tree

Convert tree into trie structure

`````


//initialize constant
private static int HEAP_SIZE = 10;
//structure of TrieNode 
Struct TrieNode {
	int freq;
	int arr[26] children;
	priority_queue<pair<int, string>> suggestions; //for storing string with frequency
};

// cat
Pair<Struct TrieNode*, int> insertWordInTrie(struct Trienode * trie, string word, int index, int freqCount){
//node is null
if(trie == null) {
	Struct TrieNode* trieNode = 
		(Struct TrieNode*) malloc(sizeof TrieNode);
	trie = trieNode;
	trie -> freq = 0;
}
//when we reach at end of the world
if(word.size() == index) {
	trie -> freq += freqCount;
	return make_pair(trie, trie -> freq); //return of pair word with frequency
 }
//node is not null

	Pair<Struct TrieNode*, int> childrenWordFreq = 
		insertWordInTrie(
			trie -> children[word[index] - ‘a’], 
			word, 
			index+1);
	trie -> children[word[index] - ‘a’] = childrenWordFreq.first;
	
	int wordTotalFreq = childrenWordFreq.second;

  	(trie->suggestions).insert(make_pair(wordTotalFreq, word));


           //if tree size is a greater than HEAP_SIZE
if((trie->suggestions).size() > HEAP_SIZE) {
	(trie->suggestions).pop();
}
	return make_pair(trie, wordTotalFreq);
}
//Search word in trie
boolean searchWordInTrie(struct Trienode * trie, string word, int index) {
	if(trie == null) {
	return false;
}

if(word.size() == index) {
	return trie -> freq!=0 ? true: false;
}

return searchWordInTrie(trie->children[word[index] - ‘a’], word, index);
}



priority_queue<pair<int, string>> getSuggestions(
			struct Trienode * trie, string prefix, int index) {
     //if trie null
	if(trie == null)
		return null; 
         //return top suggestion
	if(index == prefix.size()) {
		return trie -> suggestions; 
}

	return getSuggestions(trie->children[prefix[index]-’a’], prefix, index+1);

}


//remove all the words below the tree
Struct TrieNode* invalidateCache(string prefix) {
	// Practice
}


//Driver code
int main() {
	TrieNode trie = null;
	trie = insertWordInTrie(trie, “cat”, 0 // string index, 1);

}

`````




Suggestion service 

<a href="https://www.learnbay.io/competitive-programming-training-online/">Algorithms Online courses</a>

Data Replication



Word with frequency