System requirements

Functional:

• The system should be able to tag any item given an item_id
• You should be able to retrieve a list of items that has a specified tag

Non-Functional:

• Should be reliable, meaning a tagged item should not suddenly become untagged
• Tags should be retrieved quickly, even with a large number of items and tags.

Capacity estimation

Traffic estimation

• 10 million users
• each user tags 5 new items a day
• each user queries 10 tags a day

Storage estimation

• Item_id - 8 bytes
• tag_id - 8 bytes
• Assuming we keep data for 10 years
• 16 * 10 million * 5 * 365 * 10 bytes = 3TB

Bandwidth estimation

• Read estimation
• Assuming we retrieve 10 tagged item each request
• 10 * 10 million = 100 million requests a day
• 4 million requests an hour
• 70,000 a min
• 1200 a second = 18KB a second
• Write estimation
• 9KB a second

Cache estimation

• Assuming we want the cache the top 20% of the most queried tags a day
• Assuming out of the 100 million requests a day, 1 million of those requests are unique
• meaning we have to keep the data of 200,000 tags in cache, assuming we want to cache the first 20 items given a tag in the cache, meaning we have to keep 2 million items in memory
• 30 MB total

API design

tag_item(tag, item_id) - adds a tag to an item

query(tag) - retrieves the first 10 item_id that are associated to the tag

Database design

We want use a database that is very scalable as our service could potentially have increased amounts of traffic. We will hence use a NoSQL database like MongoDB for this purpose, this is because horizontal scaling is easily done with this kind of DB. We will not use SQL as it is not easily scalable

For our cache, we will use a key value cache like Redis or Memcache. We will use the Least Recently used algorithm to evict data

High-level design

Client -> server -> DB

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

When a user requests the list of items to be retrieved, we do not want to return the whole list from the DB and return it to the user, this should be done in chunks, a list of 10 or so can be returned every time a request is made, more will be loaded as the user scrolls down. This is to ensure that there is good user experience as multiple users querying a whole list of items from a given tag can take a very long time, it might even crash the system depending on how many items are associated with a tag

How are we able to do this? the server should can retrieve the first 10 items from the DB, then as the user scrolls down, the server can retrieve the next 10, and so on. We can keep the chunks in a linked list, a linked list is associated with a user, the server will continually query the next 10 items from the DB, while the user continues to consume and scroll from the front of the linked list. this ensures that there is little latency when loading up the next 10 items from a tag.

In terms of data sharding, how can we ensure that the data is evenly distributed? a suggestion could be that we distribute based on the tags, meaning all items of a associated tag is sent to one DB. However, this will not be a good idea especially if there is a popular tag, or a tag has many items associated with it. this could overwhelm 1-2 DBs while the rest are not queried as often, leading to an uneven distribution of load. What we could do is to distribute them by chunks, meaning the first 10 items go to 1 DB, then another 10 goes to another DB and so on. This evenly distributes the differnet chunks to different DBs. this means that we should keep an in memory storage like a HashMap (key, array) once the array reaches a size of 10, then dump them into the DB

In terms of caching, we might want to cache the top 20% of tags a day, however i think that caching the top 20% of chunks a day would be a better idea, this is because for popular tags, the top 1000 items might be extremely popular queries as compared to other tags which only retrieves the first 10 or 20 items. Hence we should keep chunks in the cache instead of the first 10 items of each tag.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

We could potentially have a functionality that allows users to edit and delete tags, we could also have a functionality that allows a user to tag multiple items at once