System requirements

Functional:

• Support tag for documents, webpages, images, audio, video
• User-specific tag creation, deletion, and retrieval
• Tags support alphabets, numbers and delimiters such as hyphen, underscore & space and no more than 128 bytes
• A user can create up to 100 unique tags per object
• User can only add tags to objects they have permission to
• If an object is deleted it should delete all the tags created for that object

Non-Functional:

• System should be scalable to 10million+ users, with 100s of tags per user
• System should be available (99.99%)
• Eventually consistent - tag once created can be retrieved within a few seconds, deletion of a tag may take a few seconds as well to propogate
• Tag creation/deletion should be idempotent - i.e. if user creates tag on same object with same content, it will not create duplicates

Capacity estimation

Estimate the scale of the system you are going to design...

API design

POST /tag

• Body contains tag content, ID of object to add tag to. Could also add List of content IDs for bulk tagging of multiple pieces of content.
• User ID via Oauth2 token
• 200 and Returns tag ID on success
• 400 if object does not exist or tag content is invalid
• 403 error if user does not have permission to add tags
• 500 if server error occurs

GET /tags/{object-id}

• User ID via Oauth2 token
• 200 and Returns list of tags created for the object with tag ID on success
• 400 if object does not exist or tag content is invalid
• 500 if server error occurs

GET /tag/{tag-id}

• User ID via Oauth2 token
• Get tag content

PUT /tag/{tag-id}

• User ID via Oauth2 token
• Body contains new tag name for the ID

DELETE /tag/{tag-id}

• User ID via Oauth2 token
• Deletes tag for the object
• 204 on success
• 403 error if user does not have permission to delete tags
• 404 if tag does not exist

GET /objects-by-tag/{tag-name}

• User ID via Oauth2 token
• Retrieve list of objects by the tag name
• Does not support wildcards

Database design

Tag table

Schema:

Tag ID (primary key)

Content ID

User ID

Tag content

Created TS

Updated TS

Hit frequency

User permissions

Schema:

User ID (Primary key)

Content ID

Permission (VIEW/EDIT/DELETE)

Content table

Content ID (primary key)

Content URL

We can use a Relational DB like MySQL or Postgres, NoSQL is not suitable because it's not easy to keep track of relationship between content, tags and users.

High level design

• Load balancer to distribute load among API servers
• Authz service - Handles user authorization based on OAuth token in request
• API gateway - takes incoming request, verifies user is authorized and routes it to correct service. Applies rate limiting.
• Tag service - microservice responsible for creation, retrieval and deletion of tags
• Permissions service - responsible for returning user permissions for object (updating permissions is out of scope)
• Object retrieval service - responsible for retrieving objects by tag.

Request flows

• Request flows in to the service and distributed to API server via load balancers.
• Depending on API request, request may be routed to Tag service or object retrieval service
• Tag service will check permission in user permissions table and if authorized will do operations for creation/retrieval/update/delete of tags. It also uses a bloom filter to track number of hits for a tag and keep in memory max heap to track most frequently appearing tags.
• Tag autocomplete service - suggests tag names using ML models. Underlying data structure can use Trie with higher weights assigned to tags that have higher number of hits, which is maintained as a heap in memory.
• Object retrieval service to retrieve objects by tag

Detailed component design

• We can partition requests by user so requests from same user can go to the same server
• We can use an in memory cache like Redis to store tags created by user
• Creation, update and deletion of tags needs to be eventually consistent, we can push these to a message broker like Kafka & process via Flink streaming
• Object retrieval service will check user permissions to get list of objects user has VIEW permissions to. It will use these objects as filter and do a scan on the Tag table to retrieve objects with the tag name created by the given user ID. This can be made efficient by adding an index on tag name. We can also use search service like ElasticSearch to search for tags
• We can have background jobs that checks deleted objects and cleans up corresponding tags. We may need an index on object ID in the tag table to do this efficiently

Trade offs/Tech choices

• Using Relational DB like MySQL to model complex relationship between tags, users and permissions. Assuming each user is rate limited, we can partition DB by user ID
• We define user specific tags for better customization at the cost of more storage for similar tags. Since tag length is limited to at most 128 bytes per tag this should not be a big issue
• Rate limiting by user ID or by IP address to ensure user cannot overload the system or create hot partitions
• Searching on the Tag DB table directly using index on tag name, instead of using a separate service like ElasticSearch to avoid running into issues with consistency. We can rate limit the number of searches per user to avoid overloading the Tag table.
• User tags can be cached in memory using Redis to make retrieval faster. Caching scheme used can be cache aside where we update data and populate cache on reads, which optimizes for reads & write speeds and avoids cache inconsistency.
• We can use a message broker like Kafka to store the create, update or delete tag events. Kafka events are durable and the events can be replayed in case of node failure.

Failure scenarios/bottlenecks

• Any of the microservices can be unavailable or be unable to scale. To avoid this we can define autoscaling groups to scale resources to handle the load.
• Databases can be overloaded either on writes or reads. We can counter this by using caching (which reduces read load) and using message broker like Kafka (to smooth write loads).
• We partition by user ID or IP address and rate limit users to avoid hot spots or hot partitions.
• Due to eventual consistency of our system it's possible it may take a long time to propagate tag additions/deletions. We can monitor this time by tracking the time event was produced vs consumed in Kafka
• Permissions service can be a bottleneck. If we are okay with delays in permissions getting reflected we can cache permissions by user/object to make it more efficient.

Future improvements

1. Advanced Data Modeling: Using graph databases for tagging relationships.
2. Utilization of AI/ML for Tag Suggestions: Explore machine learning capabilities to suggest tags based on user behavior and previous tagging patterns, enhancing user experience and tag relevance.
3. Distributed System Monitoring: We can use tools like Prometheus and Grafana for metrics and alerts.