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

Item Storage

• the item we store are images. Hence it is not suitable to keep it in database as it takes too much space and will cost the system significantly
• we store the images in object storage such as AWS S3. As it is a lot cheaper. And we assign image_id for every image and map it with S3 url.

Suggest Tag Service & Normalize Tag Service

• for both service the key action we need to do is to compare if the item/name is similar to what already existed in the system
• for suggestion, we used tag from the image that is similar to item in question to recommend the tag
• for name, we check if there exist name that is similar to the incoming name if so we just return the existing name
• we can archive this using embedding (Deep Learning Model) combine with cosine similarity algorithm
• First we need to feed image/text into the model (different model) then we will receive vector representing our input. We run cosine similarity algorithm (|input_vector||existing_vector| cos(angle)/|input_vector||existing_vector|)
• for image model, we just choose top5 images that is has cos value greater than predefine value (gain by experiment) and suggest those tags.
• For text model, we check if there is vector that has cos value greater than predefine value and if so we just return the top vector that is similar to the input

Search

• in this case we will just need to receive the input tags
• then check in cache/db if there is image_id that satisfies the condition
• return the list of image