System requirements

Functional:

1. When user types something with the keyboard, the system suggests an ending of the word or phrase
2. User can accept or reject the suggestion.

Non-Functional:

1. 1 M active users
2. 5 search queries per day
3. 10 words in a search query (about 50 characters)

Capacity estimation

1. About 500 search QPS
2. About 500 suggestion decision RPS
3. About 3 TB of users search data in one year

API design

Search

Method – GET /search

Input – user_id, query

Output – suggestion (string)

Suggestion decision

Method – POST /suggestion

Input – user_id, query, suggestion, decision (accept or reject)

Database design

Search database

For the search database we will use reverse index data structure, that supports full-text search.

Key – query

Value – possible suggestions for this query

Users decisions history database

We can use table-like data structure for the history of users decisions.

Columns:

• user_id
• query
• suggestion
• decision (accept or reject)
• date

The table may be partitioned by date, because we usually need the most recent users decisions

High-level design

1. Load balancer (Nginx). Load balancer will balance the load between backend services using round-robin algorithm.
2. Search service. Stateless backend application, that provides API for the users search.
3. Search database. Database that supports full-text search. For example, Elasticsearch, because it is has active community and the database is highly scalable. The database stores queries and possible suggestions for it.
4. Users decisions service. Service that provides API for receiving users decisions.
5. Users decisions database. The database stores history of users decisions. It has to be scalable, because it will handle big amount of writes of users decisions. It also must handle big amount of requests for retrieving the users decisions history. So I would choose ScyllaDB for this requirements, because it handles big amount of writes and it is highly scalable. This history may be deleted after some amount of time, because we usually don't need to store it infinitely.
6. Users decisions cache. To handle this amount of users decisions history retrieving we will use cache like Redis. It will store history for users that are active right now. It will increase the perfomance of the system.

Request flows

Search flow

1. Load balancer receives a request and sends it to one of search services
2. Search service makes a request to the search database and retrieves suggestions
3. Search service sends request for the last users decisions to the Users decisions service
4. Users decisions service retrieves last users decisions from cache. If the cache is empty, the service retrieves decisions from the database and puts them in cache. Users decisions service returns last users decision to the search serivce
5. Search service may use some machine learning algorithm to rank the suggestions using history of last users decisions
6. Service returns most suitable suggestion to the user

Detailed component design

Search database is built on Elasticsearch technology. It supports horizontal scaling.

We use ScyllaDB for users decisions database. The history data will be sharded with user_id as a key, because we always retireves data for a specific user. We also use partitioning using date of the decisions. So we can store last and most relevant decisions on the fast part of the database.

The users decisions cache will be horizontally scalable using Redis Cluster technology.

Failure scenarios/bottlenecks

All the services are stateless, so they are well scalable horizontally.

All the databases are also highly scalable and available.

Future improvements

We may optimize the ranking algorithms, so users will like the suggestions more. We also can add some more caching in the search flow, if we will need to decrease latency.