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.

First of all, to handle 1000 peak write RPS and 1500 peak read RPS, we need a load balancer that balances requests based on user_id, using consistent hashing to route to different servers. Then we have an API gateway that does rate limiting and authentication.

For storage of digital items, we store it in a relational database. The data model looks like

table item {

item_id: UUID,

item_image_url: String,

item_name: String,

item_description: String,

.... (other item metadata)

item_tags: List<String>

}

To handle the high write QPS, we have a caching layer (a redis cluster) that look like:

key: item_id

value: item_tags

The caching layer is a write-back cache, where we write to cache and acknowledge success, and later write in batches to database within 5 seconds. If the redis cluster crashes within 5 seconds, we run risks of losing data. However, this is a reasonable tradeoff since we improve write latency a lot by using redis to handle writes, with a peak RPS of 1000.

Another storage layer we have is the ElasticSearch index, which we use to store all digital items metadata + tags, this will allow us to search items by tags.

When users want to view digital items and associated tags, item feed service queries the redis cluster to get back items, and if not available, query the underlying relational database. With 1500 peak RPS and 1000 peak write RPS, we will create replicas for redis and database. Any replica can serve the read request, with some possibility of seeing stale data, since we are not looking for strong consistency here.

When we load the actual images of items, we use metadata to query the CDN links. The images are cached in CDN, and stored in object storage.

When users create new tags, rename or edit existing tags, delete tags or attach tags to one item, we write to the redis cluster which later batch write to databases.

For tags of items, it is not a business use case that warrants strong consistency. If for a few seconds, different users see different versions of tags for the same item, it's a reasonable tradeoff for lower latency and higher availability. In our case, we consider a write successful as long as 1 write replica acknowledges it, with the change asynchronously propagating to other replicas within 5 seconds. However, we also don't want users to experience "time travel" and see the tag they just wrote disappear. So we will implement monotonic read/write, when user just sent a read/write request, we will respond with a version vector. Any following read/write from same client must receive a response with a higher version vector.

Every time when users make a create/delete/edit, we trigger an event on a Kafka queue, that gets processed and written to 2 places.

1 is to write to ElasticSearch index. There might be delay and backlogs on the kafka queue. We will build monitoring on the queue. A reasonable delay is okay for search, if users can't find the most updated outcome when they search for a tag.

Another event on a separate kafka topic gets processed by the machine learning training service, aggregated to train a ML model. The ML model is used when users request recommended tags for an item.

For the database, as data volume grow, we may need to shard the database on top of replication.

table item {

item_id: UUID,

item_image_url: String,

item_name: String,

item_description: String,

.... (other item metadata)

item_tags: List<String>

}

We will shard the database by item_id, since querying items by searching by tags are all related to items.

However, this created the problem of hot keys. It could be that 1 item is super popular, and millions of users want to view and tag the item, and thus overloading the database shard.

To address this problem, we rely on popular requests to hit cache. If it's still too much, we can create a separate database replica built solely for hot keys, or we can break the hot keys into multiple keys and distribute them on multiple database shards.

Another problem we want to cover is how to find the popular/trending tags. For this, we need a separate tag count service. Each time an item is tagged/untagged, we trigger an event that gets processed on the message queue. When processed, update the count accordingly for a tag. When tags volume increase, we will use shard counts, that distribute the counts on multiple replicas, and later aggregate them to get accurate count for each item.

We also want to address the problem of duplicate tags. For each item, in a distributed system, we could have many users trying to give it the same tag. In this case, for each tagging request, we want to create an idempotent key, based on item_id and tag. When duplicate tags are submitted, we ignore the duplicate requests.

Also, for tag normalization, it will happen at item feed service when user try to add/modify tags. We will remove whitespace, do lowercasing etc. before any tag is written to storage.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10