System requirements

Functional:

• A user type begins typing and recommendations are displayed as suggestions
• Suggesting are listed below the input
• Show 10 be default
• don't display suggestions unless there at least 2 words

Non-Functional:

• Real time recommendation could be limited depending on the system load
• (Latency) Return suggestion in under 100 ms
• (Scalability) The system should be able to scale horizontally to accommodate growing numbers of users and traffic seamlessly. For example, it should support an increase in daily active users from 1 million to 5 million without a degraded performance.
• (Capacity)
• Aim for a high availability target of 99.9%, ensuring that users can access the service without interruption, even during maintenance periods.

Capacity estimation

10m suggestions per day * 70b = 700 MB a day

255.5 GB a year.

since I am caching the prefixes we will have to increase the amount of data by the binomial coefficient. 60 + 50 + 40 + 30 + 20 + 10 = 210b

2.10 GB a day and 765GB a year

If users continue to search for the same things we shouldn't have to create too many more records. The first year will create the most data giving 10m suggestions per day.

API design

getSuggestions(string search, string locale, {lat,long} location): string[]

query on each new word added to the search query

Database design

We will use mongoDB for storing the search queries in tries.

With the prefix being the ket and the values being the suggestions.

For each prefix, we will create a separate record

ex: How many baseball fields are in Kansas?

k: how v: [text: many baseball fields are in Kansas, w: 1, text: many people like apples, w: 7]

k: how many v: baseball fields are in Kansas, w:3

k: how baseball v: fields are in Kansas, w: 101

The db will have weight values allowing us to rank which.

Reranking the values will have to be don once the user has chosen a suggestion

High-level design

• Redis will be used to cache the most hot search queries
• MongoDB is noSQL so horizontal scaling will be easy
  • The values will be ranked and returned in rank order
  • A user selects a suggestion the other rank values will be decreased
• Read DB replica to free up DB from writes and provided backup
• Suggestion Service will look up the tries for the current search. Checking the cache and then hitting the DB
• DB records will be updated from the Suggestion Update service that pulls from a kafka stream.
• Read DB will be updated when disk I/O is low or 1 minute has elapsed

Request flows

Detailed component design

LB is round robin

API gateway will rate limit

Suggestion Service gets the highest-ranked suggestion from the cache

Trade offs/Tech choices

Consistency issues with DB. You will get different suggestions

Issues doing any complex queries that may be user-specific. So we can't tailor suggestions to a specific user efficiently.

Failure scenarios/bottlenecks

The bottlenecks would be updating prefix trie records that have very common 2-word starts?

How many

Where is

How do

...

Future improvements

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