System Requirements

Functional

1. As a user starts typing a word, the service should be able to suggest relevant words that are close to the currently typed word
2. N words should be suggested by the service, where N is a configurable parameter
3. The N words would be displayed based on priority, when a user presses the tab key the top word is pasted on the screen
4. Users should be able to create their account

Non-Functional:

1. Latency
   1. The most important requirement here
   2. Suggestions should be given near instantly
2. Scalability
   1. The service should be able to handle a growing user base
3. Availability
   1. We prioritize availability over consistency
   2. We are comfortable with the suggestions not being the most accurate but we want the service to be running all the time
4. Reliability
   1. We should store data reliably so that it does not end up being lost in case of network or power outages
   2. We replicate data multiple times over to ensure that data is backed up securely
5. Security
   1. User data should not be compromised in any case
   2. Only authorized users should be able to access the service

Capacity Estimation

1. We assume that we have a total of 100 million users
2. Each user stores 1000 words on average
3. Each word is on average 10 characters long
4. Thus, we would need 10,000 bytes of data per user, which is 10 KB
5. For 1 million users, we would need 10^8 * 10^4 bytes of data, which is 1 TB of data in total
6. Assuming that 20% of our data will be cached, we would need 200 GB of data that will be used to cache in the CDN and user data
7. Factoring in redundancy and other requirements, we would need 5 TB data in total

API Design

1. The key to high performance in this case is the browser being able to cache the responses for that particular user. That way, the user will not have the query the service for suggestions
2. /suggestions/get
   1. GET
   2. Takes in user ID as a parameter. The user can also take in a parameter N, where N is the number of words the user wants to cache
   3. Returns a list of the words that the user mostly types
   4. The list is returned in the form of a JSON
3. /suggestions/send
   1. POST
   2. Takes in a list of words that the user has typed so far. The list is sent in the form of a JSON
   3. Returns success in case of success, error otherwise

Database Design

1. For each user, we are storing a list of words against their user ID
2. We can easily store this data in the form of a key value pair
3. For this purpose, we can use a non-relational key value store like DynamoDB
4. For user data, we prioritize consistency and thus use a relational database
5. For our cache, we can use Redis

High-Level Design

flowchart TD

client[Client] --> loadBalancer{Load Balancer}

loadBalancer --> wordService[Word Service]

wordService --> wordMessageQueue[Message Queue]

wordMessageQueue --> wordDatabase[Word Database]

wordService --> redisCache[Cache]

loadBalancer --> userService[User Service]

userService --> userDatabase[User Database]

CDN[Popular Words CDN] --> client

Request Flows

1. On page loads the word retrieval API is triggered
2. We can also fetch the recent popular words from a CDN
3. We trigger the send suggestions API every M minutes, in which we gather all of the typed words in the last M minutes and send it to the service for storage
4. In case the user is new and their personalized content does not exist, we return the recent most popular words
5. We first look for content in the cache and then the database
6. We make sure we refresh content in the cache every few days

Detailed component design

1. The heart of the whole thing is the trie data structure that can quickly look up words that are close to a given word
2. The trie can look up words in O(logn) time where n is the length of the word
3. We an also store the top N results at each level of the word which would let us not go through the trie and quickly retrieve the result
4. We can also take the trie, serialize it and store it in a key value store which will mean that we do not have to hit the trie at all
5. The time complexity for the fetch operation would drop to O(1) in that case
6. We can build the trie for each user once a week and then serialize it and use the results to suggest words
7. Instead of giving the service every word as the user types it, we would send all the typed words of the user to the service every M minutes, where M is configurable parameter. This ensures that our service is not overwhelmed by a large number of queries every second
8. Words to be stored in the database are not directly added to it but to a messaging queue which then stores the words in the database. This decouples our components and ensures that components keep operating in case a component fails

Trade offs/Tech choices

1. For the user data, we would use MySQL which would provide a high degree of consistency
2. For the word data store, we will use DynamoDB which is a key value store
3. For our messaging queue, we will use Apache Kafka

Failure Scenarios/Bottlenecks

1. The user would not receive new word suggestions in case of a network outage
2. Only the words cached by the user in their browser would be used for suggestions
3. This is acceptable since we are prioritizing availability over consistency

Future Improvements

1. Suggesting emojis based on certain words, for example, typing in 'dog' would bring suggestions of dog based emojis