Typeahead Suggestion
Topic: Typeahead Suggestion
Interviewer: Iris
Interviewee: Smile
Level: L5 (Senior)
Topic
Mock System Design Interview Summary
Interview Overview
Date: 1/16/2022
Target level: L5
Duration: 45 minutes
Topic covered: Typeahead suggestion
Drawing tool used: excalibur
Key problem vote: ?
Requirements
Functional requirements
Google auto complete suggestions
How many suggestions: 10
Use frequency
How long to track data: 10 days
English
User -> customization
Location -> focus on US market first
Non functional requirements
Low latency
High QPS: 20 characters -> call 20 times
Scalability
Availability
reliability
Estimation:
Daily 5billion a day -> 60,000 queries per second
Storage:
5B * .2 = 1B new queries per day
20 characters, ASCII code, 20 bytes
20 G data everyday
10 days => 200 GB. Can put everything in memory
System Design
External APIs
API
getSuggestions(String) -> list
6:25
System design
Optimization
Precompute top 10 frequent queries for trie node
Example:
A: apple amazon airbnb
Pros: reduce latency
Cons: cost space
Limit the depth of the tree
E.g. if 30 characters long then
Limit the depth of trie: 10, 26 lower case letter: N layers, 26 ^ N
Server side cache
Client side cache
Additional optimization:
Add cache, e.g. redis
Cache will hold most frequently used queries
scalability
Interviewer: What about scalability?
Interviewee:
26^10 = 100? trillion records 10^12
May not be able to put all
Partition range based: a-b: partition1, c-d: partition 2
Dynamic rebalancing: ab, ac-ad
availability
Load balancer will stop sending to dead server
Cache: redis cluster
ServerDB: replication
Audience: “There is tech talk from FB, they point out trie: 1. An extra pointer 8 bytes waste lots of storage 2. If save trie in disk, random access is expensive.”
Logs: log files
Clean, transformation: (worker)
Frequency: noSQL for frequency DB. DynamoDB, cassandra, can handle replication by default
Interviewer:
Add machine learning recommendation
Search history, location and demographics
Machine learning model
(interviewee: latency)
Now continue with ML
Location. Can partition by geography. TrieDB per location
User: may not be able to save everything, just save 10 day query
1B users
UserID, queries
Need to clean up manually, or use database trigger to truncate the database
Machine learning model with user, queries
Interviewer:
How to update the trie?
Real time - probably not worth it since there are too many users
At certain interval, e.g. 5 minutes
Worker to create a new trie, hot replace
Master slave for trie server?
If master is down, we can promote a slave
Write not block read using snapshot isolation
update frequency / count in the trie
Batch process: mapreduce
Update every 10 days
1 DB per day
11 day: remove 1st day’s data
Potentially use moving averages to give more weight to recent data?
Answer: yes can give different weights to different days
How do we blacklist some keywords/phrases?
Add a filter in our application server, remove it from cache, trie DB
Another optimization:
Can do every 10 queries
Can reduce amount of data by 1/10
Interviewer and Audience Feedback
Interviewer:
Well structured
Solid answers
Clear presentation
Good time control
Good clarification at the beginning
Tips: localization, US market, English only, think from user flow
Tap search query
Give recommendation
Ranking
How to update phrases offline
Frequency DB: dynamoDB, cassandra, timestamp, user ID
Will be good to select the exact database, database tradeoff
Track metrics
Soft skill
==
Like like
Interviewee: did not drive
Now interviewer: cannot ask question
Interviewee: can drive harder
Machine learning, user
===
Soft skill: basically, because, transition words
In my own understanding
Do you have some preference? We
==
Hard skills
Trie
Vs hashtable
Frontend cache is a hashtable
Trie is in database
Trie: load in cache?
Trie
Key is the prefix
Trie: prefix, value: list of suggestions
Prefix hashtable
How do we set up the hashtable?
First trie -> then compute a hashtable out of suggestions
Cache with trie. How do we scale?
Key: prefix. Value: suggested
Key value pair
A is the key:
ABC as the key: suggestion as value
Google or other companies: type “goo”: we will load more than goo. 10 words. Goog
Goo: 10 suggestions
Goog: 10 suggestions
Good: 10 suggestions
Some prediction
Tradeoff - hashtable vs trie?
Trie vs hashmap
20 character
N^2 prefixes
Trie has much less consumption than hashtable
Not all character has corresponding
Why use key value not trie
Audience:
GOO
大概率 会用 GOOG
把 GOO’s 10 suggestions + GOOG’s 10 suggestions
Then
Low frequency: trie to save memory
All query goes to cache?
Go to server DB
Every server holds the whole trie
Some servers hold a-c, some servers hold d-f
Trie: hot tablet
Trie and hashtable should be combined
Want to know a strong reason to choose hashtable
Using trie: scalability is a bit more difficult
High frequency: use hashtable
Low frequency: use trie
Latency 100 ms: compute and storage are together
Same CPU thread
From the same CPU
Need to use Redis, and use Redis computation, Need to use CPU process to return
In memory operation no huge difference between hashtable vs trie
Trie vs hashtable
Hashtable is closer to the user
Trie is further away from the user
We can load-test hashtable vs trie
First GOO
Then type GOOG
Therefore GOOG need a new query
Hashtable: location can be flexible
Trie: always need to put in the trie server
Trie must be at trie server
NoSQL store. Can be put at any server
Fake trie
Trie is implemented by key-value store (hashtable).
GOOG
How big a hashmap, how much cost, memory
popular - best effort
Need to quantify to have meaningful
Cache: not saved all information, LRU
Same memory, trie can hold more things
Today most popular
GOOGL
热搜榜
Earthquake - 2 days. Not make sense
Training - trie or hashtable
Trending words, hot words
Log - emit to message queue
consumer
5-10 minutes delay
Message queue 5 minutes a lot. Not very hard
Trending words may be different from
Search query based count -
Background job to update cache server
Real time streaming system.
One day
Do we need to maintain 2 systems?
How do we merge results?
Lambda
Batch - 1-2 days
Streaming - not very stable
Seconds/ minutes
Big batch: daily
Small batch: 2-3 hours
Streaming: kafka
Work on the same data structure or different data structure?
Write to different databases.
Top 100, top 1000
Maintain a priority queue
Cache: top 10
Trending words: leaderboard?
Prefix, trending words.
Prefix top
Every prefix maintain a top 10 list
Query from both sides then merge
How to maintain, how to merge?
Machine learning
Streaming
九章：same system for 2 hours versus daily
Combine: give higher weight for 2 hour
Batch: db
If we use the same structure for
Add to trie DB
Set bigger weight for top 100
Flink
Or redis: top K.
Redis Z-set (sorted set). There is a score
Top 10, Top 100
I can also see between top 10 - top 100
Redis sort - always
跳表 - Skip list
Use weight / score
Order set, sorted set.
Score + 1, skip list, sorted list are updated
Timestamp
Frequency are computed by map reduce
Hashtable word -> count
Cache will always expire
Does not need to maintain high consistency
Stream processing: you can set a window
Word count within the window
Redis: 30 expiration
Flink: also 30 minutes
2 APIs
Typeahead API
Actual search API
Every second 100k
10k
We can separate based on language/business line