System requirements

Functional:

• Allow tagging -> normalize tags
• Allow searchability
• Provide tag suggestions

Non-Functional:

• Scalable -> Multiple tags on multiple items could grow quickly
• Prioritize Consistency
• Available but prioritize consistency -> because even if its available but tags are inaccurate, it would be considered as unavailable

Capacity estimation

Tagged Table:

Tag (VARCHAR) -> 21 bytes

ItemName (VARCHAR) -> 21 bytes

ItemID (VARCHAR) -> 16 bytes -> MD5 hash

Assuming every document has 5 tags, each document is ~142 bytes

14 200 000 000 bytes -> 14 200 000 KB -> 14 200 MB -> 14.2 GB

14.2 GB of tagging per day -> will need to scale horizontally

User Table:

UserID (INT autoincrement 4.2B should be good for now) -> 4 bytes

First Name (VARCHAR) -> 8 Bytes

Last Name (VARCHAR) -> 8 Bytes

20 bytes per row

Assuming 4 billion users (4b is an overestimation):

20 000 000 000 bytes -> 20 000 000 kb -> 20 000 mb -> 80GB

No need to scale yet

On average DB can hold 8 ZettaBytes

API design

External Endpoints:

POST:

• addTag/:tag/:item

GET:

• retrieveTag/:tag
• tagRecommendation/:currentPartialTag

Database design

Use Elastic Search DB to find items more quickly (NoSQL) to search by tag

Index by tag and item name

{

UserID: 123,

items: {

item1ID: {itemName: itemName, tags: []},

item2ID: {itemName: itemName, tags: []},

}

}

MySQL for User Table:

• UserID
• First Name
• Last Name

High-level design

• User tags item, can add multiple tags -> POST request to addTag/:tag/:item
• User can search tags on items -> GET request to retrieveTag/:tag
• Elastic search will make searches efficient to retrieve items with tag
• Tag recommendation -> GET request to tagRecommendation/:currentPartialTag
• Elastic search will make searches efficient to retrieve existing tags

Shard ElasticSearchDB by user ID to scale horizontally

Request flows

• User tags item, can add multiple tags -> POST request to addTag/:tag/:item
• User can search tags on items -> GET request to retrieveTag/:tag
• Elastic search will make searches efficient to retrieve items with tag
• Tag recommendation -> GET request to tagRecommendation/:currentPartialTag
• Elastic search will make searches efficient to retrieve existing tags

Detailed component design

Provide Tag Suggestion

-> option 1: Grab all tags and client-side can implement partial search system

-> option 2: Client side implements debouncing method, send request to serverside to get suggested tags

Trade offs/Tech choices

Use elastic search to optimize for tag searches by indexing on tags, and item name

Failure scenarios/bottlenecks

Too many tags, need to scale horizontally, can shard elasticSearchDB by useID range -> shard by userID because it doesnt matter what other people have as tags or what they have tagged on item, we only want to search for the current user

Future improvements

Can add meta data to tags