Requirements

Functional Requirements:

• Tag Creation
  • the user should be able to create tag for item

• Tag Assignment
  • the user should be able to assign tag to item

• Tag Deletion
  • the user should be able to delete tag

• Tag Removal
  • the user should be able to remove tag from items in the system

• Tag Search
  • the user should be able to search item based on tags

• Tag Normalization
  • the system must be able to merge similar tag together

• Tag Suggestion
  • the system must be able to suggest tag for the item

Non-Functional Requirements:

• Low Latency
  • the response time should be < 100 ms

• High Availability
  • 99.99% up time

• Scalability
  • able to handle 23.1481 reqs/s during normal load
  • able to handle more than 231.481 reqs/s during peak time

• Durability
  • the relationship between tags and items must be retained until deleted

• Consistency
  • every user got the same data eventually

Capacity Estimation

• Assumption
  • Total users: 1,000,000 users
  • Active users per day: 10,000
  • Each user make 200 requests/day
  • Max tag number = 15 tags per item

• Load
  • in average there is about 200 * 10,000 = 2,000,000 requests/day
  • hence average rps = 2,000,000 / (60*60*24) = 23.1481481481 reqs/s
  • can peak at 231.1481 reqs/s

• Storage usage
  • tags
    • each tag take 50 bytes of space
    • there can be a billion of tags
    • take 50 GBs
  • items
    • image only
    • there can be a billion of items
    • each item take 1 KB in average
    • take 1 TB
  • we need about 1.5 TB
  • 2x error factor -> we need about 3 TBs

API Design

External API

1.Tag Creation

• Method: POST
• endpoint: /{version}/tag
• body:
  • tag_name: str
• response
  • Create new tag success
    • status_code: int: 200
    • status: ENUM: SUCCESS
    • tag_id: id: new tag id

• • Duplicate tag
    • status_code: int: 409
    • status: ENUM: ERROR
    • message: str: can't create duplicate tag

• • Bad Request
    • status_code: int: 50x
    • status: ENUM: ERROR
    • message: str: something went wrong at the backend.

2.Tag Assignment

• Method: PATCH
• Endpoint: /version/item/{item_id}/addTags
• Path Variables:
  • item_id: id: item's id
• Body:
  • tag_ids: list[id]: ids of tag added.
• response
  • Assigning Succeeded:
    • status_code: int: 200
    • status: ENUM: SUCCESS
  • Duplicate Tag
    • status_code: int: 409
    • status: ENUM: ERROR
    • message: str: this item already had this tag
  • Item Not Found
    • status_code: int: 404
    • status: ENUM: ERROR
    • message: str: item not found
  • Bad Request:
    • status_code: int: 50x
    • status: ENUM: ERROR
    • message: str: something went wrong at the backend.

3.Tag Deletion

• METHOD: DELETE
• endpoint: /{version}/tag/{tag_id}
• Path Variables:
  • tag_id: id: id of tag that need to be deleted
• Response:
  • Delete Success:
    • status_code: int: 200
    • status: ENUM: SUCCESS
  • Used Tagged:
    • status_code: int: 460
    • status: ENUM: ERROR
    • message: str: this tag is currently being used.
  • Service Unavailable:
    • status_code: int: 503
    • status: ENUM: ERROR
    • message: str: backend went down

4.Tag Removal

• METHOD: PATCH
• Endpoint: /{version}/item/{item_id}/delTags
• Path Variable:
  • item_id: id: item's id
• Body:
  • tag_ids: list[id]: ids of tag that need to be deleted
• Response:
  • Remove Succeeded:
    • status_code: int: 200
    • status: ENUM: SUCCESS
  • Item Not Found:
    • status_code: int: 404
    • status: ENUM: ERROR
    • message: str: item not found
  • Service Unavailable:
    • status_code: int: 503
    • status: ENUM: ERROR
    • message: str: backend went down

5.Tag Suggestion

• Method: GET
• Endpoint: /{version}/suggest_tag/{item_id}
• Path Variables:
  • item_id: id: id of item
• Response:
  • Success:
    • status_code: int: 200
    • status: ENUM: SUCCESS
    • suggested_tags: list[id]: list of tag id suggest by our system
  • Service Unavailable:
    • status_code: int: 503
    • status: ENUM: ERROR
    • message: str: backend went down

6.Tag Search

• Method: GET
• Endpoint: /{version}/search?tag1={tag_1}&tag2={tag_2} ...
• Query Variable:
  • tag: str: tag's name that used as filter
• Success:
  • status_code: int: 200
  • status: ENUM: SUCCESS
  • items: list[item]: list of item that satisfied the condition

Internal API

1.Tag Normalization

• METHOD: POST
• Endpoint: /{version}/normalize
• Body:
  • tag_name: str: tag's name
• Response:
  • New Tag:
    • status_code: int: 200
    • status: SUCCESS
    • new_tag: bool: true
    • tag_name: str: tag's name

• • Existed Tag:
    • staus_code: int: 200
    • status: SUCCESS
    • new_tag: bool: false
    • tag_name: str: tag's name

High-Level Design

Database design

• Nature Of Data
  • we need to map tag_id with tag name and also map item_id with a list of tags which may not have the same length
• Choices
  • SQL database
    • we can use sql database like mySQL
    • table for tag:
      • tag_id: id: primary key
      • tag_name: str: unique name
    • table for item:
      • item_id: id: primary_key
      • object_storage_url: str: url of the image in object storage
      • tag[0..14]: 15 column of tag id
  • noSQL database
    • we can use document database for tag_id and tag_name.
    • for item we can used document db
    • schema
      • item_id: id: image id
      • object_storage_url: str: url of the image in object storage
      • tags: list[str]: a list of tag's id
• Decision
  • in this case, the system would benefit by adopting document database. On one hand, SQL db works perfectly fine with tag table. However, it is explicit that the schema for item table is dynamic, which, doesn't work well with SQL db. Hence, the second options will be more suitable.

Design

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.